Logic PuzzlesWhat are logic puzzles?The Master of Logic PuzzlesKnights and KnavesKnight and Knave ProblemSlide 6Slide 7Knight, Knave and Spy Problem from Alice in Puzzle-LandKnight, Knave and Spy Problem cont. from Alice in Puzzle-LandMultiple Choice HelpSlide 11False StatementConclusionPop Quiz!Logic PuzzlesMiran KimBen SeelbinderMatthew SgambatiWhat are logic puzzles?•“A puzzle deriving from the mathematicsfield of deduction”•Produced by Charles Lutwidge Dodgson•A puzzle that can be solved using logicalreasoning•It helps work with rules of logic (and, or, xor, etc.)•Programs that carry out logical reasoninguse these puzzles to illustrate capabilitiesThe Master of Logic Puzzles•High School dropout who gota 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 “Knightsand Knaves Problem”Raymond SmullyanKnights and Knaves•Encounter two people•Knights always tell the truth•Knaves always lie•Figure out whether each person is a knightor a knave from their statements•Example: A says, “At least one of us is aknave” and B says nothingI don’t lie!Neitherdo I!Knight and Knave ProblemA 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) ⇔ TWhat A says must be false¬P(A) ∨ ¬P(B) ⇔ FCheck:¬P(A) ∨ ¬P(B) ⇔ T ∨ ¬P(B) ⇔ TA is a knight and what A says must be true.P(A) ¬P(A) ∨ ¬P(B)∴¬P(B)Impossible Answer:A is a knight.B is a knave.Knight and Knave ProblemA 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) ⇔ TWhat A says must be trueP(A)∧P(B) ⇔ TP(B) ⇔ THowever, B says ¬P(A) ⇔ TP(A) ⇔ FA is a knave and what A says is false.¬P(A) ⇔ TP(A)∧P(B) ⇔ F ∧P(B) ⇔ F B is a knight because his statement (A is a knave) is true. ImpossibleAnswer:A is a knave.B is a knight.Knight and Knave ProblemA says, “I am a knave or B is a knight” and B says nothing.–A is a knight–B is a knightBoth A and B say, “I am a knight.”–Cannot determine the answerA says, “We are both knaves” and B says nothing.–A is a knave–B is a knightA says, “B is a knight” and B says, “The two of us are opposite types.”–A is a knave–B is a knaveKnight, Knave and Spy Problemfrom Alice in Puzzle-LandAdded 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 am the spy.”Which one is the spy, which one is the knight, which one is the knave?Knight(x): x is a knightKnave(x): x is a knaveSpy(x): x is a spyFrom C’s statement, C can’t be a knight because a knight never lie about his identity.Therefore, C is either a knave or a spy.Knight, Knave and Spy Problem cont.from Alice in Puzzle-LandSuppose C is a spy.¬Knight(C) ∧ ¬Knave(C) ∧ Spy(C) ⇔ T¬Knave(C) ⇔ T (simplification)Knave(C) ⇔FWhat A says is false, so A is knave. ¬Knight(A) ∧ Knave(A) ∧ ¬ Spy(A) ⇔ T¬Knight(A) ⇔ T (simplification)B must be a knight, and what B says must be true.Check: Knight(A) ⇔ T¬Knight(A) ⇔ FImpossible∴ C isn’t a spy.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.”Answer:C is a knave.A is telling the truth, so A is a knight.B is a spy.Multiple Choice HelpYou encounter a problem on an exam with only answer choices, the question has been omitted. Here are the answers:A. Answer AB. Answer A or Answer BC. Answer B or Answer CWe may determine the correct answer using discrete math•R(x): Answer x is right•The correct answer must be the only oneSuppose A correct ( R(A) = True ), we have the following answers:•R(A) ⇔ T ⇔ True •R(A) ∨ ¬R(B) ⇔ T ∨ F ⇔ True •¬R(B) ∨ ¬R(C) ⇔ F ∨ F ⇔ FalseKnowing this may only have one correct answer, we can determine that this answer is not right.FalseMultiple Choice HelpSuppose R(B) = True•¬R(A) ⇔ F ⇔ False •¬R(A) ∨ R(B) ⇔ F ∨ T ⇔ True •R(B) ∨ ¬R(C) ⇔ T ∨ F ⇔ True Suppose R(C) = True•¬R(A) ⇔ F ⇔ False •¬R(A) ∨ ¬R(B) ⇔ F ∨ F ⇔ False •¬R(B) ∨ R(C) ⇔ F ∨ T ⇔ TrueComparing each solution, we know that the correct answer must be C. We didn’t have to look at the question!True FalseFalse StatementWhich statement is false (assuming only one is false)?A. Statement D is trueB. Statement A is falseC. Statement B is falseD. 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 puzzlesQuestions?Pop Quiz!1. The next question with the same answer as this one is: (A) 2AAA (B) 3AAA (C) 4AAA (D) 52. The first question with answer C is: (A) 1AAA (B) 2AAA (C) 3AAA (D) 43. The last question with answer A is: (A) 5AAA (B) 6AAA (C) 7AAA (D) 84. The number of questions with answer D is: (A) 1AAA (B) 2AAA (C) 3AAA (D) 45. The answer occurring the most is (if tied, first alphabetically): (A) AAAA (B) BAAA (C) CAAA (D) D6. The first question with the same answer as the question following it is: (A) 2AAA (B) 3AAA (C) 4AAA (D) 57. The answer occurring the least is (if tied, last alphabetically): (A) AAAA (B) BAAA (C) CAAA (D) D8. The highest possible score on this test is:(A) 5AAA (B) 7AAA (C) 6AAA (D)
View Full Document
Unlocking...