Logic Puzzles Miran Kim Ben Seelbinder Matthew Sgambati What are logic puzzles A puzzle deriving from the mathematics field of deduction Produced by Charles Lutwidge Dodgson A puzzle that can be solved using logical reasoning It helps work with rules of logic and or xor etc Programs that carry out logical reasoning use these puzzles to illustrate capabilities The Master of Logic Puzzles High School dropout who got a Ph D in logic at Princeton Wrote many books on logic puzzles such as Alice in Puzzle Land and To Mock a Mockingbird Most famous for his Knights and Knaves Problem Raymond Smullyan Knights and Knaves I don t lie Neither do I Encounter two people Knights always tell the truth Knaves always lie Figure out whether each person is a knight or a knave from their statements Example A says At least one of us is a knave and B says nothing Knight and Knave Problem A says At least one of us is a knave and B says nothing P x x is a knight P x x is a knave Suppose A is a knave P A T What A says must be false P A P B F Check P A P B T P B T Impossible A is a knight and what A says must be true P A P A P B P B Answer A is a knight B is a knave Knight and Knave Problem A says The two of us are both knight and B says A is a knave P x x is a knight P x x is a knave Suppose A is a knight P A T What A says must be true P A P B T P B T However B says P A T P A F Impossibl e Answer A is a knave A is a knave and what A says is false B is a P A T knight P A P B F P B F B is a knight because his statement A is a knave is true Knight and Knave Problem A says I am a knave or B is a knight and B says nothing A is a knight B is a knight Both A and B say I am a knight Cannot determine the answer A says We are both knaves and B says nothing A is a knave B is a knight A says B is a knight and B says The two of us are opposite types A is a knave B is a knave Knight Knave and Spy Problem from Alice in Puzzle Land Added rule Spy can lie or tell the truth There is one spy one knight and one knave A says that C is a knave B says that A is a knight C says I a m the spy Which one is the spy which one is the knight which one is th e knave Knight x x is a knight Knave x x is a knave Spy x x is a spy From C s statement C can t be a knight because a knight nev er lie about his identity Therefore C is either a knave or a spy Knight Knave and Spy Problem cont from Alice in Puzzle Land Suppose C is a spy Knight C Knave C Spy C T Knave C T simplification Knave C F What A says is false so A is knave There is one spy one knight and one knave A says that C is a knave B says that A is a knight C says I am the spy Knight A Knave A Spy A T Knight A T simplification B must be a knight and what B says must be true Impossible Check C isn t a spy Knight A T Knight A F Answer C is a knave A is telling the truth so A is a knight B is a spy Multiple Choice Help You encounter a problem on an exam with only answer choices the q uestion has been omitted Here are the answers A B C Answer A Answer A or Answer B Answer B or Answer C We may determine the correct answer using discrete math R x Answer x is right The correct answer must be the only one Suppose A correct R A True we have the following answers R A R A R B R B R C T True T F True False F F False Knowing this may only have one correct answer we can determine th at this answer is not right Multiple Choice Help Suppose R B True R A R A R B R B R C F False F T True T F True False Suppose R C True R A R A R B R B R C F False F F True False F T True Comparing each solution we know that the correct answer must be C We didn t have to look at the question False Statement Which statement is false assuming only one is false A Statement D is true B Statement A is false C Statement B is false D Statement C is true When statement B is true it results in statement A being false which results in statement D being false also This results in more than one false statement so statement B is the false one Conclusion What are logic puzzles Who started logic puzzles The master of logic puzzles Knights and Knaves Method of thinking for logic puzzles Questions Pop Quiz 1 The next question with the same answer as this one is A 2 B 3 C 4 D 5 2 The first question with answer C is A 1 B 2 C 3 D 4 3 The last question with answer A is A 5 B 6 C 7 D 8 4 The number of questions with answer D is A 1 B 2 C 3 D 4 5 The answer occurring the most is if tied first alphabetically A A B B C C D D 6 The first question with the same answer as the question following it is A 2 B 3 C 4 D 5 7 The answer occurring the least is if tied last alphabetically A A B B C C D D 8 The highest possible score on this test is A 5 B 7 C 6 D 8
View Full Document
Unlocking...