L o g o1 1Discrete MathematicsSouth China University of TechnologyDr. Liu ZiwenL o g o2 2Section 1.2Chapter 1. Logic and Proof, Sets, and FunctionL o g o3 3 3 3ContentsTautology and Contradiction1Proofs with Truth Value Table2 Proofs of Logical Equivalences3L o g o4 4 4 4Tautology and ContradictionL o g o5 5 5 5TautologiesA tautology is a compound proposition that is true no matter what the truth values of its atomic propositions are!Ex. p p What is its truth table?L o g o6 6 6 6TautologiesvWhen every row of the truth table gives T.vExample: p p T F=T F T=F v T L o g o7 7 7 7ContradictionsA contradiction is a compound proposition that is false no matter what! Ex. p p Truth table?L o g o8 8 8 8ContradictionsvWhen every row of the truth table gives FvExample: p p T F=T F T=Fv FL o g o9 9 9 9Whats left besides tautologies and contradictionsAll other props. are contingencies Some rows give T, others give FNow: formulas that have the same meaningL o g o10101010Proofs with Truth Value TableL o g o11111111Propositional EquivalenceTwo syntactically (i.e., textually) different compound propositions may be semantically identical (i.e., have the same meaning). We call them logically equivalent. Notation: L o g o12121212Logical EquivalenceCompound proposition p is logically equivalent to compound proposition q, written pq, IFF p and q contain the same truth values in all rows of their truth tablesWe will also say: they express the same truth function (= the same function from values for atoms to values for the whole formula).L o g o13131313Ex. Prove that pq (p q).Example 2FTTTTTTTTTFFFFFFFFTTL o g o14141414Ex. Prove that pq p q.Example 3TTTFTTTTFTFFL o g o15151515Ex. Prove that p (q r) (p q) (p r) .Example 4 （distributive law）TTTTTTTFFTTFFTFFFFTFFFFTTTTTTTTTFTTTTFFFL o g o161616161.Consider a conjunction p1 p2 p3How many rows are there in its truth table?2.Consider a conjunctionp1 p2 pn of n propositions.How many rows are there in its truth table?3.Explain why and together are sufficient to express any Boolean truth tableQuestions for you to think aboutL o g o171717171.Consider a conjunction p1 p2 p3How many rows are there in its truth table? 8 p1 p2 p3 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0Questions for you to think aboutL o g o181818182. Consider p1 p2 pn How many rows are there in its truth table?2.2.2. .2 (n factors)Hence 2n (This grows exponentially!)Questions for you to think aboutL o g o19191919De Morgans lawsv(p1 p2 pn)= p1 p2 pnv(p1 p2 pn)= p1 p2 pnAugustusDe Morgan(1806-1871)v(p q)= p qv(p q)= p qL o g o20202020Truth Table for De Morgans LawL o g o21212121 Proofs of Logical EquivalencesL o g o22222222Equivalence Laws - ExamplesvIdentity: pT p pF pvDomination: pT T pF FvIdempotence: pp p pp pvDouble negation: p pvCommutativity: pq qp pq qpvAssociativity: (pq)r p(qr) (pq)r p(qr)L o g o23232323More Equivalence LawsvDistributive: p (q r) (p q) (p r) p (q r) (p q) (p r)vDe Morgans: (p q) p q (p q) p q vTrivial tautology/contradiction: p p T p p FAugustusDe Morgan(1806-1871)L o g o24242424Logical Equivalence Involving Implicationsv p q p q p q q pv p q p q p q (p q) v (p q) p qv (p q) (p r) p (q r)v (p r) (q r) (p q) rv (p q) (p r) p (q r)v (p r) (q r) (p q) rL o g o2525(p q) (p r) p (q r)v (p q) (p r)v ( p q) ( p r) v p (q r )v p (q r)vDistributive: p (q r) (p q) (p r) p (q r) (p q) (p r)L o g o2626(p r) (q r) (p q) rv (p r) (q r)v ( p r) ( q r) v r ( p q ) v r (p q ) v (p q ) rv (p q) rvDistributiveL o g o2727(p q) (p r) p (q r)v (p q) (p r)v ( p q) ( p r) v p (q r)v p (q r)vDistributiveL o g o2828(p r) (q r) (p q) rv (p r) (q r)v ( p r) ( q r)v r ( p q )v r (p q )v r (p q )v (p q) rL o g o29292929Logical Equivalence Involving Biconditionalsv p q (p q) (q p) v p q p q v p q (p q) ( p q) v (p q) p q L o g o3030p q (p q) (q p)v (p q) (q p)v ( p q) ( q p) v = T if p=q or F if p and q are differentvSo ( p q) ( q p) p q L o g o3131p q p q v p qv ( p q) ( q p) v ( p q) ( q p)v ( p q) (q p)v (q p) (p q)v p qL o g o3232p q (p q) ( p q)v p qv (p q) (q p)v ( p q) ( q p) v ( p q) q ) ( p q) p ) v ( pq) (q q) ( p p) (q p)v ( p q) F F (q p)v (q p) ( p q) vThe first approach of ProofL o g o3333p q (p q) ( p q)v p qv (p q) (q p)v ( p q) ( q p) v ( p q) T ) ( q p) T ) v ( p q) ( p p) ( q p) ( q q) v ( p (p q) ( q (p q)v (q p) ( p q) vThe second approach of ProofL o g o3434 (p q) p qv (p q)v (q p) ( p q)v (q p) ( p q)v ( q p) (p q)v p qv (p q) ( p q)v (p q) F) ( p q) F)v (pq) ( p p) ( p q) ( q q)v p ( p q) q ( p q) v( q p) (p q)L o g o35353535Defining Operators via EquivalencesSome equivalences can be thought of as definitions of one operator in terms of others:vExclusive or: pq (pq)(pq) pq (pq)(qp)vImplies: pq p qvBiconditional: pq (pq) (qp) pq (pq)L o g o3636p q (p q) ( p q )v p q v (p q)v (q p) ( p q)v (q p) ( p q)v ( q p) (p q)v (q p) (p q)L o g o3737p q ( p q ) ( q p)v ( p q ) ( q p )v ( ( p q ) ( q p )v ( ( p q ) ( q p )v ( p q) ( q p) v (p q) (q p)v (p q)v p qL o g o3838Example 1v (p ( p q) p q ?v (p ( p q)v p ( p q)v p ( p q )v p p p q v F p qv p qL o g o3939Example 2v ( p q ) p q Tv ( p q ) p qv (p q) (p q)v ( p q) (p q)v p q p qv p p q qv T Tv TL o g o40404040Example 3vUse equivalences to prove that (p q) (p r) p q r.v(This would be much easier using truth tables!)(p q) (p r) Expand “definition” of (p q) (p r) Expand “definition” of (p q) (p r) (p r) DeMorgan ( p q) (p r) (p r) cont.L o g o41414141Long example Continued.( p q) (p r) (p r) commutes (q p) (p r) (p r) is associative q ( p (p r) (p r) distrib. over q ( p (p r) ( p (p r) assoc.q ( p p) r) ( p (p r) taut. q (T r) ( p (p r) domination q (T ( p (p r) identity q ( p (p r) cont.L o g o42424242End of Long Exampleq ( p (p r) DeMorgan q ( p ( p r) Assoc. q ( p p) r) Idempotent q ( p r) Associativity (q p) r Commutativity p q r L o g o43434343ExercisesvP22 5vP23 8,11,13,14,16L o g o4444