Section1.1PropositionalLogic1CHAPTER1TheFoundations:LogicandProofsSECTION1.1PropositionalLogic2.Propositionsmusthaveclearlydefinedtruthvalues,soapropositionmustbeadeclarativesentencewithnofreevariables.a)Thisisnotaproposition;it’sacommand.b)Thisisnotaproposition;it’saquestion.c)Thisisapropositionthatisfalse,asanyonewhohasbeentoMaineknows.d)Thisisnotaproposition;itstruthvaluedependsonthevalueofx.e)Thisisapropositionthatisfalse.f)Thisisnotaproposition;itstruthvaluedependsonthevalueofn.4.a)JenniferandTejaarenotfriends.b)Therearenot13itemsinabaker’sdozen.(Alternatively:Thenumberofitemsinabaker’sdozenisnotequalto13.)c)Abbysentfewerthan101textmessagesyesterday.Alternatively,Abbysentatmost100textmessagesyesterday.Note:Thefirstprintingofthiseditionincorrectlyrenderedthisexercisewith“everyday”inplaceof“yesterday.”Thatmakesitamuchharderproblem,becausethedaysarequantified,andquantifiedpropositionsarenotdealtwithuntilalatersection.Itwouldbeincorrecttosaythatthenegationinthatcaseis“Abbysentatmost100textmessageseveryday.”Rather,acorrectnegationwouldbe“ThereexistsadayonwhichAbbysentatmost100textmessages.”Saying“Abbydidnotsendmorethan100textmessageseveryday”issomewhatambiguous—dowemean¬∀ordowemean∀¬?d)121isnotaperfectsquare.6.a)True,because288>256and288>128.b)True,becauseChas5MPresolutioncomparedtoB’s4MPresolution.Notethatonlyoneoftheseconditionsneedstobemetbecauseofthewordor.c)False,becauseitsresolutionisnothigher(allofthestatementswouldhavetobetruefortheconjunctiontobetrue).d)False,becausethehypothesisofthisconditionalstatementistrueandtheconclusionisfalse.e)False,becausethefirstpartofthisbiconditionalstatementisfalseandthesecondpartistrue.8.a)Ididnotbuyalotteryticketthisweek.b)EitherIboughtalotteryticketthisweekor[intheinclusivesense]IwonthemilliondollarjackpotonFriday.c)IfIboughtalotteryticketthisweek,thenIwonthemilliondollarjackpotonFriday.d)IboughtalotteryticketthisweekandIwonthemilliondollarjackpotonFriday.e)IboughtalotteryticketthisweekifandonlyifIwonthemilliondollarjackpotonFriday.f)IfIdidnotbuyalotteryticketthisweek,thenIdidnotwinthemilliondollarjackpotonFriday.
2Chapter1TheFoundations:LogicandProofsg)Ididnotbuyalotteryticketthisweek,andIdidnotwinthemilliondollarjackpotonFriday.h)EitherIdidnotbuyalotteryticketthisweek,orelseIdidbuyoneandwonthemilliondollarjackpotonFriday.10.a)Theelectionisnotdecided.b)Theelectionisdecided,orthevoteshavebeencounted.c)Theelectionisnotdecided,andthevoteshavebeencounted.d)Ifthevoteshavebeencounted,thentheelectionisdecided.e)Ifthevoteshavenotbeencounted,thentheelectionisnotdecided.f)Iftheelectionisnotdecided,thenthevoteshavenotbeencounted.g)Theelectionisdecidedifandonlyifthevoteshavebeencounted.h)Eitherthevoteshavenotbeencounted,orelsetheelectionisnotdecidedandthevoteshavebeencounted.Notethatwewereabletoincorporatetheparenthesesbyusingthewordseitherandelse.12.a)Ifyouhavetheflu,thenyoumissthefinalexam.b)Youdonotmissthefinalexamifandonlyifyoupassthecourse.c)Ifyoumissthefinalexam,thenyoudonotpassthecourse.d)Youhavetheflu,ormissthefinalexam,orpassthecourse.e)Itiseitherthecasethatifyouhavethefluthenyoudonotpassthecourseorthecasethatifyoumissthefinalexamthenyoudonotpassthecourse(orboth,itisunderstood).f)Eitheryouhavethefluandmissthefinalexam,oryoudonotmissthefinalexamanddopassthecourse.14.a)r∧¬qb)p∧q∧rc)r→pd)p∧¬q∧re)(p∧q)→rf)r↔(q∨p)16.a)ThisisT↔T,whichistrue.b)ThisisT↔F,whichisfalse.c)ThisisF↔F,whichistrue.d)ThisisF↔T,whichisfalse.18.a)ThisisF→F,whichistrue.b)ThisisF→F,whichistrue.c)ThisisT→F,whichisfalse.d)ThisisT→T,whichistrue.20.a)Theemployermakingthisrequestwouldbehappyiftheapplicantknewbothoftheselanguages,sothisisclearlyaninclusiveor.b)Therestaurantwouldprobablychargeextraifthedinerwantedbothoftheseitems,sothisisanexclusiveor.c)Ifapersonhappenedtohavebothformsofidentification,somuchthebetter,sothisisclearlyaninclusiveor.d)Thiscouldbearguedeitherway,buttheinclusiveinterpretationseemsmoreappropriate.Thisphrasemeansthatfacultymemberswhodonotpublishpapersinresearchjournalsarelikelytobefiredfromtheirjobsduringtheprobationaryperiod.Ontheotherhand,itmayhappenthattheywillbefiredeveniftheydopublish(forexample,iftheirteachingispoor).22.a)Thenecessaryconditionistheconclusion:Ifyougetpromoted,thenyouwashtheboss’scar.b)Ifthewindsarefromthesouth,thentherewillbeaspringthaw.
Section1.1PropositionalLogic3c)Thesufficientconditionisthehypothesis:Ifyouboughtthecomputerlessthanayearago,thenthewarrantyisgood.d)IfWillycheats,thenhegetscaught.e)The“onlyif”conditionistheconclusion:Ifyouaccessthewebsite,thenyoumustpayasubscriptionfee.f)Ifyouknowtherightpeople,thenyouwillbeelected.g)IfCarolisonaboat,thenshegetsseasick.24.a)IfIamtoremembertosendyoutheaddress,thenyouwillhavetosendmeane-mailmessage.(Thishasbeenslightlyrewordedsothatthetensesmakemoresense.)b)IfyouwerebornintheUnitedStates,thenyouareacitizenofthiscountry.c)Ifyoukeepyourtextbook,thenitwillbeausefulreferenceinyourfuturecourses.(Theword“then”isunderstoodinEnglish,evenifomitted.)d)Iftheirgoaltenderplayswell,thentheRedWingswillwintheStanleyCup.e)Ifyougetthejob,thenyouhadthebestcredentials.f)Ifthereisastorm,thenthebeacherodes.g)Ifyoulogontotheserver,thenyouhaveavalidpassword.h)Ifyoudonotbeginyourclimbtoolate,thenyouwillreachthesummit.26.a)YouwillgetanAinthiscourseifandonlyifyoulearnhowtosolvediscretemathematicsproblems.b)Youwillbeinformedifandonlyifyoureadthenewspapereveryday.(Itsoundsbetterinthisorder;itwouldbelogicallyequivalenttostatethisas“Youreadthenewspapereverydayifandonlyifyouwillbeinformed.”)c)Itrainsifandonlyifitisaweekendday.d)Youcanseethewizardifandonlyifheisnotin.28.a)Converse:IfIstayhome,thenitwillsnowtonight.Contrapositive:IfIdonotstayathome,thenitwillnotsnowtonight.Inverse:Ifitdoesnotsnowtonight,thenIwillnotstayhome.b)Converse:WheneverIgotothebeach,itisasunnysummerday.Contrapositive:WheneverIdonotgotothebeach,itisnotasunnysummerday.Inverse:Wheneveritisnotasunnyday,Idonotgotothebeach.c)Converse:IfIsleepuntilnoon,thenIstayeduplate.Contrapositive:IfIdonotsleepuntilnoon,thenIdidnotstayuplate.Inverse:IfIdon’tstayuplate,thenIdon’tsleepuntilnoon.30.Atruthtablewillneed2nrowsiftherearenvariables.a)22=4b)23=8c)26=64d)25=3232.Toconstructthetruthtableforacompoundproposition,weworkfromtheinsideout.Ineachcase,wewillshowtheintermediatesteps.Inpart(d),forexample,wefirstconstructthetruthtablesforp∧qandforp∨qandcombinethemtogetthetruthtablefor(p∧q)→(p∨q).Forparts(a)and(b)wehavethefollowingtable(columnthreeforpart(a),columnfourforpart(b)).p¬pp→¬pp↔¬pTFFFFTTFForparts(c)and(d)wehavethefollowingtable.pqp∨qp∧qp⊕(p∨q)(p∧q)→(p∨q)TTTTFTTFTFFTFTTFTTFFFFFT
4Chapter1TheFoundations:LogicandProofsForpart(e)wehavethefollowingtable.pq¬pq→¬pp↔q(q→¬p)↔(p↔q)TTFFTFTFFTFFFTTTFFFFTTTTForpart(f)wehavethefollowingtable.pq¬qp↔qp↔¬q(p↔q)⊕(p↔¬q)TTFTFTTFTFTTFTFFTTFFTTFT34.Forparts(a)and(b)wehavethefollowingtable(columntwoforpart(a),columnfourforpart(b)).pp⊕p¬pp⊕¬pTFFTFFTTForparts(c)and(d)wehavethefollowingtable(columnsfiveandsix).pq¬p¬qp⊕¬q¬p⊕¬qTTFFTFTFFTFTFTTFFTFFTTTFForparts(e)and(f)wehavethefollowingtable(columnsfiveandsix).Thistimewehaveomittedthecolumnexplicitlyshowingthenegationofq.Notethatthefirstisatautologyandthesecondisacontradiction(seedefinitionsinSection1.3).pqp⊕qp⊕¬q(p⊕q)∨(p⊕¬q)(p⊕q)∧(p⊕¬q)TTFTTFTFTFTFFTTFTFFFFTTF36.Forparts(a)and(b),wehavepqrp∨q(p∨q)∨r(p∨q)∧rTTTTTTTTFTTFTFTTTTTFFTTFFTTTTTFTFTTFFFTFTFFFFFFFForparts(c)and(d),wehave
Section1.1PropositionalLogic5pqrp∧q(p∧q)∨r(p∧q)∧rTTTTTTTTFTTFTFTFTFTFFFFFFTTFTFFTFFFFFFTFTFFFFFFFFinally,forparts(e)and(f)wehavepqr¬rp∨q(p∨q)∧¬rp∧q(p∧q)∨¬rTTTFTFTTTTFTTTTTTFTFTFFFTFFTTTFTFTTFTFFFFTFTTTFTFFTFFFFFFFFTFFFT38.Thistimethetruthtableneeds24=16rows.pqrsp→q(p→q)→r((p→q)→r)→sTTTTTTTTTTFTTFTTFTTFTTTFFTFTTFTTFTTTFTFFTFTFFTFTTTFFFFTFFTTTTTTFTTFTTFFTFTTFTFTFFTFTFFTTTTTFFTFTTFFFFTTFTFFFFTFT40.Thisstatementistrueifandonlyifallthreeclauses,p∨¬q,q∨¬r,andr∨¬paretrue.Supposep,q,andrarealltrue.Becauseeachclausehasanunnegatedvariable,eachclauseistrue.Similarly,ifp,q,andrareallfalse,thenbecauseeachclausehasanegatedvariable,eachclauseistrue.Ontheotherhand,ifoneofthevariablesistrueandtheothertwofalse,thentheclausecontainingthenegationofthatvariablewillbefalse,makingtheentireconjunctionfalse;andsimilarly,ifoneofthevariablesisfalseandtheothertwotrue,thentheclausecontainingthatvariableunnegatedwillbefalse,againmakingtheentireconjunctionfalse.42.a)Sincetheconditionistrue,thestatementisexecuted,soxisincrementedandnowhasthevalue2.b)Sincetheconditionisfalse,thestatementisnotexecuted,soxisnotincrementedandnowstillhasthevalue1.c)Sincetheconditionistrue,thestatementisexecuted,soxisincrementedandnowhasthevalue2.d)Sincetheconditionisfalse,thestatementisnotexecuted,soxisnotincrementedandnowstillhasthevalue1.
6Chapter1TheFoundations:LogicandProofse)Sincetheconditionistruewhenitisencountered(sincex=1),thestatementisexecuted,soxisincrementedandnowhasthevalue2.(Itisirrelevantthattheconditionisnowfalse.)44.a)11000∧(01011∨11011)=11000∧11011=11000b)(01111∧10101)∨01000=00101∨01000=01101c)(01010⊕11011)⊕01000=10001⊕01000=11001d)(11011∨01010)∧(10001∨11011)=11011∧11011=1101146.Thetruthvalueof“FredandJohnarehappy”ismin(0.8,0.4)=0.4.Thetruthvalueof“NeitherFrednorJohnishappy”ismin(0.2,0.6)=0.2,sincethisstatementmeans“Fredisnothappy,andJohnisnothappy,”andwecomputedthetruthvaluesofthetwopropositionsinthisconjunctioninExercise45.48.Thiscannotbeaproposition,becauseitcannothaveatruthvalue.Indeed,ifitweretrue,thenitwouldbetrulyassertingthatitisfalse,acontradiction;ontheotherhandifitwerefalse,thenitsassertionthatitisfalsemustbefalse,sothatitwouldbetrue—againacontradiction.Thusthisstringofletters,whileappearingtobeaproposition,isinfactmeaningless.50.No.Thisisaclassicalparadox.(Wewillusethemalepronouninwhatfollows,assumingthatwearetalkingaboutmalesshavingtheirbeardshere,andassumingthatallmenhavefacialhair.Ifwerestrictourselvestobeardsandallowfemalebarbers,thenthebarbercouldbefemalewithnocontradiction.)Ifsuchabarberexisted,whowouldshavethebarber?Ifthebarbershavedhimself,thenhewouldbeviolatingtherulethatheshavesonlythosepeoplewhodonotshavethemselves.Ontheotherhand,ifhedoesnotshavehimself,thentherulesaysthathemustshavehimself.Neitherispossible,sotherecanbenosuchbarber.SECTION1.2ApplicationsofPropositionalLogic2.Recallthatponlyifqmeansp→q.Inthiscase,ifyoucanseethemoviethenyoumusthavefulfilledoneofthetworequirements.Thereforethestatementism→(e∨p).Noticethatineverydaylifeonemightactuallysay“Youcanseethemovieifyoumeetoneoftheseconditions,”butlogicallythatisnotwhattherulesreallysay.4.Theconditionstatedhereisthatifyouusethenetwork,theneitheryoupaythefeeoryouareasubscriber.Thereforethepropositioninsymbolsisw→(d∨s).6.ThisissimilartoExercise2:u→(b32∧g1∧r1∧h16)∨(b64∧g2∧r2∧h32).8.a)“But”means“and”:r∧¬p.b)“Whenever”means“if”:(r∧p)→q.c)Accessbeingdeniedisthenegationofq,sowehave¬r→¬q.d)Thehypothesisisaconjunction:(¬p∧r)→q.10.Wewritethesesymbolically:u→¬a,a→s,¬s→¬u.Notethatwecanmakealltheconclusiontruebymakingafalse,strue,andufalse.Thereforeiftheuserscannotaccessthefilesystem,theycansavenewfiles,andthesystemisnotbeingupgraded,thenalltheconditionalstatementsaretrue.Thusthesystemisconsistent.
Section1.2ApplicationsofPropositionalLogic712.Thissystemisconsistent.WeuseL,Q,N,andBtostandforthebasicpropositionshere,“Thefilesystemislocked,”“Newmessageswillbequeued,”“Thesystemisfunctioningnormally,”and“Newmessageswillbesenttothemessagebuffer,”respectively.Thenthegivenspecificationsare¬L→Q,¬L↔N,¬Q→B,¬L→B,and¬B.Ifwewantconsistency,thenwehadbetterhaveBfalseinorderthat¬Bbetrue.ThisrequiresthatbothLandQbetrue,bythetwoconditionalstatementsthathaveBastheirconsequence.ThefirstconditionalstatementthereforeisoftheformF→T,whichistrue.Finally,thebiconditional¬L↔NcanbesatisfiedbytakingNtobefalse.Thusthissetofspecificationsisconsistent.Notethatthereisjustthisonesatisfyingtruthassignment.14.ThisissimilartoExample6,aboutuniversitiesinNewMexico.TosearchforhikinginWestVirginia,wecouldenterWESTANDVIRGINIAANDHIKING.Ifweenter(VIRGINIAANDHIKING)NOTWEST,thenwe’llgetwebsitesabouthikinginVirginiabutnotinWestVirginia,exceptforsitesthathappentousetheword“west”inadifferentcontext(e.g.,“Followthestreamwestuntilyoucometoaclearing”).16.a)Iftheexplorer(awoman,sothatourpronounswillnotgetconfusedhere—thecannibalswillbemale)encountersatruth-teller,thenhewillhonestlyanswer“no”toherquestion.Ifsheencountersaliar,thenthehonestanswertoherquestionis“yes,”sohewilllieandanswer“no.”Thuseverybodywillanswer“no”tothequestion,andtheexplorerwillhavenowaytodeterminewhichtypeofcannibalsheisspeakingto.b)Thereareseveralpossiblecorrectanswers.Oneisthefollowingquestion:“IfIweretoaskyouifyoualwaystoldthetruth,wouldyousaythatyoudid?”Thenifthecannibalisatruthteller,hewillansweryes(truthfully),whileifheisaliar,then,sinceinfacthewouldhavesaidthathedidtellthetruthifquestioned,hewillnowlieandanswerno.18.Wewilltranslatetheseconditionsintostatementsinsymboliclogic,usingj,s,andkforthepropositionsthatJasmine,Samir,andKantiattend,respectively.Thefirststatementisj→¬s.Thesecondstatementiss→k.Thelaststatementis¬k∨j,because“unless”means“or.”(Wecouldalsotranslatethisask→j.FromthecommentsfollowingDefinition5inthetext,weknowthatp→qisequivalentto“qunless¬p.Inthiscasepis¬jandqis¬k.)First,supposethatsistrue.Thenthesecondstatementtellsusthatkisalsotrue,andthenthelaststatementforcesjtobetrue.Butnowthefirststatementforcesstobefalse.Soweconcludethatsmustbefalse;Samircannotattend.Ontheotherhand,ifsisfalse,thenthefirsttwostatementsareautomaticallytrue,notmatterwhatthetruthvaluesofkandjare.Ifwelookatthelaststatement,weseethatitwillbetrueaslongasitisnotthecasethatkistrueandjisfalse.SotheonlycombinationsoffriendsthatmakeeverybodyhappyareJasmineandKanti,orJasminealone(ornoone!).20.IfAisaknight,thenhisstatementthatbothofthemareknightsistrue,andbothwillbetellingthetruth.Butthatisimpossible,becauseBisassertingotherwise(thatAisaknave).IfAisaknave,thenB’sassertionistrue,sohemustbeaknight,andA’sassertionisfalse,asitshouldbe.ThusweconcludethatAisaknaveandBisaknight.22.Wecandrawnoconclusions.Aknightwilldeclarehimselftobeaknight,tellingthetruth.Aknavewilllieandassertthatheisaknight.Sinceeveryonewillsay“Iamaknight,”wecandeterminenothing.24.SupposethatAistheknight.Thenbecausehetoldthetruth,CistheknaveandthereforeBisthespy.InthiscasebothBandCarelying,whichisconsistentwiththeiridentities.Toseethatthisistheonlysolution,firstnotethatBcannotbetheknight,becauseofhisclaimthatAistheknight(whichwouldthenhavetobealie).Similarly,Ccannotbetheknight,becausehewouldbelyingwhenstatingthatheisthespy.26.Thereisnosolution,becauseneitheraknightnoraknavewouldeverclaimtobetheknave.
8Chapter1TheFoundations:LogicandProofs28.SupposethatAistheknight.ThenB’sstatementistrue,sohemustbethespy,whichmeansthatC’sstatementisalsotrue,butthatisimpossiblebecauseCwouldhavetobetheknave.ThereforeAisnottheknight.NextsupposethatBistheknight.HistruestatementforcesAtobethespy,whichinturnforcesCtobetheknave;oncemorethatisimpossiblebecauseCsaidsomethingtrue.TheonlyotherpossibilityisthatCistheknight,whichthenforcesBtobethespyandAtheknave.Thisworksoutfine,becauseAislyingandBistellingthetruth.30.NeitherAnorBcanbetheknave,becausetheknavecannotmakethetruthfulstatementthatheisnotthespy.ThereforeCistheknave,andconsequentlyAisnotthespy.ItfollowsthatAistheknightandBisthespy.Thisworksoutfine,becauseAandBarethenbothtellingthetruthandCislying.32.a)Welookatthethreepossibilitiesofwhotheinnocentmenmightbe.IfSmithandJonesareinnocent(andthereforetellingthetruth),thenwegetanimmediatecontradiction,sinceSmithsaidthatJoneswasafriendofCooper,butJonessaidthathedidnotevenknowCooper.IfJonesandWilliamsaretheinnocenttruth-tellers,thenweagaingetacontradiction,sinceJonessaysthathedidnotknowCooperandwasoutoftown,butWilliamssayshesawJoneswithCooper(presumablyintown,andpresumablyifwewaswithhim,thenheknewhim).ThereforeitmustbethecasethatSmithandWilliamsaretellingthetruth.Theirstatementsdonotcontradicteachother.BasedonWilliams’statement,weknowthatJonesislying,sincehesaidthathedidnotknowCooperwheninfacthewaswithhim.ThereforeJonesisthemurderer.b)Thisisjustlikepart(a),exceptthatwearenottoldaheadoftimethatoneofthemenisguilty.Cannoneofthembeguilty?Ifso,thentheyarealltellingthetruth,butthisisimpossible,becauseaswejustsaw,someofthestatementsarecontradictory.Canmorethanoneofthembeguilty?If,forexample,theyareallguilty,thentheirstatementsgiveusnoinformation.Sothatiscertainlypossible.34.Thisinformationisenoughtodeterminetheentiresystem.Leteachletterstandforthestatementthatthepersonwhosenamebeginswiththatletterischatting.Thenthegiveninformationcanbeexpressedsymbolicallyasfollows:¬K→H,R→¬V,¬R→V,A→R,V→K,K→V,H→A,H→K.Notethatwewereabletoconvertallofthesestatementsintoconditionalstatements.Inwhatfollowswewillsometimesmakeuseofthecontrapositivesoftheseconditionalstatementsaswell.FirstsupposethatHistrue.ThenitfollowsthatAandKaretrue,whenceitfollowsthatRandVaretrue.ButRimpliesthatVisfalse,sowegetacontradiction.ThereforeHmustbefalse.FromthisitfollowsthatKistrue;whenceVistrue,andthereforeRisfalse,asisA.Wecannowcheckthatthisassignmentleadstoatruevalueforeachconditionalstatement.SoweconcludethatKevinandVijayarechattingbutHeather,Randy,andAbbyarenot.36.NotethatDiana’sstatementismerelythatshedidn’tdoit.a)Johndidit.Therearefourcasestoconsider.IfAliceisthesoletruth-teller,thenCarlosdidit;butthismeansthatJohnistellingthetruth,acontradiction.IfJohnisthesoletruth-teller,thenDianamustbelying,soshedidit,butthenCarlosistellingthetruth,acontradiction.IfCarlosisthesoletruth-teller,thenDianadidit,butthatmakesJohntruthful,againacontradiction.SotheonlypossibilityisthatDianaisthesoletruth-teller.ThismeansthatJohnislyingwhenhedeniedit,sohedidit.NotethatinthiscasebothAliceandCarlosareindeedlying.b)Againtherearefourcasestoconsider.SinceCarlosandDianaaremakingcontradictorystatements,theliarmustbeoneofthem(wecouldhaveusedthisapproachinpart(a)aswell).ThereforeAliceistellingthetruth,soCarlosdidit.NotethatJohnandDianaaretellingthetruthaswellhere,anditisCarloswhoislying.38.Thisisoftengivenasanexerciseinconstraintprogramming,anditisdifficulttosolvebyhand.Thefollowing