CSCI103_05c_KnightsKnaves(print)4

1 CSCI103 Week 5:Knights and Knaves Knights and Knaves • Every inhabitant of a mythical island is either a  knight or a knave. • Knights always tell the truth. K l li• Knaves always lie. • This forms the basis of several problems in  logic. Problem 1 • 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’ are either both true or both false”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 island? Problem 2 • You come across two natives. • You ask each if the other is a knight. – Do you get the same answer from both of them? 2 Problem 3 • 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  present? Problem 4 • 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  truth? Problem 5 • There are two natives, A and B. – What question should you ask A to determine if B is a  knight? Problem 6 • There are two natives, A and B. – What question should you ask A to determine whether A  and B are of the same type? 3 Problem 7 • You come to a fork in the road. • There is a restaurant down one of the two  branches. • There is a native at the fork.There is a native at the fork. – What question do you ask to find out if the restaurant lies  down the left fork? Brute 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 Logic Calculational Logic • The basis of calculational logic is to calculate  with Boolean expressions.  • These expression, called propositions, are  either true of falseeither true of false. Knights 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. • Let A represent the proposition “A is a knight”Let A represent 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 = S 4 Knights 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  restaurant is to the left or A is not a knight andrestaurant 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 =  A which tells us nothing! – Everyone claims to be a knight. Knights and Knaves • If we ask A a Yes/No  question, Q, the  response will be the truth value of A = Q. • That is, if the response is “yes”, either A is a  knight and the answer to Q really is yes or A isknight 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 deduce? f h k h• If A represents the proposition A is a knight  and B represents the proposition B is a knight: – A = B. • That is, A and B are of the same type. Boolean Equality • The Boolean equality relation satisfies a  number of properties: – Reflexive: p = p Symmetric: (p = q) = (q = p)– Symmetric: (p = q) = (q = p). – Transitive: if p = q and q = r than p = r. – Substitution of equals for equals: if p = q and f is a  Boolean function then f(p) = f(q). – Associative: (p = (q = r)) = ((p = q) = r) 5 Problem 1 • 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’ are either both true or both false”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 island? Problem 1 • 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 = G where A is  the assertion A is a knight and G the assertion there  is gold on the Islandis gold on the Island. • Any assertion by a native has the same truth value as  A so: – A = (A = G) – (A = A) = G – true = G Problem 1 • 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 knave. Problem 2 • You come across two natives. • You ask each if the other is a knight. – Do you get the same answer from both of them? 6 Problem 2 • 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’s. Problem 3 • 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  present? Problem 3 • A says B = C so:  – A = (B = C) • So – A is a knight and so are B and C or – A is a knight and B and C are knaves or – A is a knave and one of B and C is a knight • There is an odd number of knights. Problem 4 • 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  truth? 7 Problem 4 • Let Q be the unknown question we must ask, with truth  value Q. • Let A, B and C denote the the propositions A, B, C is a  knight. • The response we want is A so: – (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 = B Problem 5 • There are two natives, A and B. – What question should you ask A to determine if B is a  knight? Problem 5 • 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 6 • There are two natives, A and B. – What question should you ask A to determine whether A  and B are of the same type? 8 Problem 6 • 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 7 • You come to a fork in the road. • There is a restaurant down one of the two  branches. • There is a native at the fork.There is a native at the fork. – What question do you ask to find out if the restaurant lies  down the left fork? Problem 7 • 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?”.