Logika A Hry

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-08-25 04:38

Vstupní navigace

• Obsah příspěvku
• Bibliografie
• Akademické nástroje
• Náhled PDF přátel
• Informace o autorovi a citaci
• Zpět na začátek

Logika a hry

Poprvé publikováno Pá 27. července 2001; věcná revize Pá 16. srpna 2019

Hry mezi dvěma hráči, druhu, kde jeden hráč vyhraje a jeden prohraje, se během druhé poloviny dvacátého století staly běžným nástrojem mnoha odvětví logiky. Důležitými příklady jsou sémantické hry používané k definování pravdy, hry tam a zpět používané k porovnání struktur a hry dialogu k vyjádření (a možná i vysvětlení) formálních důkazů.

• 1. Hry v historii logiky
• 2. Logické hry
• 3. Sémantické hry pro klasickou logiku
• 4. Sémantické hry s nedokonalými informacemi
• 5. Sémantické hry pro další logiku
• 6. Back-and-Forth hry

• 7. Další modelové teoretické hry

  • 7.1 Vynucené hry
  • 7.2 Hry typu „cut-and-select“
  • 7.3 Hry na stromě dvou nástupnických funkcí
• 8. Hry dialogu, komunikace a důkazu

• Bibliografie

  • Hry v historii logiky
  • Hry pro výuku logiky
  • Logické hry
  • Sémantické hry pro klasickou logiku
  • Sémantické hry s nedokonalými informacemi
  • Sémantické hry pro další logiku
  • Back-and-Forth hry
  • Další modelové teoretické hry
  • Hry dialogu, komunikace a důkazu
• Akademické nástroje
• Další internetové zdroje
• Související záznamy

1. Hry v historii logiky

Propojení mezi logikou a hrami jde dlouhou cestu. Pokud někdo uvažuje o debatě jako o nějaké hře, pak už Aristoteles navázal spojení; jeho spisy o syllogismu jsou úzce propojeny s jeho studiem cílů a pravidel debatování. Aristotelovo hledisko přežilo do společného středověkého jména pro logiku: dialektika. V polovině dvacátého století Charles Hamblin oživil spojení mezi dialogem a pravidly řádného usuzování, brzy poté, co Paul Lorenzen propojil dialog s konstruktivními základy logiky.

Mezi hrami a výukou existuje úzká vazba. Spisovatelé po celé středověké období hovoří o dialogech jako o způsobu „výuky“nebo „testování“použití rozumných úvah. Máme alespoň dvě učebnice logiky od počátku šestnáctého století, které ji představují jako hru pro jednotlivého studenta, a hra Lewica Carrolla The Game of Logic (1887) je dalším příkladem stejného žánru. Existuje také spousta moderních příkladů, i když pravděpodobně neexistovala dostatečná kontinuita, která by odůvodňovala mluvení o tradici výuky logiky hrami.

Teorie matematické hry byla založena na počátku dvacátého století. Ačkoli až do padesátých let se neobjevily žádné matematické vazby s logikou, je překvapující, kolik z prvních průkopníků teorie her je známo i díky jejich příspěvkům k logice: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo a další. V roce 1953 David Gale a Frank Stewart vytvořili plodné propojení mezi teorií množin a hrami. Krátce nato Leon Henkin navrhl způsob, jak pomocí her dát sémantiku pro infinitární jazyky.

První polovina dvacátého století byla obdobím zvyšující se přísnosti a profesionality v logice a pro většinu logiků toho období by se použití her v logice pravděpodobně zdalo zbytečné. Iniciativa LEJ Brouwer tento postoj vyjádřila, když obvinil své odpůrce z toho, že způsobil, že se matematika „zvrhla do hry“(jak ho David Hilbert citoval v roce 1927, citován v van Heijenoort 1967). Hermann Weyl (citovaný v Mancosu 1998) použil pojem her k vysvětlení Hilbertovy metamatematiky: matematické důkazy postupují jako hry bezvýznamné hry, ale můžeme stát mimo hru a položit na ni smysluplné otázky. Wittgensteinovy jazykové hry vyvolaly jen malou odezvu logiků. Ve druhé polovině století se však těžiště logického výzkumu posunulo od základů k technikám,a od asi 1960 her bylo více a více používáno v logických novinách.

Začátkem 21. století začalo být všeobecně přijímáno, že hry a logika spolu jdou. Výsledkem bylo obrovské rozšíření nových kombinací logiky a her, zejména v oblastech, kde se používá logika. Mnoho z těchto nových vývojů pocházelo původně z práce v čisté logice, i když dnes sledují své vlastní programy. Jednou z takových oblastí je teorie argumentů, kde hry tvoří nástroj pro analýzu struktury debat.

Níže se soustředíme na ty hry, které jsou nejužší spojeny s čistou logikou.

2. Logické hry

Z pohledu teorie her nejsou hlavní hry, které logici studují, vůbec typické. Normálně se účastní pouze dva hráči, často mají nekonečnou délku, jediné výsledky vyhrávají a prohrávají a žádné akce ani výsledky nejsou spojeny s pravděpodobností. Nejmenší náležitosti logické hry jsou následující.

Existují dva hráči. Obecně je můžeme nazvat (forall) a (existuje). Výslovnosti „Abelard“a „Eloise“sahají až do poloviny osmdesátých let a užitečně opravují hráče jako muže a ženy, což usnadňuje odkaz: její pohyb, jeho pohyb. Ostatní jména se běžně používají pro hráče v konkrétních typech logické hry.

Hráči hrají výběrem prvků sady (Omega), které se nazývají doménou hry. Jak si vyberou, sestaví sekvenci

[a_0, a_1, a_2, / ldots)

prvků (Omega). Nekonečné posloupnosti prvků (Omega) se nazývají hry. Konečné posloupnosti prvků (Omega) se nazývají pozice; zaznamenávají, kam se hra mohla dostat do určité doby. Funkce (tau) (funkce otočení nebo funkce hráče) vezme každou pozici (mathbf {a}) na (existuje) nebo (forall); pokud (tau (mathbf {a}) = / existuje), znamená to, že když hra dosáhla (mathbf {a}), hráč (existuje) provede další volbu (a podobně) s (forall)). Pravidla hry definují dvě sady (W _ { forall}) a (W _ { existuje}) sestávající z pozic a her, s následujícími vlastnostmi: pokud pozice (mathbf {a}) je v (W _ { forall}), pak je to jakákoli hra nebo delší pozice, která začíná na (mathbf {a}) (a podobně s (W _ { existuje}));a žádná hra není v (W _ { forall}) ani (W _ { existuje}). Říkáme, že hráč (forall) vyhraje hru (mathbf {b}) a že (mathbf {b}) je výhra pro (forall), pokud (mathbf {b}) je v (W _ { forall}); Pokud je nějaká pozice (mathbf {a}), která je počátečním segmentem (mathbf {b}), v (W _ { forall}), pak řekneme, že hráč (forall) již vyhrál na (mathbf {a}). (A podobně s (existuje) a (W _ { existuje}).) Souhrnně řečeno, logická hra je čtyřčlenná ((Omega, / tau), (W_) { forall}), (W _ { existuje})) s právě popsanými vlastnostmi.pak říkáme, že hráč (forall) vyhrává již na (mathbf {a}). (A podobně s (existuje) a (W _ { existuje}).) Souhrnně řečeno, logická hra je čtyřčlenná ((Omega, / tau), (W_) { forall}), (W _ { existuje})) s právě popsanými vlastnostmi.pak říkáme, že hráč (forall) vyhrává již na (mathbf {a}). (A podobně s (existuje) a (W _ { existuje}).) Souhrnně řečeno, logická hra je čtyřčlenná ((Omega, / tau), (W_) { forall}), (W _ { existuje})) s právě popsanými vlastnostmi.

Říkáme, že logická hra je úplná, pokud je každá hra buď v (W _ { forall}) nebo (W _ { existuje}), takže nejsou žádné remízy. Pokud nikdo neučiní výslovnou výjimku, logické hry se vždy považují za úplné. (Nezaměňujte to, že jste totální, s mnohem silnějším majetkem určování - viz níže.)

Výše uvedená definice předpokládá, že hra bude pokračovat až do nekonečna, a to i v případě, že hráč vyhrál na určité konečné pozici, a to pouze pro matematické pohodlí; neexistuje zájem o nic, co se stane poté, co hráč vyhraje. Mnoho logických her má tu vlastnost, že v každé hře jeden z hráčů již vyhrál na nějaké konečné pozici; hry tohoto druhu jsou považovány za opodstatněné. Ještě silnější podmínkou je, že existuje nějaké konečné číslo (n), takže v každé hře již jeden z hráčů vyhrál na pozici (n) - té; v tomto případě říkáme, že hra má konečnou délku.

Strategie pro hráče je soubor pravidel, která přesně popisují, jak by si měl hráč zvolit, v závislosti na tom, jak si oba hráči vybrali při dřívějších tahech. Matematicky, strategie pro (forall) sestává z funkce, která vezme každou pozici (mathbf {a}) s (tau (mathbf {a}) = / forall) k elementu (b) z (Omega); považujeme to za instrukci k (forall) zvolit (b), když hra dosáhne pozice (mathbf {a}). (Podobně se strategií pro (existuje).) Strategie pro hráče se považuje za vítěznou, pokud tento hráč vyhraje každou hru, ve které používá strategii, bez ohledu na to, co druhý hráč dělá. Nejvýše jeden z hráčů má vítěznou strategii (protože jinak by hráči mohli hrát své výherní strategie proti sobě a oba by vyhráli,v rozporu s tím, že (W _ { forall}) a (W _ { existuje}) nemají společné hry). Občas se setkáváme se situacemi, ve kterých se zdá, že dva hráči mají výherní strategie (například v nutných hrách níže), ale podrobnější prohlídka ukazuje, že oba hráči ve skutečnosti hrají různé hry.

Hra se považuje za určenou, pokud jeden nebo druhý z hráčů má vítěznou strategii. Existuje mnoho příkladů her, které nejsou určeny, jak Gale a Stewart ukázali v roce 1953 pomocí axiomu výběru. Tento objev vedl k důležitým aplikacím pojmu determinace v základech teorie množin (viz záznam o velkých kardinálech a determinaci). Gale a Stewart se také ukázali jako důležitá věta, která nese jejich jméno: Určuje se každá opodstatněná hra. Z toho vyplývá, že každá hra s konečnou délkou je určena - což je Zermelo známo již v roce 1913. (Přesnější vyjádření Gale-Stewartovy věty je toto. Hra (G) je označena jako uzavřená, pokud () existuje) vyhrává každou hru (G), ve které se neztratila na žádné konečné pozici. Věta říká, že každá uzavřená hra je určena. Důkaz věty je v zásadě jednoduchý: Nazvěme pozici, která vyhrává pro (forall), má-li od této pozice vítěznou strategii. Předpokládejme, že (forall) nemá ve hře výherní strategii, to znamená, že na začátku pozice nevyhrává pro (forall). Pokud je prvním tahem tah (forall), pozice mu po jeho tahu stále nevyhraje. Pokud první tah je tahem (existuje), musí mít tah, po kterém pozice stále nevyhraje za (forall), jinak by předchozí pozice vyhrála za (forall)). Hra pokračuje tímto způsobem nekonečně mnoho pohybů pozicemi, které nevyhrávají pro (forall). Protože je hra uzavřena, (existuje) vyhrává.)Předpokládejme, že (forall) nemá ve hře výherní strategii, to znamená, že na začátku pozice nevyhrává pro (forall). Pokud je prvním tahem tah (forall), pozice mu po jeho tahu stále nevyhraje. Pokud první tah je tahem (existuje), musí mít tah, po kterém pozice stále nevyhraje za (forall), jinak by předchozí pozice vyhrála za (forall)). Hra pokračuje tímto způsobem nekonečně mnoho pohybů pozicemi, které nevyhrávají pro (forall). Protože je hra uzavřena, (existuje) vyhrává.)Předpokládejme, že (forall) nemá ve hře výherní strategii, to znamená, že na začátku pozice nevyhrává pro (forall). Pokud je prvním tahem tah (forall), pozice mu po jeho tahu stále nevyhraje. Pokud první tah je tahem (existuje), musí mít tah, po kterém pozice stále nevyhraje za (forall), jinak by předchozí pozice vyhrála za (forall)). Hra pokračuje tímto způsobem nekonečně mnoho pohybů pozicemi, které nevyhrávají pro (forall). Protože je hra uzavřena, (existuje) vyhrává.)Pokud první tah je tahem (existuje), musí mít tah, po kterém pozice stále nevyhraje za (forall), jinak by předchozí pozice vyhrála za (forall)). Hra pokračuje tímto způsobem nekonečně mnoho pohybů pozicemi, které nevyhrávají pro (forall). Protože je hra uzavřena, (existuje) vyhrává.)Pokud první tah je tahem (existuje), musí mít tah, po kterém pozice stále nevyhraje za (forall), jinak by předchozí pozice vyhrála za (forall)). Hra pokračuje tímto způsobem nekonečně mnoho pohybů pozicemi, které nevyhrávají pro (forall). Protože je hra uzavřena, (existuje) vyhrává.)

Stejně jako v klasické teorii her, výše uvedená logická hra slouží jako kůň na oděvy, na který můžeme zavěsit další koncepty. Například je běžné, že existují zákony, které popisují, které prvky (Omega) jsou pro hráče k dispozici při určitém tahu. Přísně toto upřesnění není nutné, protože výherní strategie nejsou ovlivněny, pokud místo toho rozhodneme, že hráč, který poruší zákon, okamžitě prohraje; ale pro mnoho her se tento způsob jejich prohlížení zdá nepřirozený. Níže uvidíme některé další zvláštní funkce, které lze přidat do her.

Definice hry a strategie výše byly čistě matematické. Vynechali tedy, co je pravděpodobně nejdůležitější vlastností her, a to, že je lidé hrají (alespoň metaforicky). Hráči si kladou za cíl vyhrát a studováním strategií, které jsou jim otevřeny, studujeme, jaké chování je pro člověka s konkrétním cílem racionální. Ve většině her existuje několik hráčů, takže můžeme studovat, co je racionální reakcí na chování někoho jiného. Omezením pohybů hráčů a možných strategií můžeme studovat omezenou racionalitu, kde agent musí činit racionální rozhodnutí za podmínek omezené informace, paměti nebo času.

Stručně řečeno, hry se používají pro modelování racionality a omezené racionality. To je nezávislé na jakémkoli spojení s logikou. Některé logiky však byly navrženy pro studium aspektů racionálního chování a v posledních letech je stále běžnější spojovat tyto logiky s vhodnými hrami. Viz oddíl 5 („Sémantické hry pro další logiku“) a jeho bibliografie.

Až donedávna však byly logické hry spojeny s racionálním chováním úplně jinak. Na povrchu dotyčná logika neměla přímou souvislost s chováním. Logici a matematici si však všimli, že některé nápady by mohly být intuitivnější, kdyby byly spojeny s možnými cíli. Například v mnoha aplikacích logických her je ústředním pojmem vítězná strategie hráče (existuje). Tyto strategie (nebo jejich existence) se často ukážou jako ekvivalent něčeho logického významu, který by mohl být definován bez použití her - například důkazu. Hry se však cítí lépe definovány, protože doslova poskytují určitou motivaci: (existuje) se snaží vyhrát.

To vyvolává otázku, která není matematicky příliš zajímavá, ale měla by se týkat filozofů, kteří používají logické hry. Pokud chceme, aby motivace (existuje) ve hře (G) měla nějakou vysvětlující hodnotu, musíme pochopit, čeho se dosáhne, pokud (existuje) zvítězí. Zejména bychom měli být schopni vyprávět realistický příběh o situaci, ve které se nějaký agent zvaný (existuje) pokouší udělat něco srozumitelného a dělat to je to samé jako vyhrát ve hře. Jak řekl Richard Dawkins, vznesl odpovídající otázku pro evoluční hry Maynard Smith,

Celým účelem našeho hledání … je najít vhodného herce, který by hrál hlavní roli v našich metaforách účelu. Chceme … říci: „Je to pro dobro…“. Naším úkolem v této kapitole je správný způsob, jak tuto větu dokončit. (Rozšířený fenotyp, Oxford University Press, Oxford 1982, strana 91.)

Budeme-li se chtít v budoucnu zmínit, nazveme to Dawkinsovou otázkou. V mnoha druzích logické hry se ukázalo být mnohem těžší odpovědět, než si uvědomili průkopníci těchto her. (Marion 2009 dále diskutuje o Dawkinsově otázce.)

3. Sémantické hry pro klasickou logiku

Na počátku třicátých let Alfred Tarski navrhl definici pravdy. Jeho definice spočívala v nezbytné a dostatečné podmínce, aby věta v jazyce typické formální teorie byla pravdivá; jeho nezbytná a dostatečná podmínka používala pouze pojmy syntaxe a teorie množin, spolu s primitivními pojmy dané formální teorie. Ve skutečnosti Tarski definoval obecnější vztah 'formulace (phi (x_1, / ldots, x_n)) platí pro elementy (a_1, / ldots, a_n)' Pravda o větě je zvláštní případ, kde (n = 0). Například otázka, zda

'Pro všechny (x) existuje (y), takže R ((x, y))' je true

redukuje na otázku, zda platí následující:

Pro každý objekt (a) je věta 'Existuje (y) taková, že R ((a, y))' je pravda.

To se zase sníží na:

Pro každý objekt (a) existuje objekt (b) takový, že věta 'R ((a, b))' je pravdivá.

V tomto příkladu je to tak daleko, jak nás definice Tarského pravdy vezme.

Na konci padesátých let si Leon Henkin všiml, že můžeme intuitivně porozumět některým větám, které Tarskova definice neumí zvládnout. Vezměme si například nekonečně dlouhou větu

Pro všechny (x_0) existuje (y_0) takové, že pro všechny (x_1) existuje (y_1) takové, že… R ((x_0, y_0, x_1, y_1, / ldots)).

Tarskiho přístup selhává, protože řetězec kvantifikátorů na začátku je nekonečný a my bychom nikdy nedosáhli konce jejich odstranění. Místo toho, navrhl Henkin, měli bychom zvážit hru, kde si osoba (forall) vybere objekt (a_0) pro (x_0), pak druhá osoba (existuje) vybere objekt (b_0) pro (y_0), poté (forall) vybere (a_1) pro (x_1, / existuje) vybere (b_1) pro (y_1) atd. Hra této hry je vítězstvím pro (existuje), a to pouze tehdy, pokud je nekonečná atomová věta

) R (a_0, b_0, a_1, b_1, / ldots))

je pravda. Původní věta platí, pouze pokud hráč (existuje) má pro tuto hru výherní strategii. Přísně Henkin použil hru pouze jako metaforu a pravdivou podmínkou, kterou navrhl, bylo, že skolemizovaná verze věty je pravdivá, tj. Že existují funkce (f_0, f_1, / ldots) takové, že pro každou volbu (a_0, a_1, a_2) atd. máme

) R (a_0, f_0 (a_0), a_1, f_1 (a_0, a_1), a_2, f_2 (a_0, a_1, a_2), / ldots).)

Tato podmínka se však okamžitě projeví v jazyce her; Skolemovy funkce (f_0) atd. definují vítěznou strategii pro (existuje) a řeknou jí, jak si vybrat na základě dřívějších voleb pomocí (forall). (Někdy později vyšlo najevo, že CS Peirce již navrhl vysvětlit rozdíl mezi „každým“a „některým“, pokud jde o to, kdo si vybere předmět; například ve své druhé přednášce v Cambridge Conference z roku 1898.)

Brzy po Henkinově práci Jaakko Hintikka dodal, že stejný nápad platí i pro spojky a disjunkce. Spojku '(phi / wedge / psi)' můžeme považovat za univerzálně kvantifikovaný výrok vyjadřující Každá z vět / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ forall) vybrat jednu z vět. Jak uvedla Hintikka, při hraní hry (G (phi / wedge / psi), / forall) se rozhodne, zda má hra pokračovat jako (G (phi)) nebo jako (G (psi))). Podobně se disjunkce stanou existenciálně kvantifikovanými výroky o sadách vět a označují pohyby, kde hráč (existuje) si vybere, jak má hra pokračovat. Aby kvantifikátory uvedli do stejného stylu, navrhl, aby hra (G (forall x / phi (x))) pokračovala takto: hráč (forall) vybere objekt a poskytne jméno (a) pro to,a hra pokračuje jako (G (phi (a))). (A podobně s existenciálními kvantifikátory, kromě toho, že si vybere (existuje).) Hintikka také podal geniální návrh na zavedení negace. Každá hra G má dvojí hru, která je stejná jako G s tou výjimkou, že hráči (forall) a (existuje) jsou transponováni jak do pravidel pro hraní, tak do pravidel pro vítězství. Hra (G (neg / phi)) je dvojnásobkem (G (phi))).

Jeden může dokázat, že pro každou větu prvního řádu (phi), interpretovanou v pevné struktuře (A), má hráč (existuje) vítěznou strategii pro Hintikkovu hru (G (phi)) pokud a pouze pokud (phi) platí v (A) ve smyslu Tarski. Zajímavé jsou dva rysy tohoto důkazu. Zaprvé, pokud (phi) je věta prvního řádu, pak hra (G (phi)) má konečnou délku, a tak nám Gale-Stewartova věta říká, že je určena. Z toho usuzujeme, že (existuje) má výherní strategii přesně v jedné z (G (phi)) a její dvojí; takže má vítěznou strategii v (G (neg / phi)), pokud a pouze pokud ji nemá v (G (phi))). To se stará o negaci. A za druhé, pokud (existuje) má výherní strategii pro každou hru (G (phi (a))), pak po výběru jedné takové strategie (f_a) pro každou (a),může je spojit do jedné výherní strategie pro (G (forall x / phi (x))) (konkrétně: 'Počkejte a uvidíme, jaký prvek (a / forall) vybere, pak zahrajte (f_a) '). Tím je zajištěna doložka pro univerzální kvantifikátory; ale argument používá axiom volby a ve skutečnosti není těžké vidět, že tvrzení, že Hintikkovy a Tarskiho definice pravdy jsou rovnocenné, je samo o sobě ekvivalentem axiomu volby (vzhledem k ostatním axiomům teorie množin Zermelo-Fraenkel).a ve skutečnosti není těžké pochopit, že tvrzení, že Hintikkovy a Tarské definice pravdy jsou rovnocenné, je samo o sobě ekvivalentem axiomu výběru (vzhledem k ostatním axiomům teorie množin Zermelo-Fraenkel).a ve skutečnosti není těžké pochopit, že tvrzení, že Hintikkovy a Tarské definice pravdy jsou rovnocenné, je samo o sobě ekvivalentem axiomu výběru (vzhledem k ostatním axiomům teorie množin Zermelo-Fraenkel).

Je záhadné, že zde máme dvě teorie, kdy je věta pravdivá, a teorie nejsou rovnocenné, pokud selže axiom volby. Ve skutečnosti důvod není příliš hluboký. Axiom volby není nutný, protože definice Hintikka používá hry, ale proto, že předpokládá, že strategie jsou deterministické, tj. Že se jedná o funkce s jednou hodnotou, které uživateli nedávají na výběr. Přirozenější způsob, jak převést Tarskiho definici do herních podmínek, je použití nedeterministických strategií, někdy nazývaných kvazistorie (podrobnosti viz Kolaitis 1985). (Hintikka 1996 však trvá na tom, že správný výklad „pravdivého“je ten, který používá deterministické strategie, a že tato skutečnost ospravedlňuje axiom volby.)

Počítačové implementace těchto her Hintikky se ukázaly jako velmi efektivní způsob výuky významů vět prvního řádu. Jeden takový balíček navrhli Jon Barwise a John Etchemendy ve Stanfordu, nazvaný 'Tarski's World'. Nezávisle další tým na univerzitě v Omsku vytvořil ruskou verzi pro použití ve školách pro nadané děti.

V publikované verzi jeho přednášek Johna Lockeho v Oxfordu vznesla Hintikka v roce 1973 otázku Dawkins (viz výše) pro tyto hry. Jeho odpověď byla, že bychom se měli dívat na Wittgensteinovy jazykové hry, a jazykové hry pro pochopení kvantifikátorů jsou ty, které se točí kolem hledání a nálezu. V odpovídajících logických hrách by člověk měl myslet na (existuje) jako na sebe a (forall) jako na nepřátelskou přírodu, na kterou se nikdy nemůžeme spolehnout při prezentaci objektu, který chci; takže pro jistotu, že ji najdete, potřebuji vítěznou strategii. Tento příběh nebyl nikdy velmi přesvědčivý; motivace přírody není relevantní a nic v logické hře neodpovídá hledání. Ve zpětném pohledu je trochu zklamáním, že nikdo neměl problém hledat lepší příběh. Může být užitečnější myslet na vítěznou strategii pro (existuje) v (G (phi)) jako druh důkazu (ve vhodném infinitárním systému), že (phi) je pravda.

Později Jaakko Hintikka rozšířil myšlenky této sekce ve dvou směrech, a to na sémantiku přirozeného jazyka a na hry nedokonalých informací (viz další část). Název Game-Theoretic Semantics, zkrátka GTS, se používá pro pokrytí obou těchto rozšíření.

Hry popsané v této části se téměř triviálně přizpůsobují mnoha třídící logice: například kvantifikátor (forall x _ { sigma}), kde (x _ { sigma}) je proměnná řazení (sigma), je instrukce pro hráče (forall) k výběru prvku řazení (sigma). To nám okamžitě dává odpovídající hry pro logiku druhého řádu, pokud uvažujeme o prvcích struktury jako o jednom druhu, o sadách prvků jako o druhém druhu, o binárních vztazích jako o třetině atd. Z toho vyplývá, že pro většinu zobecněných kvantifikátorů máme zcela běžně pravidla hry; najdeme je nejprve převedením zobecněných kvantifikátorů do logiky druhého řádu.

4. Sémantické hry s nedokonalými informacemi

V této a následující části se podíváme na některé přizpůsobení sémantických her předchozí sekce jiné logice. V našem prvním příkladu byla vytvořena logika (logika nezávislosti Hintikka a Sandu 1997, nebo stručně IF logika), aby vyhovovala hře. Podrobnější popisy této logiky najdete v logice týkající se logiky nezávislosti a Mann, Sandu a Sevenster 2011.

Hry jsou stejné jako v předchozí sekci, kromě toho, že upustíme od předpokladu, že každý hráč zná předchozí historii hry. Můžeme například požadovat, aby hráč provedl výběr, aniž by věděl, jaké volby udělal druhý hráč při určitých dřívějších tahech. Klasickým způsobem, jak to zvládnout v rámci teorie her, je omezit strategie hráčů. Můžeme například požadovat, aby strategická funkce, která říká (existuje), co dělat v určitém kroku, byla funkce, jejíž doménou je rodina možných voleb (forall) při jeho prvním a druhém tahu; to je způsob, jak vyjádřit, že (existuje) neví, jak se (forall) rozhodl při svém třetím a pozdějším tahu. Hry s takovými omezeními na strategické funkce jsou považovány za nedokonalé informace,na rozdíl od her dokonalých informací v předchozí části.

Abychom vytvořili logiku, která vyhovuje těmto hrám, používáme stejný jazyk prvního řádu jako v předchozí části, kromě toho, že k některým kvantifikátorům (a možná i některým spojivům) je přidána notace, abychom ukázali, že Skolem funguje pro tyto kvantifikátory (nebo spojovací prvky) jsou nezávislé na určitých proměnných. Například věta

[(forall x) (existuje y / / forall x) R (x, y))

se čte jako: „Pro každé (x) existuje (y), nikoli v závislosti na (x), takže (R (x, y))”).

K rozlišování mezi dokonalými a nedokonalými informacemi je třeba učinit tři důležité poznámky. První je, že Gale-Stewartova věta platí pouze pro hry dokonalých informací. Předpokládejme například, že (forall) a (existuje) hrají následující hru. Nejprve (forall) vybere jedno z čísel 0 a 1. Potom (existuje) vybere jedno z těchto dvou čísel. Hráč (existuje) vyhrává, pokud jsou dvě vybraná čísla stejná, jinak vyhraje hráč (forall). Požadujeme, aby (existuje), když se rozhodne, neví, co (forall) vybral; takže Skolemova funkce pro ni bude konstantní. (Tato hra odpovídá výše uvedené větě IF s (R) čtenou jako rovnost, ve struktuře s doménou skládající se z 0 a 1.) Je jasné, že hráč (existuje) nemá konstantní výherní strategii,a také, že hráč (forall) vůbec nemá vítěznou strategii. Tato hra je tedy neurčená, i když její délka je pouze 2.

Jedním z důsledků je, že Hintikkovo ospravedlnění pro čtení negace jako dualizace („hráči vyměňují místa“), ve svých hrách pro logiku prvního řádu, nepřechází do logiky IF. Hintikka odpověděla, že dualizace byla správným intuitivním smyslem negace, a to i v případě prvního řádu, takže není nutné žádné zdůvodnění.

Druhá poznámka je, že již ve hrách s dokonalými informacemi se může stát, že výherní strategie nevyužijí všechny dostupné informace. Například ve hře dokonalých informací, pokud hráč (existuje) má vítěznou strategii, pak má také vítěznou strategii, kde strategické funkce závisí pouze na předchozích volbách (forall). Je to proto, že dokáže rekonstruovat své předchozí kroky pomocí svých dřívějších strategických funkcí.

Když Hintikka použil ve svých hrách Skolem jako strategii pro logiku prvního řádu, učinil strategie pro hráče závislým pouze na předchozích tahech druhého hráče. (Skolemova funkce pro (existuje) závisí pouze na univerzálně kvantifikovaných proměnných.) Protože hry byly hrami dokonalých informací, nedošlo k žádné ztrátě v tomto druhém komentáři výše. Když však přešel na logiku IF, požadavek, aby strategie závisely pouze na tahech druhého hráče, opravdu změnil. Hodges 1997 to ukázal přepracováním notace, takže například ((existuje y / x)) znamená: Existuje (y) nezávislý na (x), bez ohledu na to, který hráč si vybral (x) “.

Nyní zvažte větu

[(forall x) (existuje z) (existuje y / x) (x = y),)

hrál znovu na struktuře se dvěma prvky 0 a 1. Hráč (existuje) může vyhrát následovně. Pro (z) si vybere totéž jako hráč (forall) zvolený pro (x); pak pro (y) vybere to samé, co zvolila pro (z). Tato vítězná strategie funguje pouze proto, že v této hře může (existuje) odkazovat na její předchozí předchozí volby. Neměla by žádnou vítěznou strategii, pokud by třetí kvantifikátor byl ((existuje y / xz)), protože jakákoli Skolemova funkce pro tento kvantifikátor by musela být konstantní. Příkladem jevu signalizace je způsob, jakým (existuje) předává informace sobě odkazem na její předchozí volbu. John von Neumann a Oskar Morgenstern to ilustrovali na příkladu Bridge, kde jeden hráč se skládá ze dvou partnerů, kteří musí sdílet informace pomocí svých veřejných kroků, aby si navzájem signalizovali.

Třetí poznámka je, že existuje narušení mezi intuitivní myšlenkou nedokonalé informace a herně-teoretickou definicí této strategie, pokud jde o strategie. Intuitivně jsou nedokonalé informace skutečností o okolnostech, za kterých se hra hraje, nikoli o strategiích. To je velmi složitá záležitost a stále to vede k nedorozuměním ohledně IF a podobné logiky. Vezměme si například větu

[(existuje x) (existuje y / x) (x = y),)

znovu hrál na struktuře s prvky 0 a 1. Intuitivně by si člověk mohl myslet, že pokud (existuje) si nemůže dovolit vzpomenout si na druhý kvantifikátor toho, co si vybrala na prvním místě, pak může stěží mít vítěznou strategii. Ale ve skutečnosti má velmi snadnou: „Vždy vyberte 0“!

Ve srovnání s logikou prvního řádu chybí v logice IF součást, kterou herní sémantika nedodává. Sémantika hry nám říká, kdy je věta ve struktuře pravdivá. Ale pokud vezmeme vzorec s (n) volnými proměnnými, co vyjadřuje vzorec o uspořádaném (n) - n-tách prvků struktury? V logice prvního řádu by definoval jejich množinu, tj. (N) - ary vztah ke struktuře; definice Tarského pravdy vysvětluje, jak. Existuje podobná definice pro libovolné vzorce IF logiky? Ukazuje se, že existuje jedna pro mírně odlišnou logiku zavedenou Hodgesem 1997 a vede k definici pravdy Tarského pro jazyk této logiky. S malou úpravou lze tuto definici pravdy upravit tak, aby vyhovovala i logice IF. Ale pro obě tyto nové logiky je háček:místo toho, když řekneme, že přiřazení elementů k volným proměnným činí vzorec pravdivým, říkáme, když sada přiřazení elementů k volným proměnným učiní vzorec pravdivým. Väänänen 2007 vytvořil tuto myšlenku jako základ pro celou řadu nových logik pro studium pojmu závislost (viz položka logika závislosti). V této logice je sémantika definována bez her, ačkoli původní inspirace pochází z práce Hintikky a Sandu.

V logice Väänänen je snadné pochopit, proč člověk potřebuje sady úkolů. Má atomový vzorec vyjadřující '(x) je závislé na (y)'. Jak to můžeme interpretovat ve struktuře, například ve struktuře přirozených čísel? Nemá vůbec smysl se ptát například, zda je 8 závislé na 37. Ale pokud máme množinu X uspořádaných párů přirozených čísel, má smysl se ptát, zda v X je první člen každé dvojice závislý na druhý; odpověď Ano by znamenala, že existuje funkce (f) taková, že každá dvojice ((a, b)) v X má tvar ((f (b), b)).

5. Sémantické hry pro další logiku

Struktury následujícího druhu vyvolávají zajímavé hry. Struktura (A) sestává z množiny (S) prvků (které nazýváme státy, s tím, že se často nazývají světy), binárního vztahu (R) na (S) (my musí číst (R) jako šipku) a rodinu (P_1, / ldots, P_n) podmnožin (S). Dva hráči (forall) a (existuje) hrají hru G na (A), počínaje stavem (s), který jim je dán, čtením vhodného logického vzorce (phi) jako soubor pokynů pro hraní a pro vítězství.

Pokud tedy (phi) je (P_i), vyhraje hráč (existuje) najednou, pokud (s) je v (P_i), jinak vyhraje hráč (forall) najednou. Vzorce (psi / wedge / theta, / psi / vee / theta) a (neg / psi) se chovají stejně jako v Hintikkových hrách výše; například (psi / wedge / theta) dá hráči pokyn (forall), aby si vybral, zda bude hra pokračovat jako pro (psi) nebo pro (theta). Pokud vzorec (phi) je (Box / psi), pak hráč (forall) vybere šipku z (s) do stavu (t) (tj. Stát (t) tak, že pár ((s, t)) je ve vztahu (R)) a hra poté pokračuje ze stavu (t) podle pokynů (psi). Pravidlo pro (Diamond / psi) je stejné s tou výjimkou, že hráč (existuje) provede výběr. Nakonec říkáme, že vzorec (phi) je pravdivý v s, pokud hráč (existuje) má výherní strategii pro tuto hru založenou na (phi) a začínající na (s).

Tyto hry se stávají modální logikou velmi podobně jako hry Hintikky jsou v souladu s logikou prvního řádu. Zejména jsou jedním ze způsobů, jak dát sémantiku pro modální logiku, a souhlasí s obvyklou sémantikou Kripkeho typu. Samozřejmě existuje mnoho typů a generalizací modální logiky (včetně úzce souvisejících logik, jako je časová, epistemická a dynamická logika), a proto odpovídající hry přicházejí v mnoha různých formách. Jedním příkladem zájmu je počítačově teoretická logika Matthew Hennessyho a Robina Milnera, která se používá k popisu chování systémů; zde šipky přicházejí ve více než jedné barvě a pohyb po šipce konkrétní barvy představuje provedení určité „akce“pro změnu stavu. Dalším příkladem je výkonnější modální (mu) - počet Dexter Kozen, který má operátory pevných bodů;viz kapitola 5 Stirling 2001.

Jednou z zajímavých vlastností těchto her je, že pokud má hráč od určité pozice vítěznou strategii, pak se tato strategie nikdy nemusí vztahovat k něčemu, co se při hře stalo dříve. Je irelevantní, jaké volby byly učiněny dříve, nebo dokonce kolik kroků bylo odehráno. Máme tedy to, co počítačoví vědci někdy nazývají „pamětní“výherní strategií.

V související „logice her“, kterou navrhl Rohit Parikh, jsou hry, které se pohybují mezi státy, spíše tématem než způsobem, jak definovat pravdu. Tyto hry mají mnoho zajímavých aspektů. V roce 2003 vedl časopis Studia Logica problém, který jim byl věnován, editoval Marc Pauly a Parikh.

Vlivy z ekonomiky a informatiky vedly řadu logiků k použití logiky pro analýzu rozhodování za podmínek částečné ignorace. (Viz například článek o epistemické logice.) Existuje několik způsobů, jak reprezentovat stavy znalostí. Jedním je brát je jako státy nebo světy v takové modální struktuře, kterou jsme zmínili na začátku této sekce. Dalším je použití logiky IF nebo její varianty. Jak tyto přístupy souvisejí? Johan van Benthem 2006 představuje některé myšlenky a výsledky této velmi přirozené otázky. Viz také dokumenty Johan van Benthem, Krister Segerberg, Eric Pacuit a K. Venkatesh a jejich odkazy, v části IV „Logika, agentura a hry“Van Benthem, Gupta a Parikh 2011 a položka o logice pro analýzu her pro ukázka nedávné práce v této oblasti.

6. Back-and-Forth hry

V roce 1930 Alfred Tarski formuloval představu, že dvě struktury (A) a (B) jsou elementárně ekvivalentní, tj. Že v (A) jsou přesně stejné věty prvního řádu stejné jako v (B)). Na konferenci v Princetonu v roce 1946 popsal tuto představu a vyjádřil naději, že bude možné vyvinout teorii této teorie, která bude „tak hluboká jako pojmy izomorfismu atd., Které se nyní používají“(Tarski 1946).

Jedna přirozená část takové teorie by byla čistě strukturální nutnou a dostatečnou podmínkou pro to, aby dvě struktury byly elementárně ekvivalentní. Roland Fraïssé, francouzsko-alžírský, byl první, kdo našel použitelnou nezbytnou a dostatečnou podmínku. O několik let později ji znovu objevil kazašský logik AD Taimanov a z hlediska her přeformuloval polský logik Andrzej Ehrenfeucht. Hry jsou nyní známé jako hry Ehrenfeucht-Fraïssé nebo někdy jako hry „zpět a vpřed“. Ukázalo se, že jsou jedním z nejvšestrannějších nápadů v logice dvacátého století. Plodně se přizpůsobují široké škále logik a struktur.

Ve hře tam a zpět jsou dvě struktury (A) a (B) a dva hráči, kteří se běžně nazývají Spoiler a Duplicator. (Jména jsou způsobena Joelem Spencerem na začátku 90. let. Nedávno Neil Immerman navrhl Samsona a Delilah s použitím stejných iniciál; toto umístí Spoiler jako hráče mužského pohlaví (forall) a Duplicator jako samičku (existuje).) Každý krok ve hře sestává z tahu Spoiler, následovaného tahem Duplicator. Spoiler vybere prvek jedné ze dvou struktur a Duplikátor si pak musí vybrat prvek druhé struktury. Takže po (n) krocích byly vybrány dvě sekvence, jedna z (A) a jedna z (B):

[(a_0, / ldots, a_ {n-1}; b_0, / ldots, b_ {n-1}).)

Tato pozice je pro Spoiler výhrou pouze tehdy, pokud nějaký atomový vzorec (jedné z forem '(R (v_0, / ldots, v_ {k-1})))' nebo '(mathrm {F} (v_0, / ldots, v_ {k-1}) = v_k) 'nebo' (v_0 = v_1) ', nebo některá z nich s různými proměnnými) splňuje ((a_0, / ldots, a_ { n-1})) v (A), ale ne pomocí ((b_0, / ldots, b_ {n-1})) v (B) nebo naopak. Podmínkou pro to, aby Duplicator vyhrál, jsou různé formy hry. V nejjednodušší podobě, (EF (A, B)), je hra pro Duplicator výhrou, pokud a pouze pokud žádná počáteční část není výhrou pro Spoiler (tj. Vyhraje, pokud se neztratila konečná fáze). Pro každé přirozené číslo (m) je hra (EF_m (A, B)); v této hře Duplicator vyhrává po krocích (m) za předpokladu, že se ještě neztratila. Všechny tyto hry určuje Gale-Stewartova věta. O dvou strukturách (A) a (B) se říká, že jsou ekvivalenty tam a zpět, pokud má Duplicator výherní strategii pro (EF (A, B)), a m-ekvivalent, pokud má vítězná strategie pro (EF_m (A, B)).

Jeden může dokázat, že jestliže (A) a (B) jsou (m) - ekvivalentní pro každé přirozené číslo (m), pak jsou elementárně ekvivalentní. Ve skutečnosti, pokud má Eloise výherní strategii (tau) ve hře Hintikka G ((phi)) na (A), kde má vnoření rozsahů kvantifikátoru (phi) většina úrovní m a Duplicator má výherní strategii (varrho) ve hře (EF_m (A, B)), dvě strategie (tau) a (varrho) lze skládat do vítězná strategie Eloise v G ((phi)) na (B). Na druhou stranu lze vítěznou strategii pro Spoiler v (EF_m (A, B)) převést na větu prvního řádu, která platí přesně v jedné z (A) a (B), a ve kterém vnoření rozsahů kvantifikátoru má nejvíce (m) úrovní. Máme tedy nezbytnou a dostatečnou podmínku pro elementární ekvivalenci a ještě něco navíc.

Pokud jsou (A) a (B) ekvivalenty tam a zpět, pak jsou určitě elementárně ekvivalentní; ale ve skutečnosti se zpětná ekvivalence v infinitární logice jeví jako stejná jako elementární ekvivalence, která je mnohem výraznější než logika prvního řádu. Existuje mnoho úprav hry, které dávají jiné druhy rovnocennosti. Například Barwise, Immerman a Bruno Poizat nezávisle popsali hru, ve které oba hráči mají přesně (p) očíslované oblázky; každý hráč musí označit své volby oblázkem a obě volby ve stejném kroku musí být označeny oblázky nesoucími stejné číslo. Jak hra pokračuje, hráčům dojdou oblázky, takže budou muset znovu použít oblázky, které již byly použity. Podmínka pro výhru Spoiler na pozici (a všechny následující pozice) je stejná jako dříve, kromě toho, že se počítají pouze prvky nesoucí štítky v této pozici. Existence výherní strategie pro Duplicator v této hře znamená, že se obě struktury shodují na větách, které používají nejvíce proměnných (p) (což umožňuje, aby se tyto proměnné vyskytly libovolněkrát).

Teorie zpětných a zpětných her používá jen velmi málo předpokladů o dané logice. Výsledkem je, že tyto hry jsou jednou z mála modelových teoretických technik, které se vztahují také na konečné struktury, stejně jako na nekonečné, což je činí jedním ze základních kamenů teoretické informatiky. Lze je použít k měření výrazné síly formálních jazyků, například databázových dotazovacích jazyků. Typický výsledek může například říci, že určitý jazyk nemůže rozlišovat mezi „sudým“a „lichým“; dokázali bychom to tím, že pro každou úroveň (n) složitosti vzorců jazyka najdeme dvojici konečných struktur, pro které má Duplicator výherní strategii v zpětné a čtvrté hře úrovně (n), ale jedna ze struktur má sudý počet prvků a druhá má liché číslo. Sémantici přírodních jazyků shledali, že hry typu back-and-end jsou užitečné pro srovnání expresivních schopností zobecněných kvantifikátorů. (Viz například Peters a Westerståhl 2006, oddíl IV.)

Existuje také jakási hra tam a zpět, která odpovídá naší modální sémantice výše stejným způsobem, jako hry Ehrenfeucht-Fraïssé odpovídají Hintikkově herní sémantice pro logiku prvního řádu. Hráči začínají stavem (s) ve struktuře (A) a stavem (t) ve struktuře (B). Spojler a duplikátor se pohybují střídavě, jako předtím. Pokaždé, když se pohybuje, Spoiler si vybere, zda se má pohybovat v (A) nebo v (B), a pak se Duplicator musí pohybovat v jiné struktuře. Pohyb se vždy provádí posunutím vpřed podél šipky od aktuálního stavu. Pokud se mezi nimi oba hráči právě přestěhovali do stavu (s) ´ v (A) a do stavu (t) ´ v (B), a některé predikáty (P_i) drží na pouze jeden z (s) ´ a (t) ´, pak Duplicator ztratí najednou. Také prohraje, pokud pro ni nejsou k dispozici žádné šipky, které by se mohly pohybovat;ale pokud Spoiler zjistí, že pro něj nejsou k dispozici žádné šipky, které by se pohybovaly po obou strukturách, Duplicator vyhraje. Pokud oba hráči hrají tuto hru s danými počátečními stavy (s) v (A) a (t) v (B) a obě struktury mají jen konečně mnoho stavů, pak lze ukázat, že Duplicator má vítěznou strategii pouze tehdy, pokud stejné modální věty jsou pravdivé v (s) v (A) jako jsou pravdivé v (t) v (B).

Existuje mnoho zobecnění tohoto výsledku, některé z nich zahrnují následující pojem. Nechť (Z) je binární vztah, který uvádí stavy (A) do stavů (B). Pak voláme (Z) bisimulaci mezi (A) a (B), pokud Duplicator může použít (Z) jako nedeterministickou výherní strategii v back-and-end hře mezi (A) a (B), kde první dvojice tahů obou hráčů je zvolit jejich počáteční stavy. V informatice je pojem bisimulace rozhodující pro pochopení systémů (A) a (B) jako systémů; vyjadřuje, že oba systémy interagují se svým prostředím stejným způsobem jako každý jiný, krok za krokem. Trochu předtím, než počítačoví vědci představili tento pojem, se v doktorské práci Johan van Benthema o sémantice modální logiky (1976) objevil v podstatě stejný koncept.

7. Další modelové teoretické hry

Logické hry v této části jsou nástroji matematiků, ale mají některé koncepčně zajímavé funkce.

7.1 Vynucené hry

Vynucené hry jsou také popisovány popisnými teoretiky jako hry Banach-Mazur; viz odkazy Kechris nebo Oxtoby níže pro více informací o matematickém pozadí. Teoretici modelu je používají jako způsob vytváření nekonečných struktur s kontrolovanými vlastnostmi. V nejjednodušším případě (forall) a (exist) zahrajte tzv. Model Existence Game, kde (existuje) tvrdí, že pevná věta (phi) má model, zatímco (forall) prohlašuje, že on může odvodit rozpor od (phi). Na začátku je opravena nespočetně nekonečná množina (C) nových konstantních symbolů (a_0, a_1, a_2) atd. (existuje) brání disjunkci výběrem jednoho disjunktního a existenciálního prohlášení volbou konstanty z (C) jako svědka. (forall) může napadnout spojení výběrem buď spojky,a univerzální prohlášení výběrem libovolného svědka z (C). (existuje) vyhraje, pokud se nehrají žádné protichůdné atomové věty. (existuje) má výherní strategii (vlastnost konzistence je jedním ze způsobů, jak popsat výherní strategii) pouze tehdy, má-li (phi) model. Na druhé straně, pokud (forall) má vítěznou strategii, strom (který může být konečný) všech her proti jeho výherní strategii souvisí s důkazem gentzenského stylu o negaci (phi). Tato metoda analýzy vět úzce souvisí s Bethovou metodou sémantických tabulek a Dialogickou hrou (viz oddíl 8).pokud (forall) má vítěznou strategii, strom (který může být konečný) všech her proti jeho výherní strategii souvisí s důkazem Gentzenova stylu o negaci (phi). Tato metoda analýzy vět úzce souvisí s Bethovou metodou sémantických tabulek a Dialogickou hrou (viz oddíl 8).pokud (forall) má vítěznou strategii, strom (který může být konečný) všech her proti jeho výherní strategii souvisí s důkazem Gentzenova stylu o negaci (phi). Tato metoda analýzy vět úzce souvisí s Bethovou metodou sémantických tabulek a Dialogickou hrou (viz oddíl 8).

Chcete-li načrtnout myšlenku obecné hry Forcing Game, představte si, že nekonečně velký tým stavitelů staví dům (A). Každý stavitel má svůj vlastní úkol: například instalovat koupelnu nebo tapetovat vstupní halu. Každý stavitel má nekonečně mnoho šancí vstoupit na web a přidat do domu určité množství materiálu; tyto sloty pro stavitele jsou prokládány tak, že celý proces probíhá v pořadí kroků počítaných přirozenými čísly.

Abychom ukázali, že dům lze postavit na zakázku, musíme ukázat, že každý stavitel může samostatně plnit svůj úkol bez ohledu na to, co dělají ostatní stavitelé. Představujeme si tedy každého tvůrce jako hráče (existuje) ve hře, kde jsou všichni ostatní hráči spojeni jako (forall), a snažíme se prokázat, že (existuje) má v tomto ohledu vítěznou strategii hra. Když jsme to dokázali pro každého stavitele zvlášť, můžeme si představit, že budou pracovat, každý s vlastní výherní strategií. Všichni vyhrají své hry a výsledkem je jeden krásný dům.

Techničtěji jsou prvky struktury (A) fixovány předem, řekněme jako (a_0, a_1, a_2) atd., Ale vlastnosti těchto prvků musí být vyrovnány hrou. Každý hráč se pohybuje házením do souboru atomových nebo negovaných atomových výroků o prvcích, avšak pouze pod podmínkou, že sada skládající se ze všech dosud hozených příkazů musí být v souladu s pevnou sadou axiomů zapsaných před zápasem. (Takže házení v negované atomové větě (neg / phi) má za následek to, že brání jakémukoli hráči přidat (phi) v pozdějším stádiu.) Na konci společné hry je sada atomových vět vhozený má kanonický model, a to je struktura (A); existují způsoby, jak zajistit, že se jedná o model pevné sady axiomů. O možné vlastnosti P z (A) se říká, že je vykonatelná, pokud tvůrce, kterému je dána úloha, aby P byl z (A), měl vítěznou strategii. Ústředním bodem (hlavně kvůli Ehrenfeuchtovi) je to, že spojení nespočetně nekonečné sady vynutitelných vlastností je opět vynutitelné.

Různé Löwenheim-Skolemovy věty teorie modelů lze dokázat pomocí variant Forcing Game. V těchto variantách nestavíme model, ale submodel daného modelu. Začínáme velkým modelem (M) pro větu (nebo s počitatelným množstvím vět) (phi). Pak vypíšeme podformuláře (phi) a každý hráč má podformulář s volnou proměnnou. Úkolem hráče je zajistit, aby jakmile se ve hře objeví parametry podformuláře a ve velkém modelu je svědek pravdy vzorce, hraje se jeden takový svědek. Po skončení hry byl spočítán submodel (M) tak, aby vyhovoval (phi).

Název „vynucení“pochází z aplikace souvisejících myšlenek Paula Cohena pro konstrukci modelů teorie množin na počátku šedesátých let. Abraham Robinson ji přizpůsobil, aby vytvořil obecnou metodu pro vytváření počitatelných struktur, a Martin Ziegler představil nastavení hry. Později Robin Hirsch a Ian Hodkinson používali související hry k vyřešení některých starých otázek o vztažných algebrách.

Nucené hry jsou zdravým příkladem, který je třeba mít na paměti při přemýšlení o Dawkinsově otázce. Připomínají nám, že v logických hrách nemusí být užitečné myslet na hráče jako proti sobě.

7.2 Hry typu „cut-and-select“

V tradiční hře „cut-and-select“si vezmeš kus dortu a nakrájíš ho na dva menší kousky; pak jsem si vybral jeden z kousků a snědl ho, ten druhý nechám pro tebe. Tento postup má na vás vyvíjet tlak, abyste spravedlivě řezali dort. Matematici, ne zcela pochopení účelu cvičení, trvají na opakování. Tak jsem vás donutil rozřezat kus, který jsem si vybral, na dva, pak jsem si vybral jeden z těchto dvou; pak tento kus znovu nakrájíš a tak dále. Někteří ještě více neobvyklí matematici vás donutí nakrájet dort na nespočetné množství kusů místo dvou.

Tyto hry jsou důležité v teorii definic. Předpokládejme, že máme kolekci (A) objektů a rodinu (S) vlastností; každá vlastnost vyřízne (A) do sady těch objektů, které mají vlastnost a sadu těch, které ji nemají. Nechť (existuje) řez, počínaje celou sadou (A) a používající vlastnost v (S) jako nůž; nechť (forall) vybere jeden z kusů (které jsou podmnožinami (A)) a vrátí ho zpět (existuje), aby se znovu ořízl, ještě jednou pomocí vlastnosti v (S); a tak dále. Nechte (existuje) ztratit, jakmile (forall) vybere prázdný kus. Říkáme, že ((A, S)) má hodnocení nejvýše (m), pokud (forall) má strategii, která zajišťuje, že (existuje) ztratí před ní (m) - tah. Pozice ((A, S)) poskytuje cenné informace o rodině podmnožin (A) definovatelných vlastnostmi v (S).

Varianty této hry, umožňující rozřezat kus na nekonečně mnoho menších kusů, jsou zásadní v oboru teorie modelů zvané teorie stability. Obecně řečeno, teorie je „dobrá“ve smyslu teorie stability, pokud kdykoli vezmeme model (A) teorie a (S) sadu vzorců prvního řádu v jedné volné proměnné s parametry z (A), struktura ((A, S)) má 'malé' pořadí. Jiná variace má vyžadovat, aby se v každém kroku (existuje) rozdělil na dva kousky, které přežily z předchozích kroků, a znovu ztratí, jakmile bude jeden z řezaných fragmentů prázdný. (V této verzi je (forall) nadbytečný.) S touto variantou se hodnost ((A), S) nazývá její Vapnik-Chervonenkisova dimenze; tento pojem se používá v teorii výpočetního učení.

7.3 Hry na stromě dvou nástupnických funkcí

Představte si strom, který byl vybudován v úrovních. Ve spodní úrovni je jediný kořenový uzel, ale z něj vychází levá větev a pravá větev. Na další úrovni jsou dva uzly, jeden na každé větvi az každého z těchto uzlů roste levá větev a pravá větev. Na další úrovni jsou tedy čtyři uzly a opět se větve stromů vlevo a vpravo na každém z těchto uzlů. Pokračuje do nekonečna, tento strom se nazývá strom dvou nástupnických funkcí (jmenovitě levý nástupce a pravý nástupce). Vezmeme-li uzly jako prvky a zavedeme dva funkční symboly pro nástupce vlevo a vpravo, máme strukturu. Silná věta Michaela Rabina říká, že existuje algoritmus, který nám řekne, pro každou monadickou větu druhého řádu (phi) v jazyce vhodném pro tuto strukturu,zda (phi) je ve struktuře pravda. („Monadický druhý řád“znamená, že logika je jako první řád, kromě toho, že můžeme také kvantifikovat přes množiny prvků, ale ne například nad binárními vztahy na prvcích.)

Rabinova věta má mnoho užitečných důsledků. Například Dov Gabbay to použil k prokázání rozhodovatelnosti některých modálních logik. Ale Rabinův důkaz, pomocí automatů, bylo notoricky obtížné sledovat. Yuri Gurevich a Leo Harrington a nezávisle Andrei Muchnik našli mnohem jednodušší důkazy, ve kterých je automat ve hře hráč.

Tento výsledek Rabina je jedním z několika vlivných výsledků, které spojují hry s automaty. Dalším příkladem jsou paritní hry, které se používají k ověření vlastností modálních systémů. Viz například Stirling (2001) kapitola 6; Bradfield a Stirling (2006) diskutuje o paritních hrách pro modální (mu) - počet.

8. Hry dialogu, komunikace a důkazu

Několik středověkých textů popisuje formu debaty nazývané závazky. Byli tam dva protivníci, Opponens a Respondens. Na začátku zasedání se sporní strany dohodly na „pozitivu“, obvykle na nepravdivém prohlášení. Úkolem společnosti Respondens bylo dávat racionální odpovědi na otázky od Opponens a předpokládat pravdivost pozitivu; především se musel vyhnout zbytečnému odporování. Úkolem společnosti Opponens bylo pokusit se donutit Respondens k rozporům. Takže obecně známe odpověď na otázku Dawkins, ale neznáme pravidla hry! Středověké učebnice popisují několik pravidel, kterými by se měli účastníci sporu řídit. Tato pravidla však nejsou stanovenými pravidly hry; jsou to pokyny, které učebnice vycházejí ze zásad řádného odůvodnění pomocí příkladů.(Paul Benátek ospravedlňuje jedno pravidlo praxí „velkých logiků, filozofů, geometrů a teologů“.) Zejména bylo otevřeno učiteli povinností objevit nová pravidla. Tato otevřenost znamená, že povinnosti nejsou v našem smyslu logické hry.

Ne všichni souhlasí s předchozí větou. Například Catarina Dutilh Novaes (2007, 6) podrobně obhajuje názor, že závazky představují „pozoruhodný případ pojmové podobnosti mezi středověkým a moderním teoretickým rámcem“. Ale ať už na tuto otázku přijmeme jakýkoli názor, tyto diskuse inspirovaly jednu důležitou řadu moderního výzkumu v logických hrách.

Představte si, že existuje ústní zkouška z teorie důkazů. Zkoušející jí dá větu a vyzve ji, aby ji začala dokazovat. Pokud má věta podobu

) phi / vee / psi)

pak má právo vybrat si jednu z vět a říci: „Dobře, dokážu tuhle“. (Ve skutečnosti, pokud je zkoušející intuicionista, může trvat na tom, aby si vybrala jednu z vět k prokázání.)

) phi / wedge / psi)

pak examinátor, jako examinátor, by si mohl dobře vybrat jeden ze spojek sám a vyzvat ji, aby to dokázala. Pokud ví, jak prokázat spojení, pak určitě ví, jak prokázat spojku.

Případ (phi / rightarrow / psi) je trochu jemnější. Pravděpodobně bude chtít začít tím, že za předpokladu (phi) vyvodí (psi); ale existuje určité riziko záměny, protože věty, které dosud napsala, jsou všechny věci, které mají být prokázány, a (phi) není věc, kterou je třeba dokázat. Zkoušející jí může pomoci tím, že řekne 'Budu předpokládat (phi), a uvidíme, jestli se odtud dostanete k (psi)'. V tomto okamžiku existuje šance, že vidí způsob, jak se dostat k (psi) odvozením rozporu od (phi); takže může obrátit stoly na zkoušejícího a vyzvat ho, aby prokázal, že jeho předpoklad je konzistentní, s cílem prokázat, že tomu tak není. Symetrie není dokonalá: žádal ji, aby ukázala, že věta je všude pravdivá, zatímco ona ho vyzývá, aby ukázala, že věta je někde pravda. Přesto můžeme vidět jakousi dualitu.

Myšlenky tohoto druhu leží za dialektickými hrami Paula Lorenzena. Ukázal, že s určitým množstvím tlačení a strčení je možné psát pravidla pro hru, která mají vlastnost, že (existuje) má výherní strategii, a to pouze tehdy, pokud věta, kterou je na začátku předložena, je věta intuicionistické logiky. V gestu k středověkým debatám nazýval (existuje) protikladu a druhého hráče protikladu. Téměř jako ve středověkých závazcích vyhraje odpůrce tím, že přivede navrhovatele do bodu, kdy jsou jediným možným pohybem, který má k dispozici, do očí bijící rozpory.

Lorenzen prohlašoval, že jeho hry poskytovaly ospravedlnění jak pro intuicionistickou, tak pro klasickou logiku (nebo podle jeho slov je „gerechtfertigt“, Lorenzen (1961,196)). Bohužel jakékoli „ospravedlnění“zahrnuje přesvědčivou odpověď na Dawkinsovu otázku a toto Lorenzen nikdy neposkytl. Například hovořil o pohybech jako o „útocích“, i když (jako výběr zkoušejícího ve výše uvedeném bodě (phi / wedge / psi)) vypadají spíše jako pomoc než nepřátelství.

Vstupní dialogová logika poskytuje plnější přehled Lorenzenových her a řadu novějších variant. Ve své současné podobě (leden 2013) obchází Lorenzenova tvrzení o ospravedlnění logiky. Místo toho popisuje hry jako poskytování sémantiky pro logiku (bod, s kterým by Lorenzen jistě souhlasil), a dodává, že pro pochopení rozdílů mezi logikou může být užitečné porovnat jejich sémantiku.

Z tohoto pohledu stojí Lorenzenovy hry jako důležité paradigma toho, co nedávní teoretici důkazů nazvali sémantikou důkazů. Sémantika důkazů dává „smysl“nejen myšlence prokazatelnosti, ale každému jednotlivému kroku důkazu. Odpovídá na otázku „čeho dosáhneme tím, že tento konkrétní krok provedeme v důkazu?“Během devadesátých let řada pracovníků na logickém konci výpočetní techniky hledala hry, které by obstály v lineární logice, a některé další systémy důkazů stejným způsobem, jako Lorenzenovy hry, stály na intuicionistické logice. Andreas Blass, později Samson Abramsky a jeho kolegové, dali hry, které odpovídaly částem lineární logiky, ale v době psaní zatím nemáme dokonalou souvislost mezi hrou a logikou. Tento příklad je obzvláště zajímavý, protože odpověď na otázku Dawkins by měla poskytnout intuitivní výklad zákonů lineární logiky, což tato logika velmi potřebovala. Hry Abramsky et al. vyprávět příběh o dvou vzájemně se ovlivňujících systémech. Ale zatímco začal s hrami, ve kterých se hráči zdvořile střídali, Abramsky později umožnil hráčům jednat „distribuovaným, asynchronním způsobem“, přičemž si navzájem všímali, pouze když se rozhodli. Tyto hry již nejsou v normálním formátu logických her a jejich interpretace v reálném životě vyvolává řadu nových otázek. Ale zatímco začal s hrami, ve kterých se hráči zdvořile střídali, Abramsky později umožnil hráčům jednat „distribuovaným, asynchronním způsobem“, přičemž si navzájem všímali, pouze když se rozhodli. Tyto hry již nejsou v normálním formátu logických her a jejich interpretace v reálném životě vyvolává řadu nových otázek. Ale zatímco začal s hrami, ve kterých se hráči zdvořile střídali, Abramsky později umožnil hráčům jednat „distribuovaným, asynchronním způsobem“, přičemž si navzájem všímali, pouze když se rozhodli. Tyto hry již nejsou v normálním formátu logických her a jejich interpretace v reálném životě vyvolává řadu nových otázek.

Giorgi Japaridze navrhl pro studii výpočtů „logiku počítatelnosti“. Jeho syntaxe je logika prvního řádu s některými dalšími položkami připomínajícími lineární logiku. Jeho sémantika se týká sémantických her s některými neobvyklými rysy. Například není vždy určeno, který hráč provede další tah. Pojetí strategických funkcí již není pro popis hráčů dostatečné; místo toho Japaridze popisuje způsoby čtení druhého hráče (hráče (existuje) v naší notaci) jako druhu výpočetního stroje. Další informace jsou na jeho webových stránkách.

Další skupinou her stejné obecné rodiny jako Lorenzenovy jsou zkušební hry Pavla Pudlak 2000. Zde je odpůrce (zvaný Prover) v roli právníka u soudu, který ví, že navrhovatel (zvaný protivník) je vinu za urážku. Navrhovatel bude trvat na tom, že je nevinný, a je připraven říct lži, aby se bránil. Cílem oponenta je donutit navrhovatele, aby byl v rozporu s něčím, co prohlásil, jak už bylo řečeno; ale Opponent udržuje záznam a (stejně jako ve výše uvedených oblázkových hrách) musí z důvodu nedostatku místa nebo paměti vyhodit položky ze záznamu. Důležitou otázkou není, zda má Opponent vítěznou strategii (předpokládá se od samého začátku, že ji má), ale kolik paměti potřebuje pro svůj záznam. Tyto hry jsou užitečným zařízením pro zobrazování horní a dolní hranice délky důkazů v různých důkazních systémech.

Další druh logické hry, která umožňuje lži, je Ulamova hra s lži. Zde jeden hráč myslí na číslo v určitém rozsahu. Cílem druhého hráče je zjistit, jaké je toto číslo tím, že položí prvnímu hráči ano / ne otázky; ale první hráč smí ve svých odpovědích rozeznat určitý počet lží. Stejně jako ve hrách Pudlaka existuje určitě vítězná strategie pro druhého hráče, ale otázkou je, jak tvrdě musí tento hráč pracovat, aby vyhrál. Mírou tentokrát není prostor ani paměť, ale čas: kolik otázek se musí zeptat? Cignoli a kol. 2000 Kapitola 5 spojuje tuto hru s logikou s mnoha hodnotami.

Vrátit se na okamžik k Lorenzenovi: nedokázal rozlišit mezi různými postoji, které by člověk mohl zaujmout v argumentu: říkat, předpokládat, připouštět, dotazovat, útočit, dopouštět se. Zda je skutečně možné všechny tyto pojmy definovat, aniž by se předpokládala nějaká logika, je bodem. Ale nevadí to; zdokonalení Lorenzenových her v tomto směru by mohlo sloužit jako přístup k neformální logice, a zejména k výzkumu, který si klade za cíl systematizovat možné struktury zdravých neformálních argumentů. V této souvislosti viz Walton a Krabbe 1995. Relevantní jsou také příspěvky v Bench-Capon a Dunne 2007.

Bibliografie

Některé z klíčových článků Henkina a Lorenzena a některé níže citované články se objevují ve sbírce Infinitistické metody (Sborník sympozia o základech matematiky, Varšava, 2. – 9. Září 1959), Oxford: Pergamon Press, 1961 Editoři nejsou pojmenovaní.

Hry v historii logiky

• Dutilh Novaes, Catarina, 2007, Formalizace středověkých logických teorií: Suppositio, Consequentiae a Povinnosti, New York: Springer-Verlag.
• Hamblin, Charles, 1970, Fallacies, London: Methuen.
• Hilbert, David, 1967, „Die Grundlagen der Mathematik“, překládán jako „Základy matematiky“v Jean van Heijenoort (ed.), Z Frege do Gödel, Cambridge Mass.: Harvard University Press, s. 464–479.
• Paul of Venice, Logica Magna II (8), Tractatus de Obligationibus, E. Jennifer Ashworth (ed.), New York: British Academy a Oxford University Press, 1988.
• Weyl, Hermann, 1925–7, „Die heutige Erkenntnislage in der Mathematik“, přeloženo jako „Současná epistemologická situace v matematice“v Paolo Mancosu, od Brouwera k Hilbertovi: Debata o základech matematiky ve 20. letech 20. století v New Yorku: Oxford University Press, 1988, str. 123–142.
• Zermelo, Ernst, 1913, „Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels“, v EW Hobson a AEH Love (ed.), Sborník z pátého mezinárodního kongresu matematiků, svazek II, Cambridge: Cambridge University Press.

Hry pro výuku logiky

• Barwise, Jon a John Etchemendy, 1995, Jazyk logiky prvního řádu, včetně Tarskiho World 3.0, Cambridge: Cambridge University Press.
• Carroll, Lewis, 1887, Logická hra, Londýn: Macmillan.
• Dienes, Zoltan P. a EW Golding, 1966, Learning Logic, Logical Games, Harlow: Association of Educational Supply Association.
• Havas, Katalin, 1999, „Učení k myšlení: Logika pro děti“, ve sborníku dvacátého světového kongresu filozofie (svazek 3: Filozofie vzdělávání), David M. Steiner (ed.), Bowling Green Ohio: Bowling Green State University Philosophy, pp. 11–19.
• Nifo, Agostino, 1521, Dialectica Ludicra (Logická hra jako hra), Florencie: Bindonis.
• Weng, Jui-Feng, s Shian-Shyong Tseng a Tsung-Ju Lee, 2010, „Výuka logické logiky pomocí ladění pravidel hry,“transakce IEEE, Learning Technologies, 3 (4): 319–328. [Používá hry Pac-Man k výuce booleovské logiky žákům středních škol.]

Logické hry

• Gale, David a FM Stewart, 1953, „Nekonečné hry s dokonalými informacemi“, v Příspěvcích k Teorii her II (Annals of Mathematics Studies 28), HW Kuhn a AW Tucker (ed.), Princeton: Princeton University Press, pp 245–266.
• Kechris, Alexander S., 1995, teorie klasického popisného souboru, New York: Springer-Verlag.
• Marion, Mathieu, 2009, „Proč hrát logické hry?“V edicích Ondrej Majer, Ahti-Veikko Pietarinen a Tero Tulenheimo., Hry: Unifying Logic, Language and Philosophy, New York: Springer-Verlag, pp. 3-25.
• Osbourne, Martin J. a Ariel Rubinstein, 1994, Kurz teorie her, Cambridge: MIT Press.
• Väänänen, Jouko, 2011, Modely a hry, Cambridge: Cambridge University Press.
• van Benthem, Johan, 2011, Logická dynamika informací a interakce, Cambridge: Cambridge University Press, 2011.
• –––, 2014, Logické hry, Cambridge, MA: MIT Press.

Sémantické hry pro klasickou logiku

• Henkin, Leon, 1961, „Některé poznámky k nekonečně dlouhým formám,“v Infinitistic Methods, op. cit., str. 167–183.
• Hintikka, Jaakko, 1973, Logic, Language-Games and Information: Kantian Themes in Philosophy of Logic, Oxford: Clarendon Press.
• Hintikka, Jaakko, 1996, The Principles of Mathematics Revisited, New York: Cambridge University Press. [Viz například strany 40, 82 o zvoleném axiomu.]
• Hodges, Wilfrid, 2001, „Elementary Predicate Logic 25: Skolem Functions“, v Dov Gabbay, a Franz Guenthner (eds.), Handbook of Philosophical Logic I, 2. vydání, Dordrecht: Kluwer, s. 86–91. [Důkaz rovnocennosti hry a Tarského sémantika.]
• Kolaitis, Ph. G., 1985, „Kvantifikace hry“, v J. Barwise a S. Feferman (eds.), Model-Theoretic Logics, New York: Springer-Verlag, str. 365-421.
• Peirce, Charles Sanders, 1898, Zdůvodnění a logika věcí: Cambridge Conference Lectures of 1898, ed. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.

Sémantické hry s nedokonalými informacemi

• Hintikka, Jaakko a Gabriel Sandu, 1997, „Game-teoretická sémantika“, v Johan van Benthem a Alice ter Meulen (eds.), Handbook of Logic and Language, Amsterdam: Elsevier, s. 361–410.
• Hodges, Wilfrid, 1997, „Kompoziční sémantika pro jazyk nedokonalých informací“, Logic Journal of IGPL, 5: 539–563.
• Janssen, Theo MV a Francien Dechesne, 2006, „Signaling: a záludné podnikání“, v J. van Benthem et al. (eds.), Age of Alternative Logics: Assessment of Philosophy of Logic and Mathematics Today, Dordrecht: Kluwer, pp. 223–242.
• Mann, Allen L., Gabriel Sandu a Merlin Sevenster, 2011, Logic-friendly Logic: The Game-Theoretic Approach (London Mathematical Society Lecture Note Series 386), Cambridge: Cambridge University Press.
• von Neumann, John a Oskar Morgenstern, 1944, Teorie her a ekonomického chování, Princeton: Princeton University Press.
• Väänänen, Jouko, 2007, Logika závislosti: Nový přístup k logice nezávislosti, Cambridge: Cambridge University Press.

Sémantické hry pro další logiku

• Bradfield, Julian a Colin Stirling, 2006, „Modální mu-kalkuli,“v P. Blackburn et al. (eds.), Handbook of Modal Logic, Amsterdam: Elsevier, s. 721–756.
• Dekker, Paul a Marc Pauly (eds.), 2002, Journal of Logic, Language and Information, 11 (3): 287–387. [Zvláštní vydání o logice a hrách.]
• Hennessy, Matthew a Robin Milner, 1985, „Algebraické zákony pro indeterminismus a souběžnost“, Journal of the ACM, 32: 137–162.
• Parikh, Rohit, 1985, „Logika her a její aplikace“, v Marek Karpinski a Jan van Leeuwen (eds.), „Témata v teorii výpočtu“, Annals of Diskret Mathematics, 24: 111–140.
• Pauly, Marc a Rohit Parikh (ed.), 2003, Studia Logica, 72 (2): 163–256 [Zvláštní vydání o herní logice.]
• Stirling, Colin, 2001, Modální a časové vlastnosti procesů, New York: Springer-Verlag.
• van Benthem, Johan, 2006, „Epistemická logika her IF“, v Randall Auxier a Lewis Hahn (ed.), Filozofie Jaakka Hintikky, Chicago: Open Court, s. 481–513.
• van Benthem, Johan s Amitabhou Guptou a Rohitem Parikhem, 2011, Důkaz, výpočet a agentura, Dordrecht: Springer-Verlag.

Back-and-Forth hry

• Blackburn, Patrick s Maarten de Rijke a Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press.
• Doets, Kees, 1996, Teorie základních modelů, Stanford: CSLI Publications and FoLLI.
• Ebbinghaus, Heinz-Dieter a Jörg Flum, 1999, teorie konečných modelů, 2. vydání, New York: Springer.
• Ehrenfeucht, Andrzej, 1961, „Aplikace her na problém úplnosti formalizovaných teorií“, Fundamenta Mathematicae, 49: 129–141.
• Grädel, Erich s Phokionem G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema a Scott Weinstein, 2007, konečná teorie modelu, Berlín: Springer-Verlag.
• Libkin, Leonid, 2004, Prvky teorie konečných modelů, Berlín, Springer-Verlag.
• Otto, Martin, 1997, ohraničená variabilní logika a počítání-studium na konečných modelech (přednášky v logice, 9), Berlín: Springer-Verlag.
• Peters, Stanley a Dag Westerståhl, 2006, Quantifiers in Language and Logic, Oxford: Clarendon Press.
• Tarski, Alfred, 1946, „Projev na konferenci o seminářích v Princetonské univerzitě o problémech matematiky (17. – 19. Prosince 1946),“Hourya Sinaceur (ed.), Bulletin of Symbolic Logic, 6 (2000): 1–44.
• van Benthem, Johan, 2001, „The Correspondence Theory“, v Dov Gabbay a Franz Guenthner (eds.), Handbook of Philosophical Logic III, 2. vydání, Dordrecht: Kluwer.

Další modelové teoretické hry

• Anthony, Martin a Norman Biggs, 1992, Computational Learning Theory, Cambridge: Cambridge University Press. [Pro dimenzi Vapnik-Chervonenkis.]
• Gurevich, Yuri a Leo Harrington, 1984, „Stromy, automaty a hry,“v HR Lewis (ed.), Sborník ACM sympozia o teorii výpočetní techniky, San Francisco: ACM, str. 171–182.
• Hirsch, Robin a Ian Hodkinson, 2002, Relation Algebras by Games, New York: North-Holland.
• Hodges, Wilfrid, 1985, Building Modules by Games, Cambridge: Cambridge University Press.
• Hodges, Wilfrid, 1993, Teorie modelu, Cambridge: Cambridge University Press.
• Oxtoby, JC, 1971, Measure and Category, New York: Springer-Verlag.
• Ziegler, Martin, 1980, „Algebraisch abgeschlossene Gruppen“, v SI Adian et al. (eds.), Word Problems II: The Oxford Book, Amsterdam: North-Holland, s. 449–576.

Hry dialogu, komunikace a důkazu

• Abramsky, Samson a Radha Jagadeesan, 1994, „Hry a úplnost pro multiplikativní lineární logiku,“Journal of Symbolic Logic, 59: 543–574.
• Abramsky, Samson a Paul-André Melliès, 1999, „Souběžné hry a úplnost“, v sborníku čtrnáctého mezinárodního sympozia o logice v informatice, počítačová věda Press of IEEE, s. 431–442.
• Bench-Capon, TJM a Paul E. Dunne, 2007, „Argumentace v umělé inteligenci“, Artificial Intelligence, 171: 619–641. [Úvod do bohaté sbírky článků na stejné téma na stranách 642–937.]
• Blass, Andreas, 1992, „Sémantika hry pro lineární logiku,“Annals of Pure and Applied Logic, 56: 183–220.
• Cignoli, Roberto LO, Itala ML D'Ottaviano a Daniele Mundici, 2000, Algebraické základy mnohohodnotného zdůvodnění, Dordrecht: Kluwer.
• Felscher, Walter, 2001, „Dialogy jako základ pro intuicionální logiku,“v Dov Gabbay a Franz Guenthner (ed.), Handbook of Philosophical Logic V, 2. vydání, Dordrecht: Kluwer.
• Hodges, Wilfrid a Erik CW Krabbe, 2001, „Dialogue základy“, sborník Aristotelian Society (Supplementary Volume), 75: 17–49.
• Japaridze, Giorgi, 2003, „Úvod do logiky počítatelnosti“, Annals of Pure and Applied Logic, 123: 1–99.
• Lorenzen, Paul, 1961 „Ein dialogisches Konstruktivitätskriterium,“v Infinitistic Methods, op. cit. 1961, str. 193–2002.
• Pudlak, Pavel, 2000, „Důkazy jako hry“, American Mathematical Monthly, 107 (6): 541–550.
• Walton, Douglas N. a Erik CW Krabbe, 1995, Závazek v dialogu: Základní pojmy mezilidského uvažování, Albany: State University of New York Press.

Akademické nástroje

	Jak citovat tento záznam.
	Náhled na PDF verzi tohoto příspěvku v Friends of the SEP Society.
	Vyhledejte toto vstupní téma v projektu Internet Philosophy Ontology Project (InPhO).
	Vylepšená bibliografie tohoto záznamu ve PhilPapers s odkazy na jeho databázi.

Další internetové zdroje