《Artificial Intelligence：A Modern Approach》教学资源（教材，英文版）Part III Knowledge and Reasoning 7 Logical Agents.pdf_P11-P15

204 Chapter 7.Logical Agents The final issue that must be addressed by an account of logical agents is that ofground- n if logical re and the t in hich the ular,how do at kr is true ical (Af hich nany,man Chapter 26.) te the connect The table example ell se age ell Ther wh at s s tr n th Thus rcept sen nces are definec it is ing and t he proces of sent ce t the re ef tha cause sme s in a This s not a rect repres single perc a general rul pe s,from not ide on pre called I arn is the subjec Part p ca smel epr on ar y29 ch is wher e tn baths. Th s,KB may not be true in the real world.bu s reason for optimism 7.4 PROPOSITIONAL LOGIC:A VERY SIMPLE LOGIC We now present a very simple logic called propositional logic.We cover the syntax of propositional logic and its semantics the way in which the truth of sentences is determine Then we look at entailment-the relation between a sentence and another sentence that fol lows from it- -and see how this leads to a simple algorithm for logical inference.Everything takes place,of course,in the wumpus world. Syntax The syntax of propositional logic defines the allowable sentences.The atomic sentences- 968mo the indivisible syntactic elements-consist of a single proposition symbol.Each such sym- bol stands for a proposition that can be true or false.We will use uppercase names for symbols:P,R,and so on.The names are arbitrary but are often chosen to have some mnemonic value to the reader.For example,we might use Wi.s to stand for the proposition that the wumpus is in [1,3].(Remember that symbols such as W13 are atomic,i.e.,W,1, and 3 are not meaningful parts of the symbol.)There are two proposition symbols with fixed meanings:True is the always-true proposition and False is the always-false proposition. 是s Complex sentences are constructed from simpler sentences using logical connectives. There are five connectives in common use: NEGATION (not).A sentence such as-W1.3 is called the negation of Wi.3.A literal is either an UTERAL atomic sentence(a positive literal)or a negated atomic sentence(a negative literal). Propositional logie isalso called Boolen og,after the logician George Boole(1815-1864)

204 Chapter 7. Logical Agents The final issue that must be addressed by an account of logical agents is that of groundGROUNDING ing—the connection, if any, between logical reasoning processes and the real environment in which the agent exists. In particular, how do we know that KB is true in the real world? (After all, KB is just “syntax” inside the agent’s head.) This is a philosophical question about which many, many books have been written. (See Chapter 26.) A simple answer is that the agent’s sensors create the connection. For example, our wumpus-world agent has a smell sensor. The agent program creates a suitable sentence whenever there is a smell. Then, whenever that sentence is in the knowledge base, it is true in the real world. Thus, the meaning and truth of percept sentences are defined by the processes of sensing and sentence construction that produce them. What about the rest of the agent’s knowledge, such as its belief that wumpuses cause smells in adjacent squares? This is not a direct representation of a single percept, but a general rule—derived, perhaps, from perceptual experience but not identical to a statement of that experience. General rules like this are produced by a sentence construction process called learning, which is the subject of Part VI. Learning is fallible. It could be the case that wumpuses cause smells except on February 29 in leap years, which is when they take their baths. Thus, KB may not be true in the real world, but with good learning procedures there is reason for optimism. 7.4 PROPOSITIONAL LOGIC: A VERY SIMPLE LOGIC We now present a very simple logic called propositional logic. 8 We cover the syntax of PROPOSITIONAL LOGIC propositional logic and its semantics—the way in which the truth of sentences is determined. Then we look at entailment—the relation between a sentence and another sentence that follows from it—and see how this leads to a simple algorithm for logical inference. Everything takes place, of course, in the wumpus world. Syntax ATOMIC SENTENCES The syntax of propositional logic defines the allowable sentences. The atomic sentences— the indivisible syntactic elements—consist of a single proposition symbol. Each such sym- PROPOSITION SYMBOL bol stands for a proposition that can be true or false. We will use uppercase names for symbols: P, Q, R, and so on. The names are arbitrary but are often chosen to have some mnemonic value to the reader. For example, we might use W1,3 to stand for the proposition that the wumpus is in [1,3]. (Remember that symbols such as W1,3 are atomic, i.e., W, 1, and 3 are not meaningful parts of the symbol.) There are two proposition symbols with fixed meanings: True is the always-true proposition and False is the always-false proposition. Complex sentences are constructed from simpler sentences using logical connectives. COMPLEX SENTENCES LOGICAL CONNECTIVES There are five connectives in common use: NEGATION ¬ (not). A sentence such as ¬W1,3 is called the negation of W1,3. A literal is either an LITERAL atomic sentence (a positive literal) or a negated atomic sentence (a negative literal). 8 Propositional logic is also called Boolean logic, after the logician George Boole (1815–1864)

Section 7.4. Propositional Logic: A Very Simple Logic 205 ∧ (and). A sentence whose main connective is ∧, such as W1,3 ∧ P3,1, is called a conCONJUNCTION junction; its parts are the conjuncts. (The ∧ looks like an “A” for “And.”) DISJUNCTION ∨ (or). A sentence using ∨, such as (W1,3∧P3,1)∨W2,2, is a disjunction of the disjuncts (W1,3 ∧ P3,1) and W2,2. (Historically, the ∨ comes from the Latin “vel,” which means “or.” For most people, it is easier to remember as an upside-down ∧.) IMPLICATION ⇒ (implies). A sentence such as (W1,3∧P3,1) ⇒ ¬W2,2 is called an implication (or conPREMISE ditional). Its premise or antecedent is (W1,3∧P3,1), and its conclusion or consequent CONCLUSION is ¬W2,2. Implications are also known as rules or if–then statements. The implication symbol is sometimes written in other books as ⊃ or →. BICONDITIONAL ⇔ (if and only if). The sentence W1,3 ⇔ ¬W2,2 is a biconditional. Figure 7.7 gives a formal grammar of propositional logic; see page 984 if you are not familiar with the BNF notation. Sentence → AtomicSentence | ComplexSentence AtomicSentence → True | False | Symbol Symbol → P | Q | R | . . . ComplexSentence → ¬ Sentence | ( Sentence ∧ Sentence ) | ( Sentence ∨ Sentence ) | ( Sentence ⇒ Sentence ) | ( Sentence ⇔ Sentence ) Figure 7.7 A BNF (Backus–Naur Form) grammar of sentences in propositional logic. Notice that the grammar is very strict about parentheses: every sentence constructed with binary connectives must be enclosed in parentheses. This ensures that the syntax is completely unambiguous. It also means that we have to write ((A ∧ B) ⇒ C) instead of A ∧ B ⇒ C, for example. To improve readability, we will often omit parentheses, relying instead on an order of precedence for the connectives. This is similar to the precedence used in arithmetic—for example, ab + c is read as ((ab) + c) rather than a(b + c) because multiplication has higher precedence than addition. The order of precedence in propositional logic is (from highest to lowest): ¬, ∧, ∨, ⇒, and ⇔. Hence, the sentence ¬P ∨ Q ∧ R ⇒ S is equivalent to the sentence ((¬P) ∨ (Q ∧ R)) ⇒ S . Precedence does not resolve ambiguity in sentences such as A ∧ B ∧ C, which could be read as ((A ∧ B) ∧ C) or as (A ∧ (B ∧ C)). Because these two readings mean the same thing according to the semantics given in the next section, sentences such as A∧B∧C are allowed. We also allow A ∨ B ∨ C and A ⇔ B ⇔ C. Sentences such as A ⇒ B ⇒ C are not

206 Chapter 7.Logical Agents allowed because the two readings have different meaning we insist on parentheses in this will the sentence mes use squar when it make leare Semantics Having specified the syntax of propositional logic,we now specify its semantics.The se- mantics defines the rules for determining the truth of a sentence with respect to a particular model.In propositional logic,a model simply fixes the truth value-true or false-for every proposition symbol.For example,if the sentences in the knowledge base make use of the proposition symbols P2.P22,and P1,then one possible model is m1={，2=false,.乃2=false,,.1=true} ee m之e皮eeae With three p become purely mathematical objects with no necessary connection to wumpus worlds.P2 is just a symbol:it might mean"there is a pit in Il.21or"I'm in Paris today and tomorrow. The semantics for propositional logic must specify how to compute the truth value of any sentence,given a model.This is done recursively.All sentences are constructed from five connectives.Atomic sentences are easy True is true in every model and False is false in every model .The truth value of every other proposition symbol must be specified directly in the model.For example,in the model m given earlier,P.2 is false For complex sentences,we have rules such as .For any sentence s and any model m,the sentences is true in m if and only if s is false in m. Such rules reduce the truth of a complex sentence to the truth of simpler sentences.The TRUTH TABLE rules for each connective can be summarized in a truth table that specifies the truth value of a complex sentence for each possible assignment of truth values to its components.Truth tables for the five logical connectives are given in Figure 7.8.Using these tables,the truth value of any sentence s can be computed with respect to any model m by a simple process of recursive evaluation.For example,the sentence-P2A(P2.2V P),evaluated in m,gives true A (false V true)=true A true=true.Exercise 7.3 asks you to write the algorithm PL-TRUE?(s,m),which computes the truth value of a propositional logic sentence s in a model m. Previously we said that a knowledge base consists of a set of sentences.We can now see that a logical knowledge base is a conjunction of those sentences.That is,if we start with an empty KB and do TELL(KB,S1)...TELL(KB,Sn)then we have KB=S1A...A Sn This means that we can treat knowledge bases and sentences interchangeably. The truth tables for“and,""or,”and“not”are in close accord with our intuitions about the English words.The main point of possible confusion is that PVQ is true when P is true

206 Chapter 7. Logical Agents allowed because the two readings have different meanings; we insist on parentheses in this case. Finally, we will sometimes use square brackets instead of parentheses when it makes the sentence clearer. Semantics Having specified the syntax of propositional logic, we now specify its semantics. The semantics defines the rules for determining the truth of a sentence with respect to a particular model. In propositional logic, a model simply fixes the truth value—true or false—for every proposition symbol. For example, if the sentences in the knowledge base make use of the proposition symbols P1,2, P2,2, and P3,1, then one possible model is m1 = {P1,2 = false, P2,2 = false, P3,1 = true} . With three proposition symbols, there are 2 3 = 8 possible models—exactly those depicted in Figure 7.5. Notice, however, that because we have pinned down the syntax, the models become purely mathematical objects with no necessary connection to wumpus worlds. P1,2 is just a symbol; it might mean “there is a pit in [1,2]” or “I’m in Paris today and tomorrow.” The semantics for propositional logic must specify how to compute the truth value of any sentence, given a model. This is done recursively. All sentences are constructed from atomic sentences and the five connectives; therefore, we need to specify how to compute the truth of atomic sentences and how to compute the truth of sentences formed with each of the five connectives. Atomic sentences are easy: • True is true in every model and False is false in every model. • The truth value of every other proposition symbol must be specified directly in the model. For example, in the model m1 given earlier, P1,2 is false. For complex sentences, we have rules such as • For any sentence s and any model m, the sentence ¬s is true in m if and only if s is false in m. Such rules reduce the truth of a complex sentence to the truth of simpler sentences. The TRUTH TABLE rules for each connective can be summarized in a truth table that specifies the truth value of a complex sentence for each possible assignment of truth values to its components. Truth tables for the five logical connectives are given in Figure 7.8. Using these tables, the truth value of any sentence s can be computed with respect to any model m by a simple process of recursive evaluation. For example, the sentence ¬P1,2 ∧ (P2,2 ∨ P3,1), evaluated in m1, gives true ∧ (false ∨ true) = true ∧ true = true. Exercise 7.3 asks you to write the algorithm PL-TRUE?(s, m), which computes the truth value of a propositional logic sentence s in a model m. Previously we said that a knowledge base consists of a set of sentences. We can now see that a logical knowledge base is a conjunction of those sentences. That is, if we start with an empty KB and do TELL(KB, S1) . . . TELL(KB, Sn) then we have KB = S1 ∧ . . . ∧ Sn. This means that we can treat knowledge bases and sentences interchangeably. The truth tables for “and,” “or,” and “not” are in close accord with our intuitions about the English words. The main point of possible confusion is that P ∨ Q is true when P is true

Section 7.4.Propositional Logic:A Very Simple Logic 207 Q P PAQ PVQ P→Q P÷Q false false true tru tru ru true I毛 fals true true true true Figure 7.8 for the five logical cois To use the table to e,Io Then look in that row under the to see the result:true.Another way to look at this is to think of each row as a model.and the entries under each column for that row as saying whether the corresponding sentence is true in that model orQ is true or both.There is a different connective called"exclusive or"("xor"for short)that yields false when both disjuncts are true.There is no consensus on the symbol for exclusive or:two choices are V and The truth table formay seem puzzling at first,because it might not quite fit one's intuitive understanding of"P implies "or"if P then .For one thing,propositional logic does not require any relation of causation or relevance between P and Q.The sentence"5 is odd implies Tokyo is the capital of Japan"is a true sentence of propositional logic (under the normal interpretation),even though it is a decidedly odd sentence of English.Another point of confusion is that any implication is true whenever its antecedent is false for exam is even imlies Sam is smart"is true reardless of whether sams but it makes sense if you think of"PQ"as saying,"If P is true,then I am claiming that Q is true.Otherwise I am making no claim."The only way for this sentence to be false is if P is true but Q is false. The truth table for a hiconditional po shows that it is true whenever both PO and O→P are true.In English.this is often written as“P if and only if O”or“P iff Q."The rules of the wumpus world are best written using For example,a square is breezy ifa neighboring square has a pit,and a square is breezy only ifa neighboring square has a pit.So we need biconditionals such as B1÷(B,2V1) where B1.means that there is a breeze in [1.1].Notice that the one-way implication B11→(B2VP,1) umpus it is that the im oI p re is a breeze,whereas the al o requires the absence of pits here is no breeze Latin hasa separate word,for

Section 7.4. Propositional Logic: A Very Simple Logic 207 P Q ¬P P ∧ Q P ∨ Q P ⇒ Q P ⇔ Q false false true false false true true false true true false true true false true false false false true false false true true false true true true true Figure 7.8 Truth tables for the five logical connectives. To use the table to compute, for example, the value of P ∨ Q when P is true and Q is false, first look on the left for the row where P is true and Q is false (the third row). Then look in that row under the P ∨Q column to see the result: true. Another way to look at this is to think of each row as a model, and the entries under each column for that row as saying whether the corresponding sentence is true in that model. or Q is true or both. There is a different connective called “exclusive or” (“xor” for short) that yields false when both disjuncts are true.9 There is no consensus on the symbol for exclusive or; two choices are ∨˙ and ⊕. The truth table for ⇒ may seem puzzling at first, because it might not quite fit one’s intuitive understanding of “P implies Q” or “if P then Q.” For one thing, propositional logic does not require any relation of causation or relevance between P and Q. The sentence “5 is odd implies Tokyo is the capital of Japan” is a true sentence of propositional logic (under the normal interpretation), even though it is a decidedly odd sentence of English. Another point of confusion is that any implication is true whenever its antecedent is false. For example, “5 is even implies Sam is smart” is true, regardless of whether Sam is smart. This seems bizarre, but it makes sense if you think of “P ⇒ Q” as saying, “If P is true, then I am claiming that Q is true. Otherwise I am making no claim.” The only way for this sentence to be false is if P is true but Q is false. The truth table for a biconditional, P ⇔ Q, shows that it is true whenever both P ⇒ Q and Q ⇒ P are true. In English, this is often written as “P if and only if Q” or “P iff Q.” The rules of the wumpus world are best written using ⇔. For example, a square is breezy if a neighboring square has a pit, and a square is breezy only if a neighboring square has a pit. So we need biconditionals such as B1,1 ⇔ (P1,2 ∨ P2,1) , where B1,1 means that there is a breeze in [1,1]. Notice that the one-way implication B1,1 ⇒ (P1,2 ∨ P2,1) is true in the wumpus world, but incomplete. It does not rule out models in which B1,1 is false and P1,2 is true, which would violate the rules of the wumpus world. Another way of putting it is that the implication requires the presence of pits if there is a breeze, whereas the biconditional also requires the absence of pits if there is no breeze. 9 Latin has a separate word, aut, for exclusive or

208 Chapter 7. Logical Agents A simple knowledge base Now that we have defined the semanticsfor propositional logic, we can construct a knowledge base for the wumpus world. For simplicity, we will deal only with pits; the wumpus itself is left as an exercise. We will provide enough knowledge to carry out the inference that was done informally in Section 7.3. First, we need to choose our vocabulary of proposition symbols. For each i, j: • Let Pi,j be true if there is a pit in [i, j]. • Let Bi,j be true if there is a breeze in [i, j]. The knowledge base includes the following sentences, each one labeled for convenience: • There is no pit in [1,1]: R1 : ¬P1,1 . • A square is breezy if and only if there is a pit in a neighboring square. This has to be stated for each square; for now, we include just the relevant squares: R2 : B1,1 ⇔ (P1,2 ∨ P2,1) . R3 : B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1) . • The preceding sentences are true in all wumpus worlds. Now we include the breeze percepts for the first two squares visited in the specific world the agent is in, leading up to the situation in Figure 7.3(b). R4 : ¬B1,1 . R5 : B2,1 . The knowledge base, then, consists of sentences R1 through R5. It can also be considered as a single sentence—the conjunction R1 ∧ R2 ∧ R3 ∧ R4 ∧ R5—because it asserts that all the individual sentences are true. Inference Recall that the aim of logical inference is to decide whether KB |= α for some sentence α. For example, is P2,2 entailed? Our first algorithm for inference will be a direct implementation of the definition of entailment: enumerate the models, and check that α is true in every model in which KB is true. For propositional logic, models are assignments of true or false to every proposition symbol. Returning to our wumpus-world example, the relevant proposition symbols are B1,1, B2,1, P1,1, P1,2, P2,1, P2,2, and P3,1. With seven symbols, there are 2 7 = 128 possible models; in three of these, KB is true (Figure 7.9). In those three models, ¬P1,2 is true, hence there is no pit in [1,2]. On the other hand, P2,2 is true in two of the three models and false in one, so we cannot yet tell whether there is a pit in [2,2]. Figure 7.9 reproduces in a more precise form the reasoning illustrated in Figure 7.5. A general algorithm for deciding entailment in propositional logic is shown in Figure 7.10. Like the BACKTRACKING-SEARCH algorithm on page 76, TT-ENTAILS? performs a recursive enumeration of a finite space of assignments to variables. The algorithm is sound, because it