CSCI103_05c_KnightsKnaves(print)6.pdf

《CSCI103_05c_KnightsKnaves(print)6.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、KnightsandKnaves•Everyinhabitantofamythicalislandiseitheraknightoraknave.CSCI103•Knightsalwaystellthetruth.•Knavesalwayslie.Week5:KnightsandKnaves•Thisformsthebasisofseveralproblemsinlogic.Problem1Problem2•Itisrumouredthereisgoldontheisland.•Youcomeacrosstwonatives.•Anativetellsyou“Thesta

2、tement‘thereis•Youaskeachiftheotherisaknight.goldontheisland’andthestatement‘Iama–Doyougetthesameanswerfrombothofthem?knight’areeitherbothtrueorbothfalse”.–Canyoutellifthenativeisaknight?–Canyoutellifthereisgoldontheisland?Problem3Problem4•Therearethreenatives,A,BandC.•Therearethreenative

3、s,A,BandC.•Asays“BandCareofthesametype”.•Asays“BandCareofthesametype”.–Whatcanweconcludeaboutthenumberofknights–WhatquestioncanweaskCtofindoutifAistellingthepresent?truth?1Problem5Problem6•Therearetwonatives,AandB.•Therearetwonatives,AandB.–WhatquestionshouldyouaskAtodetermineifBisa–Whatq

4、uestionshouldyouaskAtodeterminewhetherAknight?andBareofthesametype?Problem7BruteForce•Youcometoaforkintheroad.•Itistemptingtotrytosolvetheseproblemsby•Thereisarestaurantdownoneofthetwolookingatallpossiblecases.branches.•Theproblemshereare:•Thereisanativeatthefork.–thenumberofcasesrapidlyb

5、ecomestoolarge–Whatquestiondoyouasktofindoutiftherestaurantlies–theanswerisoftenstillnotcleardowntheleftfork?•Perhapsthereisabettertechnique.•OneapproachisCalculationalLogicCalculationalLogicKnightsandKnaves•Thebasisofcalculationallogicistocalculate•IfAisanativeoftheislandthestatement“Ais

6、withBooleanexpressions.aknight”iseithertrueorfalse.•Theseexpression,calledpropositions,are•So,thestatementisaproposition.eithertrueoffalse.•LetArepresenttheproposition“Aisaknight”.•SupposeAmakesomestatementS.•ThetruthorfalsityofthisstatementisthesameasthetruthorfalsityofA.–A=S2KnightsandK

7、navesKnightsandKnaves•SoifAsays“thererestaurantistotheleft”•IfweaskAaYes/Noquestion,Q,thethenA=L.responsewillbethetruthvalueofA=Q.•InotherwordseitherAisaknightandthe•Thatis,iftheresponseis“yes”,eitherAisarestaurantistotheleftorAisnotaknightandknightandtheanswertoQre