Module 1: Basic Logic Theme 1: Propositions

1 Module 1: Basic LogicTheme 1: PropositionsEnglish sentences are either true or false or neither. Consider the following sentences:1. Warsaw is the capital of +5= How are you?The first sentence is true, the second is false, while the last one is neither true nor false. A statementthat is eithertrueorfalsebut not both is called aproposition. Propositional Logic deals with suchstatements andcompound propositionsthat combine together simple Propositions ( , combiningsentences (1) and (2) above we may say Warsaw is the capital of Poland and2+5=3 ).In order to build compound Propositions we need rules on how to combine Propositions . Wedenote Propositions by lowercase lettersp,qorr. Let us define: Theconjunctionofpandq, denoted asp^q, is the propositionpandq;and it istruewhen bothpandqare true and false otherwise. Thedisjunctionofpandq, denoted asp_q, is the propositionporq;and it isfalsewhen bothpandqare false and true otherwise. Thenegationofp, denoted either as:por p, is the propositionIt is 1:Letp= Hawks swoop andq= Gulls glide.

2 Thenp_qisthesameas Hawksswoopor gulls glide . We also can translate back. For example, the English sentence it is not true thathawks swoop can be written 1A: With the same notation as in the example above write the following Propositions sym-bolically: It is not true that Hawks swoop and gulls glide . Hawks do not swoop or gulls do not glide .1 Theme 2: Truth TablesWe can express compound Propositions using atruth tablethat displays the relationships betweenthe truth values of the simple Propositions and the compound proposition. In the next three tableswe show the truth tables for the negation, conjunction, and disjunction. Observe that any propositionpcan take only two values, namelytrue, denotedT,orfalse, denotedF. Therefore, for a com-pound proposition consisting of two Propositions ( ,p^q)we must consider only four possibleassignments 1: The truth table for the :pTFFTT able 2: The truth table for the ^qTTTTFFFTFFFFT able 3: The truth table for the this Module we will often use truth tables.

3 To construct a truth table for a statement ( ,:p_q) containing two Propositions , saypandq, one first builds two columns with all possible valesofpandq( ,(T;T);(T;F);(F;T);(F;F)), and then follows already accepted rules of inferenceto determine the truth value of the compound statement (say:p_q).Exercise 1B: Construct truth tables for the following statements: p^:p; p_ 3: ImplicationsIn mathematics we often deal withconditional statementslike: ifx=2,thenx2= thenstatement is calledimplicationand it is denoted asp!q. It is false whenpis true andqis false andtrue otherwise. The reader may inspect the truth table ofp!qin Table 4 4: The truth table for the !qTTTTFFFTTFFTIt is important to emphasize thatp!qis false only whenpistrueandqisfalse. In words,truthcannotimply afalsestatement, butfalsecan implytruth. For example, consider the followingstatementifx= 2;thenx2=4which is true even if the first part of this compound statement is not true, say whenx= the implicationp!q, the propositionpis calledhypothesisorantecedentand the propositionqis known asconclusionorconsequent.

4 The conclusion expresses anecessary conditionforp,while the hypothesis expresses asufficient conditionforqto hold. Some other common ways ofexpressing the implicationp!qare: ifp,thenq; pimpliesq; ifp,q; ponly ifq; pis sufficient forq; qifp; qwheneverp; qis necessary 1C: Make truth tables for the following !:q;2.(p^:q)! are some important related implications following fromp!q, namely:1. The propositionq!pis called Thecontrapositiveofp!qis:q!:p;3. Theinverseis:p! Table 5 we compare the truth values of these 5: The truth table for the implication, contrapositive, converse, and !q:q!:pq!p:p!:qTTTTTTTFFFTTFTTTFFFFTTTTW e say that two compound propositionsPandQarelogically equivalentif they have the sametruth values. We shall writeP QorP,Q:It should be observed from Table 5 that the implicationp!qhas the same truth values as thecontrapositive:q!:p, but not as the converse and the inverse. Thus we can writep!q :q!:p;p!q6 :p!:q;p!q6 q!p:Example 2: Prove thatp!q :p_q:We use the truth table.

5 Our computation is shown in Table 6. Comparing the second column with thelast one, we see that the truth values are the same forp!qand:p_q, so the above two compoundpropositions are logically 6: The truth table for Example !q:p:p_qTTTFTTFFFFFTTTTFFTTT4 Exercise 1D: Using the truth table prove that the following Propositions are logically equivalent:p_(q^r) (p_q)^(p_r):In Exercise 1D the reader was asked to prove logical equivalence that is known under the namedistributive law. This is an example of many other logical equivalences that we list in Table 7 andprove in the 7: Logical EquivalencesEquivalenceNamep^T pIdentity lawsp_F pp_T TDomination lawsp^F Fp_p pIdempotent lawsp^p p:(:p) pDouble negation lawp_q q_pCommutative lawsp^q q^pp_(q_r) (p_q)_rAssociative lawsp^(q^r) (p^q)^rp_(q^r) (p_q)^(p_r)Distributive lawsp^(q_r) (p^q)_(p^r):(p^q) :p_:qDe Morgan s laws:(p_q) :p^:qAll laws listed above can be easily proved using the truth table. The reader is encouraged to tryto work out all the truth tables.

6 Having such laws under our belt, we can prove many new logicalequivalenceswithoutusing the truth 3: Prove that:(p_(:p^q)) :p^:q :(p_q):We proceed as follows:(p_(:p^q)) :p^:(:p^q)De Morgan s law :p^(:(:p)_:q)De Morgan s law :p^(p_:q)double negation law (:p^p)_(:p^:q)distributive law5 F_(:p^:q)since:p^p F (:p^:q)_Fcommutative law (:p^:q)identity law :(p_q)De Morgan s law:Thus the above logical equivalence is proved. The above is largely self-explanatory, but a few wordsof additional information follows: In the first statement above we, naturally, apply De Morgan s law:(P_Q)=:P^:Q. In our case,Qis a compound statementQ=:p^q, thus another applicationof De Morgan s law implies:Q=p_:q. Then we multiply out , that is,p^(q_r)=(p^q)_(p^r).The rest is compound proposition is called atautologyif it is always true, no matter what the truth valuesof the Propositions ( ,p_:p Tno matter what is the value ofp. Why?).A compound proposition is called acontradictionif it is always false, no matter what the truthvalues of the Propositions ( ,p^:p Tno matter what is the value ofp.)

7 Why?).Finally, a proposition that is neither a tautology nor a contradiction is called 4: Predicates and QuantifiersIn mathematics we often have to deal with sentences likep:x2 2x+1=0orq:nis a prime number;which arenotpropositions since their values are neither true nor false since the values of the variablesxandnare not specified. We shall denote such statements asP(x)orQ(n)and formally, letPbe a statement involving the variablexthat belongs to the apropositional functionorpredicatewith respect toDif for eachx2 Dthe sentenceP(x)is a proposition. The domainDis often called theuniverse of 4: The statement aboveP(x):x2 2x+1=0is true whenx=1and is false for anyx6=1. The statementQ(3)is true, whereQ(n): nis a primenumber .Predicates are very important in mathematics and computer science since they allow us to justifylogical inferences orsyllogisms. Consider the following famous syllogism:All men are is a , Fermat is conclusion seems to be perfectly correct, but we do not have rules of inference for propositionallogic to justify it.

8 We shall come back in Module 3 to such logical inferences when we discussmathematical saw above how to change a propositional function into a proposition: by assigning truth valuesto the variablex. There is another way of changing a predicateP(x)into a proposition: either bysaying thatP(x)is true forallvalues ofxbelonging toDor thatP(x)is true forsomevalue ofxinD. The former is called theuniversal quantificationwhile the latter theexistential quantificationTheuniversal quantificationP(x)is the propositionP(x)is true for all values ofxin the universe of shall denote is as8xP(x):7We can also read it as for allxP(x) or for everyxP(x) . The symbol8(notice that it is anupside downA) is called a universal 5: The statement8xx2 0is a universally quantified statement that is true. But8xx2>0is a universally quantified statement that is false since forx=0we havex2= how to prove that a universal quantification is false. We must showat least one valueofxforwhichP(x)is not true.

9 Such a value ofxis called acounterexamplefor8x;P(x).Finally, observe that if the universe of discourse consists of a finite number of elements, sayx1;x2;:::;xn,then8xP(x) P(x1)^P(x2)^ ^P(xn)since this conjunction is true if and only ifP(x1);P(x2);:::;P(xn)are all quantificationTheexistential quantificationP(x)is the propositionP(x)is true for some value(s) ofxin the universe of shall denote it as9xP(x):We can also read it as for somexP(x) or thereisanxsuch thatP(x) or there is at least onexsuch thatP(x) . The symbol9(notice that it is mirror image ofE) is called an existential 6:LetQ(x)denote the statement:4x2=1. What is the truth value of the quantification9xQ(x)when the universe of discourse forxis the set of real numbers? SinceQ(1=2)andQ( 1=2)are truepropositions, we conclude that9xQ(x)is true in the defined universe of discourse. But if we demandthat the universe of discourse forxis the set of integers, then9xQ(x)is false since there is no integersatisfying4x2=1.

10 Here, we observe that in order to prove that an existentially qualified statementP(x)is false, one must show that forallxin the universe of discourse the predicateP(x)is , observe that if the universe of discourse consists of a finite number of elements, sayx1;x2;:::;xn,then9xP(x) P(x1)_P(x2)_ _P(xn)since this disjunction is true if and only if at least one ofP(x1);P(x2);:::;P(xn)is now generalize De Morgan s laws to quantifications. We claim that:8xP(x) 9x:P(x);(1):9xP(x) 8x:P(x)(2)Let us try toprovethe first statement. Suppose that:8xP(x)is true. Hence,8xP(x)is false. But,as we seen before such a statement is false if there exists at least onexfor whichP(x)is false. Thisimplies that for suchxthe statement:P(x)is true, form which we infer that9x:P(x)is true. Wehave shown that if:8xP(x)is true, then9x:P(x)is true. In a similar manner, we conclude thatif:8xP(x)is false, then9x:P(x)is false. In conclusion, the pair of Propositions :8xP(x)and9x:P(x)have the same truth values, so they must be logically