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).

3 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: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?

4 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.

5 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.

6 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.)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.

7 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.

8 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).

9 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. 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.

10 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. (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).