Cavalieri e furfanti

Cavalieri e furfanti sono i protagonisti di un tipo di indovinelli logici inventati da Raymond Smullyan.

Su un'isola di fantasia, tutti gli abitanti sono o cavalieri, che dicono sempre la verità, o furfanti, che mentono sempre. Gli enigmi contengono un visitatore che approda all'isola e incontra piccoli gruppi di abitanti. Di solito il visitatore deve dedurre dalle loro affermazioni di che "tipo" sono gli abitanti, ma qualche indovinello richiede di dedurre altri fatti. L'enigma può anche consistere nella formulazione di una domanda (dalla risposta sì o no) che il visitatore possa porre agli abitanti per scoprire ciò che gli occorre sapere.

Un primo esempio di questo tipo di indovinelli coinvolge tre abitanti, che chiameremo A, B e C. Il visitatore chiede ad A di che tipo sia, ma non riesce a sentire la risposta di A. B allora dice: "A ha detto di essere un furfante" e C dice "Non credere a B: sta mentendo!"
Per risolvere l'indovinello, considerate che nessun abitante dell'isola può affermare di essere un furfante (infatti se fosse un furfante, dovendo mentire non affermerebbe mai di esserlo, e se fosse un cavaliere non potrebbe mai affermare falsamente di essere un furfante). Quindi l'affermazione di B è falsa e di conseguenza lui è un furfante, così l'affermazione di C è vera e lui è un cavaliere. A ha sicuramente detto di essere un cavaliere, ma noi non sapremo mai, in questo caso, se diceva il vero oppure no.

In qualche variante gli abitanti possono essere anche "alternatori", che alternano affermazioni vere a menzogne, o "normali", che possono dire quel che vogliono (come nel caso degli indovinelli su cavalieri, furfanti e spie). Un'ulteriore complicazione è che gli abitanti possono rispondere alle domande sì o no nella loro lingua, ed il visitatore non sa quale delle due parole usate significhi "sì" e quale "no".

Un'ampia classe di indovinelli logici elementari può essere risolta usando le leggi dell'algebra booleana e le tavole di verità. La familiarità con l'algebra booleana e con i suoi processi di semplificazione aiuta a capire i seguenti esempi.
In particolare, per risolvere il secondo quesito bisogna capire che l'unico modo affinché una proposizione del tipo "se X allora Y" sia falsa è che X sia vera e Y sia falsa.

Arturo e Bernardo sono abitanti dell'isola dei cavalieri e dei furfanti.

Arturo dice: Siamo entrambi furfanti.

Di che tipo sono?

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.

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 è falso.
Traducendo quanto appena detto in algebra booleana si ottiene:

${\displaystyle (A\wedge (\neg A\wedge \neg B))\vee (\neg A\wedge \neg (\neg A\wedge \neg B))}$

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

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

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

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

${\displaystyle \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.

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

Bernardo: Siamo di tipo diverso.

Di che tipo sono?

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.

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?

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.

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

Due guardiani si trovano ad un bivio. Voi sapete che uno di loro è un cavaliere, e l'altro un furfante, ma non sapete 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.

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 lui 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:
"Siete entrambi cavalieri?" 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.

Entrambe le domande assumono un significato diverso a seconda del guardiano a cui vengono rivolte perché contengono rispettivamente i pronomi personali "lui" e "tu".
Pertanto, a livello logico, sono quattro domande distinte.

• (1981) Quale è il titolo di questo libro?, Raymond Smullyan, Zanichelli ISBN 8808054225
• (1985) Donna o tigre?, Raymond Smullyan, Zanichelli ISBN 880806008X
• (1988) Alice nel paese degli indovinelli. Racconto alla maniera di Lewis Carrol per bambini infraottantenni, Raymond Smullyan, Zanichelli ISBN 8808053741
• (1990) Fare il verso al pappagallo e altri rompicapi logici, Raymond Smullyan, Bompiani ISBN 8845216217
• (1994) Satana, Cantor e l'infinito, Raymond Smullyan, Bompiani ISBN 8845222624

• Raymond Smullyan
• Indovinello logico
• L'indovinello più difficile del mondo

• (EN) Nota su alcune implicazioni filosofiche degli enigmi cavalieri-furfanti (PDF), su nottingham.ac.uk. URL consultato il 23 gennaio 2007 (archiviato dall'url originale il 6 dicembre 2006).
• (EN) Lista ed analisi degli enigmi con cavalieri, furfanti e spie (che possono mentire o dire il vero), su newheiser.googlepages.com. URL consultato il 23 gennaio 2007 (archiviato dall'url originale il 18 settembre 2009).