Esmakordselt avaldatud reedel 27. juulil 2001; sisuline redaktsioon reedel 16. augustil 2019
Kahe mängija vahelised mängud, kus üks mängija võidab ja kaotab, said kahekümnenda sajandi teisel poolel paljudes loogikaharudes tuttavaks tööriistaks. Olulised näited on tõe määratlemiseks kasutatavad semantilised mängud, edasi-tagasi mängud, mida kasutatakse struktuuride võrdlemiseks, ja dialoogimängud, et väljendada (ja võib-olla selgitada) formaalseid tõestusi.
1. Mängud loogika ajaloos
2. Loogilised mängud
3. Klassikalise loogika semantilised mängud
4. Ebatäiusliku teabega semantilised mängud
5. Muu loogika semantilised mängud
6. Tagasi ja tagasi mängud
7. Muud mudelteoreetilised mängud
7.1 Sunnimängud
7.2 Lõika ja vali mängud
7.3 Mängud kahe järjestikuse funktsiooni puul
8. Dialoogi, suhtluse ja tõestuse mängud
Bibliograafia
Mängud loogika ajaloos
Mängud loogika õpetamiseks
Loogilised mängud
Klassikalise loogika semantilised mängud
Ebatäiusliku teabega semantilised mängud
Muu loogika semantilised mängud
Tagasi ja teise mängu mängud
Muud mudelateoreetilised mängud
Dialoogi, suhtluse ja tõestuse mängud
Akadeemilised tööriistad
Muud Interneti-ressursid
Seotud kirjed
1. Mängud loogika ajaloos
Loogika ja mängude seosed ulatuvad kaugele. Kui mõelda vaidlusele kui omamoodi mängule, siis Aristoteles lõi juba ühenduse; tema kirjutised silogismi kohta on tihedalt seotud tema arutelude eesmärkide ja reeglite uurimisega. Aristotelese vaatenurk jäi loogika keskaegsesse üldnime: dialektika. Kahekümnenda sajandi keskel taastas Charles Hamblin dialoogi ja mõistliku arutluse reeglite vahelise seose, varsti pärast seda, kui Paul Lorenzen oli ühendanud dialoogi loogika konstruktiivsete alustega.
Mängude ja õpetamise vahel on tihedad seosed. Kirjanikud räägivad kogu keskaja jooksul dialoogidest kui viisist, kuidas õpetada või katsetada mõistliku arutluse kasutamist. Meil on vähemalt kaks kuueteistkümnenda sajandi alguse loogikaõpikut, mis esitavad seda ühele õpilasele mõeldud mänguna, ja Lewis Carrolli raamat „Mängu loogika“(1887) on veel üks näide samas žanris. Ka tänapäevaseid näiteid on palju, ehkki ilmselt pole olnud piisavalt järjepidevust, et õigustada loogika õpetamise traditsiooni mängudest rääkimist.
Matemaatiline mänguteooria asutati kahekümnenda sajandi alguses. Ehkki matemaatilisi seoseid loogikaga ei tekkinud kuni 1950. aastateni, on silmatorkav, kui paljud mängude teooria varastest pioneeridest on tuntud ka loogika panuse kaudu: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo ja teised. 1953. aastal lõid David Gale ja Frank Stewart viljakaid seoseid teooria ja mängude vahel. Vahetult pärast seda pakkus Leon Henkin välja mängude kasutamise viisi, kuidas anda infinitaarsete keelte jaoks semantikat.
Kahekümnenda sajandi esimene pool oli loogika suureneva ranguse ja professionaalsuse ajastu ning enamikule selle perioodi logistidest oleks mängude kasutamine loogikas ilmselt tundunud kergemeelne. Intuitsionist LEJ Brouwer väljendas seda suhtumist, kui ta süüdistas oma vastaseid matemaatika "mänguks degenereerumises" (nagu David Hilbert teda 1927. aastal tsiteeris, viidatud van Heijenoortis 1967). Hermann Weyl (viidatud Mancosu 1998) kasutas mängude mõistet Hilberti metamaatika selgitamiseks: matemaatilised tõestused kulgevad nagu mõttetu mängu näidendid, kuid võime seista väljaspool mängu ja küsida selle kohta tähenduslikke küsimusi. Wittgensteini keelemängud kutsusid logistid vähe esile. Kuid sajandi teisel poolel liikus loogilise uurimistöö raskuskese alustest tehnikani,ja umbes 1960. aastast alates kasutati mänge loogilistes paberites üha sagedamini.
21. sajandi alguseks oli laialt aktsepteeritud, et mängud ja loogika käivad koos. Selle tulemuseks oli loogika ja mängude uute kombinatsioonide tohutu levik, eriti valdkondades, kus loogikat rakendatakse. Paljud neist uutest arengutest said alguse puhtalt loogikast, ehkki täna järgivad nad omaenda tegevuskavasid. Üheks selliseks valdkonnaks on argumentatsiooniteooria, kus mängud moodustavad vahendi väitluste struktuuri analüüsimiseks.
Allpool keskendume neile mängudele, mis on kõige tihedamalt seotud puhta loogikaga.
2. Loogilised mängud
Mänguteooria seisukohast pole peamised mängud, mida loogikud uurivad, sugugi tüüpilised. Tavaliselt on neil vaid kaks mängijat, neil on sageli lõpmatu pikkus, ainsad tulemused on võidavad ja kaotavad ning tegevuste või tulemustega ei kaasne tõenäosusi. Loogilise mängu kõige tähtsamad põhiosad on järgmised.
Mängijaid on kaks. Üldiselt võime neid nimetada (forall) ja (on olemas). Hääldused 'Abelard' ja 'Eloise' ulatuvad 1980ndate keskpaika ja kinnitavad mängijaid meeste ja naistena, muutes viite hõlpsamaks: tema liigutus, tema käik. Muud nimed on mängijatel tavalised loogiliste mängude puhul.
Mängijad valivad komplekti (Omega), mida nimetatakse mängu domeeniks, elemendid. Valides loovad nad järjestuse
[a_0, a_1, a_2, \ ldots)
elementide hulgast (Omega). (Omega) elementide lõpmatuid jadasid nimetatakse näidenditeks. (Omega) elementide lõplikke jadasid nimetatakse positsioonideks; nad lindistavad seda, kuhu näidend teatud aja jooksul jõudis. Funktsioon (tau) (pöördefunktsioon või mängijafunktsioon) viib iga positsiooni (mathbf {a}) kas (olemas) või (forall); kui (tau (mathbf {a}) = \ eksisteerib), tähendab see, et kui mäng on jõudnud (mathbf {a}), teeb mängija (eksisteeriv) järgmise valiku (ja samamoodi koos (forall)). Mängureeglid määratlevad kaks komplekti (W _ { forall}) ja (W _ { on olemas}), mis koosnevad positsioonidest ja mängudest ning millel on järgmised omadused: kui positsioon (mathbf {a}) on (W _ { forall}), nii on ka iga esitus või pikem positsioon, mis algab tähega (mathbf {a}) (ja samamoodi ka sõnaga (W _ { on olemas}));ning ükski esitamine pole nii (W _ { forall}) kui ka (W _ { eksisteeriv}). Me ütleme, et mängija (forall) võidab mängu (mathbf {b}) ja et (mathbf {b}) on (forall) võit, kui (mathbf {b}) asub asukohas (W _ { forall}); kui mõni positsioon (mathbf {a}), mis on (mathbf {b}) algne segment, asub (W _ { forall}), siis ütleme, et see mängija (forall) võidab juba (mathbf {a}). (Ja samamoodi nagu (on olemas) ja (W _ { on olemas}).) Kokkuvõtlikult võib öelda, et loogiline mäng on 4-osaline ((Omega, \ tau), (W_ { forall}), (W _ { on olemas})) koos äsja kirjeldatud omadustega.siis ütleme, et mängija (forall) võidab juba (mathbf {a}). (Ja samamoodi nagu (on olemas) ja (W _ { on olemas}).) Kokkuvõtlikult võib öelda, et loogiline mäng on 4-osaline ((Omega, \ tau), (W_ { forall}), (W _ { on olemas})) koos äsja kirjeldatud omadustega.siis ütleme, et mängija (forall) võidab juba (mathbf {a}). (Ja samamoodi nagu (on olemas) ja (W _ { on olemas}).) Kokkuvõtlikult võib öelda, et loogiline mäng on 4-osaline ((Omega, \ tau), (W_ { forall}), (W _ { on olemas})) koos äsja kirjeldatud omadustega.
Me ütleme, et loogiline mäng on täielik, kui iga mäng toimub kas (W _ { forall}) või (W _ { on olemas}), nii et viike pole. Kui ükski selgesõnaline erand ei tee, eeldatakse loogiliste mängude koguarvust. (Ärge ajage segamini olemist palju kindlama omadusega, milleks on määramine - vt allpool.)
Ainult matemaatilise mugavuse huvides eeldab ülaltoodud määratlus, et mäng jätkub lõpmatuseni ka siis, kui mängija on mingis piiratud positsioonis võitnud; pole mingit huvi selle vastu, mis juhtub pärast seda, kui mängija on võitnud. Paljudel loogilistel mängudel on omadus, et igas mängus on üks mängijatest juba mingil piiratud positsioonil võitnud; Seda tüüpi mängud on väidetavalt hästi põhjendatud. Veelgi tugevam tingimus on see, et on olemas mingi lõplik arv (n), nii et igas mängus on mõni mängija juba võitnud (n) kohaga; sel juhul ütleme, et mäng on piiratud pikkusega.
Mängija strateegia on reeglistik, mis kirjeldab täpselt, kuidas see mängija peaks valima, sõltuvalt sellest, kuidas kaks mängijat on varasemate käikude ajal valinud. Matemaatiliselt koosneb (forall) strateegia funktsioonist, mis viib iga positsiooni (mathbf {a}) koos (tau (mathbf {a}) = \ forall) elemendi (b) (Omega); mõtleme sellele kui käsku (forall) valida (b), kui mäng on jõudnud positsiooni (mathbf {a}). (Samamoodi strateegiaga (eksisteerib).) Strateegia mängija jaoks on võidetav, kui see mängija võidab kõik mängud, milles ta strateegiat kasutab, sõltumata sellest, mida teine mängija teeb. Enamikul mängijatest on võidustrateegia (kuna vastasel juhul saavad mängijad oma võidustrateegiaid üksteise vastu mängida ja mõlemad võidavad,on vastuolus sellega, et (W _ { forall}) ja (W _ { on olemas}) pole ühist näidendit). Aeg-ajalt võib juhtuda olukordi, kus tundub, et kahel mängijal on võidustrateegiad (näiteks allpool toodud sundmängudes), kuid põhjalikum vaatlus näitab, et need kaks mängivad tegelikult erinevaid mänge.
Mäng loetakse määratuks, kui ühel või teisel mängijast on võidustrateegia. Mänge, mida ei määrata, on palju, nagu Gale ja Stewart näitasid 1953. aastal valitud aksioomi kasutades. See avastus viis settekindluse mõiste oluliste rakenduste rakendamiseni setteooria alustes (vt sissekanne suurtest kardinalidest ja determinatsioonist). Gale ja Stewart osutusid ka oluliseks teoreemiks, mis kannab nende nime: Iga hästi põhjendatud mäng on kindel. Sellest järeldub, et iga piiratud pikkusega mäng on kindlaks määratud - see on Zermelole teada juba 1913. aastal (Gale-Stewarti teoreemi täpsem lause on see. Mäng (G) öeldakse olevat suletud, kui (on olemas) võidab kõik (G) mängud, milles ta pole veel üheski lõplikus positsioonis kaotanud. Teoreem väidab, et iga suletud mäng on määratud. Teoreemi tõestamine on põhimõtteliselt lihtne: nimetagem positsiooni võitjaks (forall), kui tal on sellest positsioonist lähtuv võidustrateegia. Oletame, et (forall) pole mängus võidustrateegiat, st alguses ei võida positsiooni (forall). Kui esimene käik on (forall) käik, siis pärast tema käiku positsioon teda ikkagi võita ei saa. Kui esimene samm on (eksisteerib) käik, peab tal olema käik, mille järel positsioon ei võida ikka veel (forall), sest vastasel juhul oleks eelmine positsioon võitnud (forall). Mäng jätkub sel viisil lõpmata palju liikumisi positsioonide vahel, mis ei võida (forall). Kuna mäng on suletud, võidab (eksisteerib).)Oletame, et (forall) pole mängus võidustrateegiat, st alguses ei võida positsiooni (forall). Kui esimene käik on (forall) käik, siis pärast tema käiku positsioon teda ikkagi võita ei saa. Kui esimene samm on (eksisteerib) käik, peab tal olema käik, mille järel positsioon ei võida ikka veel (forall), sest vastasel juhul oleks eelmine positsioon võitnud (forall). Mäng jätkub sel viisil lõpmata palju liikumisi positsioonide vahel, mis ei võida (forall). Kuna mäng on suletud, võidab (eksisteerib).)Oletame, et (forall) pole mängus võidustrateegiat, st alguses ei võida positsiooni (forall). Kui esimene käik on (forall) käik, siis pärast tema käiku positsioon teda ikkagi võita ei saa. Kui esimene samm on (eksisteerib) käik, peab tal olema käik, mille järel positsioon ei võida ikka veel (forall), sest vastasel juhul oleks eelmine positsioon võitnud (forall). Mäng jätkub sel viisil lõpmata palju liikumisi positsioonide vahel, mis ei võida (forall). Kuna mäng on suletud, võidab (eksisteerib).)Kui esimene samm on (eksisteerib) käik, peab tal olema käik, mille järel positsioon ei võida ikka veel (forall), sest vastasel juhul oleks eelmine positsioon võitnud (forall). Mäng jätkub sel viisil lõpmata palju liikumisi positsioonide vahel, mis ei võida (forall). Kuna mäng on suletud, võidab (eksisteerib).)Kui esimene samm on (eksisteerib) käik, peab tal olema käik, mille järel positsioon ei võida ikka veel (forall), sest vastasel juhul oleks eelmine positsioon võitnud (forall). Mäng jätkub sel viisil lõpmata palju liikumisi positsioonide vahel, mis ei võida (forall). Kuna mäng on suletud, võidab (eksisteerib).)
Nii nagu klassikalises mänguteoorias, toimib ka loogiliste mängude määratlus ülalpool riidehobuna, millele võime riputada ka teisi mõisteid. Näiteks on tavaline, et on olemas mõned seadused, mis kirjeldavad, milliseid (Omega) elemente saab mängija konkreetse käigu jaoks valida. Rangelt pole see täpsustamine vajalik, kuna võidustrateegiaid ei mõjuta see, kui otsustame selle asemel, et seadust rikkuv mängija kaotab kohe; kuid paljude mängude jaoks tundub selline vaatamisviis ebaloomulik. Allpool näeme mõnda muud lisafunktsiooni, mida saab mängudele lisada.
Ülaltoodud mängu ja strateegia määratlused olid puhtalt matemaatilised. Nii jätsid nad välja selle, mis on ilmselt mängude kõige olulisem omadus, nimelt see, et inimesed mängivad neid (vähemalt metafooriliselt). Mängijate eesmärk on võita ja neile avatud strateegiaid uurides uurime, milline käitumine on konkreetse eesmärgiga inimese jaoks mõistlik. Enamikus mängudes on mitu mängijat, seega saame uurida, milline on mõistlik vastus kellegi teise käitumisele. Mängijate käikude ja võimalike strateegiate piiramisega saame uurida piiratud ratsionaalsust, kus agent peab tegema piiratud teabe, mälu või aja tingimustes ratsionaalseid otsuseid.
Lühidalt, mänge kasutatakse ratsionaalsuse ja piiratud ratsionaalsuse modelleerimiseks. See on sõltumatu seostest loogikaga. Kuid mõned loogikad olid mõeldud ratsionaalse käitumise aspektide uurimiseks ja viimastel aastatel on üha tavalisem siduda need loogikad sobivate mängudega. Vt 5. jagu ('Semantilised mängud muudele loogikatele') ja selle bibliograafiat.
Kuid alles hiljuti olid loogilised mängud ratsionaalse käitumisega seotud üsna erineval viisil. Pinnal polnud kõnealusel loogikal otsest seost käitumisega. Loogikud ja matemaatikud panid aga tähele, et mõnda ideed võiks muuta intuitiivsemaks, kui need oleks seotud võimalike eesmärkidega. Näiteks paljudes loogiliste mängude rakendustes on keskne mõte mängija jaoks võidu strateegia (eksisteeriv). Sageli osutuvad need strateegiad (või nende olemasolu) ekvivalentseks loogilise tähtsusega asjaga, mille oleks võinud määratleda ilma mänge kasutamata - näiteks tõestusmaterjalina. Kuid mängud annavad parema määratluse, kuna need pakuvad sõna otseses mõttes teatud motivatsiooni: (eksisteerib) üritab võita.
See tõstatab küsimuse, mis pole matemaatiliselt eriti huvipakkuv, kuid see peaks puudutama loogilisi mänge kasutavaid filosoofe. Kui me tahame, et mängul ((eksisteerib)) motivatsioonil (G) oleks mingit seletavat väärtust, peame mõistma, mida saavutatakse, kui (on olemas) võidab. Eelkõige peaksime suutma rääkida realistliku loo olukorrast, kus mõni agent nimega (eksisteerib) üritab teha midagi arusaadavat ja selle tegemine on sama, mis mängu võitmine. Nagu ütles Richard Dawkins, tõstatades Maynard Smithi evolutsioonimängudele vastava küsimuse,
Kogu meie otsingu eesmärk on leida sobiv näitleja, kes mängiks juhtrolli meie eesmärgi metafoorides. Me tahame öelda: „See on heaks…”. Meie eesmärk selles peatükis on leida õige viis selle lause täitmiseks. (Laiendatud fenotüüp, Oxford University Press, Oxford 1982, lk 91.)
Tulevaseks kasutamiseks nimetagem seda Dawkinsi küsimuseks. Mitmesuguste loogiliste mängude puhul osutub selgelt raskem vastata, kui nende mängude pioneerid mõistsid. (Marion 2009 arutab Dawkinsi küsimust lähemalt.)
3. Klassikalise loogika semantilised mängud
1930. aastate alguses esitas Alfred Tarski tõe määratluse. Tema määratlus koosnes vajalikust ja piisavast tingimusest, et lause tüüpilise formaalse teooria keeles oleks tõene; tema vajalik ja piisav tingimus kasutas ainult süntaksi ja komplektiteooria mõisteid koos kõnealuse formaalse teooria primitiivsete mõistetega. Tegelikult määratles Tarski üldisema seose "valem (phi (x_1, \ ldots, x_n)) kehtib elementide (a_1, \ ldots, a_n)"; lause tõesus on erijuhtum, kus (n = 0). Näiteks küsimus, kas
'Kõigi (x) puhul on (y) selline, et R ((x, y)) on tõene
taandatakse küsimusele, kas kehtib järgmine:
Iga objekti (a) lause "Seal on (y) selline, et R ((a, y))" on tõene.
See omakorda taandub:
Iga objekti (a) jaoks on olemas objekt (b), nii et lause 'R ((a, b))' on tõene.
Selles näites on see niipalju, kui Tarski tõe määratlus meid viib.
1950ndate lõpus märkas Leon Henkin, et me saame intuitiivselt mõista mõnda lauset, mida Tarski määratlus ei käsitle. Võtke näiteks lõpmata pikk lause
Kõigi (x_0) jaoks on (y_0) selline, et kõigi (x_1) jaoks on (y_1) selline, et… R ((x_0, y_0, x_1, y_1, \ ldots)).
Tarski lähenemine ebaõnnestub, kuna kvantitatiivide jada alguses on lõpmatu ja me ei jõuaks kunagi nende mahavõtmiseni. Henkin soovitas, et selle asemel peaksime kaaluma mängu, kus inimene (forall) valib objekti (a_0) jaoks (x_0), siis teine inimene (eksisteerib) valib objekti (b_0) jaoks (y_0), siis (forall) valib (a_1) jaoks (x_1, \ eksisteerib) valib (b_1) jaoks (y_1) ja nii edasi. See mäng on (eksisteeriva) võitu siis ja ainult siis, kui aatomitu lause on lõpmatu
) R (a_0, b_0, a_1, b_1, \ punktid))
on tõsi. Algne lause on tõene siis ja ainult siis, kui mängijal (eksisteerib) on selle mängu võidustrateegia. Rangelt kasutas Henkin mängu ainult metafoorina ja tema pakutud tõde oli, et lause skoleeritud versioon on tõene, st et on olemas funktsioone (f_0, f_1, \ ldots), mis võimaldavad iga (a_0, a_1, a_2) jne
Kuid see tingimus tähendab kohe mängude keelt; Skolemi funktsioonid (f_0) jne määratlevad (eksisteerib) võidustrateegia, öeldes talle, kuidas valida (forall) varasemate valikute valguses. (Millalgi selgus, et CS Peirce oli juba soovitanud selgitada "iga" ja "mõne" erinevust selle vahel, kes valib objekti; näiteks oma teises Cambridge'i konverentsi loengus 1898.)
Varsti pärast Henkini loomingut lisas Jaakko Hintikka, et sama mõte kehtib ka sidesõnade ja disjunktsioonide kohta. Konjunktsiooni '(phi \ kiil \ psi)' võib pidada üldiselt kvantitatiivseks avalduseks, mis väljendab 'iga lause (phi, \ psi) kehtib', nii et see peaks olema mängija jaoks (forall) ühe lause valimiseks. Nagu Hintikka ütles, valib mängu (G (phi \ kiil \ psi), \ forall) mängu, kas mäng peaks toimuma kujul (G (phi)) või nagu (G (psi)). Samuti muutuvad disjunktsioonid eksistentsiaalselt kvantitatiivseteks lauseteks lausekomplektide kohta ja need tähistavad käike, kus mängija (eksisteerib) valib, kuidas mäng peaks toimuma. Kvantifikaatorite samasse stiili viimiseks tegi ta ettepaneku, et mäng (G (forall x \ phi (x))) toimuks järgmiselt: mängija (forall) valib objekti ja annab nime (a) selle jaoksja mäng kulgeb kujul (G (phi (a))). (Ja samamoodi eksistentsiaalsete kvantifikaatoritega, välja arvatud juhul, kui valib (eksisteerib).) Hintikka tegi ka leidliku ettepaneku eituse kehtestamiseks. Igas mängus G on kaksikmäng, mis on sama mis G, välja arvatud see, et mängijad (forall) ja (eksisteerivad) on üle võetud nii mängureeglites kui ka võiduajamise reeglites. Mäng (G (neg \ phi)) on (G (phi)) dubleerimine.
Võib tõestada, et iga esimese järgu lause (phi), mida tõlgendatakse fikseeritud struktuurina (A), mängijal (olemas) on Hintikka mängu võidustrateegia (G (phi)) siis ja ainult siis, kui (phi) vastab tõele (A) Tarski tähenduses. Selle tõestuse kaks omadust on huvitavad. Esiteks, kui (phi) on mis tahes esimese astme lause, siis on mäng (G (phi)) piiratud pikkusega ja nii ütleb Gale-Stewarti teoreem, et see on kindlaks määratud. Me järeldame, et (on olemas) on võidustrateegia täpselt ühes järgmistest: (G (phi)) ja selle kahesuunaline; nii et tal on võidutrateegia rakenduses (G (neg \ phi)) siis ja ainult siis, kui tal seda pole (G (phi)). See hoolitseb eituse eest. Ja teiseks, kui (eksisteerib) on iga mängu võidustrateegia (G (phi (a))), siis pärast iga sellise strateegia valimist (f_a) iga (a) jaoks,ta saab need kokku liita üheks võidetud strateegiaks (G (forall x \ phi (x))) jaoks (nimelt: "Oota ja vaata, mis elemendi (a \ forall) valib, siis mängi (f_a) '). See hoolitseb üldiste kvantifikaatorite klausli eest; kuid argument kasutab valitud aksioomi ja tegelikult pole raske mõista, kas väide, et Hintikka ja Tarski tõe definitsioonid on samaväärsed, on samaväärne valitud aksioomiga (arvestades Zermelo-Fraenkeli komplekti teooria teisi aksioome).ja tegelikult pole raske mõista, kas väide, et Hintikka ja Tarski tõe definitsioonid on samaväärsed, on samaväärne valitud aksioomiga (arvestades Zermelo-Fraenkeli komplekti teooria teisi aksioome).ja tegelikult pole raske mõista, kas väide, et Hintikka ja Tarski tõe definitsioonid on samaväärsed, on samaväärne valitud aksioomiga (arvestades Zermelo-Fraenkeli komplekti teooria teisi aksioome).
Mõistatav on see, et meil on siin kaks teooriat lause tõesuse kohta ja teooriad pole samaväärsed, kui valitud aksioom ebaõnnestub. Tegelikult pole põhjus väga sügav. Valitud aksioom pole vajalik mitte seetõttu, et Hintikka määratluses kasutatakse mänge, vaid seetõttu, et selles eeldatakse, et strateegiad on deterministlikud, st et tegemist on ühe väärtusega funktsioonidega, mis ei anna kasutajale valikuvõimalusi. Loomulikum viis Tarski määratluse mänguterminiteks tõlkimiseks on mittedeterministlike strateegiate kasutamine, mida mõnikord nimetatakse kvaasistrateegiateks (üksikasju vt Kolaitis 1985). (Siiski nõuab Hintikka 1996, et mõiste „tõene” õigeks tõlgendamiseks kasutatakse deterministlikke strateegiaid ja see asjaolu kinnitab valitud aksioomi.)
Nende Hintikka mängude arvutipõhised rakendused osutusid väga tõhusaks viisiks esimese astme lausete tähenduste õpetamisel. Ühe sellise paketi kujundasid Stanfordis Jon Barwise ja John Etchemendy, nimega 'Tarski maailm'. Üks teine Omski ülikooli meeskond konstrueeris iseseisvalt venekeelse versiooni andekate laste koolides kasutamiseks.
Oma John Locke'i Oxfordis peetud loengute avaldatud versioonis tõstatas Hintikka 1973. aastal Dawkinsi küsimuse nende mängude kohta (vt eespool). Tema vastus oli, et tuleks uurida Wittgensteini keelemänge ja kvantitatiivide mõistmiseks mõeldud keelemängud keerlevad otsimise ja leidmise ümber. Vastavates loogilistes mängudes tuleks mõelda (eksisteerib) kui iseendale ja (forall) kui vaenulikule olemusele, kellele ei saa kunagi loota, et ta esitab soovitud objekti; nii et selle leidmiseks on mul vaja võidustrateegiat. See lugu polnud kunagi väga veenev; looduse motivatsioonil pole tähtsust ja loogilises mängus ei vasta miski otsimisele. Tagantjärele on väike pettumus, et keegi ei võtnud vaevaks parema loo otsimiseks. Võib-olla on kasulikum mõelda strateegia ((eksisteeriv]) jaoks (G (phi)) võidutrateegiale, mis on mingi tõestus (sobivas infinitaarses süsteemis), et (phi) on tõene.
Hiljem laiendas Jaakko Hintikka selle jaotise ideesid kahes suunas, nimelt looduskeele semantikale ja ebatäiusliku teabe mängudele (vt järgmist osa). Nimetust Game-Theoretic Semantics, lühidalt GTS, on tulnud kasutada mõlema laienduse katmiseks.
Selles jaotises kirjeldatud mängud kohanevad peaaegu triviaalselt paljude sorteeritud loogikaga: näiteks kvantifikaator (forall x _ { sigma}), kus (x _ { sigma}) on sort muutuja (sigma), on juhis mängijale (forall) valida sorteeritav element (sigma). See annab meile kohe vastavad mängud teise astme loogika jaoks, kui mõelda struktuuri elementidele ühe liigina, elementide komplektile teise sortina, binaarsuhetele kolmandana ja nii edasi. Sellest järeldub, et ka enamiku üldistatud kvantifikaatorite jaoks on meil mängureeglid üsna rutiinsed; leiame need, tõlkides esmalt üldistatud kvantandid teise astme loogikasse.
4. Ebatäiusliku teabega semantilised mängud
Selles ja järgmises jaotises vaatleme eelmise jaotise semantiliste mängude mõningaid kohandusi muude loogikatega. Meie esimese näite jaoks loodi mängu sobitamiseks loogika (Hintikka ja Sandu 1997 iseseisvussõbralik loogika ehk lühidalt IF loogika). Selle loogika täpsema ülevaate saamiseks lugege sissekannet iseseisvuse sõbraliku loogika kohta ning Mann, Sandu ja Sevenster 2011 kohta.
Siinsed mängud on samad, mis eelmises osas, välja arvatud see, et loobume eeldusest, et iga mängija teab mängu eelnevat ajalugu. Näiteks võime nõuda mängijalt valiku tegemist, teadmata, milliseid valikuid teine mängija on teinud teatud varasemate käikude korral. Klassikaline viis selle käsitlemiseks mängu teooria piires on mängijate strateegiatele piirangute seadmine. Näiteks võime nõuda, et strateegiafunktsioon, mis ütleb (eksisteerib), mida konkreetsel etapil teha, on funktsioon, mille domeen on (forall) võimalike valikute pere just tema esimesel ja teisel käigul; See on viis väljendada, et (eksisteerib) ei tea, kuidas (forall) valis oma kolmanda ja hilisema käigu korral. Mängud, millel on strateegiafunktsioonidele sellised piirangud, on väidetavalt ebatäiuslik teave,erinevalt eelmises jaotises esitatud täpse teabe mängudest.
Nendele mängudele sobiva loogika loomiseks kasutame sama esimese astme keelt nagu eelmises jaotises, välja arvatud see, et mõnele kvantifikaatorile (ja võib-olla ka mõnele ühendusele) lisatakse märge, mis näitab, et Skolem funktsioneerib nendes kvantifikaatorites (või ühendused) on teatud muutujatest sõltumatud. Näiteks lause
[(forall x) (eksisteerib y / \ forall x) R (x, y))
loetakse järgmiselt: “Iga (x) kohta on (y), olenemata (x), näiteks (R (x, y))”.
Täiusliku ja ebatäiusliku teabe eristamiseks on kolm olulist kommentaari. Esimene on see, et Gale-Stewarti teoreem kehtib ainult täieliku teabe mängude jaoks. Oletame näiteks, et (forall) ja (on olemas) mängivad järgmist mängu. Esiteks valib (forall) ühe arvudest 0 ja 1. Seejärel (eksisteerib) valib ühe neist kahest numbrist. Mängija (eksisteerib) võidab, kui kaks valitud numbrit on samad, vastasel juhul võidab mängija (forall). Nõuame, et (on olemas), kui ta oma valiku teeb, ei tea, mida (forall) valis; nii et tema jaoks on Skolemi funktsioon pidev. (See mäng vastab ülaltoodud IF-lausele, kui (R) loetakse võrdseks, struktuuris, mille domeen koosneb 0 ja 1-st.) On selge, et mängijal (eksisteerib) pole pidevat võidustrateegiat,ja ka sellel mängijal (forall) pole üldse võidustrateegiat. Nii et see mäng on määratlemata, ehkki selle pikkus on vaid 2.
Üks järeldus on see, et Hintikka õigustus eituse lugemiseks dubleerivaks ('mängijad vahetavad kohti') tema mängudes esimese astme loogika jaoks ei kandu üle IF loogikale. Hintikka vastus on olnud, et dubleerimine oli eituse õige intuitiivne tähendus isegi esimese astme puhul, seega pole mingit põhjendust vaja.
Teine kommentaar on see, et juba täiusliku teabe mängudes võib juhtuda, et võidustrateegiad ei kasuta kogu olemasolevat teavet. Näiteks täiusliku teabe mängul, kui mängijal (eksisteerib) on võidustrateegia, siis on tal ka võidustrateegia, kus strateegia funktsioonid sõltuvad ainult eelmistest (forall) valikutest. Selle põhjuseks on asjaolu, et ta saab oma varasemaid käike oma varasemate strateegiafunktsioonide abil rekonstrueerida.
Kui Hintikka kasutas Skolemi funktsioone oma mängudes strateegiatena esimese järgu loogika jaoks, muutis ta mängija strateegiad sõltuvaks ainult teise mängija varasematest käikudest. ((Eksisteerib) Skolemi funktsioon sõltub ainult universaalselt kvantifitseeritud muutujatest.) Kuna mängud olid täiusliku teabe mängud, siis ülaltoodud teises kommentaaris selles kaotust ei olnud. Kuid kui ta IF-loogika juurde liikus, siis see, et nõue, et strateegiad sõltuvad ainult teise mängija käikudest, muutis seda tõesti. Hodges 1997 näitas seda, muutes tähist, nii et näiteks ((eksisteerib y / x)) tähendab: “Seal on (y) sõltumatu (x), sõltumata sellest, milline mängija valis (x)”.
mängiti uuesti kahel elemendil 0 ja 1. oleval struktuuril. Mängija (eksisteerib) võib võita järgmiselt. Sest (z) valib ta sama, mida mängija (forall), kelle jaoks valis (x); siis (y) jaoks valib ta sama, mille ta valis (z) jaoks. See võidustrateegia töötab ainult seetõttu, et selles mängus (eksisteerib) saab viidata tema enda eelmistele valikutele. Tal ei oleks võidustrateegiat, kui kolmas kvantifikaator oleks ((eksisteerib y / xz)), jällegi sellepärast, et selle kvantifikaatori mis tahes Skolemi funktsioon peaks olema konstantne. See, kuidas (on olemas) edastab teavet iseendale, viidates tema eelmisele valikule, on näide signaalimise nähtusest. John von Neumann ja Oskar Morgenstern illustreerisid seda Bridži näitega, kus üks mängija koosneb kahest partnerist, kes peavad üksteisele märku andmiseks oma avalikke käike kasutades teavet jagama.
Kolmas märkus on see, et ebatäiusliku teabe intuitiivse idee ja selle mängude-teoreetilise määratluse vahel on nihe strateegiates. Intuitiivselt öeldes on ebatäiuslik teave asjaolu, milles mängu mängitakse, mitte strateegiad. See on väga keeruline küsimus ja põhjustab endiselt IF-i ja sarnase loogikaga seotud arusaamatusi. Võtke näiteks lause
[(eksisteerib x) (eksisteerib y / x) (x = y),)
mängiti jällegi struktuuril koos elementidega 0 ja 1. Intuitiivselt võiks mõelda, et kui (eksisteerib) ei luba teisel kvantitaatoril meelde jätta seda, mille ta alguses valis, siis pole tal vaevalt võidutrateegiat. Kuid tegelikult on tal väga lihtne: 'Valige alati 0'!
Võrreldes esimese astme loogikaga puudub IF loogikal komponent, mida mängu semantika ei paku. Mängu semantika ütleb meile, millal lause struktuuris tõene on. Kui aga võtame valemi, milles on (n) vabad muutujad, siis mida see valem väljendab struktuuri elementide järjestatud (n) elementide kohta? Esmajärgulises loogikas määratleks see nende hulga, st (n) - struktuuri ariaalse seose; Tarski tõdemääratlus selgitab, kuidas. Kas IF loogika suvaliste valemite jaoks on olemas sarnane määratlus? Selgub, et Hodges 1997 tutvustatud pisut teistsugusel loogikal on üks ja see viib selle loogika keele jaoks Tarski-stiilis tõdemääratluseni. Väikese kohandusega saab selle tõe määratluse sobitada ka IF loogikaga. Kuid mõlema uue loogika jaoks on saak:Selle asemel, et öelda, kui elementide määramine vabadele muutujatele muudab valemi õigeks, ütleme siis, kui elementide määramise komplekt vabadele muutujatele muudab valemi tõeseks. Väänänen 2007 tegi sellest ideest aluse hulgale uutele loogikatele sõltuvuse mõiste uurimiseks (vt sissekannet sõltuvusloogikast). Selles loogikas on semantika määratletud ilma mängudeta, ehkki algne inspiratsioon pärineb Hintikka ja Sandu töödest.
Väänäneni loogikas on lihtne aru saada, miks on vaja ülesandekomplekte. Tal on aatomivalem, mis väljendab: '(x) sõltub (y)'. Kuidas saame seda tõlgendada struktuuris, näiteks naturaalarvude struktuuris? Pole üldse mõtet küsida näiteks seda, kas 8 sõltub 37-st. Kuid kui meil on looduslike arvude järjestatud paaride hulga X, on mõistlik küsida, kas X-is on iga paari esimene liige sõltuv teine; vastus Jah tähendaks, et on olemas funktsioon (f), nii et igal paaril X ((a, b)) X-s on vorm ((f (b), b)).
5. Muu loogika semantilised mängud
Järgnevad struktuurid tekitavad huvitavaid mänge. Struktuur (A) koosneb hulgast (S) elementidest (mida kutsume olekuteks, lisades, et neid nimetatakse sageli maailmadeks), binaarsest seosest (R) saidil (S) (me loetakse (R) noolena) ja (S) alamhulkade perekonda (P_1, \ ldots, P_n). Kaks mängijat (forall) ja (eksisteerivad) mängivad mängu G (), alustades olekust (s), mis neile antakse, lugedes sobivat loogilist valemit (phi) mängimise ja võitmise juhiste kogumina.
Seega kui (phi) on (P_i), siis mängija (eksisteerib) võidab korraga, kui (s) asub (P_i), vastasel juhul võidab mängija (forall). korraga. Valemid (psi \ kiil \ teeta, \ psi \ vee \ teeta) ja (neg \ psi) käituvad nagu ülaltoodud Hintikka mängudes; näiteks (psi \ kiil \ theta) juhendab mängijat (forall) valima, kas mäng jätkub nagu (psi) või (theta). Kui valem (phi) on (Box \ psi), valib mängija (forall) noole (s) olekust (t) (st olekust (t) nii, et paar ((s, t)) on suhtes (R)) ja seejärel mäng läheb olekust (t) vastavalt juhistele (psi). Reegel (Teemant \ psi) jaoks on sama, välja arvatud juhul, kui valiku teeb mängija (eksisteerib). Lõpuks ütleme, et valem (phi) vastab punktides A tõele, kui mängijal (eksisteerib) on selle mängu võidustrateegia, mis põhineb (phi) ja algab (s).
Need mängud vastavad modaalsele loogikale samamoodi nagu Hintikka mängud esimese astme loogikale. Eelkõige on need üks viis modaalse loogika semantika andmiseks ja nõustuvad tavalise Kripke-tüüpi semantikaga. Muidugi on modaalloogika tüüpe ja üldistusi palju (sealhulgas tihedalt seotud loogika nagu ajaline, episteemiline ja dünaamiline loogika) ja seetõttu on vastavad mängud mitmesugused. Üks huvipakkuvaid näiteid on Matthew Hennessy ja Robin Milneri arvutiteoreetiline loogika, mida kasutatakse süsteemide käitumise kirjeldamiseks; siin on nooled värvides rohkem kui üks ja kindla värvi noolt mööda liikumine tähistab konkreetse "toimingu" tegemist oleku muutmiseks. Teine näide on võimsam modaalne (mu) - püsipunktioperaatoritega Dexter Kozeni arvutus;vt Stirling 2001 5. peatükki.
Nende mängude üks huvitav omadus on see, et kui mängijal on võidustrateegia alates mõnest positsioonist alates, siis ei pea see strateegia kunagi viitama millelegi, mis mängu alguses juhtus. Pole tähtis, millised valikud olid varem tehtud või isegi mitu sammu on mängitud. Nii et meil on see, mida arvutiteadlased mõnikord „mäluvabaks” võidustrateegiaks nimetavad.
Rohit Parikhi väljapakutud seotud mängude loogikas on mängud, mis viivad meid riikide vahel, pigem teema kui viis tõe määratlemiseks. Nendel mängudel on palju huvitavaid aspekte. 2003. aastal avaldas ajakiri Studia Logica neile pühendatud numbri, mille toimetasid Marc Pauly ja Parikh.
Majandus- ja infotehnoloogia mõjud on pannud paljud loogikud kasutama loogikat osalise teadmatuse tingimustes otsustamise analüüsimisel. (Vt näiteks artiklit episteemilise loogika kohta.) Teadmiste olekuid saab esindada mitmel viisil. Üks on võtta neid olekute või maailmadena sellises modaalses struktuuris, nagu me selle lõigu alguses mainisime. Teine võimalus on kasutada IF-loogikat või selle varianti. Kuidas need lähenemised on seotud? Johan van Benthem 2006 esitab selle väga loomuliku küsimuse kohta mõned mõtted ja tulemused. Vt ka Johan van Benthemi, Krister Segerbergi, Eric Pacuit'i ja K. Venkateshi artikleid ja nende viiteid IV osas „Loogika, agentuur ja mängud”, Van Benthem, Gupta ja Parikh 2011, ning kannet loogika kohta mängude analüüsimiseks hiljutise töö näide selles valdkonnas.
6. Tagasi ja tagasi mängud
Alfred Tarski sõnastas 1930. aastal arusaama, et kaks struktuuri (A) ja (B) on põhimõtteliselt ekvivalentsed, st et täpselt samad esimese järgu laused on tõesed (A) ja tõesed ka ((B)). 1946. aastal Princetonis toimunud konverentsil kirjeldas ta seda mõistet ja avaldas lootust, et on võimalik välja töötada selle teooria, mis oleks „sama sügav kui praegu kasutusel olevad isomorfismi jms mõisted” (Tarski 1946).
Sellise teooria üks loomulik osa oleks puhtstruktuurselt vajalik ja piisav tingimus, et kaks struktuuri oleksid põhimõtteliselt samaväärsed. Esimesena leidis kasutatav vajalik ja piisav seisund Prantsuse-Alžeeria Roland Fraïssé. Mõni aasta hiljem avastas selle uuesti Kasahstani loogik AD Taimanov ja Poola mänguaja logistik Andrzej Ehrenfeucht sõnastas selle mängude osas ümber. Neid mänge tuntakse nüüd Ehrenfeucht-Fraïssé mängudena või mõnikord edasi-tagasi mängudena. Need on osutunud üheks XX sajandi loogika kõige mitmekülgsemaks ideeks. Nad kohanevad viljakalt paljude loogikate ja struktuuridega.
Edasi-tagasi mängus on kaks struktuuri (A) ja (B) ning kaks mängijat, keda tavaliselt nimetatakse spooliks ja paljundusaparaadiks. (Nimed tulenevad Joel Spencerist 1990ndate alguses. Hiljuti soovitas Neil Immerman Simsoni ja Delilahit, kasutades samu initsiaale; see paneb Spoileri meesmängijaks (forall) ja paljundusaparaadi naiseks (olemas).) Mängu iga etapp koosneb Spoileri käigust, millele järgneb paljundusaparaadi käik. Spoiler valib kahest struktuurist ühe elemendi ja paljundusaparaat peab seejärel valima teise struktuuri elemendi. Nii et pärast (n) samme on valitud kaks jada, üks (A) ja teine (B) hulgast:
See koht on Spoileri jaoks võidetav siis ja ainult siis, kui mõni aatomi valem (ühes vormist '(R (v_0, \ ldots, v_ {k-1})) või' (mathrm {F} (v_0, \ ldots, v_ {k-1}) = v_k) 'või' (v_0 = v_1) 'või üks neist erinevate muutujatega) on rahul rakendusega ((a_0, \ ldots, a_ { n-1})) asukohas (A), kuid mitte ((b_0, \ ldots, b_ {n-1})) abil (B), või vastupidi. Paljundusaparaadi võitmise tingimused on mängu eri vormides erinevad. Lihtsaimal kujul (EF (A, B)) on näide paljundusaparaadi jaoks võit ainult siis ja ainult siis, kui ükski selle algne osa pole Spoileri võit (st ta võidab, kui ta pole ühegi mängijaga kaotanud) piiratud etapp). Iga naturaalarvu (m) jaoks on mäng (EF_m (A, B)); selles mängus võidab paljundusaparaat pärast (m) samme, kui ta pole veel kaotanud. Kõik need mängud määrab Gale-Stewarti teoreem. Kaks struktuuri (A) ja (B) on väidetavalt edasi-tagasi ekvivalendid, kui paljundusaparaadil on (EF (A, B)) võidustrateegia, ja m-ekvivalentsed, kui tal on võitnud strateegia (EF_m (A, B)) jaoks.
Võib tõestada, et kui (A) ja (B) on (m) - ekvivalentsed iga naturaalarvu (m) korral, siis on nad põhimõtteliselt samaväärsed. Tegelikult, kui Eloise'il on Hintikka mängus G ((phi)) (A) -mängus võidutrateegia (tau), kus (phi) kvantitatiivsete ulatuste pesitsemine on enamus m taset ja paljundusaparaadil on mängus võidustrateegia (varrho) (EF_m (A, B)), kaks strateegiat (tau) ja (varrho) võib moodustada võidukas strateegia Eloise rakenduses G ((phi)) saidil (B). Teisest küljest saab (EF_m (A, B)) Spoileri võidustrateegia teisendada esimese järgu lauseks, mis vastab tõele ühes järgmistest: (A) ja (B), ja kus kvantifikaatorite pesade pesitsemine on maksimaalselt (m) tasemel. Nii et meil on olemas vajalik ja piisav tingimus elementaarseks samaväärsuseks ja peale selle veel natuke.
Kui (A) ja (B) on edasi-tagasi ekvivalendid, siis kindlasti on nad põhimõtteliselt samaväärsed; kuid tegelikult osutub edasi-tagasi ekvivalent sama, mis infinitaarses loogikas, mis on palju väljendusrikkam kui esimese järgu loogika. Mängus on palju kohandusi, mis annavad muud tüüpi samaväärsuse. Näiteks kirjeldasid Barwise, Immerman ja Bruno Poizat iseseisvalt mängu, milles kahel mängijal on täpselt (p) nummerdatud veeris; iga mängija peab oma valikud sildistama veeris ja kaks samast valikust koosneva sammu peavad olema märgistatud sama numbriga veergudega. Mängu edenedes saavad mängijad veerisid otsa ja seetõttu peavad nad juba kasutatud veerisid uuesti kasutama. Spoileri positsioonil (ja kõigil järgnevatel positsioonidel) võitmise tingimused on samad, mis varem, välja arvatud see, et arvesse võetakse ainult selles positsioonis silte kandvaid elemente. Koopiamasina võidustrateegia olemasolu selles mängus tähendab, et kaks struktuuri lepivad kokku lausetes, mis kasutavad maksimaalselt (p) muutujaid (võimaldades neil muutujatel esineda suvalist arv kordi).
Edasi-tagasi mängude teooria kasutab väga vähe eeldusi kõnealuse loogika kohta. Selle tulemusel on need mängud üks väheseid mudeliteoreetilisi tehnikaid, mis kehtivad nii piiratud struktuuride kui ka lõpmatute jaoks, ja see teeb neist ühe teoreetilise arvutiteaduse nurgakivi. Neid saab kasutada ametlike keelte, näiteks andmebaasipäringute keelte väljendusjõu mõõtmiseks. Tüüpiline tulemus võib näiteks öelda, et teatud keeles ei saa vahet teha paaris ja paaritu; me tõestame seda, leides keele valemite iga keerukuse (n) keerukuse paari jaoks lõplike struktuuride paari, mille jaoks paljundusaparaadil on võidutrateegia taseme edasi-tagasi mängus (n), kuid ühel konstruktsioonil on paarisarv elemente ja teisel on paaritu arv. Looduskeelte semantikud on leidnud edasi-tagasi mängud kasulikeks üldistatud kvantifikaatorite väljendusjõude võrdlemiseks. (Vt näiteks Peters ja Westerståhl 2006, IV jagu.)
On olemas ka omamoodi edasi-tagasi mäng, mis vastab meie ülaltoodud modaalsele semantikale, samamoodi nagu Ehrenfeucht-Fraïssé mängud vastavad Hintikka mängusemantikale esimese astme loogika jaoks. Mängijad alustavad olekut (s) struktuuris (A) ja olekut (t) struktuuris (B). Spoiler ja paljundusaparaat liiguvad vaheldumisi, nagu varemgi. Iga kord, kui ta kolib, valib Spoiler, kas liikuda asukohas (A) või (B) ja seejärel peab paljundusaparaat liikuma teises struktuuris. Liikuda saab alati, liikudes praegusest olekust mööda noolt edasi. Kui kaks mängijat on nende vahel vahetult liikunud olekusse (s) ´ sisse (A) ja olekusse (t) ´ sisse (B) ja mõni predikaat ((P_i) on käes ainult üks (s) ´ ja (t) ´ -st, siis paljundusaparaat kaotab korraga. Samuti kaotab ta, kui tal pole liikumiseks nooli;aga kui Spoiler leiab, et kummalgi struktuuril liikumiseks pole ühtegi noolt, siis võidab paljundusaparaat. Kui kaks mängijat mängivad seda mängu antud lähteseisunditega (s) (A) ja (t) (B) ja mõlemal struktuuril on lihtsalt palju olekuid, siis saab näidata, et paljundusaparaat omab võidustrateegiat ainult siis, kui (s) (A) puhul kehtivad samad modaallaused nagu (t) (B).
Selle tulemuse kohta on tehtud palju üldistusi, mõned neist hõlmavad järgmist mõistet. Olgu (Z) binaarne seos, mis seob (A) olekuid (B) olekutega. Siis kutsume (Z) bisimulatsiooniks (A) ja (B) vahel, kui paljundusaparaat saab kasutada (Z) mittedeterministliku võidustrateegiana edasi-tagasi mängus (A) ja (B), kus kahe mängija esimene käigupaar on valida nende lähteseisundid. Arvutiteaduses on bisimulatsiooni mõiste ülioluline (A) ja (B) süsteemide mõistmiseks; see väljendab seda, et kaks süsteemi suhtlevad oma keskkonnaga samamoodi nagu üksteist, samm-sammult. Kuid veidi enne seda, kui arvutiteadlased selle idee kasutusele võtsid, ilmus sisuliselt sama mõiste Johan van Benthemi doktoritöös modaalloogika semantika kohta (1976).
7. Muud mudelteoreetilised mängud
Selle jaotise loogilised mängud on matemaatikute tööriistad, kuid neil on mõned kontseptuaalselt huvitavad omadused.
7.1 Sunnimängud
Sunnimänge teatakse kirjeldavatele kogumiteoreetikutele ka Banach-Mazuri mängudena; Matemaatilise tausta kohta leiate üksikasju Kechrise või Oxtoby allpool. Mudeliteoreetikud kasutavad neid kontrollitud omadustega lõpmatute struktuuride ehitamise viisina. Lihtsaimal juhul mängivad (forall) ja (olemasolevad) nn eksistentsimudeli mudelit, kus (eksisteerib) väidab, et fikseeritud lausel (phi) on mudel, samas kui (forall) väidab, et ta võib tuletada (phi) vastuolust. Alguses fikseeritakse võrdselt lõpmatu hulk uusi (C_) konstantseid sümboleid (a_0, a_1, a_2) jne. (eksisteerib) kaitseb disjunktsiooni, valides ühe disjunkti, ja eksistentsiaalse väite, valides tunnistajana konstandi (C) hulgast. (forall) saab konjunktsiooni vaidlustada, valides kas konjunktsiooni,ja universaalne avaldus, valides suvalise tunnistaja hulgast (C). (eksisteerib) võidab, kui ei mängita vastuolulisi aatomilauseid. (on olemas) omab võidustrateegiat (järjepidevuse omadus on üks viis võitnud strateegia kirjeldamiseks) ainult siis ja ainult siis, kui (phi) on olemas mudel. Teisest küljest, kui (forall) omab võidustrateegiat, on kõigi tema võidustrateegia vastaste mängude puu (mille saab muuta lõplikuks) seotud Gentzeni stiilis tõendiga (phi) eituse kohta.. See lausete analüüsimeetod on tihedalt seotud Bethi semantilise tabelite ja dialoogimängu meetodiga (vt 8. jagu).kui (forall) omab võidustrateegiat, on kõigi tema võidustrateegia vastaste mängude puu (mille saab muuta lõplikuks) seotud Gentzeni stiilis tõendiga (phi) eituse kohta. See lausete analüüsimeetod on tihedalt seotud Bethi semantilise tabelite ja dialoogimängu meetodiga (vt 8. jagu).kui (forall) omab võidustrateegiat, on kõigi tema võidustrateegia vastaste mängude puu (mille saab muuta lõplikuks) seotud Gentzeni stiilis tõendiga (phi) eituse kohta. See lausete analüüsimeetod on tihedalt seotud Bethi semantilise tabelite ja dialoogimängu meetodiga (vt 8. jagu).
Üldise Sunnimängu idee visandiks visandage, et maja ehitab maja (A) kindlalt lõpmatu ehitajate meeskond. Igal ehitajal on oma ülesanne, mille ta peab täitma: näiteks vanni paigaldamiseks või esiku tapeetimiseks. Igal ehitajal on lõpmata palju võimalusi platsile siseneda ja majale lisada piiratud kogus materjali; need ehitajate pilud on üksteisega ühendatud nii, et kogu protsess toimub sammude jadana, mida loendatakse naturaalarvudega.
Et näidata, et maja saab ehitada tellimuse järgi, peame näitama, et iga ehitaja saab oma määratud ülesannet eraldi täita, sõltumata sellest, mida teised ehitajad teevad. Nii et me kujutame ette iga ehitajat mängijana ((eksisteerib)) mängus, kus kõik teised mängijad on kokku koondatud kui (forall), ja meie eesmärk on tõestada, et (eksisteerib) omab selle jaoks võidustrateegiat mängu. Kui oleme seda iga ehitaja jaoks eraldi tõestanud, võime ette kujutada, et nad töötavad, igaühel on oma võidustrateegia. Nad kõik võidavad oma vastavad mängud ja tulemuseks on üks ilus maja.
Tehnilisemalt on struktuuri (A) elemendid eelnevalt fikseeritud, näiteks (a_0, a_1, a_2) jne., Kuid nende elementide omadused tuleb lahendada näidendi abil. Iga mängija liigub, viskades elementide kohta aatomisse või negatiivsetesse aatomiväidetesse komplekti, tingimusel et ainult seni kõigist välja visatud väidetest koosnev komplekt peab olema kooskõlas kindla mänguga enne mängu kirjutatud aksioomide komplektiga. (Negatiivse aatomilause (neg \ phi) viskamine takistab mõnd mängijat hilisemas faasis (phi) lisamast.) Ühismängu lõpus aatomilausete komplekt sisse visatud on kanoonilise mudeli ja see on struktuur (A); on olemas viise, kuidas tagada, et see on aksioomide fikseeritud komplekti mudel. Võimalik, et (A) omadus P on täidetav, kui ehitajal, kellele antakse ülesanne P (A) -st tõeks teha, on võidustrateegia. Keskne punkt (peamiselt Ehrenfeuchti tõttu) on see, et loendamatult lõpmatu komplekti täidetavate omaduste koosmõju on jälle täitmisele pööratav.
Erinevaid Löwenheim-Skolemi mudelateooria teoreeme saab tõestada sunnimängu variantide abil. Nendes variantides ei konstrueeri me mitte mudelit, vaid antud mudeli alammudelit. Alustame lause (või loendatava lausekomplekti) (phi) suure mudeliga (M). Seejärel loetleme (phi) alamvormid ja igal mängijal on alamvorm koos tasuta muutujaga, millest osa võtta. Mängija ülesanne on veenduda, et niipea, kui mängus ilmnevad alamvormi parameetrid ja kui suures mudelis on olemas valemi tõesuse tunnistajad, mängitakse üks selline tunnistaja. Kui mäng on lõppenud, on (M) loendatav alammudel ehitatud nii, et see rahuldab (phi).
Nimi "sundimine" pärineb Paul Coheni seotud ideede rakendamisest 1960. aastate alguses setteooria mudelite konstrueerimiseks. Abraham Robinson kohandas selle loendatavate konstruktsioonide ehitamise üldmeetodi loomiseks ja Martin Ziegler tutvustas mänguasetust. Hiljem kasutasid Robin Hirsch ja Ian Hodkinson seotud mänge, et lahendada vanu küsimusi suhete algebrate kohta.
Sunnimängud on tervislik näide, mida tuleks Dawkinsi küsimusele mõeldes meeles pidada. Nad tuletavad meile meelde, et loogilistes mängudes ei pea olema kasulik mõelda mängijatele kui üksteisele vastanduvaid.
7.2 Lõika ja vali mängud
Traditsioonilises lõigatud ja vali mängus võtad koogitüki ja lõikasid selle kaheks väiksemaks tükiks; siis valin ühe tüki ja söön selle ära, jättes teise teile. Väidetavalt avaldab see protseduur teile koogi õiglaseks lõikamiseks survet. Matemaatikud nõuavad harjutuse eesmärgi mõistmata jätmist. Nii panen ma teie valitud tüki kaheks lõikama, siis valin neist kahest ühe; siis lõikasite selle tüki uuesti ja nii edasi lõputult. Mõni veelgi ebamaine matemaatik paneb teid koogi kahe asemel tükeldama arvestatavalt paljudeks tükkideks.
Need mängud on olulised määratluste teoorias. Oletame, et meil on objektide kogum (A) ja omaduste perekond (S); iga atribuut lõikab (A) nende objektide komplekti, millel on atribuudid, ja nende komplekti, millel pole. Laske (eksisteerib) lõigata, alustades kogu komplektist (A) ja kasutades atribuudina noaga (S); lase (forall) valida üks tükkidest (mis on (A) alamhulgad) ja anda see tagasi (eksisteerib) lõigata uuesti, kasutades veel kord atribuuti (S); ja nii edasi. Laske (eksisteerib) kaotada kohe, kui (forall) valib tühja tüki. Me ütleme, et ((A, S)) on kõige kõrgemal kohal (m), kui (forall) omab strateegiat, mis tagab, et (eksisteerib) kaotab enne teda (m) - th liikuda. ((A, S)) aste annab väärtuslikku teavet (A) alamhulkade perekonna kohta, mis on määratletav (S) omaduste järgi.
Selle mängu variatsioonid, mis võimaldavad tüki lõigata lõpmata paljudeks väiksemateks tükkideks, on mudeliteooria haru, mida nimetatakse stabiilsusteooriaks, põhialused. Laias laastus võib öelda, et teooria on stabiilsusteooria mõttes hea, kui võtame teooria mudeli (A) ja (S) esimese järgu valemite komplekti ühes tasuta muutuja parameetritega alates (A), struktuuril ((A, S)) on 'väike' auaste. Erinev variatsioon on nõuda, et igal etapil jaotaks (eksisteeriv) kaheks tükkiks, mis on varasematest sammudest säilinud, ja jälle kaotab ta, kui üks lõigatud fragment on tühi. (Selles versioonis on (forall) ülearune.) Selle variatsiooni korral nimetatakse järku ((A), S) selle Vapnik-Chervonenkise mõõtmeks; seda mõistet kasutatakse arvutuslikus õppeteoorias.
7.3 Mängud kahe järjestikuse funktsiooni puul
Kujutage ette puu, mis on üles ehitatud tasemetel. Alumisel tasemel on üks juursõlm, kuid vasakult haru ja parem haru tulevad sellest välja. Järgmisel tasemel ülespoole on kaks sõlme, üks mõlemal harul ja kõigist neist sõlmedest kasvab vasak ja parem haru. Nii et järgmisel tasemel üles on neli sõlme ja jällegi puude harud vasakule ja paremale kõigis nendes sõlmedes. Jätkates lõpmatuseni, nimetatakse seda puud kahe järeltulija funktsiooniks (nimelt vasakpoolne ja paremjärglane). Võttes sõlmed elementidena ja tutvustades vasaku ja parema järeltulija jaoks kahte funktsioonisümbolit, on meil struktuur. Michael Rabini võimas teoreem väidab, et on olemas algoritm, mis ütleb meile iga monaadilise teise järgu lause ((phi)) jaoks selle struktuuri jaoks sobivas keeles,kas (phi) vastab tõele või mitte. ('Monadic teine järk' tähendab seda, et loogika sarnaneb esimese järguga, välja arvatud see, et me võime kvantifitseerida ka elementide komplektide kaudu, kuid mitte näiteks elementide binaarsuhete üle.)
Rabini teoreemil on palju kasulikke tagajärgi. Näiteks Dov Gabbay kasutas seda mõne modaalloogika otsustatavuse tõestamiseks. Kuid Rabini tõestust automaatide kasutamise kohta oli kurikuulsalt keeruline järgida. Juri Gurevitš ja Leo Harrington ning iseseisvalt Andrei Muchnik leidsid palju lihtsamaid tõestusi, milles automaat on mängu mängija.
See Rabini tulemus on üks paljudest mõjukatest tulemustest, mis ühendavad mänge automaatidega. Teine näide on pariteedimängud, mida kasutatakse modaalsüsteemide omaduste kontrollimiseks. Vt näiteks Stirlingi (2001) 6. peatükki; Bradfield ja Stirling (2006) arutavad paarsuse mänge modaalse ((mu)) - kalkuleerimise jaoks.
8. Dialoogimängud, suhtlemine ja tõestamine
Mitmed keskaegsed tekstid kirjeldavad väitlusvormi, mida nimetatakse kohustusteks. Vaidlejaid oli kaks, vastased ja vastutajad. Seansi alguses lepivad vaidlejad kokku positumi osas, mis on tavaliselt vale väide. Respondensi ülesandeks oli anda Opponensi küsimustele ratsionaalseid vastuseid, eeldades positiivse positsiooni õigsust; ennekõike pidi ta vältima end asjatult vastuollu astumisega. Opponensi ülesanne oli proovida sundida vastuseid vastuollu. Nii et me teame üldiselt vastust Dawkinsi küsimusele, kuid me ei tea mängureegleid! Keskaja õpikud kirjeldavad mitmeid reegleid, mida vaidlejad peaksid järgima. Kuid need reeglid pole mängureeglid ette nähtud; need on juhised, mille õpikud tuletavad näidete abil usaldusväärse arutluse põhimõtetest.(Veneetsia Paulus õigustab ühte reeglit suurte logistikute, filosoofide, geomeetrite ja teoloogide praktikaga.) Eelkõige oli õpetajal kohustus uusi reegleid avastada. See avatus tähendab, et kohustused pole meie mõistes loogilised mängud.
Kõik ei nõustu eelmise lausega. Näiteks kaitseb Catarina Dutilh Novaes (2007, 6) üksikasjalikult seisukohta, et kohustused esitavad „keskaja ja tänapäevase teoreetilise raamistiku kontseptuaalse sarnasuse tähelepanuväärse juhtumi”. Kuid mis iganes seisukohta me selle küsimuse suhtes võtame, on need arutelud inspireerinud loogiliste mängude tänapäevase uurimise ühte olulist joont.
Kujutage ette, et ((eksisteerib) on suulise eksami sooritamine tõendite teoorias. Eksamineerija annab talle lause ja kutsub teda üles seda tõestama. Kui lausel on vorm
) phi \ vee \ psi)
siis on tal õigus valida üks lausetest ja öelda „OK, ma tõestan selle ära”. (Tegelikult, kui eksamineerija on intuitsionist, võib ta nõuda, et naine valiks tõestamiseks ühe lause.) Teisest küljest, kui lause on
) phi \ kiil \ psi)
siis võib eksamineerija, kes on eksamineerija, valida ise ühe konjunktidest ja kutsuda teda seda tõestama. Kui ta teab, kuidas konjunktsiooni tõestada, siis ta teab kindlasti, kuidas konjunktsiooni tõestada.
(Phi \ parempoolse noole \ psi) juhtum on pisut peenem. Tõenäoliselt soovib ta alustada järeldusega (phi), et järeldada (psi); kuid seal on teatav segiajamise oht, sest tema seni kirjutatud laused on kõik asjad, mida tuleb tõestada, ja (phi) pole tõestatav asi. Eksamineerija saab teda aidata, öeldes: "Ma eeldan, et (phi), ja vaatame, kas pääsete sealt (psi)". Sel hetkel on võimalus, et ta näeb viisi, kuidas jõuda (psi), tuletades (phi) vastuolu; nii et ta võib keerata eksamineerija lauad ja kutsuda teda üles näitama, et tema eeldus on järjekindel, eesmärgiga tõestada, et see pole nii. Sümmeetria ei ole täiuslik: ta palus naisel näidata, et lause on tõene igal pool, samal ajal kui naine kutsub teda üles näitama, et lause on kuskil tõene. Sellegipoolest võime näha omamoodi kahesust.
Seda laadi ideed peituvad Paul Lorenzeni dialektiliste mängude taga. Ta näitas, et teatud hulga tõukamise ja lükkamisega saab mängureegleid kirjutada, millel on omadus, millel (eksisteerib) on võidustrateegia, ja ainult siis, kui lause, mis talle alguses esitatakse, on intuitsioonilise loogika teoreem. Keskaegsete arutelude žestil nimetas ta (eksisteerib) pooldajat ja teist mängijat vastaseks. Peaaegu nagu keskaegses kohustuses võidab vastane, juhtides pooldaja punkti, kus tema ainsateks käikudeks on räiged iseenda vastuolud.
Lorenzen väitis, et tema mängud õigustasid nii intuitsiooni kui ka klassikalist loogikat (või tegid need tema sõnul Lorenzeni (1961, 1966) gerechtfertigtiks). Kahjuks hõlmab iga „õigustamine” veenvat vastust Dawkinsi küsimusele ja seda Lorenzen ei esitanud. Näiteks rääkis ta liikumistest kui rünnakutest, isegi kui (nagu ülaltoodud eksamineerija otsus ülalpool (phi \ kiil \ psi)) näevad nad välja pigem abi kui vaenulikkust.
Sisestusdialoogiline loogika annab Lorenzeni mängudest täieliku ülevaate ja mitme uuema variandi. Praegusel kujul (jaanuar 2013) loobub ta Lorenzeni väidetest loogika õigustamise kohta. Selle asemel kirjeldab see mänge kui loogika semantikat (punkt, millega Lorenzen oleks kindlasti nõus olnud) ja lisab, et loogika erinevuste mõistmiseks võib olla kasulik võrrelda nende semantikat.
Sellest vaatenurgast on Lorenzeni mängud oluliseks paradigmaks sellele, mida hiljutised tõendusteoreetikud on nimetanud tõendite semantikaks. Tõendite semantika annab „tähenduse” mitte ainult tõestatavuse mõistele, vaid igale tõendite eraldi etapile. See annab vastuse küsimusele „Mida me saavutame, kui teeme selle konkreetse tõendi?” 1990ndatel otsisid mitmed arvutiteaduse loogilises lõpus töötavad mängud lineaarsele loogikale vastavaid mänge ja mõnda muud tõestussüsteemi, nagu Lorenzeni mängud, intuitsioonist lähtuvale loogikale. Andreas Blass ja seejärel hiljem Simson Abramsky ning tema kolleegid andsid mänge, mis vastasid lineaarse loogika osadele, kuid selle kirjutamise ajal pole meil veel mängu ja loogika vahel ideaalset vastavust. See näide on eriti huvitav, kuna vastus Dawkinsi küsimusele peaks andma lineaarse loogika seadustest intuitiivse tõlgenduse - asja, mida see loogika on hädasti vajanud. Abramsky jt mängud. jutustage lugu kahest üksteist mõjutavast süsteemist. Kuid kuigi ta alustas mängudega, milles mängijad viisakalt vaheldumisi tegid, lubas Abramsky hiljem mängijatel tegutseda "hajusalt, asünkroonselt", märkides üksteist ainult siis, kui nad seda otsustasid. Need mängud pole enam loogiliste mängude tavapärases vormingus ja nende reaalse elu tõlgendamine tekitab hulgaliselt uusi küsimusi. Kuid kuigi ta alustas mängudega, milles mängijad viisakalt vaheldumisi tegid, lubas Abramsky hiljem mängijatel tegutseda "hajusalt, asünkroonselt", märkides üksteist ainult siis, kui nad seda otsustasid. Need mängud pole enam loogiliste mängude tavapärases vormingus ja nende reaalse elu tõlgendamine tekitab hulgaliselt uusi küsimusi. Kuid kuigi ta alustas mängudega, milles mängijad viisakalt vaheldumisi tegid, lubas Abramsky hiljem mängijatel tegutseda "hajusalt, asünkroonselt", märkides üksteist ainult siis, kui nad seda otsustasid. Need mängud pole enam loogiliste mängude tavapärases vormingus ja nende reaalse elu tõlgendamine tekitab hulgaliselt uusi küsimusi.
Giorgi Japaridze on pakkunud arvutamise uurimiseks välja nn arvutatavuse loogika. Selle süntaks on esimese astme loogika koos mõne lisaüksusega, mis meenutab lineaarset loogikat. Selle semantika seisneb semantilistes mängudes, millel on mõned ebatavalised omadused. Näiteks ei ole alati kindlaks määratud, kes mängijast järgmise käigu teeb. Strateegiafunktsioonide mõiste ei ole enam mängijate kirjeldamiseks piisav; selle asemel kirjeldab Japaridze teise mängija (mängija (olemas) meie loetelus) lugemise viise kui omamoodi arvutusmasinat. Lisateave on tema veebisaidil.
Veel üks grupp sama perekonna Lorenzenitega peetud mänge on Pavel Pudlaki 2000. aasta tõestusmängud. Siin on Oponent (kutsutud Prover) kohtus advokaadi rollis, kes teab, et pooldaja (nimetatakse vastaseks) on süüdi mingis süüteos. Pooldaja väidab, et ta on süütu ja on valmis enda kaitsmiseks valedest rääkima. Oponendi eesmärk on sundida pooldajat astuma vastuollu sellega, mida pooldaja on varem registreerinud; kuid vastane peab arvestust ja (nagu ülaltoodud veerisemängudes) peab ta mõnikord ruumi või mälu puudumise tõttu üksused registrist välja viskama. Oluline küsimus pole mitte selles, kas Oponendil on võidustrateegia (algusest peale eeldatakse, et tal on see olemas), vaid selles, kui palju mälu ta oma plaadi jaoks vajab. Need mängud on kasulik seade, mis näitab tõendite pikkuse ülemist ja alumist piiri erinevates tõestussüsteemides.
Teine selline loogiline mäng, mis lubab valesid, on Ulami mäng valedega. Siin mõtleb üks mängija numbri teatud vahemikus. Teise mängija eesmärk on välja selgitada, mis see number on, esitades esimesele mängijale jah / ei küsimusi; kuid esimesel mängijal on lubatud oma vastustes rääkida kindla arvu valedest. Nagu Pudlaki mängudes, on kindlasti olemas ka teise mängija võidustrateegia, kuid küsimus on selles, kui kõvasti peab see mängija võitmiseks pingutama. Mõõde pole seekord ruum ega mälu, vaid aeg: mitu küsimust ta peab esitama? Cignoli jt. 2000. aasta 5. peatükk seob seda mängu paljude väärtustega loogikaga.
Naastes hetkeks Lorenzenisse: ta ei suutnud vahet teha erinevatel seisukohtadel, mida inimene võib argumendis kasutada: enda väitmine, eeldamine, järeleandmine, päringute tegemine, ründamine, enesele pühendumine. See, kas on tõesti võimalik kõiki neid mõisteid määratleda ilma mingisugust loogikat eeldamata, on küsimus. Kuid ärge kunagi sellega arvestage; Lorenzeni mängude täpsustamine vastavalt nendele suundadele võiks olla lähenemisviis mitteametlikule loogikale ja eriti uurimistööle, mille eesmärk on süstematiseerida usaldusväärsete mitteametlike argumentide võimalikud struktuurid. Sellel küljel vt Walton ja Krabbe 1995. Asjakohased on ka Bench-Caponi ja Dunne 2007 artiklid.
Bibliograafia
Mõned Henkini ja Lorenzeni põhjalikud ettekanded ja mõned allpool viidatud artiklid ilmuvad kogumikus Infinitistic Methods (Proceedings of the Symposium on on pamate of Mathematics, Varssavis, 2. – 9. September 1959), Oxford: Pergamon Press, 1961 Toimetajad pole nime saanud.
Mängud loogika ajaloos
Dutilh Novaes, Catarina, 2007, Keskaja loogikateooriate vormistamine: Suppositio, Consequentiae and Obligationes, New York: Springer-Verlag.
Hilbert, David, 1967, “Die Grundlagen der Mathematik”, tõlgitud kui “matemaatika alused”, Jean van Heijenoorti (toim) Fregest Gödelini, Cambridge Mass: Harvard University Press, lk 464–479.
Veneetsia Paulus, Logica Magna II (8), Tractatus de Obligationibus, E. Jennifer Ashworth (toim), New York: Briti Akadeemia ja Oxford University Press, 1988.
Weyl, Hermann, 1925–7, “Die heutige Erkenntnislage in der Mathematik”, tõlgitud kui “Matemaatika praegune epistemoloogiline olukord” Paolo Mancosus Brouwerist Hilbertini: arutelu matemaatika aluste üle 1920. aastatel, New York: Oxford University Press, 1988, lk 123–142.
Zermelo, Ernst, 1913, “Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels”, EW Hobson ja AEH Love (toim.), Viienda rahvusvahelise matemaatikute kongressi toimikud, II köide, Cambridge: Cambridge University Press.
Mängud loogika õpetamiseks
Barwise, Jon ja John Etchemendy, 1995, Esimese astme loogika keel, sealhulgas Tarski maailm 3.0, Cambridge: Cambridge University Press.
Dienes, Zoltan P. ja EW Golding, 1966, Õppimisloogika, Loogilised mängud, Harlow: Hariduse pakkumise ühing.
Havas, Katalin, 1999, “Mõtlemisõpe: laste loogika”, kahekümnenda maailma filosoofiakongressi toimetustes (3. köide: haridusfilosoofia), David M. Steiner (toim), Bowling Green Ohio: Bowling Green State Ülikooli filosoofia, lk 11–19.
Nifo, Agostino, 1521, Dialectica Ludicra (Loogika kui mäng), Firenze: Bindonis.
Weng, Jui-Feng, koos Shian-Shyong Tsengi ja Tsung-Ju Leega, 2010, "Boole'i loogika õpetamine mängureeglite häälestamise kaudu", IEEE tehingud, Learning Technologies, 3 (4): 319–328. [Kasutab Pac-Mani mänge Boole'i loogika õpetamiseks gümnaasiumiõpilastele.]
Loogilised mängud
Gale, David ja FM Stewart, 1953, “Lõpmatud mängud täiusliku teabega”, kaastöös II mängude teooriasse (Matemaatikaõppe Annals 28), HW Kuhn ja AW Tucker (toim), Princeton: Princeton University Press, lk 245–266.
Kechris, Alexander S., 1995, klassikaline kirjeldav komplekti teooria, New York: Springer-Verlag.
Marion, Mathieu, 2009, “Miks mängida loogilisi mänge?”, Ondrej Majer, Ahti-Veikko Pietarinen ja Tero Tulenheimo, toim., Games: Ühendav loogika, keel ja filosoofia, New York: Springer-Verlag, lk 3–25.
Osbourne, Martin J. ja Ariel Rubinstein, 1994, Mänguteooria kursus, Cambridge: MIT Press.
Väänänen, Jouko, 2011, mudelid ja mängud, Cambridge: Cambridge University Press.
van Benthem, Johan, 2011, teabe ja interaktsiooni loogiline dünaamika, Cambridge: Cambridge University Press, 2011.
–––, 2014, Loogika mängudes, Cambridge, MA: MIT Press.
Hintikka, Jaakko, 1973, loogika, keelemängud ja teave: Kanti teemad loogikafilosoofias, Oxford: Clarendon Press.
Hintikka, Jaakko, 1996, Matemaatika põhimõtted uuesti läbi vaadatud, New York: Cambridge University Press. [Vaadake näiteks valitud aksioomi lehti 40, 82.]
Hodges, Wilfrid, 2001, “Elementaarne ennustatav loogika 25: Skolemi funktsioonid”, Dov Gabbay, ja Franz Guenthner (toim.), Filosoofilise loogika I käsiraamat, 2. trükk, Dordrecht: Kluwer, lk 86–91. [Tõend mängu ja Tarski semantika samaväärsuse kohta.]
Kolaitis, Ph. G., 1985, “Mängu kvantifitseerimine”, J. Barwise ja S. Feferman (toim), Model-Theoretic Logics, New York: Springer-Verlag, lk 365-421.
Peirce, Charles Sanders, 1898, Mõistmine ja asjaloogika: 1898. aasta Cambridge'i konverentside loengud, toim. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.
Ebatäiusliku teabega semantilised mängud
Hintikka, Jaakko ja Gabriel Sandu, 1997, “Mänguteoreetiline semantika”, Johan van Benthem ja Alice ter Meulen (toim), loogika ja keele käsiraamat, Amsterdam: Elsevier, lk 361–410.
Janssen, Theo MV ja Francien Dechesne, 2006, “Signalisatsioon: keeruline äri”, J. van Benthem jt. (toim), Alternatiivse loogika vanus: loogika ja matemaatika filosoofia hindamine tänapäeval, Dordrecht: Kluwer, lk 223–242.
Mann, Allen L., Gabriel Sandu ja Merlin Sevenster, 2011, Sõltumatussõbralik loogika: mänguteoreetiline lähenemisviis (Londoni matemaatilise seltsi loengute seeria 386), Cambridge: Cambridge University Press.
von Neumann, John ja Oskar Morgenstern, 1944, Mängude teooria ja majanduslik käitumine, Princeton: Princeton University Press.
Väänänen, Jouko, 2007, Sõltuvusloogika: uus lähenemisviis iseseisvussõbralikule loogikale, Cambridge: Cambridge University Press.
Muu loogika semantilised mängud
Bradfield, Julian ja Colin Stirling, 2006, “Modal mu-calculi”, P. Blackburn jt. (toim), Modal Logic käsiraamat, Amsterdam: Elsevier, lk 721–756.
Dekker, Paul ja Marc Pauly (toim.), 2002, Journal of Logic, Language and Information, 11 (3): 287–387. [Loogika ja mängude eriväljaanne.]
Hennessy, Matthew ja Robin Milner, 1985, “Algebralised seadused indeterminismi ja samaaegsuse kohta”, ajakiri ACM, 32: 137–162.
Parikh, Rohit, 1985, „Mängude ja selle rakenduste loogika”, Marek Karpinski ja Jan van Leeuwen (toim), „Arvutusteooria teemad”, Annals of Discrete Mathematics, 24: 111–140.
Pauly, Marc ja Rohit Parikh (toim.), 2003, Studia Logica, 72 (2): 163–256 [Mänguloogika eriväljaanne.]
Stirling, Colin, 2001, Protsesside modaalsed ja ajalised omadused, New York: Springer-Verlag.
van Benthem, Johan, 2006, “IF-mängude episteemiline loogika”, Randall Auxier ja Lewis Hahn (toim), Jaakko Hintikka filosoofia, Chicago: avatud kohus, lk 481–513.
van Benthem, Johan koos Amitabha Gupta ja Rohit Parikh, 2011, korrektuur, arvutamine ja agentuur, Dordrecht: Springer-Verlag.
Tagasi ja teise mängu mängud
Blackburn, Patrick koos Maarten de Rijke ja Yde Venemaga, 2001, Modal Logic, Cambridge: Cambridge University Press.
Doets, Kees, 1996, Põhimudeliteooria, Stanford: CSLI Publications ja FoLLI.
Ebbinghaus, Heinz-Dieter ja Jörg Flum, 1999, lõplike mudeliteooria, 2. trükk, New York: Springer.
Grädel, Erich koos Phokion G. Kolaitisega, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema ja Scott Weinstein, 2007, Piiratud mudeliteooria, Berliin: Springer-Verlag.
Libkin, Leonid, 2004, Piiratud mudeliteooria elemendid, Berliin, Springer-Verlag.
Otto, Martin, 1997, Piiritletud muutuva loogika ja loenduse-uuring lõpumudelites (loengu märkused logikas, 9), Berliin: Springer-Verlag.
Peters, Stanley ja Dag Westerståhl, 2006, keele ja loogika kvantifikaatorid, Oxford: Clarendon Press.
Tarski, Alfred, 1946, “Kõne Princetoni ülikooli kahekümnendal konverentsil matemaatika probleemide teemal (17. – 19. Detsember 1946)”, “Hourya Sinaceur (toim.), Symbolic Logic Bulletin, 6 (2000): 1–44.
van Benthem, Johan, 2001, “Kirjavahetuse teooria”, Dov Gabbay ja Franz Guenthner (toim), III filosoofilise loogika käsiraamat, 2. trükk, Dordrecht: Kluwer.
Muud mudelateoreetilised mängud
Anthony, Martin ja Norman Biggs, 1992, Computational Learning Theory, Cambridge: Cambridge University Press. [Vapnik-Chervonenkise mõõtme jaoks.]
Gurevitš, Juri ja Leo Harrington, 1984, “Puud, automatid ja mängud”, HR Lewis (toim.), ACMi arvutusteooria teooria sümpoosion, San Francisco: ACM, lk 171–182.
Hirsch, Robin ja Ian Hodkinson, 2002, Suhete algebrad mängude poolt, New York: Põhja-Holland.
Hodges, Wilfrid, 1985, mängude ehituse mudelid, Cambridge: Cambridge University Press.
Hodges, Wilfrid, 1993, mudeliteooria, Cambridge: Cambridge University Press.
Oxtoby, JC, 1971, mõõt ja kategooria, New York: Springer-Verlag.
Ziegler, Martin, 1980, “Algebraisch abgeschlossene Gruppen”, SI Adian jt. (toim), Sõnaprobleemid II: Oxfordi raamat, Amsterdam: Põhja-Holland, lk 449–576.
Dialoogi, suhtluse ja tõestuse mängud
Abramsky, Simson ja Radha Jagadeesan, 1994, “Mängud ja multiplikatiivse lineaarse loogika täielik täielikkus”, Journal of Symbolic Logic, 59: 543–574.
Abramsky, Simson ja Paul-André Melliès, 1999, “Samaaegsed mängud ja täielik komplekteeritus”, neljateistkümnenda rahvusvahelise arvutiteaduse loogikasümpoosioni ettekandes, IEEE Computer Science Press, lk 431–442.
Bench-Capon, TJM ja Paul E. Dunne, 2007, “Argumenteerimine tehisintellektis”, tehisintellekt, 171: 619–641. [Sissejuhatus rikkalikku samateemalist paberikogumikku lehekülgedel 642–937.]
Blass, Andreas, 1992, “Lineaarse loogika mängusemantika”, Annals of Pure and Applied Logic, 56: 183–220.
Cignoli, Roberto LO, Itala ML D'Ottaviano ja Daniele Mundici, 2000, Algebralised alused mitmehäälse põhjendamise alustest, Dordrecht: Kluwer.
Felscher, Walter, 2001, “Dialoogid kui intuitsioonilise loogika alus”, Dov Gabbay ja Franz Guenthner (toim), Philosophical Logic V käsiraamat, 2. trükk, Dordrecht: Kluwer.
Hodges, Wilfrid ja Erik CW Krabbe, 2001, “Dialoogi alused”, Aristotelevi Seltsi Toimetised (lisamaht), 75: 17–49.
Japaridze, Giorgi, 2003, “Sissejuhatus arvutatavusloogikasse”, Annals of Pure and Applied Logic, 123: 1–99.
Walton, Douglas N. ja Erik CW Krabbe, 1995, pühendumus dialoogile: inimestevaheliste mõttekäikude põhikontseptsioonid, Albany: New York State University.
Akadeemilised tööriistad
sep mehe ikoon
Kuidas seda sissekannet tsiteerida.
sep mehe ikoon
Vaadake selle sissekande PDF-versiooni SEP-i sõprade veebisaidil.
info ikoon
Otsige seda sisenemisteema Interneti-filosoofia ontoloogiaprojektilt (InPhO).
phil paberite ikoon
Selle kande täiustatud bibliograafia PhilPapersis koos linkidega selle andmebaasi.
