Logic, Proofs - Northwestern University

1 CHAPTER1 Logic, a declarative sentencethatis eithertrueor false(butnotboth).For instance,thefollowingarepropositions: Parisis in France (true), Londonis in Denmark (false), 2<4 (true), 4= 7 (false) .However thefollowingarenotpropositions: whatisyourname? (thisis a question), doyourhomework (thisis acommand), thissentenceis false (neithertruenorfalse), xis aneven number (itdependsonwhatxrepresents), Socrates (itis notevena sentence).Thetruthor falsehood of a propositionis , Themainonesarethefollowing(pandqrepresen t givenpropositions):NameRepresentedMeanin gNegation p notp Conjunctionp q pandq Disjunctionp q porq(orboth) Exclusive Orp q eitherporq, butnotboth Implicationp q ifpthenq Biconditionalp q pif andonlyifq Thetruthvalueof a compoundpropositiondependsonlyonthevalue of for false andT for true ,wecansummarizethemeaningof theconnectives in pp qp qp qp qp qTTFTTFTTTFFFTTFFFTTFTTTFFFTFFFTTN otethat represents anon-exclusiveor, ,p qis truewhenany ofp,qis represents anexclusiveor, ,p qis trueonlywhenexactlyoneofpandqis , Contradiction, propositionis saidto be atautologyif itstruthvalueis Tforany assignment of truthvaluesto.

2 Thepropositionp pis a A propositionis saidto be acontradictionif itstruthvalueis Fforany assignment of truthvaluesto :Thepropositionp pis a A propositionthatis neithera tautologynora pp pp propositionof theform ifpthenq or pimpliesq , represented p q iscalledaconditionalproposition. For instance: ifJohnis fromChicagothenJohnis fromIllinois .Thepropositionpis calledhypothesisorantecedent, andthepropositionqis qistruealways exceptwhenpis trueandqis ,thefollowingsentencesaretrue: if2<4 thenParisis in France (true true), ifLondonis in Denmarkthen2<4 (false true), if4 = 7 thenLondonis in Denmark (false false).However thefollowingoneisfalse: if2<4 thenLondonis in Denmark (true false).

3 In might seemstrangethat p q is consideredtruewhenpisfalse,regardlessoft hetruthvalueofq. Thiswillbecomeclearerwhenwe studypredicatessuchas ifxis a multipleof 4 thenxis a multipleof 2 .Thatimplicationis obviouslytrue,althoughfortheparticularca sex= 3 it becomes if3 is a multipleof 4 then3is a multipleof 2 .Thepropositionp q, read pif andonlyifq ,is calledbicon-ditional. It is truepreciselywhenpandqhave thesametruthvalue, ,theyarebothtrueor qand p qhavethesametruthvalues:pq p p qp qTTFTTTFFFFFTTTTFFTTTW hentwo compoundpropositionshave thesametruthvaluesnomatterwhattruthvalue theirconstituent propositionshave, theyarecalledlogically equivalent. For instancep qand p qarelogicallyequivalent, andwe writeit:p q p qNotethatthattwo propositionsAandBarelogicallyequivalentp reciselywhenA Bis a : DeMorgan : (p q) p q (p q) p qWe cancheckit by p qp q (p q) p qp q (p q) p qTTFFTFFTFFTFFTTFFFTTFTTFTFFFTTFFTTFTTFT TE xample: Thefollowingpropositionsarelogicallyequi valent:p q (p q) (q p)Again,thiscanbecheckedwiththetruthtabl es:pqp qq p(p q) (q p)p qTTTTTTTFFTFFFTTFFFFFTTTTE xercise: Check thefollowinglogicalequivalences: (p q) p qp q q p (p q) p , aconditionalpropositionp qis thepropositionq p.

4 Aswe have seen,thebi-conditionalpropositionis equivalent to theconjunctionof a q (p q) (q p)So,forinstance,sayingthat Johnismarriedif andonlyif hehasaspouse isthesameas saying ifJohnis marriedthenhehasa spouse and ifhehasa spousethenheis married .Notethattheconverseisnotequivalent to thegivenconditionalproposition,forinstan ce ifJohnis fromChicagothenJohnis fromIllinois is true,buttheconverse ifJohnisfromIllinoisthenJohnisfromChicag o may a conditionalpropositionp qis thepropo-sition q p. Theyarelogicallyequivalent. Forinstancethecon-trapositive of ifJohnis fromChicagothenJohnis fromIllinois is ifJohnis notfromIllinoisthenJohnis notfromChicago.