# 计算机科学导论原书第二版答案第十八章

CHAPTER 18

Artificial Intelligence
(Solutions to Practice Set)

Review Questions
1. An interrogator asks a set of questions that are forwarded to a computer and a human being. The interrogator receives two sets of responses: one from the computer and one from the human. After careful examination of the two sets, if the interrogator cannot definitely tell which set has come from the computer, the computer has passed the intelligent test. Some experts think that this is an accurate definition of an intelligent system; some think that the test is not necessarily the definition of an intelligent system. 2. An intelligent agent is a system that perceives its environment, learns from it, and interacts with it intelligently. Intelligent agents can be divided into two broad categories: software agents and physical agents. 3. LISP is a programming language that manipulates lists. LISP treats data, as well as a program, as a list,. This means a LISP program can change itself. This feature matches with the idea of an intelligent agent that can learn from the environment and improves its behavior. PROLOG is a language that can build a database of facts and a knowledge base of rules. A program in PROLOG can use logical reasoning to answer questions that can be inferred from the knowledge base. 4. If an artificial agent is supposed to solve some problems relating to the real world, it needs somehow to represent knowledge. Four common methods for representing knowledge are semantic networks, frames, predicate logic, and rule-based system. 5. Propositional logic is a language made of a set of sentences that can be used to do logical reasoning about the world. In propositional logic, a symbol that represents a sentence is atomic; it cannot be broken to find some information about its components. To do so, we need predicate logic, the logic that defines the relation between the parts in a proposition. 6. Semantic networks use vertices (nodes) to represent concepts and edges (arrows) to represent the relations between concepts. In frames, data structures (records) are used to represent the same knowledge. Nodes and edges in semantic networks becomes objects and slots, respectively, in frames.
1

SECTION

2

7. A ruled-based system represents knowledge using a set of rules that can be used to deduce some new facts from already-known facts. The semantic network is a graphical representation of entities and their relationships. 8. Expert systems perform tasks expected from a human with expertise. Mundane systems perform tasks that does not require expertise (such as talking or walking). 9. The five stages of image processing are edge detection, segmentation, finding depth, finding orientation, and object recognition. 10. The four steps in language processing are speech recognition, syntactic analysis, semantic analysis, and pragmatic analysis. 11. Neural networks try to simulate the learning process of the human brain using a networks of artificial neurons. 12. A perceptron is an artificial neuron similar to a single biological neuron.

Multiple-Choice Questions
13. d 19. b 25. c 14. b 20. c 15. c 21. c 16. c 22. b 17. d 23. a 18. d 24. c

Exercises
26. The semantic network is shown in Figure S18.26. Figure S18.26 Exercise 26
Profesional Career Subclass Subclass Accountant Engineer Subclass Subclass Internist Gynocologist Family Practitioner Instance French Is Dr. Pascal Medical Doctor Subclass Subclass

27. The set of frames are shown in Figure S18.27.

SECTION

3

Figure S18.27 Exercise 27
Career
Superclass

Medical Doctor
Superclass

Accountant Career
Superclass

Internist Medical Doctor
Superclass

Engineer Career
Superclass

Gynocologist Medical Doctor
Superclass

Medcial Doctor Family Practitioner
Instance of

Family Practitioner French
Is

Dr. Pascal

28. a. ?R b. ?S c. (?R) ∨ (?S) d. R ∧ S e. S → (?R) f. R → (?S) g. S ? (?R) or (?R) ? S h. ?[R → (?S)] 29. a. It is not hot. b. It is warm or it is hot. c. It is warm and hot. d. It is warm but it is not hot. e. It is not true that it is warm and hot. f. If it is warm, then it is hot. g. If it is not cold, then it is warm. h. It is not true that if is not warm, then it is hot. i. It is hot if it is not warm. j. It is not cold and hot, or it is cold and not hot. 30. a. ?x[Fl (x) ∧ Wh (x)] b. ?x[Fl (x) ∧ ? Re(x)] c. ??x[Fl (x) → Re (x)]

SECTION

4

d. ?x{Fl (x) ∧ [Re (x) ∨ Wh (x)]} e. ??x[Fl (x) ∧ Gr(x)] f. ??x[Fl (x) ∧ Gr(x)] g. ?x[Fl (x) ∧ ? Wh(x)] 31. a. ?x[Cat (x) → Has (John, x)] b. ?x[Cat (x) → Loves (John, x)] c. Loves (John, Anne) d. ?x[Dog (x) ∧ Loves (Anne, x)] e. ?x[? Cat (x) ∧ Loves (John, x)] f. ?x[ Cat (x) ∧ ? Loves (Anne, x)] g. ?x{[ Cat (x) ∧ ? Loves (John, x)] → Loves (Anne, x)} h. ?x{[ Cat (x) ∧ ? Loves (John, x)] ? Loves (Anne, x)} 32. a. ?x[Expensive (x)] b. ?x[Cheap (x)] c. ?x[Cheap (x) → Buys (Bob, x)] d. ?x[Expensive (x) → Sells (John, x)] e. ??x[Expensive (x)] f. ??x[Cheap (x)] g. ?x{[ Cheap (x)] → ? Expensive (x)} 33. a. ? Identical (John, Anne) b. ?x[John (x)] c. ??x[Anne (x)] d. ?x e. ??x f. ?x?y[? Identical (x, y)] 34. The truth table is shown below. The argument {P → Q, P} |? Q is valid.
P F F T T Q F T F T P→Ο P Q T F F T F T F T F T T T Premise Premise Conclusion

OK

SECTION

5

35. The truth table is shown below. The argument {P ∨ Q, P} |? Q is not valid:
P F F T T Q F T F T P∨Ο P Q F F F T F T T T F Counterexample T T T OK Premise Premise Conclusion

36. The truth table is shown below. The argument {P ∧ Q, P} |? Q is valid:
P F F T T Q F T F T P∧Ο P Q F F F F F T F T F T T T Premise Premise Conclusion

OK

37. The truth table is shown. The argument {P → Q, Q → R} |? (P → R) is not valid
P F F F F T T T T Q F F T T F F T T R F T F T F T F T P→Q Q→R P→R T T T OK T T T OK T F T Counterexample T T T OK F T F F T T T F F T T T OK Premise Premise Conclusion

38. The design of the neural network, with weights w1 = w2 = 0.5 and the threshold of T = 0.5, is shown in Figure S18.38. Figure S18.38 Exercise 38
x1 . w2

Inputs
x2 . w4

Output
w1 = w2 = 0.5

y (0 or 1)

The truth table for this neural network is shown below. It is the same as the truth table for an OR gate.
Inputs 0 0 1 1 0 1 0 1 S = x1 . w1 + x2 . w2 0 0.5 0.5 1 Compare S with T Output S<T 0 S=T 1 S=T 1 S>T 1

SECTION

6

39. The design of neural network, with weights w1 = w2 = 0.5 and the threshold of T = 1, is shown in Figure S18.39. Figure S18.39 Exercise 39
x1 . w2

Inputs
x2 . w4 w1 = w2 = 0.5

Output
T=1

y (0 or 1)

The truth table for this neural network is shown below. It is the same as the truth table for an AND gate.
Inputs 0 0 1 1 0 1 0 1 S = x1 . w1 + x2 . w2 0 0.5 0.5 1 Compare S with T Output S<T 0 S<T 0 S<T 0 S=T 1

40. The heuristic search tree for solving the puzzle is shown in Figure S18.40. Figure S18.40 Exercise 40
Initial State 4 1 3 7 2 6 6 5 8 4 1 3 2 6 5 7 5 8 4 1 3 2 6 6 7 5 8 1 3 4 2 6 4 7 5 8 1 3 4 2 6 3 7 5 8 1 2 3 4 6 2 7 5 8 1 2 3 4 5 6 1 7 8 1 2 3 4 5 6 2 7 8 1 2 3 4 6 3 7 5 8 1 2 3 4 5 6 0 7 8 Goal State 1 3 4 2 6 4 7 5 8 1 2 3 4 6 3 7 5 8 4 1 3 7 2 6 7 5 8

41. Figure S18.41 shows the breadth-first search for the tree diagram.

SECTION

7

Figure S18.41 Exercise 41
A B D E F C G

H

I

J

K

L

42. Figure S18.42 shows the depth-first search for the tree diagram of Exercise 41. Figure S18.42 Exercise 42
A B D E F C G

H

I

J L

K

43. Figure S18.43 shows the tree diagram for the maze. Figure S18.43 Exercise 43
Start A B E F I J M P G K O H L N Q Finish C D

SECTION

8

44. Figure S18.44 shows the breadth-first search for Exercise 43. Figure S18.44 Exercise 44
Start A B E C D

F I J

G K M O

H L N

P

Q Finish

45. Figure S18.45 shows the depth-first search for Exercise 43. Figure S18.45 Exercise 45
Start A B E C D

F I J

G K M P O

H L N

Q Finish

2016下《计算机科学导论》第2次作业答案.doc
2016下《计算机科学导论第2次作业答案 - 《计算机科学导论第 2 次作业答案 (第 8 章第 15 章) 一、选择题 1.与批处理系统相比较,分时系统的最大...