Section 7.4.Propositional Logic:A Very Simple Logic 209 B.1 B2.1P.1B.2PB.1 P2P3.1 R R2 R3 R R5 KB fals true false false als true true falsefalse true false false false true true true true true true true false true true false true fals Figure 7.9 A truth table constructed for the knowledge base given in the text.KB is true if R:through in jus 3 of 280 so there is no pit in [1,2].On TAILS?(KB. a)returns irue or fals the query.asentence in ositional logi symbols -a list of the prop osition symbols in KB and return TT-CHECK-ALL(KB,a,sumbols,[] function TT-CHECK-ALL(KB,a,symbols,model)returns true or false if EMPTY?(symbols)then if PL-TRUE?(KB,model)then return PL-TRUE?(a,model) P+FIRST(sumbols):test +REST(sumbols) return TT-CHECK-ALL(KB,a,rest,EXTEND(P,true,model)and TT-CHECK-ALL(KB.a.rest.EXTEND(P.false.model) FrirAnhenE7ronemtnraecitegoromoomme A truth-table enumeration algorithm for deeidin mrue. implements directly the definition of entailment.and complete.because it works for any KB and o and always terminates-there are only finitely many models to examine. Ofcourse,"finitely many"is not always the same as"few."If KB and o contain n sym bols in all.then there are 2 models.Thus,the time complexity of the algorithm is O(2") (The space complexity is only O(n)because the enumeration is depth-first.)Later in this
Section 7.4. Propositional Logic: A Very Simple Logic 209 B1,1 B2,1 P1,1 P1,2 P2,1 P2,2 P3,1 R1 R2 R3 R4 R5 KB false false false false false false false true true true true false false false false false false false false true true true false true false false . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . false true false false false false false true true false true true false false true false false false false true true true true true true true false true false false false true false true true true true true true false true false false false true true true true true true true true false true false false true false false true false false true true false . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . true true true true true true true false true true false true false Figure 7.9 A truth table constructed for the knowledge base given in the text. KB is true if R1 through R5 are true, which occurs in just 3 of the 128 rows. In all 3 rows, P1,2 is false, so there is no pit in [1,2]. On the other hand, there might (or might not) be a pit in [2,2]. function TT-ENTAILS?(KB,α) returns true or false inputs: KB, the knowledge base, a sentence in propositional logic α, the query, a sentence in propositional logic symbols ←a list of the proposition symbols in KB and α return TT-CHECK-ALL(KB,α, symbols, [ ]) function TT-CHECK-ALL(KB,α, symbols, model) returns true or false if EMPTY?(symbols) then if PL-TRUE?(KB, model) then return PL-TRUE?(α, model) else return true else do P ← FIRST(symbols); rest ← REST(symbols) return TT-CHECK-ALL(KB,α, rest, EXTEND(P,true, model) and TT-CHECK-ALL(KB,α, rest, EXTEND(P,false, model) Figure 7.10 A truth-table enumeration algorithm for deciding propositional entailment. TT stands for truth table. PL-TRUE? returns true if a sentence holds within a model. The variable model represents a partial model—an assignment to only some of the variables. The function call EXTEND(P, true, model) returns a new partial model in which P has the value true. implements directly the definition of entailment, and complete, because it works for any KB and α and always terminates—there are only finitely many models to examine. Of course, “finitely many” is not always the same as “few.” If KB and α contain n symbols in all, then there are 2 n models. Thus, the time complexity of the algorithm is O(2n ). (The space complexity is only O(n) because the enumeration is depth-first.) Later in this
210 Chapter 7.Logical Agents (aAB)≡(BAa) commutativity of (aVB)(BVa) commutativity of V (aA)A）≡(aA(gAy)associativity ofA ((a vB)v)(a v(Bv))associativity ofv -(-a)=a double-negation elimination (a→3)=(-3→a)contraposition (a3)(aV3)implication elimination (a÷3)=(a→3)A(3→a)biconditional elimination (aA B)=(av-3)de Morgan (a VB)=(aA-3)de Morgan (aA(Bv))=((aAB)v(aA))distributivity of A over v (a V(BA))((a VB)A (a v))distributivity of v over A Figure 7.11 Standard propos 自 chapter,we will see algorithms that are much more efficient in practice.Unfortunately,every known inference algorithm for propositional logic has a worst-case complexity that is expo- nential in the size of the input.We do not expect to do better than this because propositional entailment is co-NP-complete.(See Appendix A.) Equivalence,validity,and satisfiability Before we plunge into the details of logical inference algorithms,we will need some addi- tional concepts related to entailment.Like entailment,these concepts apply to all forms of logic,but they are best illustrated for a particular logic,such as propositional logic. OONALENCE The first concept is logical equivalence:two sentences a and B are logically equivalent if they are true in the same set of models.We write this as a B.For example,we can easily show (using truth tables)that PAQ and A P are logically equivalent,other equivalences are shown in Figure 7.11.They play much the same role in logic as arithmetic dentities do in ordinary mathematics.An alternative definition of equivalence is as follows: for any two sentences a and B. a=B if and only if a=3 and 3a (Recall that=means entailment.) The se we will need is validity.A sentence is valid if it is true in all models senten is va d lid d he sent ces are y a els,ev the senten in a ry va ntence is logically eq our de f entailment,we can derive the deduction theorem.which was known to the ancient Greeks: For any sentences a and B.a B if and only if the sentence (B)is valid. (Exercise 7.4 asks for a proof.)We can think of the inference algorithm in Figure 7.10 as
210 Chapter 7. Logical Agents (α ∧ β) ≡ (β ∧ α) commutativity of ∧ (α ∨ β) ≡ (β ∨ α) commutativity of ∨ ((α ∧ β) ∧ γ) ≡ (α ∧ (β ∧ γ)) associativity of ∧ ((α ∨ β) ∨ γ) ≡ (α ∨ (β ∨ γ)) associativity of ∨ ¬(¬α) ≡ α double-negation elimination (α ⇒ β) ≡ (¬β ⇒ ¬α) contraposition (α ⇒ β) ≡ (¬α ∨ β) implication elimination (α ⇔ β) ≡ ((α ⇒ β) ∧ (β ⇒ α)) biconditional elimination ¬(α ∧ β) ≡ (¬α ∨ ¬β) de Morgan ¬(α ∨ β) ≡ (¬α ∧ ¬β) de Morgan (α ∧ (β ∨ γ)) ≡ ((α ∧ β) ∨ (α ∧ γ)) distributivity of ∧ over ∨ (α ∨ (β ∧ γ)) ≡ ((α ∨ β) ∧ (α ∨ γ)) distributivity of ∨ over ∧ Figure 7.11 Standard logical equivalences. The symbols α, β, and γ stand for arbitrary sentences of propositional logic. chapter, we will see algorithms that are much more efficient in practice. Unfortunately, every known inference algorithm for propositional logic has a worst-case complexity that is exponential in the size of the input. We do not expect to do better than this because propositional entailment is co-NP-complete. (See Appendix A.) Equivalence, validity, and satisfiability Before we plunge into the details of logical inference algorithms, we will need some additional concepts related to entailment. Like entailment, these concepts apply to all forms of logic, but they are best illustrated for a particular logic, such as propositional logic. The first concept is logical equivalence: two sentences α and β are logically equivalent LOGICAL EQUIVALENCE if they are true in the same set of models. We write this as α ⇔ β. For example, we can easily show (using truth tables) that P ∧ Q and Q ∧ P are logically equivalent; other equivalences are shown in Figure 7.11. They play much the same role in logic as arithmetic identities do in ordinary mathematics. An alternative definition of equivalence is as follows: for any two sentences α and β, α ≡ β if and only if α |= β and β |= α . (Recall that |= means entailment.) VALIDITY The second concept we will need is validity. A sentence is valid if it is true in all models. For example, the sentence P ∨ ¬P is valid. Valid sentences are also known as TAUTOLOGY tautologies—they are necessarily true and hence vacuous. Because the sentence True is true in all models, every valid sentence is logically equivalent to True. What good are valid sentences? From our definition of entailment, we can derive the deduction theorem, which was known to the ancient Greeks: DEDUCTION THEOREM For any sentences α and β, α |= β if and only if the sentence (α ⇒ β) is valid. (Exercise 7.4 asks for a proof.) We can think of the inference algorithm in Figure 7.10 as