Discrete Mathematics, Chapter 1.1.-1.3: Propositional Logic

1 Discrete mathematics , Chapter : Propositional LogicRichard MayrUniversity of Edinburgh, UKRichard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Outline1 Propositions2 Logical Equivalences3 Normal FormsRichard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 PropositionsA proposition is a declarative sentence that is either true or of propositions:The Moon is made of green is the capital of New is the capital of + 0 = 10 + 0 = 2 Examples that are not down!What time is it?x + 1 = 2x + y = zRichard Mayr (University of Edinburgh, UK) Discrete mathematics .

2 Chapter / 21 Propositional LogicConstructing PropositionsPropositional Variables:p,q,r,s,..The proposition that is always true is denoted byTand theproposition that is always false is denoted Propositions; constructed from logical connectives andother propositionsNegation Conjunction Disjunction Implication Biconditional Richard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 DisjunctionThe disjunction of propositionspandqis denoted byp qand hasthis truth table:pq p qTTTTFTFTTFFFR ichard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 ConjunctionThe disjunction of propositionspandqis denoted byp qand hasthis truth table:pqp q TTTTFFFTFFFFR ichard Mayr (University of Edinburgh, UK) Discrete mathematics .

3 Chapter / 21 ImplicationIfpandqare propositions, thenp qis a conditional statementor implication which is read as ifp, thenq and has this truthtable:p qp qTTTTFFFTTFFTInp q,pis the hypothesis (antecedent or premise) andqis theconclusion (or consequence).Implication can be expressed by disjunction and negation:p q p qRichard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Understanding ImplicationInp qthere does not need to be any connection between theantecedent or the consequent. The meaning depends only on thetruth values implication is perfectly fine, but would not be used in ordinaryEnglish.

4 If the moon is made of green cheese, then I have moremoney than Bill Gates. One way to view the logical conditional is to think of an obligationor contract. If I am elected, then I will lower taxes. Richard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Different Ways of Expressingp qifp, thenqpimpliesqifp,qponly ifqqunless pqwhenpqifpqwheneverppis sufficient forqqfollows frompqis necessary forpa necessary condition forpisqa sufficient condition forqispRichard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Converse, Contrapositive, and Inverseq pis theconverseofp q q pis thecontrapositiveofp q p qis theinverseofp qExample: Find the converse, inverse, and contrapositive of It is raining is a sufficient condition for my not going to town.

5 Solution:converse: If I do not go to town, then it is : If it is not raining, then I will go to : If I go to town, then it is not do the converse, contrapositive, and inverse relate top q?Clicker1converse contrapositive?2converse inverse?3contrapositive inverse?Richard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 BiconditionalIfpandqare propositions, then the biconditional propositionp qhas this truth tablepqp q TTTTFFFTFFFTp qalso reads aspif and only necessary and sufficient forqifpthenq, and converselypimpliesq, and vice-versaRichard Mayr (University of Edinburgh, UK) Discrete mathematics .

6 Chapter / 21 Precedence of Logical Operators1 2 3 4 5 Thusp q ris equivalent to(p q) the intended meaning isp (q r)then parentheses must Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Satisfiability, Tautology, ContradictionA proposition issatisfiable, if its truth table containstrueat least once. Example:p tautology, if it is always true. Example:p contradiction, if it always false. Example:p contingency, if it is neither a tautology nor a Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Logical EquivalenceDefinitionTwo compound propositionspandqare logically equivalent if thecolumns in a truth table giving their truth values is written asp is easy to show:Factp q if and only if p q is a Mayr (University of Edinburgh, UK) Discrete mathematics .

7 Chapter / 21De Morgan s Laws (p q) p q (p q) p qTruth table proving De Morgan s second p q(p q) (p q) p qTTFFTFFTFFTTFFFTTFTFFFFTTFTTR ichard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Important Logical EquivalencesDomination laws:p T T,p F FIdentity laws:p T p,p F pIdempotent laws:p p p,p p pDouble negation law: ( p) pNegation laws:p p T,p p FThe first of the Negation laws is also called law of excluded middle .Latin: tertium non datur .Commutative laws:p q q p,p q q pAssociative laws:(p q) r p (q r)(p q) r p (q r)Distributive laws:p (q r) (p q) (p r)p (q r) (p q) (p r)Absorption laws:p (p q) p,p (p q) pRichard Mayr (University of Edinburgh, UK) Discrete mathematics .

8 Chapter / 21 More Logical EquivalencesRichard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21A Proof in Propositional LogicTo prove: (p ( p q)) p q (p ( p q)) p ( p q)by De Morgan s 2nd law p ( ( p) q)by De Morgan s first law p (p q)by the double negation law ( p p) ( p q)by the 2nd distributive law F ( p q)because p p F ( p q) Fby commutativity of disj. p qby the identity law forFRichard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Conjunctive and Disjunctive Normal FormA literal is either a Propositional variable, or the negation of :p, clause is a disjunction of :p q formula in conjunctive normal form (CNF) is a conjunction :(p q r) ( p r)Similarly, one defines formulae in disjunctive normal form (DNF) byswapping the words conjunction and disjunction in the :( p q r) ( q r) (p r).

9 Richard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21 Transformation into Conjunctive Normal FormFactFor every Propositional formula one can construct an equivalent one inconjunctive normal all other operators by conjunction, disjunction negations inward by De Morgan s laws and the doublenegation law until negations appear only in the commutative, associative and distributive laws to obtainthe correct with domination, identity, idempotent, and negation laws.(A similar construction can be done to transform formulae intodisjunctive normal form.)Richard Mayr (University of Edinburgh, UK) Discrete mathematics .

10 Chapter / 21 Example: Transformation into CNFT ransform the following formula into CNF. (p q) (r p)1 Express implication by disjunction and negation. ( p q) ( r p)2 Push negation inwards by De Morgan s laws and double negation.(p q) ( r p)3 Convert to CNF by associative and distributive laws.(p r p) ( q r p)4 Optionally simplify by commutative and idempotent laws.(p r) ( q r p)and by commutative and absorbtion laws(p r)Richard Mayr (University of Edinburgh, UK) Discrete mathematics . Chapter / 21