Propositional Logic Language I A logic consists of an alphabet A a language L i e a set of formulas and a binary relation between a set of formulas and a formula I An alphabet A consists of a finite or countably infinite set of nullary relation symbols AR p q the set of connectives and the punctuation symbols and I The language L of propositional logic formulas is defined as follows Each relation symbol is a formula If F and G are formulas then F F G F G F G and F G are formulas 2 Propositional Logic 1 Notions Remarks and an Example I Nullary relation symbols are also called propositional variables nullary predicate symbols and atoms I Literals are formulas of the form p or p I We define a precedence hierarchy as follows I A simple example p1 p2 q1 q2 2 Propositional Logic 2 Structural Induction and Recursion I Theorem 2 1 Principle of Structural Induction Every formula of propositional logic has a certain property E provided that 1 Basis step Every propositional variable has property E 2 Induction steps If F has property E so does F If F and G have property E so does F G where I Theorem 2 2 Principle of Structural Recursion There is one and only one function h defined on the set of propositional formulas such that 1 Basis step The value of h is specified explicitly on propositional variables 2 Recursion steps The value of h on F is specified in terms of the value of h on F The value of h on F G is specified in terms of the values of h on F and on G where 2 Propositional Logic 3 Subformulas I The set of subformulas T H is the smallest set satisfying the following conditions H T H If F T H then F T H If F G T H then F G T H where 2 Propositional Logic 4 Propositional Logic Semantics I Goal assign a meaning to formulas with the help of a function L t f I Interpretation I a total mapping AR t f I Abbreviation I AR with the understanding that I p t iff p I I I models F in symbols I F I I I I I I p F F1 F2 F1 F2 F1 F2 F1 F2 iff iff iff iff iff iff I p t iff p I I 6 F I F1 and I F2 I F1 or I F2 I 6 F1 or I F2 I F1 F2 and I F2 F1 2 Propositional Logic 5 Connectives I Unary connective t f f t I Binary connectives t t f f t f t f t f f f t t t f t f t t t f f t 2 Propositional Logic 6 Models Validity and More Notions I An interpretation I for F is said to be a model for F iff I F I Let F be a set of formulas I is a model for F iff I is a model for each G F I F is said to be valid or a tautology iff for all I we find that I F I F is said to be satisfiable iff there exists an I such that I F I F is said to be falsifiable iff there exists an I such that I 6 F I F is said to be unsatisfiable iff for all I we find that I 6 F 2 Propositional Logic 7 Logical Entailment I A set of formulas F logically entails G or G is a logical consequence of F or G is a theorem of F in symbols F G iff each model for F is also a model for G I A satisfiable set of formulas together with all its theorems is said to be a theory I Truth tabling p q r p r p t t t t f f f f q t t f f t t f f r t f t f t f t f q r t f f f t f f f p q r t f f f t t t t p r t f t f t t t t 2 Propositional Logic 8 Logical Consequence vs Validity vs Unsatisfiability I Theorem 2 3 F G H iff F G H F1 Fn F iff F1 Fn 1 Fn F iff iff F1 F2 Fn F Logical consequence is related to validity I Abbreviation F F I Theorem 2 4 F is valid iff F is unsatisfiable Validity is related unsatisfiability Logical consequence is related to unsatisfiability 2 Propositional Logic 9 Semantic Equivalence I F G if for all interpretations I we find that I F iff I G I Some equivalences F F F F F F F G F G G F G F F G H F G H F G H F G H F G F F G F F F F G H F G H F G F H F G F H idempotency commutativity associativity absorption distributivity 2 Propositional Logic 10 More Equivalences F F F G F G F G F G F G F G F if F tautology G if F tautology F G F G G if F unsatisfiable F if F unsatisfiable F G F G G F equivalence F G F G implication double negation de Morgan tautology unsatisfiability 2 Propositional Logic 11 The Replacement Theorem I F G formula F in which the occurrences of the formula G are important I F G H formula obtained from F by replacing all occurrences of G by H I Theorem 2 5 If G H then F G F G H 2 Propositional Logic 12 Normal Forms I Negation normal form the formula is built solely by literals conjunctions and disjunctions I Conjunctive normal form the formula has the form F1 Fn n 0 where each of F1 Fn is a disjunction of literals case n 0 h i denoting a valid formula I Disjunctive normal form the formula has the form F1 Fn n 0 where each of F1 Fn is a conjunction of literals case n 0 denoting an unsatisfiable formula I Clause form set notation of formulas in conjunctive normal form I Clauses elements of these sets I Dual clause form set notation of formulas in disjunctive normal form I Dual clauses elements of these sets 2 Propositional Logic 13 Normal Form Transformation Input A propositional logic formula F Output A propositional logic formula G in conjunctive normal form which is equivalent to F 1 Eliminate all equivalence signs using the equivalence law 2 Eliminate all implication signs using the implication law 3 Eliminate all negation signs except those in literals using the de Morgan and the double negation laws 4 Distribute all disjunctions over conjunctions using the second distributivity the commutativity and the associativity laws 2 Propositional Logic 14 Normal Form Transformation Example p q r s p q r s p q r s p q r s p q r …