Det svåraste logiska pusslet någonsin

The Hardest Logic Puzzle Ever är ett logiskt pussel så kallat av den amerikanske filosofen och logikern George Boolos och publicerat i The Harvard Review of Philosophy 1996. Boolos artikel innehåller flera sätt att lösa problemet. En översättning på italienska publicerades tidigare i tidningen La Repubblica , under titeln L'indovinello più difficile del mondo .

Det står så här:

Tre gudar A, B och C kallas, utan särskild ordning, Sant, Falskt och Slumpmässigt. Sant talar alltid sant, Falskt talar alltid falskt, men om Random talar sant eller falskt är en helt slumpmässig fråga. Din uppgift är att fastställa identiteterna för A, B och C genom att ställa tre ja-nej-frågor ; varje fråga måste ställas till exakt en gud. Gudarna förstår engelska, men kommer att svara på alla frågor på sitt eget språk, där orden för ja och nej är da och ja , i någon ordning. Du vet inte vilket ord som betyder vilket.

Boolos ger följande förtydliganden: en enda gud kan ställas mer än en fråga, frågor tillåts bero på svaren på tidigare frågor, och arten av Randoms svar bör betraktas som beroende på hur ett rättvist mynt gömmer sig i hans hjärna: om myntet kommer ner i huvudet, talar han sant; om svansar, falskt.

Historia

Boolos krediterar logikern Raymond Smullyan som upphovsmannen till pusslet och John McCarthy med att tillägga svårigheten att inte veta vad da och ja betyder. Relaterade pussel finns i Smullyans skrifter. Till exempel i What is the Name of This Book? , beskriver han en haitisk ö där hälften av invånarna är zombies (som alltid ljuger) och hälften är människor (som alltid säger sanningen). Han förklarar att "situationen är enormt komplicerad av det faktum att även om alla infödda förstår engelska perfekt, förbjuder ett uråldrigt tabu på ön dem att någonsin använda icke-infödda ord i sitt tal. Därför när du ställer dem en ja-nej-fråga , svarar de Bal eller Da - varav den ena betyder ja och den andra nej . Problemet är att vi inte vet vilken av Bal eller Da som betyder ja och vilken som betyder nej." Det finns andra relaterade pussel i The Riddle of Scheherazade .

Pusslet är baserat på Knights and Knaves -pussel. En miljö för det här pusslet är en påhittad ö som bara bebos av riddare och knep, där riddare alltid säger sanningen och knavar alltid ljuger. En besökare på ön måste ställa ett antal ja/nej-frågor för att upptäcka vad han behöver veta (vars detaljer varierar mellan olika versioner av pusslet). En version av dessa pussel populariserades av en scen i fantasyfilmen Labyrinth från 1986 . Det finns två dörrar, var och en med ett skydd. Den ena vakten ljuger alltid och den andra svarar alltid sanningsenligt. En dörr leder till slottet och den andra leder till "viss död". Pusslet är att ta reda på vilken dörr som leder till slottet genom att ställa en fråga till en av vakterna. I filmen gör huvudpersonen detta genom att fråga "Skulle han [den andra vakten] berätta för mig att den här dörren leder till slottet?"

Lösningen

Boolos gav sin lösning i samma artikel där han presenterade pusslet. Boolos säger att "första draget är att hitta en gud som du kan vara säker på inte är slumpmässig, och därför är antingen Sann eller Falsk". Det finns många olika frågor som kommer att uppnå detta resultat. En strategi är att använda komplicerade logiska kopplingar i dina frågor (antingen biconditionals eller någon likvärdig konstruktion).

Boolos fråga var att fråga A:

Betyder da ja om och bara om du är Sann, om och bara om B är Slumpmässig ?

Motsvarande:

Är ett udda antal av följande påståenden sanna: du är falsk, da betyder ja , B är slumpmässig?

Det observerades av Roberts (2001) och oberoende av Rabern och Rabern (2008) att pusslets lösning kan förenklas genom att använda vissa kontrafakta . Nyckeln till den här lösningen är att, för alla ja/nej-frågor Q, ställa frågan antingen Sant eller Falskt

Om jag frågade dig Q, skulle du säga ja ?

resulterar i svaret ja om det sanningsenliga svaret på Q är ja , och svaret da om det sanna svaret på Q är nej (Rabern och Rabern (2008) kallar detta resultat för det inbäddade frågelemmat). Anledningen till att detta fungerar kan ses genom att studera den logiska formen av det förväntade svaret på frågan. Denna logiska form ( booleskt uttryck ) utvecklas nedan (' Q' är sant om svaret på Q är 'ja', ' Gud' är sant om guden till vilken frågan ställs agerar som en sanningssägare och ' Ja ' är sant om innebörden av Ja är 'ja'):

  1. Hur en gud skulle välja att svara på Q ges av negationen av den exklusiva disjunktionen mellan Q och Gud (om svaret på Q och gudens natur är motsatta, är svaret som guden ger måste vara 'nej', medan om de är lika, måste det vara 'ja'):
    • ¬ ( Q ⊕ Gud)
  2. Huruvida svaret som guden gav skulle vara Ja eller inte ges igen genom negationen av den exklusiva disjunktionen mellan det föregående resultatet och Ja
    • ¬ ( ( ¬ ( Q ⊕ Gud) ) ⊕ Ja )
  3. Resultatet av steg två ger det sanningsenliga svaret på frågan: 'Om jag frågar dig Q, skulle du säga ja'? Vad som skulle vara svaret som Gud kommer att ge kan fastställas genom att använda resonemang liknande det som används i steg 1 ¬ ( (
    • ¬ ( ( ¬ ( Q ⊕ Gud) ) ⊕ Ja ) ) ⊕ Gud )
  4. Slutligen, för att ta reda på om detta svar kommer att vara Ja eller Da , kommer (när en) negation av den exklusiva disjunktionen av Ja med resultatet av steg 3 att krävas
    • ¬ ( ( ¬ ( ( ¬ ( ( ¬ ( Q ⊕ Gud)))) ⊕ Ja ) ) ⊕ Gud ) ) ⊕ Ja )

Detta slutliga uttryck utvärderas till sant om svaret är Ja och falskt annars. De åtta fallen utarbetas nedan (1 representerar sant och 0 falskt):

F

Sant om svar på

Q är "ja"

 Gud

Sant om gud beter sig

som sanningssägare

 Ja

Sant om betydelsen av

ja är "ja"

Steg 1

(Guds svar på Q)

 Steg 2

(Är det Ja ?)

Steg 3

(Guds svar på kontrafaktisk)

 Steg 4

(Är det Ja ?)

0 0 0 1 0 1 0
0 0 1 1 1 0 0
0 1 0 0 1 1 0
0 1 1 0 0 0 0
1 0 0 0 1 0 1
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 1 1 1 1

Att jämföra den första och sista kolumnen gör det tydligt att svaret är Ja endast när svaret på frågan är "ja". Samma resultat gäller om frågan istället var: 'Om jag frågade dig Q, skulle du säga Da'? eftersom utvärderingen av det kontrafaktiska inte är ytligt beroende av betydelser av Ja och Da. Vart och ett av de åtta fallen är likvärdigt motiverat nedan med ord:

  • Antag att ja betyder ja och da betyder nej .
  1. True tillfrågas och svarar med ja . Eftersom han talar sanning är det sanningsenliga svaret på Q ja , vilket betyder ja .
  2. True tillfrågas och svarar med da . Eftersom han talar sanning är det sanningsenliga svaret på Q da , vilket betyder nej .
  3. False tillfrågas och svarar med ja . Eftersom han ljuger följer det att om du frågade honom Q, skulle han istället svara da . Han skulle ljuga, så det sanna svaret på Q är ja , vilket betyder ja .
  4. False tillfrågas och svarar med da . Eftersom han ljuger, följer det att om du frågade honom Q, skulle han faktiskt svara ja . Han skulle ljuga, så det sanna svaret på Q är da , vilket betyder nej .
  • Antag att ja betyder nej och da betyder ja .
  1. True tillfrågas och svarar med ja . Eftersom han talar sanning är det sanningsenliga svaret på Q da , vilket betyder ja .
  2. True tillfrågas och svarar med da . Eftersom han talar sanning är det sanningsenliga svaret på Q ja , vilket betyder nej .
  3. False tillfrågas och svarar med ja . Eftersom han ljuger, följer det att om du frågade honom Q, skulle han faktiskt svara ja . Han skulle ljuga, så det sanna svaret på Q är da , vilket betyder ja .
  4. False tillfrågas och svarar med da . Eftersom han ljuger följer det att om du frågade honom Q, skulle han istället svara da . Han skulle ljuga, så det sanna svaret på Q är ja , vilket betyder nej.

Oavsett om den tillfrågade guden ljuger eller inte och oavsett vilket ord som betyder ja och vilket nej , kan du avgöra om det sanna svaret på Q är ja eller nej .

Lösningen nedan konstruerar sina tre frågor med hjälp av lemmat som beskrivs ovan.

Fråga 1: Fråga gud B: "Om jag frågade dig 'Är A Random?', skulle du säga ja ?". Om B svarar ja , är antingen B Slumpmässig (och svarar slumpmässigt), eller B är inte Slumpmässig och svaret indikerar att A verkligen är Slumpmässig. Hur som helst, C är inte Random. Om B svarar da är antingen B Slumpmässig (och svarar slumpmässigt), eller B är inte Slumpmässig och svaret indikerar att A inte är Slumpmässig. Hur som helst, du vet identiteten på en gud som inte är Random.
F2: Gå till guden som identifierades som inte slumpmässig av föregående fråga (antingen A eller C), och fråga honom: "Om jag frågade dig 'Är du falsk?', skulle du säga ja ?". Eftersom han inte är Random, indikerar ett svar av da att han är Sant och ett svar av ja indikerar att han är falsk.
F3: Ställ frågan till samma gud: "Om jag frågade dig 'Är B Random?', skulle du säga ja ?". Om svaret är ja , är B Slumpmässig; om svaret är da , är guden du ännu inte har pratat med Random. Den återstående guden kan identifieras genom eliminering.
Fall 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A Sann Sann Falsk Slumpmässig Falsk Slumpmässig Sann Sann Falsk Slumpmässig Falsk Slumpmässig
B Falsk Slumpmässig Sann Sann Slumpmässig Falsk Falsk Slumpmässig Sann Sann Slumpmässig Falsk
C Slumpmässig Falsk Slumpmässig Falsk Sann Sann Slumpmässig Falsk Slumpmässig Falsk Sann Sann
Jaha Ja Ja Ja Ja Ja Ja Nej Nej Nej Nej Nej Nej
Ja Nej Nej Nej Nej Nej Nej Ja Ja Ja Ja Ja Ja
Är A verkligen slumpmässigt? Nej Nej Nej Ja Nej Ja Nej Nej Nej Ja Nej Ja
Hur skulle B svara "Är A slumpmässig?" engelsk Ja Antingen Nej Ja Antingen Nej Ja Antingen Nej Ja Antingen Nej
Deras språk Ja Antingen Ja Ja Antingen Ja Ja Antingen Ja Ja Antingen Ja
B:s svar på fråga 1 — "Om jag frågade dig 'Är en slumpmässig', skulle du säga ja ?" engelsk Ja Antingen Ja Nej Antingen Nej Nej Antingen Nej Ja Antingen Ja
Deras språk Ja Antingen Ja Ja Antingen Ja Ja Antingen Ja Ja Antingen Ja
Ja Ja Ja Ja Ja Ja Ja Ja
Således är __ (hädanefter kallat X) inte slumpmässig. A A C A C A C C A A C A C A C C
Är X verkligen falskt? Nej Nej Ja Ja Ja Ja Nej Nej Nej Nej Ja Ja Ja Ja Nej Nej
Hur skulle X svara "Är du falsk?" engelsk Nej Nej Nej Nej Nej Nej Nej Nej Nej Nej Nej Nej Nej Nej Nej Nej
Deras språk Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja
X:s svar på fråga 2 — "Om jag frågade dig 'Är du falsk?', skulle du säga ja ?" engelsk Ja Ja Nej Nej Nej Nej Ja Ja Nej Nej Ja Ja Ja Ja Nej Nej
Deras språk Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja
X är alltså __. Sann Sann Falsk Falsk Falsk Falsk Sann Sann Sann Sann Falsk Falsk Falsk Falsk Sann Sann
Är B verkligen slumpmässigt? Nej Ja Nej Nej Ja Nej Nej Ja Nej Nej Ja Nej
Hur skulle X svara "Är B slumpmässig?" engelsk Nej Ja Nej Ja Ja Nej Ja Nej Nej Ja Nej Ja Ja Nej Ja Nej
Deras språk Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja
X:s svar på fråga 3—"Om jag frågade dig 'Är B Random?', skulle du säga ja ?" engelsk Ja Nej Nej Ja Ja Nej Nej Ja Nej Ja Ja Nej Nej Ja Ja Nej
Deras språk Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja Ja
__ är alltså slumpmässig. C B B C A B B A C B B C A B B A
Således genom eliminering är (bokstav) (namn). Brev B C A B B C A B B C A B B C A B
namn Falsk Falsk Sann Sann Sann Sann Falsk Falsk Falsk Falsk Sann Sann Sann Sann Falsk Falsk

Randoms beteende

Boolos tredje klargörande anmärkning förklarar Randoms beteende på följande sätt:

Huruvida Random talar sant eller inte bör ses som beroende på huruvida ett mynt fälls gömt i hans hjärna: om myntet faller ner i huvudet, talar han sant; om svansar, falskt.

Detta anger inte om myntvändningen är för varje fråga, eller varje "session", det vill säga hela serien av frågor. Om det tolkas som ett enda slumpmässigt urval som varar under sessionens varaktighet, visar Rabern och Rabern att användbara svar kan extraheras även från Random; detta beror på att det kontrafaktiska hade utformats så att oavsett om svararen (i det här fallet Random) var som en sanningssägare eller en falsksägare, så skulle det sanningsenliga svaret på Q vara tydligt.

En annan möjlig tolkning av Randoms beteende när han ställs inför det kontrafaktiska är att han svarar på frågan i dess helhet efter att ha vänt myntet i huvudet, men räknar ut svaret på Q i sitt tidigare sinnestillstånd, medan frågan ställs. Återigen gör detta att fråga Random är det kontrafaktiska värdelöst. Om så är fallet, ger en liten ändring av frågan ovan en fråga som alltid kommer att framkalla ett meningsfullt svar från Random. Ändringen är som följer:

Om jag frågade dig Q i ditt nuvarande mentala tillstånd , skulle du säga ja ?

Detta extraherar effektivt sanningssägaren och lögnarpersonligheterna från Random och tvingar honom att bara vara en av dem. Genom att göra så blir pusslet helt trivialt, det vill säga sanningsenliga svar kan lätt fås. Det förutsätter dock att Random har bestämt sig för att ljuga eller berätta sanningen innan man bestämt det korrekta svaret på frågan – något som inte framgår av pusslet eller den klargörande kommentaren.

Fråga gud A, "Om jag frågade dig 'Är du Random?" i ditt nuvarande mentala tillstånd, skulle du säga ja ?"
  1. Om A svarar ja , A är slumpmässig: Fråga gud B: "Om jag frågade dig 'Är du Sann?', skulle du säga ja ?"
    • Om B svarar ja är B Sant och C är falskt.
    • Om B svarar da är B Falskt och C är Sant. I båda fallen är pusslet löst.
  2. Om A svarar da , A är inte slumpmässig: Fråga gud A, "Om jag frågade dig 'Är du Sann?', skulle du säga ja ?"
    • Om A svarar ja är A Sant.
    • Om A svarar da är A falskt.
  3. Fråga gud A, "Om jag frågade dig 'Är B Random?', skulle du säga ja ?"
    • Om A svarar ja är B Slumpmässig och C är motsatsen till A.
    • Om A svarar da är C Slumpmässig och B är motsatsen till A.

Man kan elegant få sanningsenliga svar under loppet av att lösa det ursprungliga problemet som förtydligats av Boolos ("om myntet faller i huvudet, talar han sant; om svansar, falskt") utan att förlita sig på några påstådda outtalade antaganden, genom att göra en ytterligare förändring till frågan:

Om jag frågade dig Q, och om du svarade lika sanningsenligt som du svarar på den här frågan , skulle du säga ja ?

Här är det enda antagandet att Random, när han besvarar frågan , antingen svarar sanningsenligt ("talar sanningsenligt") ELLER svarar falskt ("talar falskt"), vilket är uttryckligen en del av förtydligandena av Boolos. Det ursprungliga omodifierade problemet (med Boolos förtydliganden) på detta sätt kan ses vara det "Hardest Logical Puzzle Ever" med den mest eleganta och okomplicerade lösningen.

Rabern och Rabern (2008) föreslår att man gör en ändring av Boolos ursprungliga pussel så att Random faktiskt är slumpmässigt. Ändringen är att ersätta Boolos tredje förtydligande anmärkning med följande:

Huruvida Random säger ja eller da bör ses som beroende på hur ett mynt vänder sig gömt i hans hjärna: om myntet faller i huvudet, säger han ja ; om svansar, säger han da .

Med denna modifiering kräver pusslets lösning den mer noggranna gudsförhören som ges överst i avsnittet Lösningen .

Obesvarbara frågor och exploderande gudar

I En enkel lösning på det svåraste logiska pusslet någonsin erbjuder B. Rabern och L. Rabern en variant av pusslet: en gud, konfronterad med en paradox, kommer att säga varken ja eller da och istället inte svara alls. Till exempel, om frågan "Ska du svara på den här frågan med ordet som betyder nej på ditt språk?" ställs till Sant kan han inte svara sanningsenligt. (Tidningen representerar detta när hans huvud exploderar , "...de är ofelbara gudar! De har bara en utväg – deras huvuden exploderar.") Att tillåta fallet med "exploderande huvud" ger ännu en lösning på pusslet och introducerar möjligheten att lösa pusslet (modifierat och original) på bara två frågor istället för tre. Till stöd för en tvåfrågelösning på pusslet löser författarna ett liknande enklare pussel med bara två frågor.

Tre gudar A, B och C kallas, i någon ordning, Zephyr, Eurus och Aeolus. Gudarna talar alltid sant. Din uppgift är att fastställa identiteterna för A, B och C genom att ställa ja-nej-frågor; varje fråga måste ställas till exakt en gud. Gudarna förstår engelska och kommer att svara på engelska.

Observera att detta pussel är trivialt löst med tre frågor. Dessutom, för att lösa pusslet i två frågor, bevisas följande lemma .

Tempered Liar Lemma. Om vi ​​frågar A "Är det så att {[(du ska svara 'nej' på den här frågan) AND (B är Zephyr)] OR (B är Eurus)}?", indikerar svaret 'ja' att B är Eurus, ett svar på 'nej' indikerar att B är Aeolus, och ett exploderande huvud indikerar att B är Zephyr. Därför kan vi bestämma identiteten för B i en fråga.

Med hjälp av detta lemma är det enkelt att lösa pusslet i två frågor. Rabern och Rabern (2008) använder ett liknande knep (tempera lögnarens paradox) för att lösa det ursprungliga pusslet på bara två frågor. Uzquiano (2010) använder dessa tekniker för att tillhandahålla en lösning med två frågor till det ändrade pusslet. Två frågelösningar till både det ursprungliga och ändrade pusslet drar fördel av det faktum att vissa gudar har en oförmåga att svara på vissa frågor. Varken Sant eller Falskt kan ge svar på följande fråga.

Skulle du svara på samma sätt som Random skulle svara på frågan "Är Dushanbe i Kirgiziien ?"?

Eftersom de ändrade Random svaren på ett verkligt slumpmässigt sätt kan varken Sant eller Falskt förutsäga om Random skulle svara ja eller da på frågan om Dushanbe är i Kirgiziien. Med tanke på denna okunskap kommer de inte att kunna berätta sanningen eller ljuga – de kommer därför att förbli tysta. Random, men den som sprutar slumpmässigt nonsens kommer inte att ha några problem att spruta av varken ja eller da . Uzquiano (2010) utnyttjar denna asymmetri för att tillhandahålla en lösning med två frågor till det modifierade pusslet. Ändå kan man anta att gudarna har en "orakulär förmåga att förutsäga Randoms svar redan innan myntet vänder i Randoms hjärna?" I det här fallet finns en lösning med två frågor fortfarande tillgänglig genom att använda självrefererande frågor av den stil som används i Rabern och Rabern (2008).

Skulle du svara ja på frågan om du skulle svara da på den här frågan?

Även här kan varken Sant eller Falskt svara på denna fråga med tanke på deras åtaganden om sanning respektive lögn. De tvingas svara ja ifall svaret de är fast beslutna att ge är da och detta kan de inte göra. Precis som tidigare kommer de att drabbas av en huvudexplosion. Däremot kommer Random tanklöst att spruta ut sina nonsens och slumpmässigt svara ja eller da . Uzquiano (2010) använder också denna asymmetri för att tillhandahålla en tvåfrågelösning till det modifierade pusslet. Uzquianos egen modifiering av pusslet, som eliminerar denna asymmetri genom att tillåta Random att antingen svara "ja", "da" eller förbli tyst, kan dock inte lösas med färre än tre frågor.

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=The_Hardest_Logic_Puzzle_Ever&oldid=1103951166 "