Propositional Logic - University at Buffalo

1 Propositional LogicCSE 191, Class Note 01 Propositional LogicComputer Sci & Eng DeptSUNY Buffaloc Xin He ( University at Buffalo )CSE 191 discrete Structures1 / 37 discrete MathematicsWhat isDiscrete Mathematics?In Math 141-142, you learn continuous math. It deals withcontinuous functions, differential and integral contrast, discrete math deals with mathematical topics in asense that it analyzes data whose values are separated (such asintegers: integer number line has gaps).Here is a very rough comparison between continuous math anddiscrete math: consider an analog clock (one with hands thatcontinuously rotate, which shows time in continuous fashion) vs.

2 Adigital clock (which shows time in discrete fashion).c Xin He ( University at Buffalo )CSE 191 discrete Structures3 / 37 Course TopicsThis course provides some of the mathematical foundations and skillsthat you will need in your further study of computer science andengineering. These topics include: Logic ( Propositional and predicate Logic )Logical inferences and mathematical proofCounting methodsSets and set operationsFunctions and sequencesIntroduction to number theory and CryptosystemMathematical inductionRelationsIntroduction to graph theoryBy definition, computers operate on discrete data (binary strings). So,in some sense, the topics in this class are more relavent to CSE majorthan Xin He ( University at Buffalo )CSE 191 discrete Structures4 / 37 The Foundations: Logic and ProofThe rules of Logic specify the precise meanings of is the basis of the correct mathematical arguments, that is, also has important applications in computer science.

3 To verify that computer programs produce the correct output for allpossible input show algorithms always produce the correct establish the security of Xin He ( University at Buffalo )CSE 191 discrete Structures6 / 37 Propositional LogicDefinitionA proposition is a declarative must be either TRUE or cannot be both TRUE and use T to denote TRUE and F to denote of propositions:Example of propositions:John loves CSE +3= +3= rises from of non-propositions:Does John love CSE 191?2+ the equation2+x= +x> Xin He ( University at Buffalo )CSE 191 discrete Structures7 / 37 Negation operatorDefinition:Supposepis a negation ofpis of p:pis :John does not love that pis a new proposition generated have generated one proposition from another we call (the symbol we used to generate the newproposition) the negation Xin He ( University at Buffalo )CSE 191 discrete Structures8 / 37 Logic operatorsIn general, we can define Logic operators that transform one or morepropositions to a new is a unitary operator since it transforms one propositionto will see a few binary operators shortly.

4 They transform twopropositions to a new Xin He ( University at Buffalo )CSE 191 discrete Structures9 / 37 Truth tableHow can we formally specify an operator ( , the negation operator)?One possibility is to use a truth truth table lists all possible combinations of the values of theoperands, and gives the corresponding values of the : Truth table for negation:p pTFFTc Xin He ( University at Buffalo )CSE 191 discrete Structures10 / 37 ConjunctionNow we introduce a binary operator: conjunction , which correspondsto and:p qis true if and only ifpandqare both :Alice is tall AND table for conjunction:pqp qTTTTFFFTFFFFc Xin He ( University at Buffalo )CSE 191 discrete Structures11 / 37 DisjunctionAnother binary operator is disjunction , which corresponds to or, (butis slightly different from common use.)

5 P qis true if and only ifporq(or both of them) are :Alice is smart OR table for disjunction:pqp qTTTTFTFTTFFFc Xin He ( University at Buffalo )CSE 191 discrete Structures12 / 37 ImplicationYet another binary operator implication :p qcorresponds :If this car costs less than $10000, then John will buy table for implication:pqp qTTTTFFFTTFFTNote that whenpis F,p qis always Xin He ( University at Buffalo )CSE 191 discrete Structures13 / 37 Bidirectional implicationAnother binary operator bidirectional implication :p qcorresponds topis T if and only ifqis :A student gets A in CSE 191 if and only if his weighted total is 95%.Truth table for bidirectional implication:pqp qTTTTFFFTFFFTc Xin He ( University at Buffalo )CSE 191 discrete Structures14 / 37 Terminology for implication statements play such an essential role inmathematics, a variety of terminology is used to expressp q: ifp, thenq.

6 Q, ifp . p, only ifq . pimpliesq . pis sufficient forq . qis necessary forp . qfollows fromp .c Xin He ( University at Buffalo )CSE 191 discrete Structures15 / 37 Terminology for : Alice is : Alice is Alice is smart is sufficient for Alice to be honest. Alice is honest if Alice is smart .q p:That Alice is smart is necessary for Alice to be honest. Alice is honest only if Alice is smart .c Xin He ( University at Buffalo )CSE 191 discrete Structures16 / 37 Exclusive Or operatorTruth table for Exclusive Or pqp qTTFTFTFTTFFFA ctually, this operator can be expressed by using other operators:p qis the same as (p q). is used often in CSE. So we have a symbol for Xin He ( University at Buffalo )CSE 191 discrete Structures17 / 37 Number of binary Logic operatorsWe have introduced 5 binary Logic operators.

7 Are there more?Fact: There are totally 16 binary Logic see this:For any binary operator, there are 4 rows in its truth operator is completely defined by the T/F values in the 3rdcolumn of its truth entry in the 3rd column of the truth table has 2 possiblevalues (T/F).So the total number of different 3rd column (hence the number ofdifferent binary operators) is2 2 2 2= of other 11 binary operators are not used often, so we do nothave symbols for Xin He ( University at Buffalo )CSE 191 discrete Structures18 / 37 Precedence of OperatorsOperatorPrecedence 1 2 3 4 5 Example: p qmeans( p) qp q rmeans(p q) rWhen in doubt, use Xin He ( University at Buffalo )CSE 191 discrete Structures19 / 37 Translating logical formulas to English sentencesUsing the above Logic operators, we can construct more complicatedlogical formulas.

8 (They are called compound propositions.)ExamplePropositionp: Alice is : Alice is honest. p q:Alice is not smart but ( p q):Either Alice is smart, or she is not smart but q:If Alice is smart, then she is not Xin He ( University at Buffalo )CSE 191 discrete Structures20 / 37 Translating logical formulas from English sentencesWe can also go in the other direction, translating English sentences tological formulas:Alice is either smart or honest, but Alice is not honest if she issmart:(p q) (p q).That Alice is smart is necessary and sufficient for Alice to behonest:(p q) (q p).(This is often written asp q).c Xin He ( University at Buffalo )CSE 191 discrete Structures21 / 37 Tautology and Logical equivalenceDefinitions:A compound proposition that is always True is called a propositionspandqare logically equivalent if their truthtables are the ,pandqare logically equivalent ifp qis a logically equivalent, we writep Xin He ( University at Buffalo )CSE 191 discrete Structures22 / 37 Examples of Logical equivalenceExample:Look at the following two compound propositions:p qandq qTTTTFFFTTFFTpq pq pTTFTTFFFFTTTFFTTThe last column of the two truth tables are identical.

9 Therefore(p q)and(q p)are logically (p q) (q p)is a :(p q) (q p).Example:By using truth table, provep q (p q).c Xin He ( University at Buffalo )CSE 191 discrete Structures23 / 37De Morgan lawWe have a number of rules for logical equivalence. For example:De Morgan Law: (p q) p q(1) (p q) p q(2)The following is the truth table proof for (1). The proof for (2) is q (p q)TTTFTFFTFTFTFFFTpq p qTTFTFTFTTFFTc Xin He ( University at Buffalo )CSE 191 discrete Structures24 / 37 DistributivityDistributivityp (q r) (p q) (p r)(1)p (q r) (p q) (p r)(2)The following is the truth table proof of (1). The proof of (2) is rp (q r)p qp r(p q) (p r)TTTTTTTTTTFFTTTTTFTFTTTTTFFFTTTTFTTTTT TTFTFFFTFFFFTFFFTFFFFFFFFFc Xin He ( University at Buffalo )CSE 191 discrete Structures25 / 37 ContrapositivesContrapositivesThe proposition q pis called the Contrapositive of the propositionp q.

10 They are logically q q ppqp qTTTTFFFTTFFTpq q pTTTTFFFTTFFTc Xin He ( University at Buffalo )CSE 191 discrete Structures26 / 37 Logic EquivalencesEquivalenceNamep T p,p F pIdentity lawsp T T,p F FDomination lawsp p p,p p pIdempotent laws ( p) pDouble negation lawp q q pp q q pCommutative laws(p q) r p (q r)(p q) r p (q r)Associative lawsp (q r) (p q) (p r)p (q r) (p q) (p r)Distributive laws (p q) p q (p q) p qDe Morgan s lawsp (p q) pp (p q) pAbsorption lawsp p T,p p FNegation lawsc Xin He ( University at Buffalo )CSE 191 discrete Structures27 / 37 Logic EquivalencesLogical Equivalences Involving Conditional Statementsp q p qp q q pp q p qp q (p q) (p q) p q(p q) (p r) p (q r)(p r) (q r) (p q) r(p q) (p r) p (q r)(p r) (q r) (p q) rLogical Equivalences Involving Biconditional Statementsp q (p q) (q p)p q p qp q (p q) ( p q) (p q) p qc Xin He ( University at Buffalo )CSE 191 discrete Structures28 / 37 Prove equivalenceBy using these laws, we can prove two propositions are 1: Prove (p ( p q)) p q.