关闭

关闭

关闭

封号提示

内容

首页 CSCI103_05c_KnightsKnaves(print)4.pdf

CSCI103_05c_KnightsKnaves(print)4.pdf

CSCI103_05c_KnightsKnaves(print…

喬@24h OL 2012-02-28 评分 0 浏览量 0 0 0 0 暂无简介 简介 举报

简介:本文档为《CSCI103_05c_KnightsKnaves(print)4pdf》,可适用于IT/计算机领域,主题内容包含CSCIWeek :Knights and KnavesKnights and Knaves•Every inhabitant of a mythi符等。

CSCIWeek :Knights and KnavesKnights and Knaves•Every inhabitant of a mythical island is either a knight or a knave•Knights always tell the truthKlli•Knaves always lie•This forms the basis of several problems in logicProblem •It is rumoured there is gold on the island•A native tells you “The statement ‘there is gold on the island’ and the statement ‘I am a knight’areeitherbothtrueorbothfalse”knight are either both true or both false–Can you tell if the native is a knight–Can you tell if there is gold on the islandProblem •You come across two natives•You ask each if the other is a knight–Do you get the same answer from both of themProblem •There are three natives, A, B and C•A says “B and C are of the same type”–What can we conclude about the number of knights presentProblem •There are three natives, A, B and C•A says “B and C are of the same type”–What question can we ask C to find out if A is telling the truthProblem •There are two natives, A and B–What question should you ask A to determine if B is a knightProblem •There are two natives, A and B–What question should you ask A to determine whether A and B are of the same typeProblem •You come to a fork in the road•There is a restaurant down one of the two branches•ThereisanativeattheforkThere is a native at the fork–What question do you ask to find out if the restaurant lies down the left forkBrute Force •It is tempting to try to solve these problems by looking at all possible cases•The problems here are:–the number of cases rapidly becomes too large–the answer is often still not  clear•Perhaps there is a better technique•One approach is Calculational LogicCalculational Logic•The basis of calculational logic is to calculate with Boolean expressions •These expression, called propositions, are eithertrueoffalseeither true of falseKnights and Knaves•If A is a native of the island the statement “A is a knight” is either true or false•So, the statement is a proposition•LetArepresenttheproposition“Aisaknight”Let Arepresent the proposition A is a knight•Suppose A make some statement S•The truth or falsity of this statement is the same as the truth or falsity of A–A= SKnights and Knaves•So if A says “there restaurant is to the left” then A= L•In other words either A is a knight and the restaurantistotheleftorAisnotaknightandrestaurant is to the left or A is not a knight and the restaurant is not to the left•If A says “I am a knight” we conclude that A= Awhich tells us nothing!–Everyone claims to be a knightKnights and Knaves•If we ask A a YesNo  question, Q, the response will be the truth value of A= Q•That is, if the response is “yes”, either A is a knightandtheanswertoQreallyisyesorAisknight and the answer to Q really is yes or A is a knave and the answer is really no•Otherwise the response will be “no”Knights and Knaves•Let's say we have two natives, A and B•A says “B is a knight”–What can we deducefhkh•If Arepresents the proposition A is a knight and Brepresents the proposition B is a knight:–A= B•That is, A and B are of the same typeBoolean Equality•The Boolean equality relation satisfies a number of properties:–Reflexive: p= pSymmetric:(p=q)=(q=p)–Symmetric: (p= q) = (q= p)–Transitive: if p= qand q= rthan p= r–Substitution of equals for equals: if p= qand fis a Boolean function then f(p) = f(q)–Associative: (p= (q= r)) = ((p= q) = r)Problem •It is rumoured there is gold on the island•A native tells you “The statement ‘there is gold on the island’ and the statement ‘I am a knight’areeitherbothtrueorbothfalse”knight are either both true or both false–Can you tell if the native is a knight–Can you tell if there is gold on the islandProblem •If A says “The statement ‘there is gold on the island’ and the statement ‘I am a knight’ are either both true or both false” he is asserting A= Gwhere A is the assertion Ais a knight and Gthe assertion there isgoldontheIslandis gold on the Island•Any assertion by a native has the same truth value as Aso:–A= (A= G)–(A= A) = G–true=GProblem •From this we can conclude that there is gold on the island, even though we have no idea if the native is a knight or a knaveProblem •You come across two natives•You ask each if the other is a knight–Do you get the same answer from both of themProblem •A will answer “yes” if he is a knight and so is B or if he is a knave and so is B•In other words:–Q= (A= B)•Using the symmetry property:–(A= B) = (B= A)–Q= (B= A)•So B’s answer will be the same as A’sProblem •There are three natives, A, B and C•A says “B and C are of the same type”–What can we conclude about the number of knights presentProblem •A says B= Cso: –A= (B= C)•So–A is a knight and so are B and Cor–A is a knight and B and C are knavesor–A is a knave and one of B and C is a knight•There is an odd number of knightsProblem •There are three natives, A, B and C•A says “B and C are of the same type”–What question can we ask C to find out if A is telling the truthProblem •Let Q be the unknown question we must ask, with truth value Q•Let A, Band Cdenote the the propositions A, B, C is a knight•The response we want is Aso:–(Q=C)=A–(Q= C) = A•Which we regroup to give:–Q= ( C= A)•But A= (B= C) so substituting for A we get:–Q= (C= (B= C) )•Which simplifies (after rearrangement) to:–Q= BProblem •There are two natives, A and B–What question should you ask A to determine if B is a knightProblem •We want a question, Q, whose answer, when asked of B, is the type of B–(Q= A) = B•Reorganising:–Q= (A= B)•In other words “Is B of the same type as you”Problem •There are two natives, A and B–What question should you ask A to determine whether A and B are of the same typeProblem •We want a question, Q, which, when asked of A, determines if A and B are of the same type:–(Q= A) = (A= B)•Regrouping and simplifying:–Q= (A= (A= B))–Q= ((A= A) = B)–Q= (true= B)•In other words “Is B a knight”Problem •You come to a fork in the road•There is a restaurant down one of the two branches•ThereisanativeattheforkThere is a native at the fork–What question do you ask to find out if the restaurant lies down the left forkProblem •Following the same rules as before:–(Q= A) = L•Which we can rearrange as:–Q= (A= L) •So our question is “Is the truth value of the statement ‘you are a knight’ the same as the truth value of ‘the restaurant lies down the left fork’”•In simpler English, “If you were a knight would you say the restaurant lies down the left fork”

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +1积分

资料评分:

/8
1下载券 下载 加入VIP, 送下载券

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部

举报
资料