Logika A Hry

2023 Autor: Noah Black | [email protected]. Naposledy zmenené: 2023-08-25 04:39

Vstupná navigácia

• Obsah vstupu
• Bibliografia
• Akademické nástroje
• Náhľad priateľov PDF
• Informácie o autorovi a citácii
• Späť na začiatok

Logika a hry

Prvýkrát publikované piatok 27. júla 2001; podstatná revízia piatok 16. augusta 2019

Hry medzi dvoma hráčmi toho druhu, v ktorom jeden hráč vyhrá a jeden prehral, sa stali v druhej polovici dvadsiateho storočia známym nástrojom v mnohých odvetviach logiky. Dôležitými príkladmi sú sémantické hry, ktoré sa používajú na definovanie pravdy, hry dozadu a dopredu, ktoré sa používajú na porovnávanie štruktúr, a hry zamerané na dialóg, ktoré vyjadrujú (a možno vysvetľujú) formálne dôkazy.

• 1. Hry v histórii logiky
• 2. Logické hry
• 3. Sémantické hry pre klasickú logiku
• 4. Sémantické hry s nedokonalými informáciami
• 5. Sémantické hry pre ďalšiu logiku
• 6. Back-and-Forth hry

• 7. Ďalšie modelové teoretické hry

  • 7.1 Nútené hry
  • 7.2 Hry s výberom
  • 7.3 Hry na strome dvoch nástupníckych funkcií
• 8. Hry dialógu, komunikácie a dôkazu

• Bibliografia

  • Hry v histórii logiky
  • Hry pre výučbu logiky
  • Logické hry
  • Sémantické hry pre klasickú logiku
  • Sémantické hry s nedokonalými informáciami
  • Sémantické hry pre ďalšiu logiku
  • Back-and-Forth hry
  • Ďalšie modelové teoretické hry
  • Hry dialógu, komunikácie a dôkazu
• Akademické nástroje
• Ďalšie internetové zdroje
• Súvisiace záznamy

1. Hry v histórii logiky

Prepojenia medzi logikou a hrami siahajú dlhú cestu. Ak niekto uvažuje o debatách ako o nejakej hre, potom už Aristoteles nadviazal spojenie; jeho spisy o sylogológii úzko súvisia so štúdiom cieľov a pravidiel debatovania. Aristotelovo hľadisko prežilo do logiky stredoveké meno: dialektika. V polovici dvadsiateho storočia Charles Hamblin obnovil spojenie medzi dialógom a pravidlami správneho usudzovania, krátko potom, čo Paul Lorenzen prepojil dialóg s konštruktívnymi základmi logiky.

Medzi hrami a výučbou sú úzke väzby. Spisovatelia počas stredovekého obdobia hovoria o dialógoch ako o spôsobe „výučby“alebo „testovania“použitia rozumných dôvodov. Máme aspoň dve učebnice logiky zo začiatku šestnásteho storočia, ktoré ju prezentujú ako hru pre individuálneho študenta, a hra Logic od Lewisa Carrolla (1887) je ďalším príkladom toho istého žánru. Existuje veľa moderných príkladov, aj keď pravdepodobne neexistovala dostatočná kontinuita, ktorá by opodstatňovala hovorenie o tradícii výučby logiky hrami.

Teória matematickej hry bola založená začiatkom dvadsiateho storočia. Hoci až do 50. rokov 20. storočia nevznikli žiadne matematické prepojenia s logikou, je prekvapujúce, koľko prvých priekopníkov teórie hier je známych aj pre ich prínos k logike: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo a ďalšie. V roku 1953 nadviazali David Gale a Frank Stewart plodné spojenia medzi teóriou množín a hrami. Krátko nato Leon Henkin navrhol spôsob použitia hier na sémantiku pre nekonečné jazyky.

Prvá polovica dvadsiateho storočia bola obdobím zvyšovania prísnosti a profesionality v logike a pre väčšinu logistov toho obdobia by sa používanie hier v logike pravdepodobne zdalo zbytočne zbytočné. Intuicionista LEJ Brouwer vyjadril tento postoj, keď obvinil svojich oponentov z toho, že spôsobil, že matematika „degeneruje do hry“(ako ho citoval David Hilbert v roku 1927, citovaný vo van Heijenoort 1967). Hermann Weyl (citovaný v Mancosu 1998) použil pojem hry na vysvetlenie Hilbertovej metamatematiky: matematické dôkazy postupujú ako hry bezvýznamnej hry, ale môžeme stáť mimo hry a klásť na ňu zmysluplné otázky. Wittgensteinove jazykové hry vyvolali len malú reakciu logikov. Ale v druhej polovici storočia sa ťažisko logického výskumu presunulo od základov k technikám,a asi od roku 1960 sa hry čoraz častejšie používali v logických papieroch.

Začiatkom 21. storočia sa všeobecne akceptovalo, že hry a logika spolu idú. Výsledkom bolo obrovské rozšírenie nových kombinácií logiky a hier, najmä v oblastiach, kde sa uplatňuje logika. Mnohé z týchto nových udalostí pochádzajú pôvodne z práce v čistej logike, aj keď dnes sledujú svoje vlastné programy. Jednou z takýchto oblastí je teória argumentácie, kde hry tvoria nástroj na analýzu štruktúry diskusií.

Ďalej sa sústredíme na tie hry, ktoré sú najužšie spojené s čistou logikou.

2. Logické hry

Z hľadiska teórie hier nie sú hlavné hry, ktoré logici študujú, vôbec typické. Zvyčajne zahŕňajú iba dvoch hráčov, často majú nekonečnú dĺžku, jediné výsledky vyhrávajú a strácajú a akcie alebo výsledky nie sú spojené s pravdepodobnosťou. Najdôležitejšie náležitosti logickej hry sú nasledujúce.

Sú dvaja hráči. Všeobecne ich môžeme nazývať (forall) a (existuje). Výslovnosti „Abelard“a „Eloise“siahajú do polovice osemdesiatych rokov minulého storočia a užitočne opravujú hráčov, aby uľahčili referenciu pre mužov a ženy: jej pohyb, pohyb. Ostatné mená sa bežne používajú pre hráčov v konkrétnych typoch logickej hry.

Hráči hrajú výberom prvkov súboru (Omega), ktorý sa nazýva doménou hry. Podľa vlastného výberu zostavujú postupnosť

[a_0, a_1, a_2, / ldots)

prvkov (Omega). Nekonečné sekvencie prvkov (Omega) sa nazývajú hry. Konečné sekvencie prvkov (Omega) sa nazývajú pozície; zaznamenávajú, kde sa hra mohla dostať do určitého času. Funkcia (tau) (funkcia otočenie alebo funkcia hráča) zaujme každú pozíciu (mathbf {a}) buď / (existuje) alebo (forall); ak (tau (mathbf {a}) = / existuje), znamená to, že keď hra dosiahne (mathbf {a}), hráč (existuje) urobí nasledujúcu voľbu (a podobne) s (forall)). Pravidlá hry definujú dve sady (W _ { forall}) a (W _ { existuje}) pozostávajúce z pozícií a hier, s nasledujúcimi vlastnosťami: ak pozícia (mathbf {a}) je v (W _ { forall}), tak je tu aj akákoľvek hra alebo dlhšia pozícia, ktorá začína na (mathbf {a}) (a podobne s (W _ { existuje}));a žiadna hra nie je v (W _ { forall}) ani (W _ { existuje}). Hovoríme, že hráč (forall) vyhrá hru (mathbf {b}) a že (mathbf {b}) je výhra pre (forall), ak (mathbf {b}) je v (W _ { forall}); ak je nejaká pozícia (mathbf {a}), ktorá je počiatočným segmentom (mathbf {b}), v (W _ { forall}), potom hovoríme, že hráč (forall) vyhráva už na (mathbf {a}). (A podobne s (existuje) a (W _ { existuje}).) Takže, ak to zhrniem, logická hra je štvorčlenná ((Omega, / tau), (W_) { forall}), (W _ { existuje})) s práve opísanými vlastnosťami.potom hovoríme, že hráč (forall) vyhral už na (mathbf {a}). (A podobne s (existuje) a (W _ { existuje}).) Takže, ak to zhrniem, logická hra je 4-násobná ((Omega, / tau), (W_) { forall}), (W _ { existuje})) s práve opísanými vlastnosťami.potom hovoríme, že hráč (forall) vyhral už na (mathbf {a}). (A podobne s (existuje) a (W _ { existuje}).) Takže, ak to zhrniem, logická hra je štvorčlenná ((Omega, / tau), (W_) { forall}), (W _ { existuje})) s práve opísanými vlastnosťami.

Hovoríme, že logická hra je úplná, ak je každá hra v hre (W _ { forall}) alebo (W _ { existuje}), takže nie sú k dispozícii žiadne remízy. Pokiaľ nedôjde k výslovnej výnimke, logické hry sa vždy považujú za úplné. (Nezamieňajte si to, že ste celkom, s oveľa silnejšou vlastnosťou odhodlania - pozri nižšie)

Vyššie uvedená definícia predpokladá, že hra bude naďalej nekonečná, a to aj v prípade, že hráč vyhral na určitej konečnej pozícii len z dôvodu matematického pohodlia; nie je záujem o nič, čo sa stane potom, čo hráč vyhral. Mnoho logických hier má tú vlastnosť, že v každej hre už jeden z hráčov vyhral na určitej konečnej pozícii; Hry tohto druhu sa považujú za opodstatnené. Ešte silnejšou podmienkou je, že existuje určité konečné číslo (n) také, že v každej hre už jeden z hráčov vyhral na pozícii (n); v tomto prípade hovoríme, že hra má obmedzenú dĺžku.

Stratégia pre hráča je súbor pravidiel, ktoré presne popisujú, ako by si mal hráč zvoliť, v závislosti od toho, ako si dvaja hráči vybrali pri predchádzajúcich ťahoch. Matematicky stratégia pre (forall) pozostáva z funkcie, ktorá prevezme každú pozíciu (mathbf {a}) s (tau (mathbf {a}) = / forall) k prvku (b) z (Omega); považujeme to za pokyn pre (forall) zvoliť (b), keď hra dosiahne pozíciu (mathbf {a}). (Rovnako ako pri stratégii pre (existuje).) Stratégia pre hráča sa považuje za víťaznú, ak tento hráč vyhrá každú hru, v ktorej stratégiu používa, bez ohľadu na to, čo robí iný hráč. Najviac jeden z hráčov má výhernú stratégiu (pretože inak by hráči mohli proti sebe hrať svoje výherné stratégie a obaja by vyhrávali,v rozpore s tým, že (W _ { forall}) a (W _ { existuje}) nemajú spoločné hry). Niekedy sa stretnú situácie, keď sa zdá, že dvaja hráči majú výherné stratégie (napríklad v nútených hrách nižšie), ale podrobnejšia kontrola ukazuje, že obaja hráči v skutočnosti hrajú rôzne hry.

O hre sa hovorí, že je určená, ak jeden alebo druhý z hráčov má výhernú stratégiu. Existuje veľa príkladov hier, ktoré nie sú určené, ako ukázali Gale a Stewart v roku 1953 pomocou zvolenej axiómy. Tento objav viedol k dôležitým aplikáciám pojmu determinácia v základoch teórie množín (pozri vstup na veľkých kardinálov a determináciu). Gale a Stewart sa tiež ukázali ako dôležitá veta, ktorá nesie ich meno: Určuje sa každá dobre podložená hra. Z toho vyplýva, že každá hra s obmedzenou dĺžkou je určená - čo je Zermelo známe už v roku 1913. (Presnejšie to hovorí o Gale-Stewartovej vete. Hovorí sa, že hra (G) je uzavretá, ak (existuje) vyhrá každú hru (G), v ktorej sa už nestratila na žiadnom konečnom mieste. Veta uvádza, že každá uzavretá hra je určená. Dôkaz vety je v podstate jednoduchý: zavolajte pozíciu, ktorá vyhráva za (forall), ak má od tejto pozície víťaznú stratégiu. Predpokladajme, že (forall) nemá v hre výhernú stratégiu, to znamená, že na začiatku pozícia nezískava za (forall). Ak je prvým ťahom ťah (forall), pozícia po jeho ťahu stále pre neho nevyhrá. Ak je prvý ťah ťahom (existuje), musí mať ťah, po ktorom pozícia stále nevyhráva za (forall), inak by predchádzajúca pozícia vyhrala za (forall)). Hra pokračuje týmto spôsobom nekonečne veľa ťahov cez pozície, ktoré nezískajú za (forall). Pretože hra je uzavretá, (existuje) vyhráva. Predpokladajme, že (forall) nemá v hre výhernú stratégiu, to znamená, že na začiatku pozícia nezískava za (forall). Ak je prvým ťahom ťah (forall), pozícia po jeho ťahu stále pre neho nevyhrá. Ak je prvý ťah ťahom (existuje), musí mať ťah, po ktorom pozícia stále nevyhráva za (forall), inak by predchádzajúca pozícia vyhrala za (forall)). Hra pokračuje týmto spôsobom nekonečne veľa ťahov cez pozície, ktoré nezískajú za (forall). Pretože hra je uzavretá, (existuje) vyhráva. Predpokladajme, že (forall) nemá v hre výhernú stratégiu, to znamená, že na začiatku pozícia nezískava za (forall). Ak je prvým ťahom ťah (forall), pozícia po jeho ťahu stále pre neho nevyhrá. Ak je prvý ťah ťahom (existuje), musí mať ťah, po ktorom pozícia stále nevyhráva za (forall), inak by predchádzajúca pozícia vyhrala za (forall)). Hra pokračuje týmto spôsobom nekonečne veľa ťahov cez pozície, ktoré nezískajú za (forall). Pretože hra je uzavretá, (existuje) vyhráva. Ak je prvý ťah ťahom (existuje), musí mať ťah, po ktorom pozícia stále nevyhráva za (forall), inak by predchádzajúca pozícia vyhrala za (forall)). Hra pokračuje týmto spôsobom nekonečne veľa ťahov cez pozície, ktoré nezískajú za (forall). Pretože hra je uzavretá, (existuje) vyhráva. Ak je prvý ťah ťahom (existuje), musí mať ťah, po ktorom pozícia stále nevyhráva za (forall), inak by predchádzajúca pozícia vyhrala za (forall)). Hra pokračuje týmto spôsobom nekonečne veľa ťahov cez pozície, ktoré nezískajú za (forall). Pretože hra je uzavretá, (existuje) vyhráva.

Rovnako ako v klasickej teórii hier, aj vyššie uvedená logická hra slúži ako kôň na šaty, na ktorý sa môžeme zavesiť aj iné koncepcie. Napríklad je bežné, že existujú zákony, ktoré popisujú, ktoré prvky (Omega) sú pre hráča k dispozícii pri konkrétnom ťahu. Toto vylepšenie nie je potrebné, pretože víťazné stratégie nie sú ovplyvnené, ak namiesto toho rozhodneme, že hráč, ktorý poruší zákon, okamžite prehrá; ale pre mnoho hier sa tento spôsob ich prezerania zdá neprirodzený. Nižšie nájdete niektoré ďalšie ďalšie funkcie, ktoré je možné pridať do hier.

Definície hry a stratégie uvedené vyššie boli čisto matematické. Takže vynechali, čo je pravdepodobne najdôležitejšou vlastnosťou hier, a to, že ich ľudia hrajú (aspoň metaforicky). Hráči sa snažia vyhrať a štúdiom stratégií, ktoré sú im otvorené, študujeme, aké správanie je pre človeka s konkrétnym cieľom racionálne. Vo väčšine hier existuje niekoľko hráčov, takže môžeme študovať, čo je racionálnou reakciou na správanie niekoho iného. Obmedzením pohybov hráčov a možných stratégií môžeme študovať obmedzenú racionalitu, kde agent musí robiť racionálne rozhodnutia za podmienok obmedzených informácií, pamäte alebo času.

Stručne povedané, hry sa používajú na modelovanie racionality a obmedzenej racionality. To je nezávislé od akéhokoľvek spojenia s logikou. Niektoré logiky boli navrhnuté na štúdium aspektov racionálneho správania a v posledných rokoch je čoraz bežnejšie spájať tieto logiky s vhodnými hrami. Pozri oddiel 5 („Sémantické hry pre ďalšiu logiku“) a jeho bibliografia.

Až donedávna však boli logické hry spojené s racionálnym správaním úplne iným spôsobom. Na povrchu predmetná logika nemala žiadne priame spojenie s správaním. Logici a matematici si však všimli, že niektoré nápady by mohli byť intuitívnejšie, keby boli spojené s možnými cieľmi. Napríklad v mnohých aplikáciách logických hier je ústrednou predstavou víťazná stratégia hráča (existuje). Tieto stratégie (alebo ich existencia) sa často ukážu ako ekvivalent niečoho logického významu, ktorý by mohol byť definovaný bez použitia hier - napríklad dôkazu. Hry však pociťujú lepšiu definíciu, pretože doslova poskytujú určitú motiváciu: (existuje) sa snaží vyhrať.

To vyvoláva otázku, ktorá nie je matematicky veľmi zaujímavá, ale mala by sa týkať filozofov, ktorí používajú logické hry. Ak chceme, aby motivácia (existuje) v hre (G) mala nejakú vysvetľujúcu hodnotu, musíme pochopiť, čo sa dosiahne, ak (existuje) vyhrá. Najmä by sme mali byť schopní rozprávať realistický príbeh o situácii, keď sa nejaký agent s názvom (existuje) snaží urobiť niečo zrozumiteľné a jeho uskutočnenie je to isté ako víťazstvo v hre. Ako povedal Richard Dawkins, zodpovedajúca otázka pre vývojové hry Maynarda Smitha,

Celkovým účelom nášho hľadania … je nájsť vhodného herca, ktorý bude hrať hlavnú úlohu v našich metaforách účelu. Chceme … povedať: „Je to pre dobro…“. Našou snahou v tejto kapitole je nájsť správny spôsob, ako túto vetu dokončiť. (The Extended Phenotype, Oxford University Press, Oxford 1982, strana 91.)

Pre budúce použitie, povedzme to Dawkinsovu otázku. V mnohých druhoch logickej hry sa ukazuje, že je oveľa ťažšie odpovedať, ako si uvedomili priekopníci týchto hier. (Marion 2009 ďalej rozoberá otázku Dawkinsa.)

3. Sémantické hry pre klasickú logiku

Na začiatku tridsiatych rokov Alfred Tarski navrhol definíciu pravdy. Jeho definícia spočívala v nevyhnutnej a dostatočnej podmienke, aby bola veta v jazyku typickej formálnej teórie pravdivá; jeho nevyhnutná a dostatočná podmienka používala iba pojmy zo syntaxe a teórie množín, spolu s primitívnymi pojmami príslušnej formálnej teórie. Tarski v skutočnosti definoval všeobecnejší vzťah „vzorec (phi (x_1, / ldots, x_n)) platí pre prvky (a_1, / ldots, a_n) ' pravdivosť vety je zvláštny prípad, keď (n = 0). Napríklad otázka, či

'Pre všetkých (x) existuje (y), takže R ((x, y))' je true

redukuje sa na otázku, či platí nasledujúce:

Pre každý objekt (a) sa veta „Existuje (y) tak, že R ((a, y))“je pravdivá.

To sa zase zníži na:

Pre každý objekt (a) existuje objekt (b) taký, že veta 'R ((a, b))' je pravdivá.

V tomto príklade je to, pokiaľ ide o definíciu Tarského pravdy.

Koncom 50. rokov 20. storočia si Leon Henkin všimol, že vieme intuitívne porozumieť niektorým vetám, ktoré Tarskova definícia nemôže zvládnuť. Zoberme si napríklad nekonečne dlhú vetu

Pre všetkých (x_0) existuje (y_0) také, že pre všetkých (x_1) existuje (y_1) také, že … R ((x_0, y_0, x_1, y_1, / ldots)), Tarskiho prístup zlyhá, pretože reťazec kvantifikátorov na začiatku je nekonečný a nikdy by sme ich nedokončili. Namiesto toho, navrhol Henkin, mali by sme zvážiť hru, kde osoba (forall) vyberie objekt (a_0) pre (x_0), potom druhá osoba (existuje) vyberie objekt (b_0) pre (y_0), potom (forall) vyberie (a_1) pre (x_1, / existuje) vyberie (b_1) pre (y_1) atď. Hra tejto hry je výhra pre (existuje), iba ak je nekonečná atómová veta

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

je pravda. Pôvodná veta platí iba vtedy, ak hráč (existuje) má pre túto hru výhernú stratégiu. Prísne Henkin použil hru iba ako metaforu a pravdou bolo, že navrhol, že skolemizovaná verzia vety je pravdivá, tj že existujú funkcie (f_0, f_1, / ldots) také, že pre každú voľbu (a_0, a_1, a_2) atď

(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).)

Táto podmienka sa však okamžite premieta do jazyka hier; Skolemove funkcie (f_0) atď. definujú víťaznú stratégiu pre (existuje), ktorá jej povie, ako si vybrať na základe predchádzajúcich rozhodnutí pomocou (forall). (Vyšlo najavo niekedy neskôr, že CS Peirce už navrhol vysvetliť rozdiel medzi „každým“a „niektorým“z hľadiska toho, kto si vyberie predmet; napríklad vo svojej druhej prednáške v Cambridge Conference z roku 1898.)

Krátko po Henkinovej práci Jaakko Hintikka dodal, že rovnaká myšlienka platí aj pri spojeniach a disjunkciách. Spojenie '(phi / wedge / psi)' môžeme považovať za všeobecne kvantifikované vyhlásenie vyjadrujúce "Každá z viet (phi, / psi) platí", takže by to malo byť pre hráča (forall) vybrať jednu z viet. Ako uviedla Hintikka, pri hraní hry (G (phi / wedge / psi), / forall) sa vyberie, či má hra pokračovať ako (G (phi)) alebo ako (G (psi))). Podobne sa disjunkcia stáva existenciálne kvantifikovanými výrokmi o sériách viet a označuje pohyby, pri ktorých hráč (existuje) zvolí, ako má hra pokračovať. Aby priniesol kvantifikátory do rovnakého štýlu, navrhol, aby hra (G (forall x / phi (x))) postupovala takto: hráč (forall) vyberie objekt a poskytne meno (a) pre to,a hra pokračuje ako (G (phi (a))). (A podobne s existenciálnymi kvantifikátormi, s výnimkou toho, že sa vyberie (existuje).) Hintikka tiež navrhla geniálny návrh na zavedenie negácie. Každá hra G má dvojakú hru, ktorá je rovnaká ako hra G s tým rozdielom, že hráči (forall) a (existuje) sú transponovaní do pravidiel hry aj do pravidiel víťazstva. Hra (G (neg / phi)) je dvojnásobok hry (G (phi)).

Dá sa dokázať, že pre každú vetu prvého rádu (phi) interpretovanú v pevnej štruktúre (A) má hráč (existuje) víťaznú stratégiu pre hru Hintikky (G (phi)) iba vtedy, ak (phi) platí v (A) v zmysle Tarského. Zaujímavé sú dva znaky tohto dôkazu. Najprv, ak (phi) je veta prvého rádu, potom hra (G (phi)) má konečnú dĺžku, a preto nám Gale-Stewartova veta hovorí, že je určená. Z toho vyvodzujeme, že (existuje) má výhernú stratégiu presne v jednej z (G (phi)) a jej duálnej; takže má víťaznú stratégiu v (G (neg / phi)) iba vtedy, ak ju nemá v (G (phi))). Postará sa o negáciu. A za druhé, ak (existuje) má výhernú stratégiu pre každú hru (G (phi (a))), potom po výbere jednej takejto stratégie (f_a) pre každú (a),môže ich spojiť do jedinej výhernej stratégie pre (G (forall x / phi (x))) (konkrétne: Počkajte a uvidíme, ktorý element (a / forall) vyberie, potom zahrajte (f_a) ). Týmto sa zabezpečuje doložka o univerzálnych kvantifikátoroch; ale argument používa axióma voľby a v skutočnosti nie je ťažké vidieť, že tvrdenie, že Hintikkove a Tarskiho definície pravdy sú rovnocenné, je samo osebe ekvivalentné axiómom voľby (vzhľadom na ďalšie axiómy teórie množín Zermelo-Fraenkel),a v skutočnosti nie je ťažké vidieť, že tvrdenie, že definície Hintikkovho a Tarského definície pravdy sú rovnocenné, je samo osebe rovnocenné axiómu voľby (vzhľadom na ďalšie axiómy teórie množín Zermelo-Fraenkel).a v skutočnosti nie je ťažké vidieť, že tvrdenie, že definície Hintikkovho a Tarského definície pravdy sú rovnocenné, je samo osebe rovnocenné axiómu voľby (vzhľadom na ďalšie axiómy teórie množín Zermelo-Fraenkel).

Je zarážajúce, že tu máme dve teórie o tom, kedy je veta pravdivá, a teórie nie sú rovnocenné, ak zlyhá axióma voľby. V skutočnosti dôvod nie je príliš hlboký. Axióma voľby nie je potrebná, pretože definícia Hintikka používa hry, ale preto, že predpokladá, že stratégie sú deterministické, tj že ide o funkcie s jedinou hodnotou, ktoré používateľovi nedávajú na výber. Prirodzenejší spôsob, ako premeniť definíciu Tarski na herné termíny, je použitie nedeterministických stratégií, ktoré sa niekedy nazývajú kvasistrategórie (podrobnosti pozri v časti Kolaitis 1985). (Hintikka 1996 však trvá na tom, že správny výklad pojmu „true“je ten, ktorý používa deterministické stratégie a že táto skutočnosť potvrdzuje axióma výberu.)

Počítačové implementácie týchto hier Hintikka sa ukázali ako veľmi efektívny spôsob výučby významov viet prvého rádu. Jeden taký balík navrhli Jon Barwise a John Etchemendy v Stanforde s názvom „Tarskiho svet“. Nezávisle ďalší tím na univerzite v Omsku zostavil ruskú verziu pre použitie v školách pre nadané deti.

V publikovanej verzii prednášok Johna Lockea v Oxforde vzniesol Hintikka v roku 1973 Dawkinsovu otázku (pozri vyššie) pre tieto hry. Jeho odpoveď bola, že by sme sa mali pozrieť na Wittgensteinove jazykové hry a jazykové hry na pochopenie kvantifikátorov sú tie, ktoré sa točia okolo hľadania a hľadania. V zodpovedajúcich logických hrách by sme mali myslieť na (existuje) ako na seba a (forall) ako na nepriateľskú prírodu, na ktorú sa nikdy nemožno spoľahnúť pri prezentácii objektu, ktorý chcem; Aby som si bol istý, že to nájdu, potrebujem víťaznú stratégiu. Tento príbeh nebol nikdy veľmi presvedčivý; motivácia prírody nie je relevantná a nič v logickej hre nezodpovedá hľadaniu. Pri spätnom pohľade je trochu sklamaním, že nikto nemal problém hľadať lepší príbeh. Môže byť užitočnejšie uvažovať o víťaznej stratégii pre (existuje) v (G (phi)) ako o nejaký dôkaz (vo vhodnom infinitárnom systéme), že (phi) je pravda.

Neskôr Jaakko Hintikka rozšíril myšlienky tejto sekcie dvoma smermi, a to sémantikou prirodzeného jazyka a hrami nedokonalých informácií (pozri nasledujúcu časť). Názov Game-Theoretic Semantics, skrátene GTS, sa používa na pokrytie oboch týchto rozšírení.

Hry opísané v tejto časti sa takmer triviálne prispôsobujú mnohorakej logike: napríklad kvantifikátor (forall x _ { sigma}), kde (x _ { sigma}) je premenná usporiadania (sigma), je inštrukcia pre hráča (forall) na výber prvku sort (sigma). Toto nám okamžite dáva zodpovedajúce hry pre logiku druhého poriadku, ak uvažujeme o prvkoch štruktúry ako o jednom druhu, o množinách prvkov ako o druhom, o binárnych vzťahoch ako o treťom a tak ďalej. Z toho vyplýva, že dosť často máme pravidlá hry aj pre väčšinu zovšeobecnených kvantifikátorov; môžeme ich nájsť tak, že zovšeobecnené kvantifikátory najprv preložíme do logiky druhého poriadku.

4. Sémantické hry s nedokonalými informáciami

V tejto a nasledujúcej časti sa zameriame na niektoré úpravy sémantických hier predchádzajúcej časti na iné logiky. V našom prvom príklade bola vytvorená logika (logika nezávislosti Hintikka a Sandu 1997, alebo stručne IF logika), aby zodpovedala hre. Podrobnejšie informácie o tejto logike nájdete v časti venovanej logike nezávislosti a Mann, Sandu a Sevenster 2011.

Hry tu sú rovnaké ako v predchádzajúcej časti s tým rozdielom, že upustíme od predpokladu, že každý hráč pozná predchádzajúcu históriu hry. Napríklad môžeme požadovať, aby si hráč vybral bez toho, aby vedel, aké rozhodnutia urobil druhý hráč pri určitých predchádzajúcich ťahoch. Klasickým spôsobom, ako to zvládnuť v rámci teórie hier, je obmedziť stratégie hráčov. Napríklad môžeme požadovať, aby funkcia stratégie, ktorá hovorí (existuje), čo robiť v konkrétnom kroku, bola funkciou, ktorej doménou je rodina možných výberov (forall) iba pri prvom a druhom pohybe; to je spôsob, ako vyjadriť, že (existuje) nevie, ako si (forall) vybral pri svojom treťom a neskoršom ťahu. Hry s takýmito obmedzeniami, ktoré sa týkajú strategických funkcií, sa považujú za nedokonalé informácie,na rozdiel od hier dokonalých informácií v predchádzajúcej časti.

Aby sme vytvorili logiku, ktorá vyhovuje týmto hrám, používame rovnaký jazyk prvého poriadku ako v predchádzajúcej časti, s výnimkou toho, že k niektorým kvantifikátorom (a prípadne aj niektorým spojivom) sa pridá notácia, aby sme ukázali, že Skolem pre tieto kvantifikátory funguje (alebo spojivá) sú nezávislé od určitých premenných. Napríklad veta

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

sa číta ako: „Pre každé (x) existuje (y), nie v závislosti od (x), napríklad (R (x, y))”.

K rozlišovaniu medzi dokonalými a nedokonalými informáciami je potrebné urobiť tri dôležité poznámky. Prvým je, že Gale-Stewartova veta platí iba pre hry s dokonalými informáciami. Predpokladajme napríklad, že (forall) a (existuje) zahrajú nasledujúcu hru. Najprv si (forall) vyberie jedno z čísiel 0 a 1. Potom (existuje) vyberie jedno z týchto dvoch čísiel. Hráč (existuje) vyhráva, ak sú dve zvolené čísla rovnaké a inak hráč (forall) vyhráva. Požadujeme, aby (existuje), keď sa rozhodne, nevie, čo (forall) vybral; takže funkcia Skolem pre ňu bude konštantná. (Táto hra zodpovedá vyššie uvedenej vete IF s (R) čítanou ako rovnosť, v štruktúre s doménou pozostávajúcou z 0 a 1.) Je zrejmé, že hráč (existuje) nemá stálu výhernú stratégiu,a tiež, že hráč (forall) nemá víťaznú stratégiu. Táto hra je teda neurčená, hoci jej dĺžka je iba 2.

Jedným z dôsledkov je, že Hintikkove opodstatnenie čítania negácie, pretože dualizácia („hráči vymieňajú miesta“), vo svojich hrách pre logiku prvého poriadku neprechádza do logiky IF. Hintikka odpovedala, že dualizácia bola správnym intuitívnym významom negácie aj v prípade prvého poriadku, takže nie je potrebné žiadne odôvodnenie.

Druhá poznámka je, že už v hrách s dokonalými informáciami sa môže stať, že výherné stratégie nevyužijú všetky dostupné informácie. Napríklad v hre dokonalých informácií, ak hráč (existuje) má výhernú stratégiu, potom má tiež výhernú stratégiu, kde strategické funkcie závisia iba od predchádzajúcich možností (forall). Je to preto, že dokáže rekonštruovať svoje predchádzajúce kroky pomocou svojich predchádzajúcich strategických funkcií.

Keď Hintikka použil vo svojich hrách Skolemove funkcie ako stratégie pre logiku prvého poriadku, urobil stratégie pre hráča závislým iba od predchádzajúcich ťahov druhého hráča. (Skolemova funkcia pre (existuje) závisí iba od univerzálne kvantifikovaných premenných.) Pretože hry boli hrami s dokonalými informáciami, pri druhej vyššie uvedenej poznámke nedošlo k žiadnym stratám. Keď však prešiel na logiku IF, požiadavka, aby stratégie záviseli iba od ťahov druhého hráča, skutočne zmenila. Hodges 1997 to ukázal revidovaním zápisu, takže napríklad ((existuje y / x)) znamená: „Existuje (y) nezávislý od (x), bez ohľadu na to, ktorý hráč si vybral (x) .

Zvážte teraz vetu

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

hral znovu na štruktúre s dvoma prvkami 0 a 1. Hráč (existuje) môže vyhrať nasledovne. Pre (z) si vyberie to isté ako hráč (forall) zvolený pre (x); potom pre (y) si vyberie to isté, ako pre (z). Táto víťazná stratégia funguje iba preto, že v tejto hre sa môže (existuje) odvolať na jej predchádzajúce voľby. Nemala by žiadnu víťaznú stratégiu, ak by tretí kvantifikátor bol ((existuje y / xz)), opäť preto, že akákoľvek Skolemova funkcia pre tento kvantifikátor by musela byť konštantná. Spôsob, akým (existuje) odovzdáva informácie sebe odkazom na predchádzajúcu voľbu, je príkladom javu signalizácie. John von Neumann a Oskar Morgenstern to ilustrovali na príklade Bridge, kde jeden hráč pozostáva z dvoch partnerov, ktorí musia zdieľať informácie pomocou svojich verejných krokov, aby si navzájom signalizovali.

Tretia poznámka je, že existuje dislokácia medzi intuitívnou myšlienkou nedokonalých informácií a hernou teoretickou definíciou z hľadiska stratégií. Intuitívne sú nedokonalé informácie skutočnosťou o okolnostiach, za ktorých sa hra hrá, a nie o stratégiách. Je to veľmi zložitá záležitosť a naďalej to vedie k nedorozumeniam v súvislosti s IF a podobnou logikou. Vezmite si napríklad vetu

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

opäť hral na štruktúre s prvkami 0 a 1. Intuitívne by sme si mohli myslieť, že ak (existuje) si nemôže zapamätať pri druhom kvantifikátore to, čo si vybrala na prvom mieste, ťažko môže mať víťaznú stratégiu. Ale v skutočnosti má veľmi jednoduchú: „Vždy si vyberaj 0“!

V porovnaní s logikou prvého poriadku chýba v logike IF komponent, ktorý herná sémantika nedodá. Sémantika hry nám hovorí, kedy je veta v štruktúre pravdivá. Ale ak vezmeme vzorec s (n) voľnými premennými, čo tento vzorec vyjadruje o usporiadaných (n) - násobkoch prvkov štruktúry? V logike prvého poriadku by definoval ich množinu, tj (n) - ary vzťah k štruktúre; definícia Tarského pravdy vysvetľuje ako. Existuje podobná definícia pre ľubovoľné vzorce IF logiky? Ukazuje sa, že existuje jedna pre mierne odlišnú logiku zavedenú Hodgesom 1997 a vedie k definícii pravdy v Tarskom pre jazyk tejto logiky. S malou úpravou je možné túto definíciu pravdy urobiť tak, aby vyhovovala aj logike IF. Ale pre obe tieto nové logiky je háčik:Namiesto toho, keď priradenie prvkov k voľným premenným robí vzorec pravdivým, hovoríme, keď súbor priradení prvkov k voľným premenným robí vzorec pravdivým. Väänänen 2007 vytvoril túto myšlienku ako základ pre celý rad nových logík pre štúdium pojmu závislosť (pozri položku logika závislosti). V týchto logikách je sémantika definovaná bez hier, hoci pôvodná inšpirácia vychádza z práce Hintikka a Sandu.

V logike Väänänen je ľahké pochopiť, prečo človek potrebuje sady úloh. Má atómový vzorec vyjadrujúci '(x) je závislé od (y)'. Ako to môžeme interpretovať v štruktúre, napríklad v štruktúre prirodzených čísel? Nemá zmysel vôbec sa opýtať napríklad, či je 8 závislé na 37. Ale ak máme množinu X usporiadaných párov prirodzených čísel, má zmysel sa opýtať, či je v X prvý člen každého páru závislý od druhý; Odpoveď Áno by znamenala, že existuje funkcia (f) tak, že každý pár ((a, b)) v X má tvar ((f (b), b)).

5. Sémantické hry pre ďalšiu logiku

Štruktúry tohto druhu vedú k zaujímavým hrám. Štruktúra (A) pozostáva z množiny (S) prvkov (ktoré nazývame stavmi, s tým, že sa často nazývajú svety), binárneho vzťahu (R) na (S) (my bude čítať (R) ako šípku) a rodinu (P_1, / ldots, P_n) podskupín (S). Obaja hráči (forall) a (existuje) hrajú hru G na (A), začínajúc v stave (s), ktorý im je daný, prečítaním vhodného logického vzorca (phi) ako súbor pokynov na hranie a na víťazstvo.

Takže ak (phi) je (P_i), potom hráč (existuje) vyhrá okamžite, ak (s) je v (P_i), inak vyhrá hráč (forall) naraz. Vzorce (psi / wedge / theta, / psi / vee / theta) a (neg / psi) sa správajú ako v Hintikkových hrách vyššie; napríklad (psi / wedge / theta) dá hráčovi pokyn, aby si vybral, či bude hra pokračovať rovnako ako pre (psi) alebo pre (theta). Ak vzorec (phi) je (Box / psi), potom hráč (forall) vyberie šípku z (s) na stav (t) (tj stav (t) tak, že pár ((s, t)) je vo vzťahu (R)) a hra potom pokračuje zo stavu (t) podľa pokynov (psi), Pravidlo pre (Diamond / psi) je rovnaké s tou výnimkou, že hráč (existuje) si vyberie. Nakoniec hovoríme, že vzorec (phi) je pravdivý v s, ak hráč (existuje) má výhernú stratégiu pre túto hru založenú na (phi) a začínajúc od (s).

Tieto hry sa stávajú modálnou logikou veľmi podobne ako hry Hintikky majú logiku prvého poriadku. Predovšetkým sú jedným zo spôsobov, ako dať sémantiku pre modálnu logiku, a súhlasia s obvyklou sémantikou Kripkeho typu. Samozrejme existuje veľa druhov a zovšeobecnení modálnej logiky (vrátane úzko súvisiacich logík, ako je časová, epistemická a dynamická logika), a preto príslušné hry prichádzajú v mnohých rôznych formách. Jedným z príkladov záujmu je počítačovo-teoretická logika Matthew Hennessyho a Robina Milnera, ktorá sa používa na opis správania systémov; tu šípky majú viac ako jednu farbu a pohyb po šípke konkrétnej farby predstavuje vykonanie konkrétnej „akcie“na zmenu stavu. Ďalším príkladom je výkonnejší modálny (mu) - počet Dextera Kozena, ktorý má operátorov pevných bodov;pozri kapitolu 5 Stirling 2001.

Jednou z zaujímavých čŕt týchto hier je, že ak má hráč od nejakého miesta výhernú stratégiu, potom táto stratégia nikdy nemusí odkazovať na čokoľvek, čo sa stalo skôr v hre. Nie je relevantné, aké rozhodnutia boli prijaté skôr alebo dokonca koľko krokov sa už vykonalo. Máme teda to, čo počítačoví vedci niekedy nazývajú „pamätná“výherná stratégia.

V súvisiacej „logike hier“, ktorú navrhol Rohit Parikh, sú hry, ktoré sa pohybujú medzi štátmi, skôr predmetom definície pravdy. Tieto hry majú veľa zaujímavých aspektov. V roku 2003 sa v nich venoval časopis Studia Logica, ktorý vydali Marc Pauly a Parikh.

Vplyvy ekonómie a informatiky viedli množstvo logikov k tomu, aby použili logiku na analýzu rozhodovania v podmienkach čiastočnej nevedomosti. (Pozri napríklad článok o epistemickej logike.) Existuje niekoľko spôsobov, ako vyjadriť stav vedomostí. Jedným je brať ich ako štáty alebo svety v takej modálnej štruktúre, ktorú sme spomenuli na začiatku tejto časti. Ďalšou možnosťou je použitie logiky IF alebo jej variantu. Ako tieto prístupy súvisia? Johan van Benthem 2006 predstavuje niekoľko myšlienok a výsledkov k tejto veľmi prirodzenej otázke. Pozri tiež dokumenty Johan van Benthema, Kristera Segerberga, Eric Pacuita a K. Venkatesha a ich referencie v časti IV „Logika, agentúra a hry“Van Benthema, Gupty a Parikha 2011 a položka o logike pre analýzu hier na ukážka najnovšej práce v tejto oblasti.

6. Back-and-Forth hry

V roku 1930 Alfred Tarski formuloval predstavu, že dve štruktúry (A) a (B) sú elementárne ekvivalentné, tj že v (A) sú presne rovnaké vety prvého poriadku ako v (B)). Na konferencii v Princetone v roku 1946 opísal tento pojem a vyjadril nádej, že bude možné vyvinúť jeho teóriu, ktorá bude „tak hlboká, ako sa teraz používajú pojmy izomorfizmu atď.“(Tarski 1946).

Jednou z prirodzených častí tejto teórie by bola čisto štrukturálna nevyhnutná a dostatočná podmienka, aby boli dve štruktúry elementárne ekvivalentné. Roland Fraïssé, francúzsko-alžírsky štát, ako prvý našiel použiteľnú nevyhnutnú a dostatočnú podmienku. O niekoľko rokov neskôr ju objavil kazašský logista AD Taimanov a poľský logik Andrzej Ehrenfeucht preformuloval hry. Tieto hry sa teraz nazývajú hry Ehrenfeucht-Fraïssé alebo niekedy aj hry „dozadu a dopredu“. Ukázalo sa, že sú jedným z najuniverzálnejších nápadov v logike dvadsiateho storočia. Úspešne sa prispôsobujú širokej škále logík a štruktúr.

V hre tam a späť sú dve štruktúry (A) a (B) a dvaja hráči, ktorí sa bežne nazývajú Spoiler a Duplicator. (Mená sú podľa Joela Spencera na začiatku 90. rokov. Neskôr Imilman navrhol Samsona a Delilahu s použitím rovnakých iniciálok; toto umiestni Spoiler ako mužský hráč (forall) a Duplicator ako ženský (existuje).) Každý krok v hre pozostáva z ťahu Spoiler, nasledovaného ťahom Duplicator. Spojler vyberie prvok jednej z týchto dvoch štruktúr a duplikátor potom musí zvoliť prvok druhej štruktúry. Takže po (n) krokoch boli vybrané dve sekvencie, jedna z (A) a jedna z (B):

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

Táto pozícia je pre Spoiler výherou iba vtedy, ak nejaký atómový vzorec (jedného z tvarov '(R (v_0, / ldots, v_ {k-1})))' alebo '(mathrm {F} (v_0, / ldots, v_ {k-1}) = v_k) 'alebo' (v_0 = v_1) 'alebo niektorá z nich s rôznymi premennými) je uspokojená pomocou ((a_0, / ldots, a_ { n-1})) v (A), ale nie pomocou ((b_0, / ldots, b_ {n-1})) v (B) alebo naopak. Podmienka výhry pre Duplicator je v rôznych formách hry odlišná. V najjednoduchšej podobe, (EF (A, B)), hra je výhra pre Duplikátor iba vtedy, ak žiadna počiatočná časť nie je výhra pre Spoiler (tj vyhrá, ak sa nestratila konečná fáza). Pre každé prirodzené číslo (m) je hra (EF_m (A, B)); v tejto hre Duplikátor vyhrá po (m) krokoch za predpokladu, že sa ešte nestratil. Všetky tieto hry určuje Gale-Stewartova veta. Hovorí sa, že dve štruktúry (A) a (B) sú rovnocenné tam, kde má duplikátor výhernú stratégiu pre (EF (A, B)), a m-ekvivalent, ak má víťazná stratégia pre (EF_m (A, B)).

Dá sa dokázať, že ak (A) a (B) sú (m) - ekvivalentné pre každé prirodzené číslo (m), potom sú elementárne ekvivalentné. V skutočnosti, ak má Eloise výhernú stratégiu (tau) v hre Hintikka G ((phi)) na (A), kde má hniezdenie rozsahov kvantifikátora (phi) väčšina metrov a duplikátor má výhernú stratégiu (varrho) v hre (EF_m (A, B)), dve stratégie (tau) a (varrho) je možné zložiť do víťazná stratégia Eloise v G ((phi)) na (B). Na druhej strane víťaznú stratégiu pre Spoiler v (EF_m (A, B)) je možné previesť na vetu prvého poriadku, ktorá platí presne v jednej z (A) a (B), a kde hniezdenie rozsahov kvantifikátora má najviac (m) úrovní. Máme teda potrebnú a dostatočnú podmienku pre elementárnu ekvivalenciu a o niečo viac.

Ak (A) a (B) sú ekvivalentné tam a späť, potom sú určite elementárne ekvivalentné; ale v skutočnosti sa ukazuje, že ekvivalencia tam a späť je rovnaká ako elementárna ekvivalencia v infinitárnej logike, ktorá je oveľa výraznejšia ako logika prvého poriadku. Existuje veľa úprav hry, ktoré dávajú iné druhy rovnocennosti. Napríklad Barwise, Immerman a Bruno Poizat nezávisle opísali hru, v ktorej dvaja hráči majú presne (p) očíslované kamienky; každý hráč musí označiť svoje výbery štrkom a obe voľby v tom istom kroku musia byť označené kamienkami nesúcimi rovnaké číslo. Ako hra pokračuje, hráčom dôjdu kamienky, a preto budú musieť znovu použiť už použité kamienky. Podmienka pre výhru Spoiler na pozícii (a všetky nasledujúce pozície) je rovnaká ako predtým, okrem toho, že sa počítajú iba prvky nesúce štítky v tejto pozícii. Existencia výhernej stratégie pre duplikátor v tejto hre znamená, že obe štruktúry sa dohodli na vetách, ktoré používajú najviac premenných (p) (čo umožňuje, aby sa tieto premenné vyskytovali ľubovoľne často).

Teória dozadu a dozadu používa veľmi málo predpokladov o predmetnej logike. Výsledkom je, že tieto hry sú jednou z mála modelovo-teoretických techník, ktoré sa uplatňujú rovnako na konečné štruktúry, ako na nekonečné, a preto sa stávajú jedným zo základných kameňov teoretickej informatiky. Dá sa použiť na meranie expresívnej sily formálnych jazykov, napríklad dopytovacích jazykov databázy. Typický výsledok by mohol napríklad povedať, že určitý jazyk nedokáže rozlišovať medzi „párnym“a „nepárnym“; dokázali by sme to tak, že pre každú úroveň (n) zložitosti vzorcov jazyka nájdeme pár konečných štruktúr, pre ktoré má Duplicator výhernú stratégiu v back-and-end hre úrovne (n), ale jedna zo štruktúr má párny počet prvkov a druhá má nepárne číslo. Sémantici prírodných jazykov zistili, že sú užitočné hry na porovnávanie výrazových schopností zovšeobecnených kvantifikátorov. (Pozri napríklad Peters a Westerståhl 2006, oddiel IV.)

Existuje aj akási spiatočná hra, ktorá zodpovedá našej modálnej sémantike vyššie rovnakým spôsobom, ako hry Ehrenfeucht-Fraïssé zodpovedajú Hintikkovej hernej sémantike pre logiku prvého poriadku. Hráči začínajú stavom (s) v štruktúre (A) a stavom (t) v štruktúre (B). Spojler a duplikátor sa pohybujú striedavo, ako predtým. Zakaždým, keď sa pohybuje, Spoiler si vyberie, či sa má pohybovať v (A) alebo v (B), a potom sa musí duplikátor pohybovať v inej štruktúre. Pohyb sa vždy robí pohybom vpred pozdĺž šípky od aktuálneho stavu. Ak medzi nimi dvaja hráči práve prešli do stavu (s) ´ v (A) a do stavu (t) ´ v (B), a niektorí predikáti (P_i) sú na iba jeden z (s) 'a (t)', potom duplikátor stratí naraz. Stratí tiež, ak pre ňu nie sú k dispozícii žiadne šípy, ktoré by sa mohli pohybovať;ale ak Spoiler zistí, že nie sú k dispozícii žiadne šípky, ktoré by mu umožnili pohybovať sa v oboch štruktúrach, potom Duplikátor vyhrá. Ak dvaja hráči hrajú túto hru s danými počiatočnými stavmi (s) v (A) a (t) v (B) a obidve štruktúry majú práve konečne veľa štátov, potom je možné ukázať, že duplikátor má výhernú stratégiu iba vtedy, ak rovnaké modálne vety sú pravdivé v (s) v (A) ako sú pravdivé v (t) v (B).

Existuje mnoho zovšeobecnení tohto výsledku, niektoré z nich zahŕňajú nasledujúci pojem. Nech (Z) je binárny vzťah, ktorý spája stavy (A) so stavmi (B). Potom voláme (Z) bimuláciu medzi (A) a (B), ak Duplicator môže použiť (Z) ako nedeterministickú výhernú stratégiu v back-and-end hre medzi (A) a (B), kde prvým párom ťahov oboch hráčov je výber počiatočného stavu. V informatike je pojem bisimulácia rozhodujúci pre pochopenie systémov (A) a (B) ako systémov; Vyjadruje, že dva systémy interagujú so svojím prostredím rovnakým spôsobom ako každý iný, krok za krokom. Trochu predtým, ako počítačoví vedci predstavili tento pojem, sa v doktorskej práci Johana van Benthema o sémantike modálnej logiky objavil v podstate ten istý koncept (1976).

7. Ďalšie modelové teoretické hry

Logické hry v tejto časti sú nástrojmi matematikov, majú však niekoľko koncepčne zaujímavých funkcií.

7.1 Nútené hry

Nútené hry sú tiež známe ako opisné teoretiky ako hry Banach-Mazur; pozri odkazy od Kechrisa alebo Oxtobyho nižšie, kde nájdete ďalšie podrobnosti o matematickom pozadí. Teoretici modelu ich používajú ako spôsob budovania nekonečných štruktúr s kontrolovanými vlastnosťami. V najjednoduchšom prípade (forall) a (existuje) zahrajte tzv. Model Existence Game, kde (existuje) tvrdí, že pevná veta (phi) má model, zatiaľ čo (forall) tvrdí, že môže odvodiť rozpor od (phi). Na začiatku je opravená nespočetne nekonečná množina (C) nových konštantných symbolov (a_0, a_1, a_2) atď. (existuje) obhajuje disjunkciu výberom jedného disjunktu a existenciálneho výroku výberom konštanty z (C) ako svedka. (forall) môže napadnúť spojenie výberom jedného zo spojov,a všeobecné vyhlásenie výberom ľubovoľného svedka z (C). (existuje) vyhrá, ak sa nehrajú žiadne protirečivé atómové vety. (existuje) má výhernú stratégiu (konštantná vlastnosť je jedným zo spôsobov, ako opísať výhernú stratégiu) iba vtedy, ak (phi) má model. Na druhej strane, ak (forall) má výhernú stratégiu, strom (ktorý môže byť konečný) všetkých hier proti jeho výhernej stratégii súvisí s dôkazom gentzenského štýlu o negácii (phi), Táto metóda analýzy viet úzko súvisí s Bethovou metódou sémantických tabliet a s Dialogickou hrou (pozri časť 8).ak (forall) má výhernú stratégiu, strom (ktorý môže byť konečný) všetkých hier proti jeho výhernej stratégii súvisí s dôkazom gentzénskeho štýlu o negácii (phi). Táto metóda analýzy viet úzko súvisí s Bethovou metódou sémantických tabliet a s Dialogickou hrou (pozri časť 8).ak (forall) má výhernú stratégiu, strom (ktorý môže byť konečný) všetkých hier proti jeho výhernej stratégii súvisí s dôkazom gentzénskeho štýlu o negácii (phi). Táto metóda analýzy viet úzko súvisí s Bethovou metódou sémantických tabliet a s Dialogickou hrou (pozri časť 8).

Ak chcete načrtnúť myšlienku všeobecnej hry Forcing Game, predstavte si, že nespočetne nekonečný tím staviteľov stavia dom (A). Každý stavebník musí vykonať svoju vlastnú úlohu: napríklad nainštalovať kúpeľ alebo tapetu vstupnej haly. Každý staviteľ má nekonečne veľa príležitostí vstúpiť na web a pridať do domu určité množstvo materiálu; tieto sloty pre buildery sú vkladané tak, že celý proces prebieha v poradí krokov počítaných prirodzenými číslami.

Aby sme dokázali, že dom je možné postaviť na zákazku, musíme ukázať, že každý staviteľ môže samostatne plniť svoju úlohu bez ohľadu na to, čo robia ostatní stavitelia. Takže si každý tvorca predstavujeme ako hráča (existuje) v hre, kde sú všetci ostatní hráči sústredení ako (forall), a naším cieľom je dokázať, že (existuje) má víťaznú stratégiu hra. Keď sme to dokázali pre každého staviteľa osobitne, vieme si predstaviť, že budú pracovať, každý s vlastnou výhernou stratégiou. Všetci vyhrávajú svoje príslušné hry a výsledkom je jeden krásny dom.

Z technického hľadiska sú prvky štruktúry (A) pevne stanovené vopred, napríklad ako (a_0, a_1, a_2) atď., Ale vlastnosti týchto prvkov sa musia vyrovnať hrou. Každý hráč sa hýbe hádzaním do súboru atómových alebo negovaných atómových výrokov o prvkoch, pod podmienkou, že množina pozostávajúca zo všetkých doposiaľ vyhodených výrokov musí byť v súlade s pevnou množinou axiómov zapísaných pred zápasom. (Takže hádzanie do negovanej atómovej vety (neg / phi) má za následok zabránenie akémukoľvek hráčovi pridať (phi) v neskoršom štádiu.) Na konci spoločnej hry je sada atómových viet vrhnutý má kanonický model a toto je štruktúra (A); existujú spôsoby, ako zabezpečiť, aby išlo o model pevnej sady axiómov. Prípadná vlastnosť P z (A) sa považuje za vykonateľnú, ak staviteľ, ktorému bola zverená úloha, aby P bol z (A), mal výhernú stratégiu. Ústredným bodom (hlavne kvôli Ehrenfeuchtovi) je to, že spojenie nespočetne nekonečného súboru vykonateľných vlastností je opäť vynútiteľné.

Rôzne Löwenheim-Skolemove vety teórie modelov sa dajú dokázať pomocou variantov Forcing Game. V týchto variantoch netvoríme model, ale submodel daného modelu. Začíname s veľkým modelom (M) pre vetu (alebo s počítateľnou množinou viet) (phi). Potom vypíšeme podformuláre (phi) a každý hráč má podformulu s voľnou premennou, ktorej sa má venovať. Úlohou hráča je zabezpečiť, aby hneď ako sa v hre vyskytnú parametre podformulu a vo veľkom modeli je svedok pravdy vzorca, hrá sa jeden taký svedok. Po skončení hry sa spočítal submodel (M) tak, aby vyhovoval (phi).

Názov „nútenie“pochádza z aplikácie súvisiacich myšlienok Paula Cohena na zostavenie modelov teórie množín začiatkom 60. rokov. Abraham Robinson ju prispôsobil, aby vytvoril všeobecnú metódu budovania počítateľných štruktúr, a Martin Ziegler predstavil nastavenie hry. Neskôr Robin Hirsch a Ian Hodkinson použili súvisiace hry na vyriešenie niektorých starých otázok týkajúcich sa vzťahových algebier.

Nútené hry sú zdravým príkladom, ktorý je potrebné mať na pamäti pri uvažovaní o otázke Dawkinsa. Pripomínajú nám, že v logických hrách nemusí byť užitočné myslieť na hráčov, že sú proti sebe.

7.2 Hry s výberom

V tradičnej hre „vyber a choď“si vezmeš koláč a nakrájiš ho na dva menšie kúsky; potom si vyberiem jeden z kúskov a zjem ho, ten druhý nechám pre teba. Tento postup má na vás vyvíjať tlak, aby ste tortu spravodlivo nakrájali. Matematici, ktorí nie celkom chápu účel cvičenia, trvajú na opakovaní. Preto vás donútim rozrezať kúsok, ktorý som si vybral, na dve, potom vyberiem jednu z týchto dvoch; potom tento kus znova nakrájate a tak ďalej. Niektorí ešte viac nezmyselní matematici vás donútia nakrájať tortu na nespočetné množstvo kusov namiesto dvoch.

Tieto hry sú dôležité v teórii definícií. Predpokladajme, že máme kolekciu (A) objektov a rodinu (S) vlastností; každá vlastnosť nastrihá (A) na množinu tých objektov, ktoré majú danú vlastnosť, a množinu tých, ktoré ju nemajú. Nech / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ \\ / n / \ / \ / \ / \ / \ n / \ / \ / \ ıľ, / n / \ / \ / \ / \ / \ / \ / \ / \ / \ / \. nech (forall) vyberie jeden z kúskov (ktoré sú podmnožinami (A)) a vráti ho späť (existuje), aby si ho znova orezal, ešte raz pomocou vlastnosti v (S); a tak ďalej. Hneď ako (forall) vyberie prázdny kus, / \ / \ / \ / \ / \ / \ \. Hovoríme, že ((A, S)) má najvyššie hodnotenie (m), ak (forall) má stratégiu, ktorá zaisťuje, že (existuje) stratí pred ňou (m) - pohyb. Poradie ((A, S)) poskytuje cenné informácie o rodine podmnožín (A) definovateľných vlastnosťami v (S).

Variácie tejto hry, ktoré umožňujú rozrezať kus na nekonečne veľa menších kusov, sú základné v odbore teórie modelov nazývané teória stability. Všeobecne povedané, teória je „dobrá“v zmysle teórie stability, ak vždy, keď vezmeme model (A) teórie a (S) množinu vzorcov prvého poriadku v jednej voľnej premennej s parametrami z (A), štruktúra ((A, S)) má „malú“hodnosť. Iná variácia spočíva v tom, že v každom kroku sa (existuje) rozdelí na dve časti, ktoré prežili z predchádzajúcich krokov, a opäť stratí, akonáhle bude jeden z vyrezaných fragmentov prázdny. (V tejto verzii (forall) je nadbytočný.) S touto variáciou sa hodnosť ((A), S) nazýva jej dimenzia Vapnik-Chervonenkis; tento pojem sa používa v teórii výpočtového vzdelávania.

7.3 Hry na strome dvoch nástupníckych funkcií

Predstavte si strom, ktorý bol vybudovaný v úrovniach. Na spodnej úrovni je jeden koreňový uzol, ale vychádza z neho ľavá vetva a pravá vetva. Na vyššej úrovni sú dva uzly, jeden na každej vetve az každého z týchto uzlov vyrastie ľavá vetva a pravá vetva. Na vyššej úrovni sú teda štyri uzly a na každom z týchto uzlov sú opäť vetvy stromov doľava a doprava. Pokračovaním do nekonečna sa tento strom nazýva strom dvoch nástupníckych funkcií (menovite ľavého a pravého nástupcu). Berúc uzly ako prvky a zavádzajúce dva funkčné symboly pre ľavého a pravého nástupcu, máme štruktúru. Silná veta Michaela Rabina uvádza, že existuje algoritmus, ktorý nám povie, pre každú monadickú vetu druhého rádu (phi) v jazyku vhodnom pre túto štruktúru,či je (phi) pravdivé v štruktúre. („Monadický druhý rád“znamená, že logika je ako prvý rád, okrem toho, že môžeme kvantifikovať aj množiny prvkov - napríklad nie binárne vzťahy medzi prvkami.)

Rabinova veta má množstvo užitočných dôsledkov. Napríklad Dov Gabbay ju použil na preukázanie rozhodovateľnosti niektorých modálnych logík. Avšak Rabinov dôkaz, pomocou automatov, bol notoricky ťažké sledovať. Yuri Gurevich a Leo Harrington a nezávisle Andrei Muchnik našli oveľa jednoduchšie dôkazy, v ktorých je automat v hre hráč.

Tento výsledok Rabina je jedným z niekoľkých vplyvných výsledkov, ktoré spájajú hry s automatmi. Ďalším príkladom sú paritné hry, ktoré sa používajú na overovanie vlastností modálnych systémov. Pozri napríklad Stirling (2001) kapitola 6; Bradfield a Stirling (2006) diskutuje o paritných hrách pre modálny (mu) - počet.

8. Hry dialógu, komunikácie a dôkazov

Niekoľko stredovekých textov opisuje formu debaty nazývanú povinnosti. Boli tu dvaja protivníci, Opponens a Respondens. Na začiatku zasadnutia by sa účastníci sporu dohodli na pozitívnom vyjadrení, zvyčajne na nepravdivom vyhlásení. Úlohou spoločnosti Respondens bolo racionálne odpovedať na otázky spoločnosti Opponens, pričom vychádzali z pravdy pozitivity; predovšetkým sa musel vyhnúť zbytočným protirečeniam. Úlohou spoločnosti Opponens bolo pokúsiť sa prinútiť Respondensa k rozporom. Takže všeobecne vieme odpoveď na otázku Dawkins, ale nepoznáme pravidlá hry! Stredoveké učebnice popisujú niekoľko pravidiel, ktoré by sa mali v spore uplatňovať. Tieto pravidlá však nie sú stanovenými pravidlami hry; sú to usmernenia, z ktorých sa učebnice odvodzujú zo zásad správneho zdôvodnenia pomocou príkladov.(Paul Benátok ospravedlňuje jedno pravidlo praxou „veľkých logikov, filozofov, geometrov a teológov“.) Zejména bolo umožnené učiteľovi povinností objaviť nové pravidlá. Táto otvorenosť znamená, že povinnosti nie sú v našom zmysle logické hry.

Nie všetci súhlasia s predchádzajúcou vetou. Napríklad Catarina Dutilh Novaes (2007, 6) podrobne obhajuje názor, že povinnosti predstavujú „pozoruhodný prípad koncepčnej podobnosti medzi stredovekým a moderným teoretickým rámcom“. Bez ohľadu na to, aký názor na túto otázku berieme, tieto diskusie inšpirovali jednu dôležitú líniu moderného výskumu v oblasti logických hier.

Predstavte si (existuje) ústnu skúšku z teórie dôkazov. Skúšajúci jej dá trest a vyzve ju, aby to začala dokazovať. Ak má veta tvar

(phi / vee / psi)

potom má právo vybrať si jednu z viet a povedať: „Dobre, ukážem túto.“(Ak je skúšajúci v skutočnosti intuicionista, môže trvať na tom, aby si vybrala jednu z viet na preukázanie.) Na druhej strane, ak je trest

(phi / wedge / psi)

potom skúšajúci, ako skúšajúci, by si mohol dobre vybrať jeden zo spojoviek sám a vyzvať ju, aby to dokázala. Ak vie, ako dokázať spojenie, určite vie, ako dokázať spojku.

Prípad (phi / rightarrow / psi) je trochu jemnejší. Pravdepodobne bude chcieť začať predpokladaním (phi), aby vyvodila (psi); existuje však určité riziko zámeny, pretože vety, ktoré doteraz napísala, sú všetky veci, ktoré treba dokázať, a (phi) nie je dôkazom. Skúšajúci mu môže pomôcť tým, že povie „Budem predpokladať (phi), a uvidíme, či sa odtiaľto dostanete k (psi)“. V tomto bode existuje šanca, že vidí spôsob, ako sa dostať k (psi) odvodením rozporu od (phi); takže môže obrátiť stoly na examinátora a vyzvať ho, aby preukázal, že jeho predpoklad je konzistentný, s cieľom dokázať, že tomu tak nie je. Symetria nie je dokonalá: požiadal ju, aby ukázala, že veta je všade pravdivá, a zároveň ho vyzýva, aby ukázala, že veta je niekde pravdivá. Napriek tomu môžeme vidieť druh duality.

Myšlienky tohto druhu ležia za dialektickými hrami Paula Lorenzena. Ukázal, že s určitým množstvom tlačenia a strkania je možné napísať pravidlá pre hru, ktorá má tú vlastnosť, že (existuje) má výhernú stratégiu iba vtedy, ak veta, ktorú má na začiatku, je veta o intuicionistickej logike. V geste smerom k stredovekým debatám nazval (existuje) navrhovateľa a druhého hráča oponentom. Tak ako v stredovekých záväzkoch, aj ona vyhráva tým, že proroka nasmeruje do bodu, v ktorom sú jediným možným pohybom očividné rozpory.

Lorenzen tvrdil, že jeho hry poskytovali dôvody pre intuicionistickú aj klasickú logiku (alebo podľa jeho slov z nich robili „gerechtfertigt“, Lorenzen (1961,196)). Nanešťastie akékoľvek „ospravedlnenie“zahŕňa presvedčivú odpoveď na otázku Dawkinsa a toto Lorenzen nikdy neposkytol. Napríklad hovoril o pohyboch ako o „útokoch“, aj keď (podobne ako pri výbere skúšajúceho na (phi / wedge / psi) vyššie) vyzerajú skôr ako pomoc ako nepriateľstvo.

Vstupná dialógová logika poskytuje ucelenejší prehľad o hrách Lorenzena a niekoľkých najnovších variantoch. V súčasnej podobe (január 2013) sa vyhýba tvrdeniam Lorenzena o odôvodnení logiky. Namiesto toho opisuje hry ako sémantiku pre logiku (bod, s ktorým by Lorenzen určite súhlasil), a dodáva, že na pochopenie rozdielov medzi logikou môže byť užitočné porovnať ich sémantiku.

Z tohto hľadiska predstavujú Lorenzenove hry dôležitý paradigma toho, čo nedávni teoretici dôkazov nazvali sémantikou dôkazov. Sémantika dôkazov dáva „zmysel“nielen myšlienke preukázateľnosti, ale každému jednotlivému kroku dôkazu. Odpovedá na otázku „Čo dosiahneme tým, že sa tento konkrétny krok preukáže?“V deväťdesiatych rokoch veľa pracovníkov na logickom konci počítačovej vedy hľadalo hry, ktoré by stáli za lineárnou logikou, a niektoré ďalšie systémy dokazovania rovnako ako Lorenzenove hry stáli za intuicionistickou logikou. Andreas Blass, neskôr Samson Abramsky a jeho kolegovia, dali hry, ktoré korešpondovali s časťami lineárnej logiky, ale v čase písania ešte nemáme dokonalú zhodu medzi hrou a logikou. Tento príklad je obzvlášť zaujímavý, pretože odpoveď na otázku Dawkins by mala poskytnúť intuitívny výklad zákonov lineárnej logiky, čo táto logika veľmi potrebovala. Hry Abramsky a kol. rozprávať príbeh o dvoch vzájomne pôsobiacich systémoch. Ale zatiaľ čo začal s hrami, v ktorých sa hráči slušne striedajú, Abramsky neskôr dovolil hráčom konať „distribuovaným, asynchrónnym spôsobom“a navzájom si ich všimli, len keď sa rozhodli. Tieto hry už nie sú v normálnom formáte logických hier a ich interpretácia v reálnom živote vyvoláva množstvo nových otázok. Ale zatiaľ čo začal s hrami, v ktorých sa hráči slušne striedajú, Abramsky neskôr dovolil hráčom konať „distribuovaným, asynchrónnym spôsobom“a navzájom si ich všimli, len keď sa rozhodli. Tieto hry už nie sú v normálnom formáte logických hier a ich interpretácia v reálnom živote vyvoláva množstvo nových otázok. Ale zatiaľ čo začal s hrami, v ktorých sa hráči slušne striedajú, Abramsky neskôr dovolil hráčom konať „distribuovaným, asynchrónnym spôsobom“a navzájom si ich všimli, len keď sa rozhodli. Tieto hry už nie sú v normálnom formáte logických hier a ich interpretácia v reálnom živote vyvoláva množstvo nových otázok.

Giorgi Japaridze navrhol „logiku počítateľnosti“pre štúdium výpočtov. Jeho syntax je logika prvého poriadku a niektoré ďalšie položky pripomínajú lineárnu logiku. Jeho sémantika je z hľadiska sémantických hier s niektorými neobvyklými vlastnosťami. Napríklad nie je vždy rozhodnuté, ktorý hráč urobí ďalší ťah. Pojem strategické funkcie už nie je dostatočný na opis hráčov; Namiesto toho Japaridze popisuje spôsoby čítania druhého hráča (hráča (existuje) v našom zápise) ako druhu počítačového stroja. Ďalšie informácie sú na jeho webovej stránke.

Ďalšou skupinou hier rovnakej všeobecnej rodiny ako Lorenzen sú hry s ukážkami Pavla Pudlak 2000. V tomto prípade je protihráč (nazývaný Prover) v úlohe advokáta na súde, ktorý vie, že navrhovateľ (nazývaný protivník) je vinný z nejakého trestného činu. Navrhovateľ bude trvať na tom, že je nevinný, a je pripravený povedať lži, aby sa bránil. Cieľom oponenta je prinútiť navrhovateľa, aby bol v rozpore s tým, čo je zaznamenané, ako už bolo povedané; ale Oponent si vedie záznam a (ako vo vyššie uvedených kamienkových hrách) niekedy musí z dôvodu nedostatku miesta alebo pamäte vyhodiť položky zo záznamu. Dôležitou otázkou nie je to, či má oponent výhernú stratégiu (predpokladá sa od začiatku, že ju má), ale koľko pamäte potrebuje pre svoj záznam. Tieto hry sú užitočným zariadením na zobrazovanie hornej a dolnej hranice dĺžok dôkazov v rôznych systémoch dôkazov.

Ďalším typom logickej hry, ktorá umožňuje klamstvo, je Ulamova hra s lži. Jeden hráč tu myslí na číslo v určitom rozsahu. Cieľom druhého hráča je zistiť, aké je toto číslo tým, že položíte prvému hráčovi áno / nie otázky; ale prvý hráč môže vo svojich odpovediach uviesť určitý počet klamstiev. Rovnako ako v hrách Pudlak, určite existuje víťazná stratégia pre druhého hráča, ale otázkou je, ako tvrdo musí tento hráč pracovať, aby vyhral. Meradlom nie je čas ani pamäť, ale čas: koľko otázok musí položiť? Cignoli a kol. 2000 Kapitola 5 spája túto hru s mnohými hodnotami.

Aby sa na chvíľu vrátil k Lorenzenovi, nedokázal rozlíšiť rôzne postoje, ktoré by človek mohol zaujať v argumente: uviedol, predpokladal, pripúšťal, pýtal sa, útočil, dopúšťal sa. Či je skutočne možné definovať všetky tieto predstavy bez toho, aby sa predpokladala nejaká logika, je priekopníkom. Ale nevadí to; zdokonalenie Lorenzenových hier v tomto duchu by mohlo slúžiť ako prístup k neformálnej logike, a najmä k výskumu, ktorého cieľom je systematizovať možné štruktúry zdravých neformálnych argumentov. V tejto súvislosti pozri Walton a Krabbe 1995. Relevantné sú aj dokumenty v Bench-Capon a Dunne 2007.

Bibliografia

Niektoré zo seminárnych prác Henkina a Lorenzena a niektoré z citovaných článkov sa objavujú v zbierke Infinitistické metódy (Zborník sympózia o základoch matematiky, Varšava, 2. - 9. septembra 1959), Oxford: Pergamon Press, 1961 Redaktori nie sú menovaní.

Hry v histórii logiky

• Dutilh Novaes, Catarina, 2007, Formalizácia stredovekých logických teórií: Suppositio, Consequentiae a Povinnosti, New York: Springer-Verlag.
• Hamblin, Charles, 1970, Fallacies, London: Methuen.
• Hilbert, David, 1967, „Die Grundlagen der Mathematik“, preložený ako „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“, preložený v časti „Súčasná epistemologická situácia v matematike“v Paolo Mancosu, od Brouwera k Hilbertovi: Debata o základoch matematiky v 20. rokoch 20. storočia v New Yorku.: Oxford University Press, 1988, s. 123 - 142.
• Zermelo, Ernst, 1913, „Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels“, v EW Hobson a AEH Love (ed.), Zborník z piateho medzinárodného kongresu matematikov, zväzok II, Cambridge: Cambridge University Press.

Hry pre výučbu logiky

• Barwise, Jon a John Etchemendy, 1995, Jazyk logiky prvého poriadku, vrátane sveta Tarskiho 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, „Naučiť sa myslieť: Logika pre deti“, v zborníku dvadsiateho svetového kongresu filozofie (zväzok 3: Filozofia vzdelávania), David M. Steiner (ed.), Bowling Green Ohio: Bowling Green State University Philosophy, pp., 11–19.
• Nifo, Agostino, 1521, Dialectica Ludicra (Logická hra), Florencia: Bindonis.
• Weng, Jui-Feng, s Shian-Shyong Tseng a Tsung-Ju Lee, 2010, „Výučba logickej logiky prostredníctvom ladenia pravidiel hry,“IEEE Transactions, Learning Technologies, 3 (4): 319–328. [Používa hry Pac-Man na výučbu booleovskej logiky pre študentov stredných škôl.]

Logické hry

• Gale, David a FM Stewart, 1953, „Nekonečné hry s dokonalými informáciami“, v Príspevkoch k teórii hier II (Annals of Mathematics Studies 28), HW Kuhn a AW Tucker (ed.), Princeton: Princeton University Press, pp 245 - 266.
• Kechris, Alexander S., 1995, Teória klasickej deskriptívnej množiny, New York: Springer-Verlag.
• Marion, Mathieu, 2009, „Prečo hrať logické hry?“V vydavateľoch Ondrej Majer, Ahti-Veikko Pietarinen a Tero Tulenheimo., Games: Unifying Logic, Language and Philosophy, New York: Springer-Verlag, s. 3-25,
• Osbourne, Martin J. a Ariel Rubinstein, 1994, Kurz teórie hier, Cambridge: MIT Press.
• Väänänen, Jouko, 2011, Modely a hry, Cambridge: Cambridge University Press.
• van Benthem, Johan, 2011, Logická dynamika informácií a interakcie, Cambridge: Cambridge University Press, 2011.
• –––, 2014, Logické hry, Cambridge, MA: MIT Press.

Sémantické hry pre klasickú logiku

• Henkin, Leon, 1961, „Niektoré poznámky o nekonečne dlhých receptúrach“, v Infinitistic Methods, op. cit. 167 až 183.
• Hintikka, Jaakko, 1973, Logic, Language-Games and Information: Kantian Themes in Philosophy of Logic, Oxford: Clarendon Press.
• Hintikka, Jaakko, 1996, Princip of Mathematics Revisited, New York: Cambridge University Press. [Pozri napríklad strany 40, 82 o zvolenom axióme.]
• Hodges, Wilfrid, 2001, „Elementary Predicate Logic 25: Skolem Functions“, v Dov Gabbay, a Franz Guenthner (ed.), Handbook of Philosophical Logic I, 2. vydanie, Dordrecht: Kluwer, s. 86–91. [Dôkaz o rovnocennosti hry a Tarskiho sémantika.]
• Kolaitis, Ph. G., 1985, „kvantifikácia hier“, v J. Barwise a S. Feferman (eds.), Model-Theoretic Logics, New York: Springer-Verlag, str. 365-421.
• Peirce, Charles Sanders, 1898, Zdôvodnenie a logika vecí: Cambridge Conference Lectures of 1898, ed. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.

Sémantické hry s nedokonalými informáciami

• Hintikka, Jaakko a Gabriel Sandu, 1997, „Game-teoretická sémantika“, v Johan van Benthem a Alice ter Meulen (ed.), Handbook of Logic and Language, Amsterdam: Elsevier, s. 361–410.
• Hodges, Wilfrid, 1997, „Kompozitná sémantika pre jazyk nedokonalých informácií“, Logic Journal of IGPL, 5: 539–563.
• Janssen, Theo MV a Francien Dechesne, 2006, „Signaling: a záludné podnikanie“, v J. van Benthem et al. (eds.), Age of Alternative Logics: Assessment of Philosophy of Logic and Mathematics Today, Dordrecht: Kluwer, s. 223 - 242.
• Mann, Allen L., Gabriel Sandu a Merlin Sevenster, 2011, Logika priateľská k nezávislosti: prístup založený na teórii hier (londýnska poznámka o matematickej spoločnosti v Londýne, séria 386), Cambridge: Cambridge University Press.
• von Neumann, John a Oskar Morgenstern, 1944, Teória hier a hospodárskeho správania, Princeton: Princeton University Press.
• Väänänen, Jouko, 2007, Logika závislosti: Nový prístup k logike nezávislosti, Cambridge: Cambridge University Press.

Sémantické hry pre ďalšiu logiku

• Bradfield, Julian a Colin Stirling, 2006, „Modal mu-calculi“, P. Blackburn a kol. (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áštne vydanie o logike a hrách.]
• Hennessy, Matthew a Robin Milner, 1985, „Algebraické zákony pre indeterminizmus a súbežnosť“, Journal of the ACM, 32: 137–162.
• Parikh, Rohit, 1985, „Logika hier a ich aplikácií“, v Marek Karpinski a Jan van Leeuwen (ed.), „Témy v teórii výpočtu“, Annals of Diskret Mathematics, 24: 111–140.
• Pauly, Marc a Rohit Parikh (ed.), 2003, Studia Logica, 72 (2): 163–256 [Special issue on Game Logic.]
• Stirling, Colin, 2001, Modálne a časové vlastnosti procesov, New York: Springer-Verlag.
• van Benthem, Johan, 2006, „Epistemická logika IF hier“, v Randall Auxier a Lewis Hahn (eds.), Filozofia Jaakka Hintikka, Chicago: Open Court, s. 481–513.
• van Benthem, Johan s Amitabha Guptou a Rohitom Parikhom, 2011, Dôkaz, výpočty a agentúry, 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, Teória základných modelov, Stanford: Publikácie CSLI a FoLLI.
• Ebbinghaus, Heinz-Dieter a Jörg Flum, 1999, konečná teória modelu, 2. vydanie, New York: Springer.
• Ehrenfeucht, Andrzej, 1961, „Aplikácia hier na problém úplnosti formalizovaných teórií“, Fundamenta Mathematicae, 49: 129–141.
• Grädel, Erich a Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema a Scott Weinstein, 2007, konečná teória modelu, Berlín: Springer-Verlag.
• Libkin, Leonid, 2004, Prvky konečnej teórie modelov, Berlín, Springer-Verlag.
• Otto, Martin, 1997, ohraničená variabilná logika a štúdium sčítania na konečných modeloch (prednášky v logike, 9), Berlín: Springer-Verlag.
• Peters, Stanley a Dag Westerståhl, 2006, Quantifiers in Language and Logic, Oxford: Clarendon Press.
• Tarski, Alfred, 1946, „Vystúpenie na konferencii v Bicentennial University of Princeton University o problémoch matematiky (17. - 19. decembra 1946),“Hourya Sinaceur (ed.), Bulletin of Symbolic Logic, 6 (2000): 1-44.
• van Benthem, Johan, 2001, „Teória korešpondencie“, v publikácii Dov Gabbay a Franz Guenthner (ed.), Handbook of Philosophical Logic III, 2. vydanie, Dordrecht: Kluwer.

Ďalšie modelové teoretické hry

• Anthony, Martin a Norman Biggs, 1992, Computational Theory Theory, Cambridge: Cambridge University Press. [Pre dimenziu Vapnik-Chervonenkis.]
• Gurevich, Yuri a Leo Harrington, 1984, „Stromy, automaty a hry,“v HR Lewis (ed.), Zborník sympózia ACM o teórii výpočtovej techniky, San Francisco: ACM, s. 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, Teória modelov, 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 dialógu, komunikácie a dôkazu

• Abramsky, Samson a Radha Jagadeesan, 1994, „Hry a úplnosť pre multiplikatívnu lineárnu logiku“, Journal of Symbolic Logic, 59: 543–574.
• Abramsky, Samson a Paul-André Melliès, 1999, „Súbežné hry a úplnosť“, v zborníku zo štrnásteho medzinárodného sympózia o logike v informatike, počítačová veda Press of IEEE, s. 431–442.
• Bench-Capon, TJM a Paul E. Dunne, 2007, „Argumentácia v umelej inteligencii“, Artificial Intelligence, 171: 619–641. [Úvod k bohatej zbierke článkov na rovnakú tému na stranách 642–937.]
• Blass, Andreas, 1992, „Herná sémantika pre lineárnu logiku“, Annals of Pure and Applied Logic, 56: 183–220.
• Cignoli, Roberto LO, Itala ML D'Ottaviano a Daniele Mundici, 2000, Algebraické základy mnohokrokového odôvodnenia, Dordrecht: Kluwer.
• Felscher, Walter, 2001, „Dialógy ako základ pre intuicionálnu logiku“, v Dov Gabbay a Franz Guenthner (ed.), Handbook of Philosophical Logic V, 2. vydanie, Dordrecht: Kluwer.
• Hodges, Wilfrid a Erik CW Krabbe, 2001, „Nadácie pre dialóg“, zborník Aristotelian Society (Supplementary Volume), 75: 17–49.
• Japaridze, Giorgi, 2003, „Úvod do logiky počítateľnosti“, Annals of Pure and Applied Logic, 123: 1–99.
• Lorenzen, Paul, 1961 „Ein dialogisches Konstruktivitätskriterium,“v Infinitistic Methods, op. cit. 1961, str. 193 - 200.
• Pudlak, Pavel, 2000, „Dôkazy ako hry“, American Mathematical Monthly, 107 (6): 541–550.
• Walton, Douglas N. a Erik CW Krabbe, 1995, Záväzok v dialógu: Základné pojmy interpersonálneho zdôvodnenia, Albany: State University of New York Press.

Akademické nástroje

	Ako citovať tento záznam.
	Ukážku verzie tohto príspevku vo formáte PDF si môžete pozrieť na stránke Friends of the SEP Society.
	Vyhľadajte túto vstupnú tému v projekte Internet Philosophy Ontology Project (InPhO).
	Vylepšená bibliografia tohto záznamu vo PhilPapers s odkazmi na jeho databázu.

Ďalšie internetové zdroje