Propositional Logic PDF

Propositional logic Artificial intelligence Kristóf Karacs PPKE-ITK Outline n Logics of different order: 0, 1, 2, higher n Basic concepts and nomenclature ¨ Syntax vs. semantics ¨ Entailment n Propositional logic n Entailment and pro...

Propositional logic Artificial intelligence Kristóf Karacs PPKE-ITK Outline n Logics of different order: 0, 1, 2, higher n Basic concepts and nomenclature ¨ Syntax vs. semantics ¨ Entailment n Propositional logic n Entailment and proof methods ¨ Truth table, equivalence, resolution 1 Logics of different order n Propositional logic (a. k. a. Boolean logic) ¨ Only constant Boolean statements n First order predicate logic (FOPL) ¨ Introduces variables, predicates, functions, and quantifiers n Higher order logics ¨ Quantifiers canalso be applied to predicates and functions ¨ Meta level reasoning Logic n A formal language in which knowledge can be expressed n In problem solving we enumerate states n Logic provides a means of describing set of states and carrying out reasoning ¨ “Peter is hungry”: refers to all world states in which Peter is hungry regardless of other things influencing the state 2 Basic concepts n Syntax: specifies what expressions are legal ¨ Well-formed sentences n Semantics: meaning of sentences ¨ Interpretation: assigns meaning to logic symbols ¨ Semantics define the truth of sentences w. r. t. all possible interpretations ¨ An interpretation i is a model of a set of sentences iff each of the sentences is true in interpretation i n Logical inference: entailment ¨ A set of sentences KB entails φ (KB ⊨ φ) iff every model of KB is also a model of φ ¨ Sentence φ logically follows from KB Syntax of propositional logic n Atomic sentences: Propositions ¨ Symbols: P, Q, R, … (uppercase letters) ¨ Special cases: T (true) and F (false) n Complex sentences ¨ Brackets ¨ Connectives in order of precedence (high to low) n not (¬), and (Ù), or (Ú), implies (→), equivalent (↔) ¨ If φ and ψ are sentences, then (φ), ¬φ, φ Ù ψ, φ Ú ψ, φ → ψ and φ ↔ ψ are also sentences 3 Semantics n Meaning of a sentence is a truth value ¨ {T, F} n An interpretation is an assignment of truth values to the propositional variables ¨ ⊨i φ Sentence φ is T in interpretation i ¨ ⊭i φ Sentence φ is F in interpretation i Semantic rules n ⊨i T for all i n ⊭i F for all i n ⊨i ¬φ iff ⊭i φ n ⊨i φ Ù ψ iff ⊨i φ and ⊨i ψ (conjunction) n ⊨i φ Ú ψ iff ⊨i φ or ⊨i ψ (disjunction) n ⊨i P iff i(P) = T 4 Properties of sentences n Equivalence φ ºψ ¨φ and ψ are true for the same models n Validity ⊨φ ¨A sentence is valid iff its truth value is T in all interpretations ¨ Valid sentences are called tautologies ¨ Examples: T, P Ú ¬P, A ® A n Satisfiability ¨A sentence is satisfiable iff it has at least one model Entailment theorem KB ⊨ φ iff ⊨ (KB → φ) n Enables proving entailment if we have means to prove the validity of a sentence n This theorem is valid for all logics 5 Proving validity n Truth table n Equivalence rules n Resolution n (X ® (Y Ù Z)) ↔ ((X ® Y) Ù (X ® Z)) Proving by truth table 6 Proving by truth table X Y Z YÙZ X®Y X®Z X ® (YÙZ) ((X®Y) Ù (X®Z)) S Proving by truth table X Y Z YÙZ X®Y X®Z X ® (YÙZ) ((X®Y) Ù (X®Z)) S T T T T T T T T T T T F F T F F F T T F T F F T F F T T F F F F F F F T F T T T T T T T T F T F F T T T T T F F T F T T T T T F F F F T T T T T 7 Equivalence (re-write) rules n Logical equivalence ¨ Different syntax ¨ Same semantics n Usage ¨ Proving via showing equivalence ¨ Modifying to a particular syntax to allow the use of other techniques (e.g. resolution) Commutativity and associativity of connectives n Commutativity: ¨ PÙQ can be replaced by QÙP (& vice-versa) ¨ PÚQ can be replaced by QÚP (& vice-versa) ¨ P«Q can be replaced by Q«P (& vice-versa) n Associativity ¨ ((PÙQ) Ù R) can be replaced by (P Ù (QÙR)) (& vice- versa) ¨ ((PÚQ) Ú R) can be replaced by (P Ú (QÚR)) (& vice- versa) 8 Distributivity of connectives n And over or, or over and: ¨ (P Ù (QÚR)) can be replaced by ((PÙQ) Ú (PÙR)) ¨ (P Ú (QÙR)) can be replaced by ((PÚQ) Ù (PÚR)) n Over the implies sign ¨ (P ® (QÚR)) can be replaced by ((P®Q) Ú (P®R)) ¨ (P ® (QÙR)) can be replaced by ((P®Q) Ù (P®R)) Double negation n Double negations can be removed ¨ ¬¬P is equivalent to P n Caution when translating from natural language 9 de Morgan’s laws and contraposition n de Morgan’s laws ¨ ¬(PÙQ) is equivalent to (¬PÚ¬Q) ¨ ¬(PÚQ) is equivalent to (¬PÙ¬Q) n Contraposition ¨ (P®Q) is equivalent to (¬Q®¬P) Other equivalences n (P®Q) is equivalent to (¬PÚQ) n (P«Q) is equivalent to ((P®Q) Ù (Q®P)) n (P«Q) is equivalent to ((PÙQ) Ú (¬PÙ¬Q)) n (PÙ¬P) is equivalent to F n (PÚ¬P) is equivalent to T 10 Exercise (P®Q) ® (¬P®Q) n Show that this sentence is false Propositional implication rules n Re-write rules are good for bidirectional search ¨ What if equivalence does not hold n Modus Ponens A®B, A B ¨ Comma used for conjunction ¨ Above the line: what we know ¨ Below the line: what we can deduce 11 Proving Modus Ponens A B A®B a: A®B, A :B True True True True True True False False False False False True True False True False False True False True Elimination and introduction of “and” n “and” elimination A1, A2, …, An Ai [1 £ i £ n] n “and” introduction A1, A2, …, An A1 Ù A2 Ù … Ù An 12 Introduction of “or”; Unit resolution n “or” introduction Ai A1 Ú A2 Ú … Ú An [1 £ i £ n] n Unit resolution ¨ Basis for theorem proving (AÚB) Ù ¬B A Problems n Too many predicates ¨ Sample r.: “If you see a stop sign, then stop!” ¨ A new predicate for every stop sign n Slow inference n No variables (many constants needed) ¨ Even more predicates 13