Discrete Mathematics I - University Of Cambridge

2.1The Language of Propositional LogicAtomic Propositions1 1 210 10 30Tom is a studentslide 13 Is Tom a student? Give Tom food! x 7 101 2 . n n(n 1)/2 Atomic Propositionsslide 14We’ll use lowercase letters p, q, for atomic propositions.When you use logic to reason about particular things, you will want to have meaningfulatomic propositions, like “Tom is a student” or “It is raining”. For studying logic in generalwe use symbols like p and q.Some people say “propositional variable” instead of “atomic proposition”.We do not fix atomic propositions to be true or false. Rather, we investigate how their truthand falsity affects the compound propositions that we build. Atomic propositions are atomicbecause, for the purposes of logic, they are indivisible and their truth does not depend onthe truth of other things.Building Propositions: Truth and FalsityWe’ll write T for the constant true proposition, and F for the constantslide 15false proposition.Compound PropositionsWe’ll build more complex compound propositions out of the atomicslide 16propositions (p, q ) and T and F .We’ll use capital letters (P , Q , etc.) to stand for arbitrary propositions.They might stand for atomic propositions or compound propositions.Building Compound Propositions: ConjunctionIf P and Q are two propositions, P Q is a proposition.Pronounce P Q as ‘P and Q ’. Sometimes written with & or .Definition:P Q is true if (and only if) P is true and Q is trueExamples:slide 17Tom is a student Tom has red hair(1 1 2) (7 10)(1 1 2) (2 3)((1 1 2) (7 10)) (5 5)(p q) p9

Building Compound Propositions: ConjunctionWe defined the meaning of P Q by saying ‘P Q is true if and only ifP is true and Q is true’.We could instead, equivalently, have defined it by enumerating all thecases, in a truth table:P QP T TTTFFFTFFFFAccording to this definition, is ((1 1Qslide 18 2) (7 10)) (5 5) trueor false?Building Compound Propositions: ConjunctionWe pronounce P Q as ‘P and Q ’, but not all uses of the English ‘and’can be faithfully translated into .Tom and Alice had a dance.GroupingTom went to a lecture and had lunch.slide 19Temporal ordering?The Federal Reserve relaxed banking regulations, and the marketsboomed.Causality?When we want to talk about time or causality in CS, we’ll do so explicitly;they are not built into this logic.Building Compound Propositions: ConjunctionBasic properties:The order doesn’t matter: whatever P and Q are, P Q means thesame thing as Q P .Check, according to the truth table definition, considering each of the 4 possiblecases:slide 20PQPTTTTTFFFFTFFFFFF QQIn other words, is commutative10 P

Building Compound Propositions: Conjunction.and:The grouping doesn’t matter: whatever P , Q , and R are, P (Q R)means the same thing as (P Q) R .(Check, according to the truth table definition, considering each of the 8 possibleslide 21cases).In other words, is associativeSo we’ll happily omit some parentheses, e.g. writing P1 P2 P3 P4for P1 (P2 (P3 P4 )).Building Compound Propositions: DisjunctionIf P and Q are two propositions, P Q is a proposition.Pronounce P Q as ‘P or Q ’. Sometimes written with or Definition:P Q is true if and only if P is true or Q is trueEquivalent truth-table definition:slide 22P QP T TTTFTFTTFFFQBuilding Compound Propositions: DisjunctionYou can see from that truth table that is an inclusive or:P Q if at leastone of P and Q .(2 2 4) (3 3 6) is true(2 2 4) (3 3 7) is trueThe English ‘or’ is sometimes an exclusive or:P xor Q if exactly one ofslide 23P and Q . ‘Fluffy is either a rabbit or a cat.’PQTTPTFTFTTFTTTFFFF QP xor QAlthough xor is important in electronics, it does not play a primitive role in logic. If you feelthat an English sentence ‘P or Q’ reads as (P xor Q), you should regard it more precisely as‘either P or Q but not both’, which can be formalized using negation as (P Q) (P Q).11

Building Compound Propositions: DisjunctionBasic Properties is also commutative and associative:P Q and QP (Q P have the same meaningR) and (P Q) R have the same meaningslide 24distributes over :P (Q R) and (P Q) (P‘P and either Q or R ’ R) have the same meaning‘either (P and Q ) or (P and R )’and the other way round: distributes over P (Q R) and (P Q) (P R) have the same meaningWhen we mix and , we take care with the parentheses!Building Compound Propositions: NegationIf P is some proposition, P is a proposition.Pronounce P as ‘not P ’. Sometimes written as P or PDefinition: P is true if and only if P is falseslide 25Equivalent truth-table definition:P PTFFTBuilding Compound Propositions: ImplicationIf P and Q are two propositions, PPronounce PDefinition: Q is a proposition. Q as ‘P implies Q ’. Sometimes written with P Q is true if (and only if), whenever P is true, Q is trueEquivalent truth-table definition:slide 26P QP QT TTTFFFTTFFT12

Building Compound Propositions: ImplicationThat can be confusing. First, the logic is not talking about causation, butjust about truth values.(1 1 2) (3 4) is true Q is vacuously true if P is false.Second, P‘If I’m a giant squid, then I live in the ocean’slide 27For that to be true, either:(a) I really am a giant squid, in which case I must live in the ocean, or(b) I’m not a giant squid, in which case we don’t care where I live.P Q and (P Q) P and Q P all have the same meaningBuilding Compound Propositions: ImplicationBasic properties:P Q and Q P have the same meaning is not commutative: P Q and Q P do not have the sameslide 28meaningP (Q R) and (P Q) (P R) have the same meaning(P Q) R and (P R) (Q R) do not(P Q) R and P (Q R) doBuilding Compound Propositions: Bi-ImplicationIf P and Q are two propositions, P Q is a proposition. Q as ‘P if and only if Q ’. Sometimes written withP Q or P Q .Pronounce PDefinition:P Q is true if (and only if) P is true whenever Q is true,and vice versaslide 29Equivalent truth-table definition:P QP QT TTTFFFTFFFTThe Language of Propositional LogicSummarising, the propositions of propositional logic are the terms of thegrammarP , Q :: p q . T F P P Q P Q P Q P QWe use parentheses (P ) as necessary to avoid ambiguity.For any such proposition P , once the truth value of each atomicproposition p it mentions is fixed (true or false), we’ve defined whether Pis true or false.13slide 30

Example Compound Truth TableGiven an arbitrary proposition P , we can calculate the meaning of P forall possible assumptions on its atomic propositions by enumerating thecases in a truth table.For example, consider Pdef ((p q) (p q)). It mentions twoatomic propositions, p and q, so we have to consider 22 possibilities:pslide 31 q p q p q (p q) (p q)qT TFTTTT FTTFFF TFFFTFTTFFFNotice that this calculation is compositional in the structure of P .The Binary Boolean Functions of one and two variables2(21 )functions of one variablePTP PFTTTFFFTFTFslide 3222(2 ) functions of two variablesPQT P Q TFFTTFFTTFFFFTFTFTFTFTFTFTFTFFAll boolean functions can be defined in terms of connectives that we have introduced so far(see Ex Sheet 1, Q12).2.2Equational reasoning, validity and satisfiabilityEquivalencesIdentity:P T and P have the same meaningP F and P have the same meaningComplement:P P and F have the same meaningP P and T have the same meaningslide 33De Morgan: (P Q) and P Q have the same meaning (P Q) and P Q have the same meaningTranslating away :P Q and (P Q) (Q P ) have the same meaning14

EquivalencesWhen we say ‘P and Q have the same meaning’, we really mean‘whatever assumption we make about the truth values of their atomicslide 34propositions, P and Q have the same truth value as each other’. In otherwords, ‘P and Q have the same truth table’.We write that as P QEquational ReasoningEquivalences are really useful because they can be used anywhere.In more detail, this P Q is a proper notion of equivalence. You can seefrom its definition that it’s reflexive, i.e., for any proposition P , we have P Pslide 35 it’s symmetric, i.e., if P Q then Q P it’s transitive, i.e., if P Q and Q R then P RMoreover, if P Q then we can replace a subformula P by Q in anycontext, without affecting the meaning of the whole thing. For example,if P Q then P r Q r, r P r Q , P Q , etc.Equational ReasoningNow we’re in business: we can do equational reasoning, replacing equalsubformulae by equal subformulae, just as you do in normal algebraicmanipulation (where you’d use 2 2 4 without thinking).slide 36This complements direct verification using truth tables — sometimesthat’s more convenient, and sometimes this is. Later, we’ll see a thirdoption — structured proof.Some Collected Equivalences, for ReferenceFor any propositions P , Q , and RUnit:Commutativity:PPQ Q Q Q PPP (and-comm) P (or-comm) (Q (Q R) (P R) (P Q) R (and-assoc) Q) R (or-assoc) (Q (Q R) (P R) (P Identity:PPT P (and-id) F P (or-id) F F (and-unit)T T (or-unit)PP P F (and-comp) P T (or-comp)De Morgan:Distributivity:PP Complement:Associativity:PP Q) (P Q) (P R) (and-or-dist) (P R) (or-and-dist) (P Q) PQ) P Q (and-DM) Q (or-DM)Defn:P Q Q P (imp)P Q (P Q) (Q P ) (bi)15slide 37

Equational Reasoning — ExampleSuppose we wanted to prove a 3-way De Morgan law (P1 P2 P3 ) P1 P2 P3We could do so either by truth tables, checking 23 cases, or by equationalreasoning: (P1 P2 P3 ) (P1 (P2 P3 )) choosing an associationslide 38 P1 (P2 P3 ) by (and-DM)(and-DM) is (P Q) P Q . Instantiating the metavariables P and Q asP% P1Q% P2 P3we get exactly the (P1 (P2 P3 )) P1 (P2 P3 ) needed. (P1 P2 P3 ) (P1 (P2 P3 )) P1 (P2 P3 )choosing an associationby (and-DM) P1 ( P2 P3 ) by (and-DM)(and-DM) is (P Q)we get (P2 P3 ) P Q . Instantiating the metavariables P and Q asP% P2Q% P3slide 39 P2 P3 . Using that in the context P1 . gives us exactly P1 ( P2 P3 ).the equality P1 (P2 P3 )) P1 P2 P3So by transitivity of , we have (P1 P2 P3 )forgetting the association P1 P2 P3There I unpacked the steps in some detail, so you can see what’s reallygoing on. Later, we’d normally just give the brief justification on each line;we wouldn’t write down the boxed reasoning (instantiation, context,transitivity) — but it should be clearly in your head when you’re doing aproof.slide 40If it’s not clear, write it down — use the written proof as a tool for thinking.Still later, you’ll use equalities like this one as single steps in biggerproofs.Theorem. Equational reasoning is sound: however we instantiate theequations, and chain them together, if we deduce that P Q thenP Q.Soundness is proved by combining the various facts established in thissection so far, but we won’t go into detail on the proof of soundness in thiscourse.Soundness is pragmatically important: if you’ve faithfully modelled somereal-world situation in propositional logic, then you can do any amount ofequational reasoning, and the result will be meaningful.16slide 41

Theorem. Equational reasoning complete: if P Q , then there is anequational proof.Proving completeness is beyond the scope of DM1.Completeness is pragmatically important: if P Q , and youslide 42systematically explore all possible candidate equational proofs, eventuallyyou’ll find one. But there are infinitely many candidates: at any point,there might be several you could try to apply, and sometimes there areinfinitely many instantiations (consider T P P ).so naive proof search is not a decision procedure (but sometimes youcan find short proofs).slide 43In contrast, we had a terminating algorithm for checking truth tables (butthat’s exponential in the number of atomic propositions).Tautology, validity, and satisfiabilitySay P is a tautology, or is valid, if it is always true — i.e., if, whateverassumption we make about the truth values of its atomic propositions,then P is true. In other words, P is a tautology if every row of its truthtable is T .There is a connection with equational reasoning: (P(P Q ) exactly when Q ) is a tautology.slide 44Say P is a satisfiable if, under some assumption about the truth values ofits atomic propositions, P is true.p p is a tautology (always true, no matter what assumptions aremade about p)p q satisfiable (true under the assumption p T , q F )p p unsatisfiable (not true under p T or p F )P is unsatisfiable if and only if P is valid.Object, Meta, Meta-Meta,.We’re taking care to distinguish the connectives of the object languagethat we’re studying (propositional logic), and the informal mathematicsslide 45and English that we’re using to talk about it (our meta-language).For now, we adopt a simple discipline: the former in symbols, the latter inwords.Application: Combinational CircuitsUse T and F to represent high and low voltage values on a wire.Logic gates (AND, OR, NAND, etc.) compute propositional functions oftheir inputs. Notation:T , F , , , vs 0, 1, ., ,SAT solvers: compute satisfiability of propositions with 10 000’s of atomicpropositions.17slide 46

3Predicate LogicPredicate Logicslide 47In this section we extend propositional logic with predicates and quantifiers.Predicate Logic(or Predicate Calculus, or First-Order Logic)Socrates is a man. All men are mortal. So Socrates is mortal.slide 48Can we formalise in propositional logic?Write p for Socrates is a manWrite q for Socrates is mortalpp qq?Predicate LogicOften, we want to talk about properties of things, not just atomicpropositions.All lions are fierce.Some lions do not drink coffee.Therefore, some fierce creatures do not drink coffee.[Lewis Carroll, 1886]Let x range over creatures. Write L(x ) for ‘x is a lion’. Write C(x ) for ‘xdrinks coffee’. Write F(x ) for ‘x is fierce’. x .L(x ) F(x ) x .L(x ) C(x ) x .F(x ) C(x )18slide 49

3.1The Language of Predicate LogicPredicate LogicSo, we extend the language.Variables x , y , etc., ranging over some specified domain.Atomic predicates A(x ), B(x ), etc., like the earlier atomic propositions,but with truth values that depend on the values of the variables.Let A(x ) denote xnumbers. 7 10, where x ranges over the naturalA(x ) is true if x 3, otherwise false, so A(3) A(4)slide 50Let B(n) denote 1 2 . nover the naturals. n(n 1)/2, where n rangesB(n) is true for any value of n , so B(27).Add these to the language of formulae:P , Q :: A(x ) T F P P Q P Q P Q P Qwhere A ranges over atomic predicates A, B, etc.Predicate Logic — Universal QuantifiersIf P is a formula, then Pronounce Definition:x .P is a formulax .P as ‘for all x , P ’. x .P is true if (and only if) P is true for all values of x (takenfrom its specified domain).Sometimes we write P (x ) for a formula that might mention x , so that wecan write (e.g.)slide 51P (27) for the formula with x instantiated to 27.Then, if x is ranging over the naturals, x .P (x ) if and only if P (0) and P (1) and P (2) and .Or, if x is ranging over {red, green, blue},then( x .P (x )) P (red) P (green) P (blue).Predicate Logic — Existential QuantifiersIf P is a formula, then Pronounce Definition:x .P is a formulax .P as ‘exists x such that P ’. x .P is true if (and only if) there is at least one value of x(taken from its specified domain) such that P is true.So, if x is ranging over {red, green, blue}, then ( x .P (x )) if and onlyif P (red) P (green) P (blue).Because the domain might be infinite, we don’t give truth-table definitionsfor and .Note also that we don’t allow infinitary formulae — I carefully didn’t write( x .P (x )) P (0) P (1) P (2) .19 slide 52

The Language of Predicate LogicSummarising, the formulae of predicate logic are the terms of thegrammarP , Q :: A(x ) T F P P Q P Q P Q slide 53P Q x .P x .PConvention: the scope of a quantifier extends as far to the right aspossible, so (e.g.) x .A(x ) B(x ) is x .(A(x ) B(x )), not( x .A(x )) B(x ).(other convention — no dot, always parenthesise: x (P ) )Predicate Logic — Extensionsn-ary atomic predicates A(x , y), B(x , y, z ),.(regard our old p, q, etc. as 0-ary atomic predicates) e # ) where e and e # are somemathematical expressions (that might mention variables such as x ), andsimilarly for , , , over numbers.Equality as a special binary predicate (eslide 54(e / e # ) is shorthand for (e e # )(e e # ) is shorthand for (e e # ) (e e # )Predicate Logic — ExamplesWhat do these mean? Are they true or false? x .(x 2 2x 1 0) where x ranges over the integersslide 55 x .(x 0) (x 0) (x 0) where x ranges over the reals x .(x 0) (2x x ) where x ranges over the realsPredicate Logic — ExamplesFormalise:If someone learns discrete mathematics, then they will find a good job. (*)slide 56Let x range over all people.Write L(x ) to mean ‘x learns discrete mathematics’Write J(x ) to mean ‘x will find a good job’Then x .L(x ) J(x ) is a reasonable formalisation of (*).Is it true? We’d need to know more.Predicate Logic — Nested QuantifersWhat do these mean? Are they true? x . y.(x y y x ) where x , y range over the integers x . y.(x y 10) where x , y range over the integers x . y.(x y) where x , y range over the integers y. x .(x y) where x , y range over the integers x . y.(4x 2y) (x 1 y) where x , y range over the integers20slide 57

Predicate Logic — ExamplesFormalise:Every real number except 0 has a multiplicative inverseslide 58 x .( (x 0)) y.(x y 1) where x ranges over the realsPredicate Logic — Free and Bound VariablesA slightly odd (but well-formed) formula:A(x ) ( x .B(x ) x .C(x , x ))Really there are 3 different x ’s here, and it’d be clearer to writeA(x ) ( x # .B(x # ) x ## .C(x ## , x ## )) orA(x ) ( y.B(y) z .C(z , z ))slide 59Say an occurrence of x in a formula P is free if it is not inside any( x .) or ( x .)All the other occurrences of x are bound by the closest enclosing( x .) or ( x .)The scope of a quantifier in a formula .( x .P ). is all of P (except anysubformulae of P of the form x . or x .).Truth SemanticsWhether a formula P is true or false might depend on1. an interpretation of the atomic predicate symbols used in P(generalising the ‘assumptions on its atomic propositions’ we hadslide 60before)2. the values of the free variables of POften 1 is fixed (as it is for e e #)Predicate Logic — Basic PropertiesDe Morgan laws for quantifiers:( x .P ) x . P( x .P ) x . Pslide 61Distributing quantifiers over and :( x .P Q) ( x .P ) ( x .Q)( x .P Q) / ( x .P ) ( x .Q) (left-to-right holds)( x .P Q) / ( x .P ) ( x .Q) (right-to-left

Discrete Mathematics I Computer Science Tripos, Part 1A Paper 1 Natural Sciences Tripos, Part 1A, Computer Science option Politics, Psychology and Sociology, Part 1, Introduction to Computer Science option 2012–13 Lecturer: Sam Staton Computer Laboratory University of C