Report

AE1APS Algorithmic Problem Solving John Drake Invariants – Chapter 2 River Crossing – Chapter 3 Logic Puzzles – Chapter 5 (13) ◦ Knights and Knaves ◦ Portia’s Casket Matchstick Games - Chapter 4 Sum Games – Chapter 4 Induction – Chapter 6 Tower of Hanoi – Chapter 8 Conjunction: X ∧ Y (AND) Disjunction: X ∨ Y (OR) Negation (or complement): ¬X (NOT) Inequivalence: ≢ (DIFFERENT) Implication: X ⇒ Y, (X implies Y) Boolean expressions are either true or false. Boolean valued expressions are called propositions. “it is sunny” is an atomic Boolean expression. “it is sunny and warm” is non atomic as it can be broken down into two expressions. We are concerned with the rules for manipulating Boolean expressions. = or ≡ ? In which order should x = y = z be processed? As an example, if x = true, y = false and z = false. If read continually - true = false = false evaluates to false However if read associatively – (x = y) = z or x = (y = z) it will evaluate to true To remove this confusion we use ≡ to indicate that an expression should be considered associatively. The property of associativity is very powerful! Negation: [¬ x ≡ x ≡ false] p.106 Inequivalance: x ≢ y or ¬(x ≡ y) p.113 [¬(x ≡ y) ≡ x ≡ ¬y ] Equality is a binary relation. It is a function with a range of Boolean values true and false. Equality is reflexive: [x ≡ x] It is symmetric: [x ≡ y is the same as y ≡ x] It is transitive: [x ≡ y and y ≡ z implies z ≡ x] It is associative: [(x ≡ y) ≡ z is the same as x ≡ (y ≡ z) ] It is substitutive: [x ≡ (y ≡ z) can be replaced by (y ≡ z) ≡ (y ≡ z) ] Given a pair of natives, what question would you ask one to discover if the other is a knight? I’m a Knight I’m a Knight If A is the proposition: “person A is a knight" and suppose the native makes a statement S. We can infer that A is true is the same as S is true. That is, A≡S If native A is asked a yes/no question Q then the response to the question is: A≡Q Let R be the desired response when we ask question Q: i.e. R ≡ (A ≡ Q) R ≡ (A ≡ Q) A – The statement “A is a knight” Q – The response to a given question R – The desired response from the native R ≡ (A ≡ Q) A – The statement “A is a knight” ◦ We can ask Q – The response to a given question ◦ What we are trying to find R – The desired response from the native ◦ “Is B a knight?” – we will call this proposition B So, B ≡ (A ≡ Q) A and B are statements, Q is the question to be asked As equality is associative B ≡ (A ≡ Q) becomes (B ≡ A) ≡ Q As equality is symmetric (B ≡ A) ≡ Q becomes Q ≡ (A ≡ B) So we ask the native is (A ≡ B)? “Is the statement of your being a knight equivalent to the statement of B being a knight” In Shakespeare's Merchant of Venice, Portia had three caskets: gold, silver and lead. Inside one of these caskets Portia had put her portrait and on each was an inscription. Portia explained to her suitor that each inscription could be either true or false but on the basis of the inscriptions he was to choose the casket containing the portrait. If he succeeded he could marry her. Here we will consider a simpler variant of this problem using only two caskets Suppose there are two caskets, gold and silver, into one of which Portia placed her portrait. The inscriptions are: ◦ Gold: The portrait is not in here. ◦ Silver: Exactly one of these inscriptions is true. Which casket contains the portrait? Let pg stand for “the portrait is in the gold casket“ Let ps stand for “the portrait is in the silver casket“ Let ig stand for “the inscription on the gold casket is true" and let is stand for “the inscription on the silver casket is true“ What do we know? If the inscription on the gold casket is true then the portrait is in the silver casket i.e. ig ≡ ps As there is only one portrait pg and ps cannot both be true i.e. pg ≢ ps The inscriptions are: Gold: The portrait is not in here. Silver: Exactly one of these inscriptions is true. What do we know? For one statement to be true ig ≡ ¬is So for is to be true this condition must hold i.e. is ≡ (ig ≡ ¬is) The inscriptions are: Gold: The portrait is not in here. Silver: Exactly one of these inscriptions is true. This leaves us with three statements to help us decide which casket the portrait is in. (ig ≡ ¬pg) ∧ (pg ≢ ps) ∧ (is ≡ ig ≡ ¬is) The inscriptions are: Gold: The portrait is not in here. Silver: Exactly one of these inscriptions is true. (ig ≡ ps) ∧ (pg ≢ ps) ∧ (is ≡ ig ≡ ¬is) Using the definition of negation and inequivalance (ig ≡ ps) ∧ (pg ≡ ps ≡ false) ∧ (is ≡ ig ≡ is ≡ false) Using reflexivity of equality [( is ≡ is) ≡ true] (ig ≡ ps) ∧ (pg ≡ ps ≡ false) ∧ (ig ≡ false) Equality is substitutive, then use reflexivity (false ≡ ps) ∧ (pg ≡ true) ∧ (ig ≡ false) What can we deduce? ps is false pg is true ig is false So the portrait is in the Gold casket Note: we know nothing about the inscription on the Silver casket Please e-mail me with any questions or problems you are having Tutorial session this afternoon at 1pm Hopefully extra slots start next week [email protected]