Bizonyítási módszerek, matematikai logika
Univerzális kvantor
Az univerzális kvantor egy jelölése a "minden" kifejezésnek.
Jele: $\forall$
Egzisztenciális kvantor
Az egzisztenciális kvantor egy jelölése a "létezik" vagy "van olyan" kifejezésnek.
Jele: $\exists$
Logikai műveletek | Negáció
Az állítás negációja (vagy tagadása) egy egyváltozós művelet. Egy $A$ kijelentés negációja az a kijelentés, amely akkor igaz, ha $A$ hamis és akkor hamis, ha $A$ igaz.
Állítás
Az állítás (vagy kijelentés) olyan kijelentő mondat, amelyről egyértelműen eldönthetjük, hogy az igaz vagy hamis.
Logikai műveletek | Konjunkció
A konjunkció két állítás közti logikai művelet. Két kijelentés konjunkciója pontosan akkor igaz, ha mindkét kijelentés igaz, különben hamis.
Jele: $ A \land B$
Logikai műveletek | Diszjunkció
A diszjunkció két állítás közti logikai művelet. Két kijelentés diszjunkciója pontosan akkor igaz, ha legalább az egyik kijelentés igaz, különben hamis.
Jele: $ A \lor B$
Logikai műveletek | Implikáció
A "ha $A$, akkor $B$" kapcsolatnak megfelelő logikai műveletet nevezzük implikációnak. Az implikáció akkor hamis, ha $A$ igaz és $B$ hamis, minden más esetben igaz.
Jele: $A \Rightarrow B$
Logikai műveletek | Ekvivalencia
Az ekvivalencia egy olyan logikai művelet, amikor $A \Rightarrow B$ és $A \Leftarrow B$. Az ekvivalencia akkor igaz, ha $A$ és $B$ logikai értéke azonos, különben hamis.
Jele: $A \Leftrightarrow B$
Logikai De Morgan azonosságok
\( \neg \left( A \land B \right ) = \neg A \lor \neg B \)
\( \neg \left( A \lor B \right ) = \neg A \land \neg B \)
\( \neg \left( A \Rightarrow B \right ) = A \land \neg B \)
\( \neg \left( A \Leftrightarrow B \right ) = A \Leftrightarrow \neg B \)
Végezzük el az alábbi feladatokat:
a) Egy vonaton 400-an utaznak. Bizonyítsuk be, hogy utazik rajta két olyan utas, akiknek ugyanazon a napon van a születésnapja.
b) Mi történik, ha felszáll újabb 333 utas?
c) És ha 1200-an utaznak a vonaton?
a) Egy 5 kocsiból álló vonaton 460-an utaznak. Bizonyítsuk be, hogy van olyan kocsi, amiben legalább 80 utas van.
b) Egy másik vonat szintén 5 kocsiból áll. Legalább hányan utaznak a vonaton, ha tudjuk, hogy biztosan van olyan kocsi, amiben legalább 40-en utaznak?
c) Az egyik kocsiban egy 10 tagú társaság utazik. Mindenki a társaságból legalább 7 másik embert ismer. Bizonyítsuk be, hogy bármely 3 embernek van közös ismerőse.
Van itt ez az állítás: "Minden mamut sárga."
Válasszuk ki innen azokat, amik az állítás tagadása:
Egyik mamut sem sárga.
Van olyan mamut, ami sárga.
Van olyan mamut, ami nem sárga.
A legtöbb mamut nem sárga.
Nem minden mamut sárga.
Dontsük el az alábbi állításokról, hogy igazak, vagy hamisak.
a) Esik az eső és a mamut piros.
b) Esik az eső vagy a mamut piros.
c) Ha esik az eső, akkor a mamut piros.
Készítsük el az alábbi állítások igazságtábláit.
a) \( \neg A \wedge \neg B \)
b) \( A \wedge \neg B \)
c) \( \left( A \lor B \right) \Rightarrow \left( A \wedge B \right) \)
d) \( \neg A \Rightarrow \left( A \wedge B \right) \)
e) \( \neg A \wedge \left( A \lor B \right) \)
a) Van itt két láda. Az egyikben arany van, a másik üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is. Anélkül, hogy hozzárénénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
A ládák feliratai: "Ha a másik ládában van az arany, akkor mindkét ládában hamis felirat van." és "Az arany nem ebben a ládában van."
b) Ezúttal már három láda van. Az egyikben arany van, a másik kettő üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
A ládák feliratai:
"A másodikon ládán a felirat igaz."
"Az arany ebben a ládában van és az első ládán a felirat hamis."
"Az arany olyan ládában van, amin a felirat hamis."
c) Most pedig tegyünk egy kört a lovagok és lókötők szigetén. Ezen a szigeten kétféle ember él, akik külsejük alapján teljesen egyformák. Csak éppen a lovagok mindig igazat mondanak, a lókötők pedig mindig hazudnak. Találkozunk két szigetlakóval.
X azt mondja: "Ha Y lovag, akkor én lókötő vagyok.". Y nem mond semmit. Milyen típusú X és Y?
d) Egy másik alkalommal három szigetlakóval találkozunk, akik ezt mondják:
X: "Y lókötő és Z lovag."
Y: "Lókötő vagyok és Z lovag."
Milyen típusú X, Y és Z?
e) Végü legy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
X: Y lovag.
Y: X lókötő és Z lovag.
Milyen típusú X, Y és Z?
Egy vonaton 400-an utaznak. Bizonyítsuk be, hogy utazik rajta két olyan utas, akiknek ugyanazon a napon van a születésnapja.
Hát, ez így elsőre elég furán hangzik…
Mégis honnan kéne tudnunk, hogy kinek mikor van a születésnapja…
De pont ez a lényeg, hogy nem kell tudni.
Itt van például Bob.
És itt van 365 darab doboz, mert egy évben 365 nap van.
Sőt, legyen 366, mert néha szökőév is van.
Azt kell bizonyítani, hogy van két ember ugyanabban a dobozban.
Betesszük Bobot abba a dobozba, amelyik napon született.
Tegyük be, mondjuk ide.
Aztán itt van a következő utas.
Hogyha ugyanazon a napon született, mint Bob…
akkor meg is van a két ember ugyanabban a dobozban.
Ha viszont más napon született…
Hát igen, akkor még nem vagyunk kész.
Itt jönnek sorban az utasok.
Ha mindegyik utas más napon született, mint a többi…
akkor mindegyiket külön-külön dobozban helyezzük el.
Most járunk 366 darab utasnál.
És ekkor megjelenik a 367-edik utas…
Hová is tegyük?
Már nincsen üres doboz, tehát mindegy mikor született…
valakivel így is úgyis közös dobozba kerül.
Egészen biztos, hogy 367 darab utas nem fér el 366 dobozban.
Csak úgy, hogyha valamelyik dobozban ketten vannak.
Ezt a nem túl bonyolult gondolatot hívjuk skatulya-elvnek.
A skatulya a doboz régies elnevezése.
És ezt az elvet elég régen találták ki…
Ha a vonaton 367 ember, vagy ennél több utazik, akkor biztosan lesz két olyan utas, akik ugyanazon a napon születtek.
Most nézzük, mi történik akkor, hogyha fölszáll újabb 333 utas.
Ekkor a vonaton éppen 733-an utaznak.
A 733 pedig egy mágikus szám:
utast még éppen el tudunk úgy helyezni, hogy minden dobozban csak ketten legyenek.
De a plusz egy ember miatt valahol már biztosan hárman lesznek.
Hogyha 733 ember utazik a vonaton, egészen biztosan van köztük 3, akik ugyanazon a napon születtek.
És ha 1200-an utaznak a vonaton…
Ennyi utas már ki sem fér ide.
Szerencsére az ilyen esetekre is van egy matematikai módszer, amit úgy hívunk, hogy indirekt bizonyítás.
Rögtön folytatjuk…
Ha van öt darab labda és négy doboz…
Akkor a labdákat nem tudjuk úgy betenni a dobozokba, hogy mindegyikben csak egy labda legyen.
Valamelyik dobozban biztosan legalább két labda lesz.
Röviden összefoglalva erről szól a skatulya-elv.
Most pedig lássuk, mi ez az indirekt bizonyítás.
Egy 5 kocsiból álló vonaton 460-an utaznak. Bizonyítsuk be, hogy van olyan kocsi, amiben legalább 80 utas van.
Az indirekt bizonyítás lényege, hogy elképzeljük, mi történne, hogyha az állítás nem lenne igaz.
Vagyis tegyük föl, hogy mindegyik kocsiban 80-nál kevesebb utas van.
Ha minden kocsiban 80-nál kevesebb utas van, akkor lássuk csak, 
tehát az egész vonaton 400-nál kevesebben lennének.
De ez lehetetlen, hiszen a vonaton 460-an vannak.
Vagyis lennie kell olyan kocsinak, ahol legalább 80-an vannak.
Egy másik vonat szintén öt kocsiból áll. Legalább hányan utaznak a vonaton, ha tudjuk, hogy biztosan van olyan kocsi, amiben legalább 40-en utaznak?
Hát, ez is valami skatulya-elvnek tűnik…
Csak most valahogy fordítva.
Hogyha mondjuk 100-an utaznak a vonaton, az valószínű kevés, mert simán lehet kocsinként 20 ember.
A 200 már határozottan biztatóbb.
Ha 200-an utaznak a vonaton, akkor biztosan van olyan kocsi, amiben legalább 40-en vannak.
Mert ha nem lenne, tehát minden kocsiban 40-nél kevesebben lennének, akkor az egész vonaton is 200-nál kevesebben lennének.
A 200 utas tehát már elég.
De a kérdés úgy szólt, hogy legalább hányan utaznak a vonaton, és előfordulhat, hogy már 200-nál kevesebb utas is jó lehet.
Ha 195-en utaznak a vonaton, akkor még előfordulhat, hogy minden kocsiban csak 39-en vannak.
De ha 196-an…
Akkor már kell lennie olyan kocsinak, amiben legalább 40-en vannak.
Hiszen, ha minden kocsiba csak 39-en lennének, akkor az egész vonaton is csak 195-en.
Tehát a válasz…
A vonaton legalább 196-an kell, hogy utazzanak.
Az egyik kocsiban egy 10 tagú társaság utazik. Mindenki a társaságból legalább 7 másik embert ismer. Bizonyítsuk be, hogy bármely 3 embernek van közös ismerőse.
Na, ez már egy izgalmasabb ügy.
Megint indirekten bizonyítunk, vagyis tegyük föl, hogy van 3 olyan ember, akiknek nincs közös ismerőse.
Hát, ha nincs közös ismerős, akkor itt bizony csak két ismertség lehet…
Sőt az is lehet, hogy kevesebb…
De az biztos, hogy legfeljebb kettő.
És itt is legfeljebb kettő…
Meg mindenhol.
Ebből a 7 emberből így legfeljebb 14 ismertség indulhat ki.
Mivel a társaságban mindenki legalább 7 másik embert ismer, hogyha embereink egymást ismerik...
akkor is még fejenként legalább 5 ismerősre van szükségük.
Így aztán legalább 15 ismertség indul ki innen.
Ez lehetetlen, mert azok ott heten legfeljebb 14 ismertséggel rendelkeznek.
Tehát ellentmondásra jutottunk.
Nem fordulhat elő, hogy van 3 ember, akinek nincs közös ismerőse.
Vagyis bármely 3 embernek van közös ismerőse.
Most, hogy ezt is megtudtuk, már csak egyetlen nyugtalanító kérdésre keressük a választ.
Arra, hogy mégis mit keres itt ez a rengeteg darázs?
Nem, valójában mégsem ez a kérdés…
Ez túlzottan életszerű lenne.
A kérdés úgy szól, hogy van itt ez a 7x7-es sakktábla és mindegyik mezőn egy darázs.
Egy adott pillanatban minden darázs átmászik valamelyik szomszédos mezőre.
A sarkuknál találkozó mezők nem számítanak szomszédosnak.
Lehetséges-e, hogy ekkor megint mindegyik mezőn pontosan egy darázs álljon?
Tegyük fel, hogy ez lehetséges.
Ez azt jelenti, hogy minden fekete mezőn álló darázsnak át kell másznia egy szomszédos fehér mezőre.
Fekete mezőből 25 darab van, fehérből meg csak 24 darab.
Nem tud a 25 darab fekete mezőn álló darázs átmászni a 24 fehér mezőre, csak úgy, ha lesz olyan mező, amin több darázs is van.
A nagy darázscserélő akció tehát lehetetlen.
A kvantorok. Hogy mik?
Minden ember utálja a matekot…
Azért ez így nem teljesen igaz, itt van ugyanis például Bob.
És Bob szereti a matekot.
Ez az állítás, hogy „Minden ember utálja a matekot.” tehát hamis.
Azért hamis, mert „Van olyan ember, aki szereti”.
Az egészből elég annyit megjegyezni, hogy Bobnak nehéz gyerekkora volt.
Nem, valójában ne ezt jegyezzük meg.
Hanem azt, hogy ez a két állítás egymás tagadása.
Nézzünk erre még egy példát és rögtön minden érthető lesz.
Itt van például ez az állítás:
Minden mamut piros.
Ennek az állításnak a tagadása:
Nem minden mamut piros.
Van olyan mamut, ami nem piros.
Tehát annak a tagadása, hogy „minden”…
így szól, hogy „van olyan, ami nem”.
A matematikában ezek a kifejezések meglehetősen gyakran előfordulnak.
Így aztán külön jelölés van rájuk forgalomban.
Ezt a jelet úgy hívják, hogy univerzális kvantor.
Ezt a másikat pedig úgy, hogy egzisztenciális kvantor.
Ezeknek a jeleknek a segítségével komplett kis titkosírásokat hozhatunk létre.
Ez például azt jelenti, hogy minden x-re létezik olyan y, hogy x+y=1.
A dolog igaznak tűnik, tényleg mindig létezik ilyen y.
Vagy itt van például egy másik:
Ami azt jelenti, hogy létezik olyan x, hogy minden y-ra x+y=1.
Na, ez már sajnos nem igaz.
Nem létezik olyan x szám, ami azt tudná, hogy bármilyen y-t adunk hozzá 1-et kapunk.
De visszatérve egy kicsit a mamutokra…
Van itt ez az állítás:
Minden mamut sárga.
Válasszuk ki innen azokat, amik az állítás tagadása:
Egyik mamut sem sárga.
Van olyan mamut, ami sárga.
Van olyan mamut, ami nem sárga.
A legtöbb mamut nem sárga.
Nem minden mamut sárga.
Hogyha még emlékszünk Bobra…
akkor talán rémlik valami, hogy a „minden” tagadása így szól: „van olyan, ami nem”.
Ez tehát biztosan jó.
Ez a másik pedig csak megtévesztésből van itt…
Hiányzik belőle a „nem” szócska.
Ócska kis trükk…
Aztán nyilván ez is az eredeti állítás tagadása…
Hiszen a mágikus „nem” szócskát őseink éppen a tagadás kifejezésére fejlesztették ki.
Ezek pedig nem tagadásai az eredeti állításnak, csak rá kell nézni itt lent a mamutokra és kiderül.
Próbáljuk meg eldönteni, hogy vajon igaz vagy hamis a következő állítás:
Esik az eső és a mamut piros.
Hát, eléggé hamisnak tűnik.
gy néz ki egyáltalán nem.
A mondat első fele sem igaz…
és a másik fele sem.
Ha mondjuk az eső legalább esne…
Az állítás ettől továbbra is hamis maradna.
Egyetlen egy esetben lenne igaz…
Ha mindkét fele igaz.
Készítsünk ebből egy kis táblázatot.
igaz
hamis
Végülis a mamutokra és az esőre nincs is szükség.
Az „és”-re pedig bevezetünk egy jelölést.
Itt jön aztán egy másik állítás:
Esik az eső vagy a mamut piros.
Készítsünk erről is egy táblázatot.
Hogyha mindkét rész hamis…
akkor az egész állítás is hamis.
Ha a két rész közül valamelyik igaz…
akkor az egész állítás is igaz.
Hogyha pedig mindkét rész igaz…
Ilyen esetekben az emberek hétköznapi logikája nem nagyon tudja értelmezni a „vagy” szócskát.
A matematika viszont igen, és az állítás ebben az esetben is igaz.
A „vagy”-ra is létezik egy matematikai jelölés…
Éppen itt is van.
Egy ősi népi megfigyelés szerint:
Ha esik az eső, akkor a mamut piros.
Nézzük, mikor lesz ez az állítás igaz.
Nos, olyankor, amikor süt a nap…
teljesen mindegy, hogy milyen színű a mamut.
Hiszen csak olyankor kell pirosnak lennie, ha esik.
Ezt az állítást matematikailag így jelöljük:
Olyankor, amikor a kiinduló feltevés hamis, már bármi történhet…
Maga az állítás igaz lesz.
És olyankor is igaz lesz, ha mindkét rész igaz.
Egyetlen egy esetben lesz az állítás hamis.
Amikor esik az eső, de a mamut mégsem piros.
Ezek itt valójában ugyanolyan műveletek, mint az algebrában az összeadás vagy a szorzás.
És ugyanúgy nevük is van.
KONJUNKCIÓ
DISZJUNKCIÓ
IMPLIKÁCIÓ
Vannak aztán még további műveletek is.
Az egyik az ekvivalencia.
Az ekvivalencia jeléből is látszik, hogy ez egy olyan művelet, amikor
Tehát A-ból következik B és B-ből is következik A.
A dolog valójában még ennél is egyszerűbb, az egész azt jelenti, hogy A pontosan akkor igaz, amikor B.
Ezek a műveletek mind kétváltozós műveletek, vagyis kell hozzá egy A és egy B is.
Itt jön aztán egy olyan logikai művelet is, ami egyváltozós.
Ez a művelet a tagadás, vagyis a „nem A”.
Olyan, mint az algebrában az ellentett…
A művelet neve negáció.
Jók ezek a táblázatok, csak hát rémesen sok helyet foglalnak.
Kénytelenek leszünk egy kicsit egyszerűsíteni őket:
Na, így már sokkal jobb.
Most nézzünk egy izgalmas feladványt, ami azt tesztelte, hogy a hétköznapi emberek mennyire fogékonyak a matematikai logika iránt.
A teszt során az derült ki, hogy nem különösebben…
De lássuk a feladványt.
Van itt ez a négy darab kártya. Az egyik oldalán mindegyiknek egy szám áll, a másik oldalon pedig egy betű.
És van itt ez az állítás:
Ha a kártya egyik oldalán magánhangzó van, akkor a másik oldalán páros szám áll.
A kérdés az, legfeljebb hány kártyát kell megfordítanunk ahhoz, hogy kiderüljön igaz-e az állítás?
A tipikus rossz válaszokat bárki megtudhatja, hogyha elmondja ezt a kis feladványt ismerőseinek…
És most lássuk a jó választ.
Ez az állítás tulajdonképpen mindig igaz, kivéve egyetlen esetben.
Egyedül az okozza a bajt, amikor A igaz, de B hamis.
Ez megtörténhet itt, ha a túloldalon páratlan szám van…
És itt, ha a másik oldalon magánhangzó van.
A többi esetben vagy eleve A hamis, és akkor már mindegy…
vagy B igaz és akkor is mindegy.
Ezt a két kártyát kell tehát megfordítani.
Itt jön néhány állítás, és fogalmazzuk meg ezek tagadását.
Az ég kék és a fű zöld.
Az állítás tagadásának a táblázata úgy kell, hogy kinézzen…
hogy itt mindenhol 0 helyett 1 és 1 helyett pedig 0 van.
Hát, ilyen éppen van…
Csak A-t és B-t is tagadni kellene.
Ha esetleg elsőre ez kicsit zavarosnak tűnik, az teljesen normális...
Nézzük meg szépen lépésről lépésre, és minden ki fog derülni.
Az állítás tagadásában tehát „vagy”-nak kell lennie…
És úgy fog stimmelni a táblázat, ha külön-külön A-t és B-t is tagadjuk.
Valahogy így:
Az ég nem kék vagy a fű nem zöld.
Lássuk a táblázatot.
Úgy tűnik ez meg is van.
A táblázat utolsó oszlopában minden épp a fordítottja lett annak, ami eredetileg volt.
Ez tehát valóban az eredeti állítás tagadása.
Végül nézzünk meg még egyet.
Ha az ég kék, akkor a fű zöld.
Megint megnézzük a táblázatot…
és keresünk egy ezzel ellentéteset.
Ami itt 0 volt…
az ebben 1.
Most hasonlítsuk össze ezt a két sort.
Csak a B-nél van változás, így most csak a B-t kell tagadni.
Az eredeti állítás tagadásában tehát „és” fog szerepelni és 
.
Az ég kék és a fű nem zöld.
Az utolsó oszlop épp a fordítottja annak, mint ami eredetileg volt.
Ez tehát az állítás tagadása.
Most pedig őrülten izgalmas dolgokat fogunk csinálni.
Elkészítjük néhány állítás igazságtáblázatát.
Épp itt is van az első:
edu10
Hát, ez kész is.
És ami azt illeti, élénken emlékeztet az A vagy B tagadására.
Sőt ez maga az A vagy B tagadása.
Hogyha most elkészítenénk az igazságtáblázatát…
akkor az derülne ki, hogy az pedig A és B tagadása.
Lássuk aztán, mi a helyzet ezzel:
Már jön is az igazságtáblázat…
A jelek szerint ez éppen az tagadása.
Az ekvivalencia tagadása pedig ez volna…
Most pedig lássuk, mi a tagadása ennek a nagyon egyszerű mondatnak:
Ha az ég kék, akkor a fű zöld és a mamut piros.
Beazonosítjuk a szereplőket.
És íme, az állítás:
Ez pedig a tagadása…
Hát ez megvolna.
Az ég kék, és a fű nem zöld vagy a mamut nem piros.
Végül vannak itt ezek az állítások:
És készítsük el az igazságtáblázatukat.
Ez a táblázat élénken emlékeztet az ekvivalencia igazságtáblázatára…
Annyira emlékeztet, hogy az is.
A jelek szerint ez éppen A.
Ez leginkább erre emlékeztet…
Egy kis módosítással.
Csodás.
Van itt ez a két láda. Az egyikben arany van, a másik üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
Anélkül, hogy hozzáérnénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
Ha a másik ládában van az arany, akkor mindkét ládán hamis felirat van.
Az arany nem ebben a ládában van.
Kezdjük az első ládán szereplő felirattal.
Ez a felirat csak abban az esetben hamis…
ha az arany a másik ládában van…
és nem mindkét ládán van hamis felirat.
Mivel ez a felirat hamis, így a másik ládán lévőnek kell igaznak lennie.
De ez lehetetlen, hiszen az arany abban a ládában van.
Az első ládán lévő felirat tehát nem lehet hamis.
Lássuk, mi van akkor, ha az első ládán a felirat igaz.
Ha az arany mégis a másik ládában van…
akkor ennek a résznek is igaznak kéne lennie.
De ez lehetetlen.
Csak úgy lehet az első ládán igaz felirat, hogy az állítás első fele hamis.
És ekkor a másik láda üres ugyan, de a rajta lévő felirat igaz.
Ezúttal már három láda van. Az egyikben arany van, a másik kettő üres, a ládákon lévő feliratok pedig lehetnek igazak vagy hamisak is.
Anélkül, hogy hozzáérnénk a ládákhoz, meg tudjuk-e mondani, hogy melyikben van az arany?
A második ládán a felirat igaz.
Az arany ebben a ládában van és az első ládán a felirat hamis.
Az arany olyan ládában van, amin a felirat hamis.
Az első két láda felirata egy kicsit ellentmond egymásnak.
Az első ládán a felirat biztosan nem lehet igaz.
Így aztán a második ládán is hamis felirat van.
De ennek a második fele igaz…
tehát az első felének mindenképp hamisnak kell lennie.
Most nézzük a harmadik ládát.
Ha ez a felirat hamis, akkor az aranynak olyan ládában kell lennie, amin a felirat igaz.
Csakhogy nincs ilyen láda, mert ebben az esetben mindegyik felirat hamis.
A harmadik láda felirata csak igaz lehet.
És az arany nem lehet ebben a ládában.
Az arany az első ládában van.
Hát, ennyit a ládákról. Most pedig tegyünk egy kört a lovagok és lókötők szigetén.
Ezen a szigeten kétféle ember él, akik külsejük alapján teljesen egyformák.
Csak éppen a lovagok mindig igazat mondanak, a lókötők pedig mindig hazudnak.
Találkozunk két szigetlakóval.
X azt mondja:
Ha Y lovag, akkor én lókötő vagyok.
Y nem mond semmit.
Milyen típusú X és Y?
Kezdjük azzal, hogy mi van akkor, ha X hazudik.
Ez csak úgy lehetséges, ha Y lovag…
és X is lovag.
De ez lehetetlen, hiszen akkor X nem hazudhat.
X-nek mindenképpen igazat kell mondania.
X tehát lovag.
És Y nem lehet lovag…
mert akkor X-nek lókötőnek kéne lennie.
Vagyis Y lókötő.
Egy másik alkalommal három szigetlakóval találkozunk, akik ezt mondják:
X: Y lókötő és Z lovag.
Y: Lókötő vagyok és Z lovag.
Milyen típusú X, Y és Z?
Kezdjük azzal, hogy lovag ilyet nem mondhat…
Y tehát biztosan lókötő, mivel pedig az állítás első fele igaz…
a második felének mindenképpen hamisnak kell lennie.
Eddig tehát ott tartunk, hogy Y és Z is lókötő.
Ez azt jelenti, hogy X hazudik.
Így aztán X is lókötő.
Egy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
Kezdjük azzal a lehetőséggel, hogy Y hazudik.
Ekkor annak a résznek is hazugságnak kell lenni, hogy lókötő vagyok.
De az a rész éppen igaz, ez tehát ellentmondás.
Y csak lovag lehet, és így ez a rész biztosan igaz.
És a jelek szerint X is igazat mond.
Vagyis mindhárman lovagok.
Végül egy újabb esetben ismét három szigetlakóval találkozunk, akik ezt mondják:
Ha X igazat mond és Y lovag…
akkor X-nek lókötőnek kéne lennie.
Ez ellentmondás.
X tehát hazudik, így X és Y is lókötő.
Hogyha Y lókötő, akkor neki is hazudnia kell, de mivel az állítás első fele igaz…
a második fele nem lehet igaz.
Tehát Z-nek lókötőnek kell lennie.
