Utente:Rossa1/lavoriSmull

True, False, and Random

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which. [Boolos (1996), p. 62]

Boolos provides the following clarifications:

• It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).

• What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)

• Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly;if tails, falsely.

• Random will answer 'da' or 'ja' when asked any yes-no question.

History

The so-called "Hardest Logic Puzzle Ever" was coined as such by George Boolos (first published in La Repubblica 1992 under the title "L’indovinello più difficile del mondo"). Boolos credits the logician Raymond Smullyan as the originator of the puzzle and John McCarthy with adding the difficulty of not knowing what 'da' and 'ja' mean. Related puzzles can be found throughout Smullyan’s writings, e.g. in What is the Name of This Book?, pp. 149-156, he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth) and explains that "the situation is enormously complicated by the fact that although all the natives understand English perfectly, an ancient taboo of the island forbids them ever to use non-native words in their speech. Hence whenever you ask them a yes-no question, they reply 'Bal' or 'Da' - one of which means yes and the other no. The trouble is that we do not know which of 'Bal' or 'Da' means yes and which means no". There are other related puzzles in The Riddle of Sheherazade (see especially, p. 114).

More generally this puzzle is based off of Smullyan's famous Knights and Knaves puzzles (e.g. there are two doors with two guards. One guard lies and one guard doesn't. One door leads to heaven and one door leads to hell. The puzzle is to find out which door leads to heaven by asking one of the guards one question. One way to do this is to ask "Which door would the other guard say leads to hell?"). A version of this puzzle was popularised by a scene in the 1980's fantasy film, Labyrinth (film).

The Solution

Template:Solution Boolos provided his solution in the same article in which he introduced the puzzle. Boolos states that the "first move is to find a God that you can be certain is not Random, and hence is either True or False". There are many different questions that will achieve this result. One strategy is to use complicated logical connectives in your questions (either biconditionals or some equivalent construction).

Boolos' question was:

• Does 'da' mean yes if and only if you are True if and only if B is Random? (see [1])

The puzzle's solution can be simplified by using counterfactuals as shown in [2] and [3]. The key to this solution is that, for any yes/no question Q, asking either True or False the question

• If I asked you Q, would you say 'ja'?

results in the answer 'ja' if the truthful answer to Q is yes, and the answer 'da' if the truthful answer to Q is no. The reason this works can be seen by looking at the eight possible cases.

• Assume that 'ja' means yes and 'da' means no.

(i) True is asked and responds with 'ja'. Since he is telling the truth the truthful answer to Q is 'ja', which means yes.

(ii) True is asked and responds with 'da'. Since he is telling the truth the truthful answer to Q is 'da', which means no.

(iii) False is asked and responds with 'ja'. Since he is lying it follows that if you asked him Q he would instead answer 'da'. He would be lying, so the truthful answer to Q is 'ja', which means yes.

(iv) False is asked and responds with 'da'. Since he is lying it follows that if you asked him Q he would in fact answer 'ja'. He would be lying, so the truthful answer to Q is 'da', which means no.

• Assume 'ja' means no and 'da' means yes.

(v) True is asked and responds with 'ja'. Since he is telling the truth the truthful answer to Q is 'da', which means yes.

(vi) True is asked and responds with 'da'. Since he is telling the truth the truthful answer to Q is 'ja', which means no.

(vii) False is asked and responds with 'ja'. Since he is lying it follows that if you asked him Q he would in fact answer 'ja'. He would be lying, so the truthful answer to Q 'da', which means yes.

(viii) False is asked and responds with 'da'. Since he is lying it follows that if you asked him Q he would instead answer 'da'. He would be lying, so the truthful answer to Q is 'ja', which means no.

Most readers of the puzzle assume that Random will provide completely random answers to any question asked of him; however, the puzzle does not actually state this. In fact, Boolos' third clarifying remark explicitly refutes this assumption.

• Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly;if tails, falsely.

This says that Random randomly acts as a liar or a truth-teller, not that Random answers randomly.

A small change to the question above yields a question which will always elicit a meaningful answer from Random. The change is as follows:

• If I asked you Q in your current mental state, would you say 'ja'?

We have effectively extracted the truth-teller and liar personalities from Random and forced him to be only one of them. This completely trivializes the puzzle since we can now get truthful answers to any questions we please.

• Ask god A, "If I asked you 'Are you Random?' in your current mental state, would you say 'ja'?"

If A answers 'ja', then A is Random.

• Ask god B, "If I asked you 'Are you True?' in your current mental state, would you say 'ja'?"

If B answers 'ja', then B is True and C is False. If B answers 'da', then B is False and C is True. And we are done.

If A answers 'da', then A is not Random.

• Ask god A, "If I asked you 'Are you True?' in your current mental state, would you say 'ja'?"
• Ask god B, "If I asked you 'Are you Random?' in your current mental state, would you say 'ja'?"

If A answers 'ja', then A is True. If A answers 'da', then A is False.

If B answers 'ja', then B is Random and C is the opposite of A. If B answers 'da', then B is the opposite of A and C is Random. And we are done.

We can modify Boolos' puzzle so that it follows the interpretation of most people (so that Random ignores the actual content of the question entirely and mindlessly answers 'ja' or 'da' at random). In this case, the problem can be solved as follows:

• Ask god B, "If I asked you 'Is A Random?', would you say 'ja'?". If B answers "ja", then either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is indeed Random. Either way, C is not Random. If B answers "da", then either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is not Random. Either way, A is not Random.
• Go to the God who was identified as not being Random by the previous question, and ask them: "If I asked you 'Are you True?', would you say 'ja'?". Since they cannot be Random, their answer must be meaningful. If they answer "ja", they are True. If they answer "da", then again because they cannot be Random, they must be False.
• Ask the same god the question: "If I asked you 'Is B Random?', would you answer 'ja'?". If the answer is "ja" then B is Random; if the answer is "da" then C is Random. The one remaining unidentified god can be identified by elimination; he is the opposite of the one you are speaking to.

Development

[4] develops the puzzle further by pointing out that it is not the case that "ja" and "da" are the only possible answers a god can give. It is also possible for a god to be unable to answer at all. For example, if the question "Are you going to answer this question with the word that means no in your language?" is put to True, he cannot answer truthfully. (The paper represents this as his head exploding, "...they are infallible Gods! They have but one recourse – their heads explode") This introduces the possibility that, by allowing for the "no answer" case, it would be possible to solve the problem in two questions rather than three. It also introduces a fresh problem concerning Random's behaviour: if he answers at random mindlessly, then his head cannot explode, as he never notices paradoxes in question he is asked; but if he acts as either True or False at random, then his head may explode if he is asked a question paradoxical to either of these. In this case, the problem as literally written may actually be harder than the one in which Random answers mindlessly.

External Links

• George Boolos. The hardest logic puzzle ever. The Harvard Review of Philosophy, 6:62–65, 1996.
• Roberts T.S. Some thoughts about the hardest logic puzzle ever. Journal of Philosophical Logic, 30:609–612(4), December 2001.
• A Simple Solution to the Hardest Logic Puzzle Ever
• An illustration of the puzzle

True, False, and Random

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are 'da' and 'ja', in some order. You do not know which word means which. [Boolos (1996), p. 62]

Boolos provides the following clarifications:

• It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).

• What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)

• Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly;if tails, falsely.

• Random will answer 'da' or 'ja' when asked any yes-no question.

History

The so-called "Hardest Logic Puzzle Ever" was coined as such by George Boolos (first published in La Repubblica 1992 under the title "L’indovinello più difficile del mondo"). Boolos credits the logician Raymond Smullyan as the originator of the puzzle and John McCarthy with adding the difficulty of not knowing what 'da' and 'ja' mean. Related puzzles can be found throughout Smullyan’s writings, e.g. in What is the Name of This Book?, pp. 149-156, he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth) and explains that "the situation is enormously complicated by the fact that although all the natives understand English perfectly, an ancient taboo of the island forbids them ever to use non-native words in their speech. Hence whenever you ask them a yes-no question, they reply 'Bal' or 'Da' - one of which means yes and the other no. The trouble is that we do not know which of 'Bal' or 'Da' means yes and which means no". There are other related puzzles in The Riddle of Sheherazade (see especially, p. 114).

More generally this puzzle is based off of Smullyan's famous Knights and Knaves puzzles (e.g. there are two doors with two guards. One guard lies and one guard doesn't. One door leads to heaven and one door leads to hell. The puzzle is to find out which door leads to heaven by asking one of the guards one question. One way to do this is to ask "Which door would the other guard say leads to hell?"). A version of this puzzle was popularised by a scene in the 1980's fantasy film, Labyrinth (film).

The Solution

Template:Solution Boolos provided his solution in the same article in which he introduced the puzzle. Boolos states that the "first move is to find a God that you can be certain is not Random, and hence is either True or False". There are many different questions that will achieve this result. One strategy is to use complicated logical connectives in your questions (either biconditionals or some equivalent construction).

Boolos' question was:

• Does 'da' mean yes if and only if you are True if and only if B is Random? (see [5])

The puzzle's solution can be simplified by using counterfactuals, such as:

• If I asked you 'Is A Random?', would you say 'ja'? (see [6] and [7]).

External Links

• George Boolos. The hardest logic puzzle ever. The Harvard Review of Philosophy, 6:62–65, 1996.
• Roberts T.S. Some thoughts about the hardest logic puzzle ever. Journal of Philosophical Logic, 30:609–612(4), December 2001.
• A Simple Solution to the Hardest Logic Puzzle Ever
• An illustration of the puzzle

Enigmi

Quesito 1

Arturo dice: Siamo entrambi furfanti.

Di che tipo sono?

Soluzione

In forma più estesa Arturo ha affermato:

"Arturo è un furfante e Bernardo è un furfante."

Poniamo che la frase sia vera. Allora chi la dice sarebbe un furfante, il quale però non potrebbe mai affermare nulla di vero.
Quindi la frase è falsa, e Arturo che la pronuncia è perciò un furfante, di conseguenza Bernardo non potrà essere un furfante (altrimenti la frase diverrebbe vera) ma un cavaliere.
Arturo è un furfante, Bernardo un cavaliere.

Soluzione con l'uso dell'algebra booleana

Possiamo usare l'algebra booleana per dedurre di che tipo sono i due indigeni in questo modo:

sia A vera se Arturo è un cavaliere e B vera se Bernardo è un cavaliere.
Allora, o Arturo è un cavaliere e quello che dice è vero o Arturo non è un cavaliere e quello che dice e falso.
Traducendo quanto appena detto in algebra booleana si ottiene:

$(A\wedge (\neg A\wedge \neg B))\vee (\neg A\wedge \neg (\neg A\wedge \neg B))$

$\equiv {\rm {falso}}\vee (\neg A\wedge \neg (\neg A\wedge \neg B))$     (perché $A\wedge \neg A\equiv {\rm {falso}}$)

$\equiv \neg A\wedge \neg (\neg A\wedge \neg B)$    (perché ${\rm {falso}}\vee X\equiv X$)

$\equiv \neg A\wedge (A\vee B)$    (per la legge di De Morgan)

$\equiv (\neg A\wedge A)\vee (\neg A\wedge B)$    (per la legge di distributività)

$\equiv \neg A\wedge B$

Quindi Arturo è un furfante e Bernardo un cavaliere.

Nonostante la maggioranza delle persone riesca a risolvere questo semplice enigma senza l'uso dell'algebra booleana, l'esempio serve comunque a mostrare la potenza dell'algebra booleana nella risoluzione degli indovinelli logici.

Quesito 2

Arturo: Se Bernardo è un furfante io sono un cavaliere.

Bernardo: Siamo di tipo diverso.

Di che tipo sono?

Soluzione

Iniziamo con l'analizzare la seconda affermazione. Poniamo che sia vera. In tal caso, chi la pronuncia (Bernardo) è un cavaliere e l'altro indigeno (Arturo) è un furfante. Poniamo invece che sia falsa. In questo caso chi la pronuncia è un furfante, ed essendo falsa, entrambi gli indigeni saranno dello stesso tipo, quindi anche l'altro sarà un furfante. Ecco che, a prescindere dalla verità o falsità dell'affermazione di Bernardo (e quindi dal suo essere cavaliere o furfante), abbiamo provato che Arturo è in ogni caso un furfante. Di conseguenza la sua affermazione dovrà essere falsa, e l'unico caso in cui un'implicazione (se X allora Y) è falsa è quello in cui la premessa X è vera e la conclusione Y è falsa. Che la conclusione (Arturo è un cavaliere) sia falsa è già provato, dunque dovrà esser vera la premessa (Bernardo è un furfante).
Arturo e Bernardo sono entrambi furfanti.

Quesito 3

Logico: Siete entrambi cavalieri?
Arturo risponde sì o no, ma il logico non ha ancora sufficienti informazioni per risolvere il problema.

Logico: Siete entrambi furfanti?
Arturo risponde sì o no, e il logico è ora in grado di risolvere il problema.

Di che tipo sono?

Soluzione

Analizziamo tutte le risposte che potrebbe ricevere il logico:

Sì - Sì: rispondendo sì ad entrambe le domande, è ovvio che Arturo sta mentendo, e dovendo quindi essere false entrambe le risposte, i due isolani sono di tipo diverso, Arturo furfante e Bernardo cavaliere.

Sì - No: poniamo che Arturo sia un cavaliere, non c'è alcuna contraddizione nell'ipotizzare vere entrambe le sue risposte, sia Arturo che Bernardo sono cavalieri. Poniamo invece che Arturo sia un furfante. La falsità della sua prima risposta è ovvia, ma dovrà essere falsa anche la seconda, quindi i due dovranno essere entrambi furfanti.

No - Sì: rispondendo "sì" alla seconda domanda ("Siete entrambi furfanti?"), è ovvio che Arturo non può essere un cavaliere (nessun cavaliere potrebbe mai affermare di essere un furfante), dovrebbe quindi essere un furfante. Ma allora la risposta "no" alla prima domanda ("Siete entrambi cavalieri?") sarebbe veritiera, e questa è una contraddizione. Quindi, semplicemente, questa (no-sì) è una combinazione di risposte che non può esser data.

No - No: se Arturo fosse un furfante, la risposta "no" alla prima domanda sarebbe vertiera, e questa è una contraddizione. Arturo è quindi un cavaliere e Bernardo un furfante, in questo modo le due risposte sono entrambe appropriate.

Di conseguenza, poiché al logico non è bastato udire la prima risposta per determinare di che tipo fossero Arturo e Bernardo, non è possibile che Arturo abbia risposto No - No, e poiché gli è stato sufficiente udirle entrambe, non è possibile che Arturo abbia risposto Sì - No (che avrebbe lasciato ancora un'indeterminazione). Quindi Arturo aveva risposto Sì - Sì e Arturo è furfante e Bernardo cavaliere.

Molto più semplicemente, consideriamo invece tutte le possibili combinazioni di tipi assunte da Arturo e Bernardo e le relative risposte alle domande del logico:

A cavaliere - B cavaliere: sì - no
A cavaliere - B furfante: no - no
A furfante - B cavaliere: sì - sì
A furfante - B furfante: sì - no

È evidente che la combinazione che permette di essere individuata alla seconda risposta è la terza, e quindi Arturo è un furfante e Bernardo un cavaliere.

Quesito 4

Ed ecco una versione di quello che è forse il più famoso di questo tipo di enigmi:

Due guardiani si trovano ad un bivio. Tu sai che uno di loro è un cavaliere, e l'altro un furfante, ma non sai chi sia l'uno e chi l'altro. Una delle due strade porta a Qualcheposto, l'altra a Nessunluogo.

• Ponendo una sola domanda che abbia risposta sì o no, siete in grado di determinare la strada per Qualcheposto?
• Ponendo una sola domanda che abbia risposta sì o no, siete in grado di determinare quale dei due è il cavaliere?

Questa versione dell'enigma è stata resa ancora più popolare da una scena di un film fantasy del 1986, Labyrinth, in cui Sarah (Jennifer Connelly) si trova a dover scegliere fra due porte custodite da un guardiano a due teste. Una delle porte conduce al castello che si trova al centro del labirinto, l'altra invece conduce alla morte.

Soluzione

Per individuare qual è la strada che porta a Qualcheposto potremmo rivolgerci ad uno dei due guardiani, indicando una qualsiasi delle due strade, e chiedergli:
"Se chiedessi all'altro guardiano se questa è la strada giusta per Qualcheposto luì risponderebbe sì o no?"
Se il guardiano risponde no, allora è la strada giusta, se risponde sì è quella sbagliata.

Per individuare quale tra i due guardiani è il cavaliere mi basta chiedere ad uno dei due:
"Se chiedessi all'altro guardiano se tu sei un cavaliere, cosa mi risponderebbe?" Se ottengo come risposta "no", allora la persona a cui ho rivolto la domanda è proprio il cavaliere, se invece ottengo la risposta "sì", il cavaliere è l'altro.

Enigmi su cavalieri e furfanti nella cultura popolare

€♠۩ױؤئك