Artificial Intelligence{Components of Propositional Logic}{Propositional Variables}{Properties of Logical Connectives}{Properties of Logical Connectives}{Negation Normal Form (NNF)}{Conjunctive Normal Form (CNF)}{Existence of CNF}{Specifying Problems in Propositional Logic}{The Wumpus World (cont')}{Example: The 8-Queen Problem}{Interpretations and Models}{Validity vs. Satisfiability}{Inference Systems}{All These Fancy Symbols!}{All These Fancy Symbols!}{All These Fancy Symbols!}{Sound and Complete Inference Systems}{Inference in Propositional Logic}{Inference by Truth Tables}{Rule-Based Inference System}{Rule-Based Inference System}{Rule-Based Inference System}{Rule-Based Inference Systems}{Inference by Proof}{Inference by Proof}{Rule-Based Inference System}{Soundness of Rule-Based Inferences}{The Rules of $ul $}{One Rule Suffices!}{Resolution Proof}{Soundness of the Proof by Contradiction}{An Example}{How to get CNF from $(p IFF q)IFF r$}{Some Resolution Strategies}Artificial IntelligenceLogic and InferencesReadings: Chapter 7 of Russell &Norvig.Components of Propositional LogicLogic constants: True (1), and False (0)Propositional variables: X = {p1, q2, ...}, a set ofBoolean variablesLogical connectives: F = {¬, ∧, ∨, ⇒, ⇔, ...}Logical sentences: L(X, F), expressions built from Xand FLogical interpretations: a mapping θ from X to {0, 1}Logical evaluations: a process of applying a mapping θto sentences in L(X, F) (to obtain a value in {0, 1})Propositional VariablesAlso called Boolean variables, 0-1 variables.Every statement can be represented by a propositionalvariable:p1= “It is sunny today”p2= “Tom went to school yesterday”p3= “f(x) = 0 has two solutions”p4= “point A is on line BC”p5= “place a queen at position (1, 2) on a 8 by 8chessboard”...Properties of Logical Connectives∧ and ∨ are commutativeϕ1∧ ϕ2≡ ϕ2∧ ϕ1ϕ1∨ ϕ2≡ ϕ2∨ ϕ1∧ and ∨ are associativeϕ1∧ (ϕ2∧ ϕ3) ≡ (ϕ1∧ ϕ2) ∧ ϕ3ϕ1∨ (ϕ2∨ ϕ3) ≡ (ϕ1∨ ϕ2) ∨ ϕ3∧ and ∨ are mutually distributiveϕ1∧ (ϕ2∨ ϕ3) ≡ (ϕ1∧ ϕ2) ∨ (ϕ1∧ ϕ3)ϕ1∨ (ϕ2∧ ϕ3) ≡ (ϕ1∨ ϕ2) ∧ (ϕ1∨ ϕ3)∧ and ∨ are related by ¬ (DeMorgan’s Laws)¬(ϕ1∧ ϕ2) ≡ ¬ϕ1∨ ¬ϕ2¬(ϕ1∨ ϕ2) ≡ ¬ϕ1∧ ¬ϕ2Properties of Logical Connectives∧, ⇒, and ⇔ are actually redundant:ϕ1∧ ϕ2≡ ¬(¬ϕ1∨ ¬ϕ2)ϕ1⇒ ϕ2≡ ¬ϕ1∨ ϕ2ϕ1⇔ ϕ2≡ (ϕ1⇒ ϕ2) ∧ (ϕ2⇒ ϕ1)We keep them all mainly for convenience.ExerciseUse the truth tables to prove all the logicalequivalences seen so far.Negation Normal Form (NNF)A propositional sentence is said to be in Negation NormalForm if it contains no connectives other than ∨, ∧, ¬, andif ¬(α) appears in the sentence, then α must be apropositional variable.¬p, p ∨ q, p ∨ (q ∧ ¬r) are NNF.p ⇔ q, ¬(p ∨ q) are not NNF.Every propositional sentence can be transformed into anequivalent NNF.ϕ1⇔ ϕ2≡ (ϕ1⇒ ϕ2) ∧ (ϕ2⇒ ϕ1)ϕ1⇒ ϕ2≡ ¬ϕ1∨ ϕ2¬(ϕ1∧ ϕ2) ≡ ¬ϕ1∨ ¬ϕ2¬(ϕ1∨ ϕ2) ≡ ¬ϕ1∧ ¬ϕ2¬¬ϕ ≡ ϕ¬T rue ≡ F alse¬F alse ≡ T rueConjunctive Normal Form (CNF)A propositional sentence φ is said to be in ConjunctiveNormal Form ifφ is True, False, or a conjunction of αi’s:α1∧ α2∧ · · · ∧ αn,where each α is a clause (a disjunction of βj’s):α = (β1∨ β2∨ · · · ∨ βm),where each β is called a literal, which is either avariable or the negation of a variable:β = p or β = ¬(p).¬p, p ∨ q, p ∧ (q ∨ ¬r) are CNF.p ∨ (q ∧ ¬r) are not CNF.Every CNF is an NNF but the opposite does not hold.Existence of CNFEvery propositional sentence can be transformed into anequivalent CNF. That is, from NNF, using(ϕ1∧ ϕ2) ∨ ϕ3≡ (ϕ1∨ ϕ3) ∧ (ϕ2∨ ϕ3)Specifying Problems in Propositional LogicThe Wumpus World:ABGPSW = Agent = Breeze = Glitter, Gold = Pit = Stench = WumpusOK = Safe squareV = VisitedAOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4OKOKBP?P?AOK OKOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4V(a)(b)Si,j: true iff there is a stench in square (i, j);Bi,j: true iff there is a breeze in square (i, j);Wi,j: true iff the Wumpus is in square (i, j).The Wumpus World (cont’)ABGPSW = Agent = Breeze = Glitter, Gold = Pit = Stench = WumpusOK = Safe squareV = VisitedAOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4OKOKBP?P?AOK OKOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4V(a)(b)Initial facts : ¬S1,1, ¬B1,1R1: ¬S1,1⇒ ¬W1,1∧ ¬W1,2∧ ¬W2,1R2: ¬S2,1⇒ ¬W1,1∧ ¬W2,1∧ ¬W2,2∧ ¬W3,1R3: ¬S1,2⇒ ¬W1,1∧ ¬W1,2∧ ¬W2,2∧ ¬W1,3R4: S1,2⇒ W1,1∨ W1,2∨ W2,2∨ W1,3...Example: The 8-Queen ProblemVariables: qi,j, 1 ≤ i, j ≤ 8. qijis true iff a queen is placed in thesquare at row i and column j.Clauses:Every row has a queen: For each 1 ≤ i ≤ 8,qi,1∨ qi,2∨ qi,3∨ qi,4∨ qi,5∨ qi,6∨ qi,7∨ qi,8Two queens from the same row cannot see each other:¬qi,1∨ ¬qi,2, ...Two queens from the same column cannot see each other:¬q1,j∨ ¬q2,j, ...Two queens on the same diagonal cannot see each other:¬q1,1∨ ¬q2,2, ...Interpretations and ModelsA (partial) interpretation is a mapping from variables to {0, 1}.An complete interpretation is if it maps every variables to {0, 1}.An interpretation θ can be extended to be a mapping frompropositional sentences to {0, 1} if it obeys the following rules:θ(¬p) = 1 if and only if θ(p) = 0;if θ(p) = 1 or θ(q) = 1 then θ(p ∨ q) = 1;if θ(p) = 1 and θ(q) = 1 then θ(p ∧ q) = 1; ...Computing this interpretation is called evaluation.For any propositional sentence Φ, if there exists an interpreation θsuch that θ(Φ) = 1, then θ is a model of Φ and Φ is said to besatisfiable.If every complete interpretation is a model for Φ, then Φ is said to bevalid.Validity vs. SatisfiabilityA sentence issatisfiable if it is true in some interpretation,valid if it is true in every possible interpretation.Reasoning Tools for Propositional Logic:A tool to prove a sentence is valid needs only to returnyes or no.A tool to prove a sentence is satisfiable often returns aninterpretation under which the sentence is true.A sentence φ is valid if and only if ¬φ is unsatisfiable.Inference SystemsIn practice, an inference system I for PL is a procedurethat given a setΓ = {α1, . . . , αm} of sentences and asentence ϕ,