Logika I Igre

Sadržaj:

Logika I Igre
Logika I Igre

Video: Logika I Igre

Video: Logika I Igre
Video: Приложение "Логика" по информатике за 9 класс. Прохождение :) 2024, Ožujak
Anonim

Ulazna navigacija

  • Sadržaj unosa
  • Bibliografija
  • Akademske alate
  • Prijatelji PDF pregled
  • Podaci o autoru i citiranju
  • Povratak na vrh

Logika i igre

Prvo objavljeno pet srpnja 27, 2001; suštinska revizija Fri Aug 16, 2019

Igre između dva igrača, onakve u kojoj jedan igrač pobijedi, a jedan izgube, postale su poznato sredstvo u mnogim granama logike tijekom druge polovice dvadesetog stoljeća. Važni primjeri su semantičke igre koje se koriste za definiranje istine, igre napred-nazad za usporedbu struktura i dijaloške igre za izražavanje (a možda i objašnjenje) formalnih dokaza.

  • 1. Igre u povijesti logike
  • 2. Logičke igre
  • 3. Semantičke igre za klasičnu logiku
  • 4. Semantičke igre s nesavršenim informacijama
  • 5. Semantičke igre za drugu logiku
  • 6. Igre unazad i naprijed
  • 7. Ostale model-teoretske igre

    • 7.1 Prisiljavanje igara
    • 7.2 Igre rezanja i izbora
    • 7.3 Igre na drvetu dviju funkcija nasljednika
  • 8. Igre dijaloga, komunikacije i dokazivanja
  • Bibliografija

    • Igre u povijesti logike
    • Igre za podučavanje logike
    • Logičke igre
    • Semantičke igre za klasičnu logiku
    • Semantičke igre sa nesavršenim informacijama
    • Semantičke igre za drugu logiku
    • Igre unazad i naprijed
    • Ostale Teoretske igre
    • Igre dijaloga, komunikacije i dokazivanja
  • Akademske alate
  • Ostali internetski resursi
  • Povezani unosi

1. Igre u povijesti logike

Veze između logike i igara sežu daleko. Ako netko misli na raspravu kao na neku vrstu igre, tada je Aristotel već uspostavio vezu; njegovi su spisi o silogizmu usko povezani s proučavanjem ciljeva i pravila rasprave. Aristotelovo gledište prešlo je u uobičajeni srednjovjekovni naziv za logiku: dijalektika. Sredinom dvadesetog stoljeća Charles Hamblin oživio je vezu između dijaloga i pravila zdravog rasuđivanja, ubrzo nakon što je Paul Lorenzen dijalog povezao s konstruktivnim osnovama logike.

Između igara i nastave postoje uske veze. Pisci kroz srednjovjekovno razdoblje govore o dijalozima kao načinu „poučavanja“ili „ispitivanja” upotrebe zvučnih rezonovanja. Imamo barem dva udžbenika logike iz ranog šesnaestog stoljeća koji ga prikazuju kao igru za pojedinog učenika, a Lewis Carroll je Igra logike (1887) još jedan primjer u istom žanru. Puno je suvremenih primjera, mada vjerojatno nije bilo dovoljno kontinuiteta da bi se igrama opravdala tradicija podučavanja logike.

Matematička teorija igara osnovana je početkom dvadesetog stoljeća. Iako se matematičke veze s logikom nisu pojavile do 1950-ih, upečatljivo je koliko je ranih pionira teorije igara također poznato po svojim doprinosima logici: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo i drugi. Godine 1953. David Gale i Frank Stewart urodili su plodom između teorije skupova i igara. Ubrzo nakon toga Leon Henkin predložio je način korištenja igara da bi dao semantiku za infinitarne jezike.

Prva polovina dvadesetog stoljeća bila je doba sve veće strogosti i profesionalizma u logici, a većini logičara toga razdoblja upotreba igara u logici vjerojatno bi se činila neozbiljna. Intuicionist LEJ Brouwer izrazio je takav stav kada je optužio svoje protivnike da su matematiku natjerali na „degeneriranje u igru“(kao što je citirao David Hilbert 1927., citirano u van Heijenoort 1967.). Hermann Weyl (citirano u Mancosu 1998.) koristio je pojam igara da bi objasnio Hilbertovu metamatematiku: matematički dokazi odvijaju se poput igranja besmislene igre, ali mi možemo stajati izvan igre i postavljati smislena pitanja o njoj. Wittgensteinove jezične igre izazvale su malo odgovora logičara. No, u drugoj polovici stoljeća težište logičkog istraživanja prešlo je iz temelja u tehnike,a od oko 1960. godine igre su se sve češće koristile u logičkim radovima.

Početkom dvadeset prvog stoljeća postalo je široko prihvaćeno da igre i logika idu zajedno. Rezultat je bila velika količina novih kombinacija logike i igara, posebno u područjima gdje se logika primjenjuje. Mnogi su od tih novih razvoja nastali izvorno iz čiste logike, iako danas slijede vlastite programe. Jedno takvo područje je teorija argumentacije, gdje igre čine alat za analizu strukture rasprava.

U nastavku ćemo se usredotočiti na one igre koje su najuže povezane s čistom logikom.

2. Logičke igre

Sa stajališta teorije igara, glavne igre koje logičari proučavaju uopće nisu tipične. Obično uključuju samo dva igrača, često imaju beskonačnu duljinu, jedini ishodi su pobjeda i gubitak i nikakve vjerojatnosti nisu povezane s radnjama ili ishodima. Najosnovnije suštine logičke igre su sljedeće.

Postoje dva igrača. Općenito ih možemo nazvati (forall) i (postoji). Izgovori "Abelard" i "Eloise" sežu do sredine 1980-ih i korisno popravljaju igrače kao muško i žensko što olakšava referencu: njezin potez, njegov potez. Druga su imena uobičajena za igrače u određenim vrstama logičke igre.

Igrači igraju odabirom elemenata skupa (Omega), koji se nazivaju domenom igre. Kako odluče, grade niz

[a_0, a_1, a_2, / ldots)

elemenata (Omega). Beskonačni nizovi elemenata (Omega) nazivaju se igrama. Konačni nizovi elemenata (Omega) nazivaju se položajima; oni bilježe gdje bi do određenog vremena mogla doći neka predstava. Funkcija (tau) (funkcija skretanja ili funkcija igrača) zauzima svaku poziciju (mathbf {a}) bilo (postoji) ili (forall); ako je (tau (mathbf {a}) = / postoji), to znači da kad igra stigne (mathbf {a}), igrač (postoji) donosi sljedeći izbor (i slično sa (forall)). Pravila igre određuju dva skupa (W _ { forall}) i (W _ { postoji}) koji se sastoje od pozicija i igra, sa sljedećim svojstvima: ako je pozicija (mathbf {a}) nalazi se u (W _ { forall}), tada je svaka igra ili duža pozicija koja započinje s (mathbf {a}) (i slično s (W _ { postoji}));i nema igranja ni u (W _ { forall}) ni u (W _ { postoji}). Kažemo da igrač (forall) pobjeđuje u igri (mathbf {b}), a da je (mathbf {b}) dobitak za (forall), ako (mathbf {b}) je u (W _ { forall}); ako je neka pozicija (mathbf {a}) koja je početni segment (mathbf {b}) u (W _ { forall}), tada kažemo da je igrač (forall) pobjeđuje već kod (mathbf {a}). (I isto tako s (postoji) i (W _ { postoji}). Dakle, ukratko, logična igra je četverougla ((Omega, / tau), (W_ { forall}), (W _ { postoji})) sa upravo opisanim svojstvima.tada kažemo da igrač (forall) pobjeđuje već kod (mathbf {a}). (I isto tako s (postoji) i (W _ { postoji}). Dakle, ukratko, logična igra je četverougla ((Omega, / tau), (W_ { forall}), (W _ { postoji})) sa upravo opisanim svojstvima.tada kažemo da igrač (forall) pobjeđuje već kod (mathbf {a}). (I isto tako s (postoji) i (W _ { postoji}). Dakle, ukratko, logična igra je četverougla ((Omega, / tau), (W_ { forall}), (W _ { postoji})) sa upravo opisanim svojstvima.

Kažemo da je logična igra totalna ako je svaka igra u (W _ { forall}) ili (W _ { postoji}), tako da nema izvlačenja. Ako netko ne napravi izričiti izuzetak, logične se igre uvijek pretpostavljaju kao totalne. (Nemojte brkati da ste totalni s mnogo jačim svojstvom utvrđivanja - pogledajte dolje.)

Matematička pogodnost samo je da gornja definicija očekuje da igra nastavi u beskonačnost čak i kad igrač pobijedi na nekoj određenoj poziciji; nema interesa za bilo što što se dogodi nakon što igrač pobijedi. Mnoge logičke igre imaju svojstvo toga što je u svakoj igri jedan od igrača već pobijedio na određenoj poziciji; igre ove vrste kažu da su dobro utemeljene. Još je jači uvjet da postoji neki konačni broj (n) takav da je u svakoj igri jedan od igrača već osvojio (n) - poziciju; u ovom slučaju kažemo da igra ima ograničenu duljinu.

Strategija za igrača je skup pravila koja točno opisuju kako taj igrač treba odabrati, ovisno o tome kako su dva igrača odabrala u ranijim potezima. Matematički se strategija za (forall) sastoji od funkcije koja zauzima svaki položaj (mathbf {a}) s (tau (mathbf {a}) = / forall) elementom (b) od (Omega); mislimo na to kao naputak (forall) da odabere (b) kad igra dosegne poziciju (mathbf {a}). (Isto tako, sa strategijom za (postoji).) Za strategiju igrača se kaže da je dobitna ako taj igrač pobijedi u svakoj igri u kojoj koristi strategiju, bez obzira što drugi igrač radi. U većini slučajeva jedan od igrača ima pobjedničku strategiju (jer u protivnom igrači mogu igrati svoje pobjedničke strategije jedni protiv drugih, a oba će pobijediti,suprotno da (W _ { forall}) i (W _ { postoji}) nemaju zajedničko igranje). Povremeno se susreću situacije u kojima se čini da dva igrača imaju strategije pobjede (na primjer, u prisilnim igrama ispod), ali pomniji pregled pokazuje da dva igrača zapravo igraju različite igre.

Kaže se da se igra određuje ako jedan ili drugi igrač ima strategiju pobjedništva. Mnogo je primjera igara koje nisu određene, kao što su Gale i Stewart pokazali 1953. koristeći aksiom izbora. Ovo otkriće dovelo je do važne primjene pojma determiniranosti u temeljima teorije skupova (vidi unos o velikim kardinalima i odlučnosti). Gale i Stewart su se također pokazali važnom teoremom koja nosi njihovo ime: Svaka dobro utemeljena igra je određena. Iz toga slijedi da je svaka igra konačne duljine određena - činjenica koja je Zermelo-u već poznata 1913. (Točnija tvrdnja teoreme Gale-Stewart je ovo. Igra se (G) kaže da je zatvorena ako (postoji) pobjeđuje svaku igru (G) u kojoj se već nije izgubila ni na jednom konačnom položaju. Teorem navodi da je svaka zatvorena igra određena. Dokaz teoreme je u osnovi jednostavan: Nazovimo poziciju koja je dobitna za (forall) ako on ima strategiju pobjedništva polazeći od ove pozicije. Pretpostavimo da (forall) nema pobjedničku strategiju u igri, tj. U početku pozicija ne pobjeđuje za (forall). Ako je prvi potez potez (forall), nakon njegovog poteza pozicija još uvijek nije dobitna za njega. Ako je prvi potez potez (postoji), ona mora imati pomak, nakon čega pozicija još uvijek ne pobjeđuje za (forall), jer bi u suprotnom prethodna pozicija bila dobitna za (forall). Igra se nastavlja na ovaj način beskonačno mnogo kretanja kroz pozicije koje ne pobjeđuju za (forall). Budući da je igra zatvorena, pobjeđuje (postoji).)Pretpostavimo da (forall) nema pobjedničku strategiju u igri, tj. U početku pozicija ne pobjeđuje za (forall). Ako je prvi potez potez (forall), nakon njegovog poteza pozicija još uvijek nije dobitna za njega. Ako je prvi potez potez (postoji), ona mora imati pomak, nakon čega pozicija još uvijek ne pobjeđuje za (forall), jer bi u suprotnom prethodna pozicija bila dobitna za (forall). Igra se nastavlja na ovaj način beskonačno mnogo kretanja kroz pozicije koje ne pobjeđuju za (forall). Budući da je igra zatvorena, pobjeđuje (postoji).)Pretpostavimo da (forall) nema pobjedničku strategiju u igri, tj. U početku pozicija ne pobjeđuje za (forall). Ako je prvi potez potez (forall), nakon njegovog poteza pozicija još uvijek nije dobitna za njega. Ako je prvi potez potez (postoji), ona mora imati pomak, nakon čega pozicija još uvijek ne pobjeđuje za (forall), jer bi u suprotnom prethodna pozicija bila dobitna za (forall). Igra se nastavlja na ovaj način beskonačno mnogo kretanja kroz pozicije koje ne pobjeđuju za (forall). Budući da je igra zatvorena, pobjeđuje (postoji).)Ako je prvi potez potez (postoji), ona mora imati pomak, nakon čega pozicija još uvijek ne pobjeđuje za (forall), jer bi u suprotnom prethodna pozicija bila dobitna za (forall). Igra se nastavlja na ovaj način beskonačno mnogo kretanja kroz pozicije koje ne pobjeđuju za (forall). Budući da je igra zatvorena, pobjeđuje (postoji).)Ako je prvi potez potez (postoji), ona mora imati pomak, nakon čega pozicija još uvijek ne pobjeđuje za (forall), jer bi u suprotnom prethodna pozicija bila dobitna za (forall). Igra se nastavlja na ovaj način beskonačno mnogo kretanja kroz pozicije koje ne pobjeđuju za (forall). Budući da je igra zatvorena, pobjeđuje (postoji).)

Baš kao u klasičnoj teoriji igara, gore definirana logička igra služi kao konj za odjeću na koji možemo objesiti druge koncepte. Na primjer, uobičajeno je da postoje neki zakoni koji opisuju koje elemente (Omega) su na raspolaganju da igrač odabere u određenom potezu. Strogo je to preciziranje nepotrebno, jer na pobjedničke strategije ne utječemo ako umjesto toga odlučimo da igrač koji krši zakon odmah gubi; ali za mnoge se igre takav način njihovog gledanja čini neprirodnim. Ispod ćemo vidjeti neke druge dodatne značajke koje se mogu dodati igrama.

Prethodne definicije igre i strategije bile su čisto matematičke. Tako su izostavljali ono što je vjerojatno najvažnija karakteristika igara, a to je da ih ljudi igraju (barem metaforički). Igrači ciljaju na pobjedu, a proučavanjem otvorenih strategija proučavamo koje je ponašanje racionalno za osobu s određenim ciljem. U većini igara ima nekoliko igrača, tako da možemo proučiti što je racionalan odgovor na tuđe ponašanje. Ograničavajući igračeve poteze i moguće strategije, možemo proučavati ograničenu racionalnost, gdje agent mora donositi racionalne odluke u uvjetima ograničenih informacija, memorije ili vremena.

Ukratko, igre se koriste za modeliranje racionalnosti i ograničene racionalnosti. To je neovisno o bilo kakvoj vezi s logikom. No neke su logike bile stvorene za proučavanje aspekata racionalnog ponašanja, a posljednjih je godina sve češće povezivanje tih logika s prikladnim igrama. Vidi Odjeljak 5 ('Semantičke igre za ostale logike') i njegovu bibliografiju.

No donedavno su logične igre na sasvim drugačiji način bile povezane s racionalnim ponašanjem. Na površini, dotična logika nije imala izravnu vezu s ponašanjem. No, logičari i matematičari primijetili su da neke ideje mogu postati intuitivnije ako se povežu s mogućim ciljevima. Na primjer, u mnogim aplikacijama logičkih igara, središnji je smisao dobitne strategije za igrača (postoji). Često se te strategije (ili njihovo postojanje) pokaže kao ekvivalentne nečemu što je logično važno što se moglo definirati bez korištenja igara - na primjer, dokaz. No igre se smatraju boljom definicijom jer doslovno nude neku motivaciju: (postoji) pokušava pobijediti.

Postavlja se pitanje koje matematički ne zanima previše, ali bi se trebalo odnositi na filozofe koji koriste logičke igre. Ako želimo da (postoji) motivacija u igri (G) ima neku objašnjenu vrijednost, tada moramo razumjeti što se postiže ako (postoji) pobijedi. Naročito bismo trebali biti u stanju da ispričamo realnu priču o situaciji u kojoj neki agent zvan (postoji) pokušava učiniti nešto razumljivo, a raditi to je isto što i pobjeda u igri. Kao što je rekao Richard Dawkins, postavljajući odgovarajuće pitanje za evolucijske igre Maynarda Smitha,

Cjelokupna svrha naše potrage… je otkriti prikladnog glumca koji bi igrao vodeću ulogu u našim metaforama svrhe. Mi … želimo reći: "Za dobro je …". Naša potraga u ovom poglavlju je pravi način da dovršimo tu rečenicu. (Prošireni fenotip, Oxford University Press, Oxford 1982, str. 91.)

Za buduću upotrebu nazovimo ovo Dawkinsovo pitanje. U mnogim vrstama logičnih igara ispada da je znatno teže odgovoriti nego što su to pokazali pioniri ovih igara. (Marion 2009 dalje razmatra Dawkinsovo pitanje.)

3. Semantičke igre za klasičnu logiku

U ranim tridesetima Alfred Tarski predložio je definiciju istine. Njegova se definicija sastojala od nužnog i dovoljnog uvjeta da je rečenica na jeziku tipične formalne teorije istinita; njegov nužni i dovoljan uvjet koristio je samo pojmove iz sintakse i teorije skupa, zajedno s primitivnim pojmovima formalne teorije u pitanju. Zapravo je Tarski definirao općenitiji odnos 'formula (phi (x_1, / ldots, x_n)) je istina za elemente (a_1, / ldots, a_n)' istina rečenice je poseban slučaj gdje (n = 0). Na primjer pitanje da li

'Za sve (x) postoji (y) takav da je R ((x, y))' istina

svodi se na pitanje ima li sljedeće:

Za svaki objekt (a) rečenica "Postoji (y) takva da je R ((a, y))" istinita.

To se zauzvrat svodi na:

Za svaki objekt (a) postoji objekt (b) takav da je rečenica "R ((a, b))" istinita.

U ovom primjeru, to je onoliko koliko će nas odvesti definicija Tarske.

Krajem pedesetih godina prošlog stoljeća Leon Henkin primjetio je da intuitivno možemo razumjeti neke rečenice koje se ne mogu nositi s Tarskijevom definicijom. Uzmimo za primjer beskonačno dugu rečenicu

Za sve (x_0) postoji (y_0) takav da za sve (x_1) postoji (y_1) takav da … R ((x_0, y_0, x_1, y_1, / ldots)), Tarski pristup ne uspijeva jer je niz kvantifikatora na početku beskonačan, i nikad ih ne bismo doveli do kraja uklanjanja. Umjesto toga, predložio je Henkin, trebali bismo razmotriti igru u kojoj osoba (forall) odabire objekt (a_0) za (x_0), a onda druga osoba (postoji) bira objekt (b_0) za (y_0), tada (forall) bira (a_1) za (x_1, / postoji) bira (b_1) za (y_1) i tako dalje. Igra ove igre je dobit za (postoji) ako i samo ako je beskonačna atomska rečenica

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

je istina. Izvorna rečenica je istinita ako i samo ako igrač (postoji) ima pobjedničku strategiju za ovu igru. Strogo je Henkin koristio igru samo kao metaforu, a uvjet istine koji je predložio je da je skolizirana verzija rečenice istinita, tj. Da postoje funkcije (f_0, f_1, / ldots) takve da za svaki izbor (a_0, a_1, a_2) itd. imamo

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

Ali to se stanje odmah prevodi u jezik igara; Skolemske funkcije (f_0) itd. definiraju pobjedničku strategiju za (postoji), govoreći joj kako da odabere u svjetlu ranijih izbora pomoću (forall). (Došlo je do izražaja nešto kasnije da je CS Peirce već predložio da se objasni razlika između "svakog" i "nekog" u pogledu onoga tko odabere objekt; na primjer, u svom drugom predavanju iz Cambridgeove konferencije iz 1898.)

Ubrzo nakon Henkinova djela, Jaakko Hintikka dodao je da se ista ideja odnosi i na veznike i disjunkcije. Vezu "(phi / wedge / psi)" možemo smatrati univerzalno kvantificiranom izjavom koja izražava "Svaka jedna rečenica (phi, / psi) drži", pa bi to trebalo biti za igrača (forall) za odabir jedne od rečenica. Kako je rekao Hintikka, za igranje igre (G (phi / klin / psi), / forall) bira hoće li igra nastaviti kao (G (phi)) ili kao (G (psi))). Isto tako disjunkcije postaju egzistencijalno kvantificirane izjave o skupu rečenica i označavaju poteze tamo gdje igrač (postoji) odabere kako će igrati igru. Da bi kvantifikatore doveo u isti stil, predložio je da igra (G (forall x / phi (x))) nastavi tako: igrač (forall) bira objekt i daje ime (a) za to,a igra se odvija kao (G (phi (a))). (I isto tako s egzistencijalnim kvantifikatorima, osim što odabere (postoji).) Hintikka je također iznijela genijalan prijedlog za uvođenje negacije. Svaka igra G ima dvostruku igru koja je isto što i G, osim što su igrači (forall) i (postoji) pretočeni u oba pravila igre i u pravila za pobjedu. Igra (G (neg / phi)) je dvostruka od (G (phi)).

Može se dokazati da svaka rečenica prvog reda (phi), interpretirana u fiksnoj strukturi (A), igrač (postoji) ima pobjedničku strategiju za Hintikkinu igru (G (phi)) ako i samo ako je (phi) istinito u (A) u smislu Tarski. Dvije značajke ovog dokaza su zanimljive. Prvo, ako je (phi) bilo koja rečenica prvog reda, tada igra (G (phi)) ima ograničenu duljinu, pa nam teorem Gale-Stewart govori da je ona određena. Zaključujemo da (postoji) ima pobjedničku strategiju u točno jednom od (G (phi)) i njegovom dvojniku; tako da ona ima dobitnu strategiju u (G (neg / phi)) ako i samo ako je nema u (G (phi)). Ovo vodi računa o negaciji. I drugo, ako (postoji) ima dobitnu strategiju za svaku igru (G (phi (a))), nakon odabira jedne takve strategije (f_a) za svaku (a),ona ih može povezati u jedinstvenu pobjedničku strategiju za (G (forall x / phi (x))) (naime, Pričekajte i pogledajte koji element (a / forall) odabere, a zatim igrajte (f_a) '). Time se vodi računa o klauzuli za univerzalne kvantifikatore; ali argument koristi aksiom izbora, a zapravo nije teško vidjeti da je tvrdnja da su Hintikkine i Tarške definicije istine jednake, sama po sebi jednaka aksiomu izbora (s obzirom na ostale aksiome teorije skupova Zermelo-Fraenkel),i zapravo nije teško vidjeti da je tvrdnja da su Hintikkine i Tarske definicije istine jednake, sama po sebi jednaka aksiomu izbora (s obzirom na ostale aksiome teorije skupova Zermelo-Fraenkel).i zapravo nije teško vidjeti da je tvrdnja da su Hintikkine i Tarske definicije istine jednake, sama po sebi jednaka aksiomu izbora (s obzirom na ostale aksiome teorije skupova Zermelo-Fraenkel).

Zbunjujuće je da ovdje imamo dvije teorije o tome kada je rečenica istinita, a teorije nisu ekvivalentne ako aksiom izbora ne uspije. Zapravo, razlog nije baš dubok. Aksiom izbora potreban je ne zato što Hintikka definicija koristi igre, već zato što pretpostavlja da su strategije determinirane, tj. Da su jednoznačne funkcije koje korisniku ne biraju mogućnost izbora. Prirodniji način prevođenja Tarške definicije u izraze igre jest upotreba netermineričkih strategija, ponekad nazvanih kvazistragijama (za detalje vidjeti Kolaitis 1985). (Međutim, Hintikka 1996 inzistira na tome da je ispravna eksplikacija "istine" ona koja koristi determinirane strategije i da ta činjenica ukazuje na aksiom izbora.)

Računalne implementacije ovih igara na Hintikki pokazale su se kao vrlo učinkovit način učenja značenja rečenica prvog reda. Jedan takav paket dizajnirali su Jon Barwise i John Etchemendy u Stanfordu, nazvan 'Tarski svijet'. Neovisno o tome, drugi tim na Sveučilištu u Omsku konstruirao je rusku verziju za uporabu u školama za nadarenu djecu.

U objavljenoj verziji svojih predavanja Johna Lockea na Oxfordu, Hintikka je 1973. postavila Dawkinsovo pitanje (vidi gore) za ove igre. Njegov je odgovor bio da treba paziti na Wittgensteinove jezične igre, a jezične igre za razumijevanje kvantifikata su one koje se vrte oko traženja i pronalaženja. U odgovarajućim logičkim igrama treba misliti o (postoji) kao Ja i (forall) kao neprijateljskoj prirodi kojoj se nikad ne može pouzdati u predstavljanje željenog predmeta; pa da bih bio siguran da mi je potreban, potrebna mi je dobitna strategija. Ova priča nikad nije bila vrlo uvjerljiva; motivacija prirode je nebitna i ništa u logičkoj igri ne odgovara traženju. Iz retrospektive je pomalo razočaravajuće što nitko nije napravio probleme da potraži bolju priču. Možda bi bilo korisnije razmišljati o pobjedničkoj strategiji za (postoji) u (G (phi)) kao svojevrsnom dokazu (u prikladnom infinitarnom sustavu) da je (phi) istina.

Kasnije je Jaakko Hintikka proširio ideje ovog odjeljka u dva smjera, naime semantiku prirodnog jezika i igre nesavršenih informacija (vidi sljedeći odjeljak). Naziv Game-Theoretic Semantics, ukratko, GTS, počeo se upotrebljavati za obojicu ova proširenja.

Igre opisane u ovom odjeljku gotovo se trivijalno prilagođavaju raznovrsnoj logici: na primjer, kvantifikator (forall x _ { sigma}), gdje je (x _ { sigma}) varijanta sorte (sigma), je uputa za igrača (forall) da odabere element sortiranja (sigma). To nam odmah daje odgovarajuće igre za logiku drugog reda, ako elemente strukture mislimo kao jednu vrstu, skupove elemenata kao drugu vrstu, binarne odnose kao treću i tako dalje. Iz toga slijedi da imamo i pravila rutine za većinu generaliziranih kvantifikatora; možemo ih pronaći tako što ćemo prvo prevesti generalizirane kvantifikatore u logiku drugog reda.

4. Semantičke igre s nesavršenim informacijama

U ovom i sljedećem odjeljku razmatramo neke prilagodbe semantičkih igara iz prethodnog odjeljka drugim logikama. U našem prvom primjeru logika (logika neovisnosti Hintikka i Sandu 1997, ili ukratko IF logika) stvorena je kako bi se uklopila u igru. Pogledajte članak o logici prilagođenoj neovisnosti i Mann, Sandu i Sevenster 2011 za potpunije objašnjenja ove logike.

Igre ovdje su iste kao i u prethodnom odjeljku, s tim što isključujemo pretpostavku da svaki igrač zna prethodnu povijest igre. Na primjer, možemo tražiti od igrača da odabere bez da znamo što je drugi igrač napravio u određenim ranijim potezima. Klasičan način da se to riješi unutar teorije igara je ograničenje na strategije igrača. Na primjer, možemo zahtijevati da strateška funkcija koja govori (postoji) što treba učiniti u određenom koraku, bude funkcija čija je domena obitelj mogućih izbora (forall) samo na njegovom prvom i drugom potezu; ovo je način izražavanja da (postoji) ne zna kako je (forall) odabrao u svom trećem i kasnijem potezu. Za igre s takvim ograničenjima na strateške funkcije kaže se da su nesavršene informacije,za razliku od igara savršenih informacija u prethodnom odjeljku.

Da bismo napravili logiku koja odgovara ovim igrama, koristimo isti jezik prvog reda kao u prethodnom odjeljku, osim što se nekim kvantifikatima (a možda i nekim veznicima) dodaje notacija kako bismo pokazali da Skolem funkcionira za ove kvantifikatore (ili poveznice) neovisne su o određenim varijablama. Na primjer rečenica

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

čita se kao: "Za svaki (x) postoji (y), ne ovisi o (x), tako da je (R (x, y))".

Tri su važna komentara o razlici između savršenih i nesavršenih informacija. Prvo je da teorem Gale-Stewart vrijedi samo za igre savršenih informacija. Pretpostavimo na primjer da (forall) i (postoji) igraju sljedeću igru. Prvo, (forall) bira jedan od brojeva 0 i 1. Zatim (postoji) bira jedan od ova dva broja. Igrač (postoji) pobjeđuje ako su dva odabrana broja ista, a u protivnom igrač (forall) pobjeđuje. Zahtijevamo da (postoji) kad odluči, ne zna što je odabrala (forall); pa će Skolemova funkcija za nju biti konstanta. (Ova igra odgovara gornjoj rečenici IF sa (R) koja se čita kao jednakost, u strukturi s domenom koja se sastoji od 0 i 1.) Jasno je da igrač (postoji) nema stalnu strategiju pobjedništva,a isto tako taj igrač (forall) uopće nema pobjedničku strategiju. Dakle, ova je igra neodređena, iako je njezina duljina samo 2.

Jedna od posljedica je da Hintikkino opravdanje za čitanje negacije kao dualisation ("igrači zamjenjuju mjesta"), u svojim igrama za logiku prvog reda, ne prelazi na logiku IF-a. Hintikkin odgovor je bio da je udvostručavanje bilo ispravno intuitivno značenje negacije čak iu slučaju prvog reda, pa nije potrebno nikakvo opravdanje.

Drugi komentar je da se već u igrama savršenih informacija može dogoditi da pobjedničke strategije ne koriste sve dostupne informacije. Na primjer, u igri sa savršenim informacijama, ako igrač (postoji) ima pobjedničku strategiju, tada ona također ima i dobitnu strategiju gdje strategije strategije ovise samo o prethodnim izborima (forall). To je zato što ona može rekonstruirati vlastite prethodne poteze pomoću svojih ranijih strateških funkcija.

Kad je Hintikka koristio Skolem funkcije kao strategije u svojim igrama za logiku prvog reda, učinio je da strategije za igrača ovise samo o prethodnim potezima drugog igrača. (Skolemska funkcija za (postoji) ovisi samo o univerzalno kvantificiranim varijablama.) Budući da su igre bile savršene informacije, tu nije bilo gubitaka, drugi komentar gore. Ali kad je prešao na logiku IF-a, zahtjev da strategije ovise samo o potezima drugog igrača doista je promijenio. Hodges 1997 je to pokazao revizijom notacije, tako da primjerice ((postoji y / x)) znači: Postoji (y) neovisno od (x), bez obzira na to koji je igrač izabrao (x)”.

Razmotrimo sada rečenicu

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

ponovo igra na strukturi s dva elementa 0 i 1. Igrač (postoji) može pobijediti na sljedeći način. Za (z) ona je odabrala isto što i igrač (forall) izabrao za (x); tada za (y) ona odabire isto što je odabrala za (z). Ova pobjednička strategija djeluje samo zato što se u ovoj igri (postoji) može odnositi na vlastite prethodne izbore. Ona ne bi imala pobjedničku strategiju ako je treći kvantifikator ((postoji y / xz)), opet zato što bi bilo koja Skolemova funkcija za ovaj kvantifikator morala biti konstantna. Način na koji (postoji) prenosi informacije sebi pozivajući se na svoj prethodni izbor primjer je signalizacije. John von Neumann i Oskar Morgenstern ilustrirali su to primjerom Bridgea, gdje se jedan igrač sastoji od dva partnera koji moraju dijeliti informacije koristeći svoje javne poteze kako bi signalizirali jedni drugima.

Treći komentar je da postoji dislokacija između intuitivne ideje o nesavršenim informacijama i teorijski definirane igre u smislu strategija. Intuitivno, nesavršeni podaci su činjenica o okolnostima u kojima se igra igra, a ne o strategijama. To je vrlo škakljiva stvar i nastavlja voditi do nesporazuma o IF-u i sličnim logikama. Uzmimo za primjer rečenicu

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

opet igra na strukturi s elementima 0 i 1. Intuitivno bi se moglo pomisliti da ako (postoji) na drugom kvantifikatoru ne zapamti ono što je odabrala na prvom, teško može imati pobjedničku strategiju. Ali u stvari, ona ima vrlo jednostavno: 'Uvijek izaberi 0'!

U usporedbi s logikom prvog reda, IF logici nedostaje komponenta koju semantika igre neće dostaviti. Semantika igre govori nam kada je rečenica istinita u strukturi. Ali ako uzmemo formulu s (n) slobodnim varijablama, što formula izražava o uređenim (n) - zbirkama elemenata strukture? U logici prvog reda to bi definiralo njihov skup, tj. Odnos (n) arija na strukturi; definicija Tarske istine objašnjava kako. Postoji li slična definicija za proizvoljne formule logike IF-a? Ispada da postoji nešto za malo drugačiju logiku koju je Hodges 1997. uveo, a ona vodi do definicije istine u Tarski za jezik te logike. Uz malo podešavanja, ova se definicija istine može prilagoditi i IF logici. Ali za obje ove nove logike postoji ulov:umjesto da kažemo kada dodjeljivanje elemenata slobodnim varijablama formula daje istinu, kažemo kada skup dodjeljivanja elemenata slobodnim varijablama formulu čini istinitom. Väänänen 2007 tu je ideju postavio kao osnova za niz novih logika za proučavanje pojma ovisnosti (vidi unos o logici ovisnosti). U tim se logikama semantika definira bez igara, iako originalna inspiracija dolazi iz djela Hintikka i Sandu.

U Väänänenovoj logici lako je vidjeti zašto su potrebni skupovi zadataka. On ima atomsku formulu koja izražava '(x) ovisi o (y)'. Kako to možemo protumačiti u strukturi, na primjer, strukturi prirodnih brojeva? Nema smisla pitati na primjer da li 8 ovisi o 37. Ali ako imamo skup X uređenih parova prirodnih brojeva, ima smisla pitati je li u X prvi član svakog para ovisan o drugi; odgovor Da bi značio da postoji funkcija (f) takva da svaki par ((a, b)) u X ima oblik ((f (b), b)).

5. Semantičke igre za drugu logiku

Sljedeće strukture stvaraju zanimljive igre. Struktura (A) sastoji se od skupa (S) elemenata (koje ćemo nazvati stanjima, dodajući da ih često nazivamo svjetovima), binarnog odnosa (R) na (S) (mi čitat će (R) kao strelicu) i obitelj (P_1, / ldots, P_n) podskupine (S). Dva igrača (forall) i (postoji) igraju igru G on (A), počevši od stanja (s) koje im je dano, čitanjem odgovarajuće logičke formule (phi) kao skup uputa za igru i za pobjedu.

Dakle, ako je (phi) (P_i), tada igrač (postoji) pobjeđuje odjednom ako je (s) u (P_i), a u protivnom igrač (forall) pobijedi odjednom. Formule (psi / klin / theta, / psi / vee / theta) i (neg / psi) ponašaju se kao u Hintikkinim igrama gore; na primjer, (psi / wedge / theta) upućuje igrača (forall) da odabere hoće li se igra nastaviti kao za (psi) ili za (theta). Ako je formula (phi) (Box / psi), tada igrač (forall) bira strelicu iz (s) u stanje (t) (tj. Stanje (t) tako da je par ((s, t)) u odnosu (R)), a igra tada prelazi iz stanja (t) u skladu s uputama (psi), Pravilo za (Diamond / psi) je isto, osim što igrač (postoji) odabire izbor. Napokon kažemo da je formula (phi) istina u s u A ako igrač (postoji) ima pobjedničku strategiju za ovu igru koja se temelji na (phi) i započinje s (s).

Te igre stoje prema modalnoj logici na gotovo isti način kao i Hintikkine igre prema logici prvog reda. Osobito su jedan način davanja semantike modalnoj logici, a slažu se s uobičajenom semantikom Kripkeove vrste. Naravno da postoji mnogo vrsta i generalizacija modalne logike (uključujući usko povezane logike poput vremenske, epistemičke i dinamičke logike), pa se odgovarajuće igre pojavljuju u mnogo različitih oblika. Jedan primjer interesa je računalno-teorijska logika Matthewa Hennessyja i Robina Milnera, koja se koristi za opisivanje ponašanja sustava; ovdje strelice dolaze u više boja, a pomicanje strelicom određene boje predstavlja izvođenje određene 'akcije' za promjenu stanja. Drugi primjer je snažniji modalni (mu) - račun Dextera Kozena, koji ima operatore sa fiksnom točkom;vidi 5. poglavlje Stirlinga 2001.

Jedna zanimljiva značajka ovih igara je da ako igrač ima dobitnu strategiju od neke pozicije, onda se ta strategija nikada ne mora odnositi na bilo što što se dogodilo ranije u igri. Nebitno je koji su odluke doneseni ranije, ili čak koliko je koraka odigrano. Tako imamo ono što računalni znanstvenici ponekad nazivaju pobjedničkom strategijom „bez pamćenja“.

U srodnoj 'logici igara', koju je predložio Rohit Parikh, igre koje nas premještaju između država su tema, a ne način davanja definicije istine. Ove igre imaju mnogo zanimljivih aspekata. U časopisu Studia Logica 2003. godine posvećen im je broj, koji su uredili Marc Pauly i Parikh.

Utjecaji ekonomije i informatike naveli su brojne logičare da koriste logiku za analizu donošenja odluka u uvjetima djelomičnog nepoznavanja. (Pogledajte na primjer članak o epiztemskoj logici.) Postoji nekoliko načina na koji se mogu prikazati stanja znanja. Jedan je uzeti ih kao države ili svjetove u onu vrstu modalne strukture koju smo spomenuli na početku ovog odjeljka. Drugi je korištenje IF logike ili njene varijante. Kako su ti pristupi povezani? Johan van Benthem 2006 iznosi neke misli i rezultate na ovom vrlo prirodnom pitanju. Pogledajte i radove Johana van Benthema, Kristera Segerberga, Erica Pacuita i K. Venkatesha i njihove reference, u dijelu IV „Logika, agencija i igre“Van Benthema, Gupte i Parikh 2011, te unos o logici za analizu igara za uzorak nedavnog rada na ovom području.

6. Igre unazad i naprijed

1930. Alfred Tarski formulirao je pojam da su dvije strukture (A) i (B) elementarno ekvivalentne, tj. Da su u (A) tačno iste rečenice istinite kao i u B (B)). Na konferenciji u Princetonu 1946. opisao je taj pojam i izrazio nadu da će biti moguće razviti njegovu teoriju koja bi bila "duboka koliko i pojmovi izomorfizma itd. Koji su sada u upotrebi" (Tarski 1946).

Jedan prirodni dio takve teorije bio bi čisto strukturalno nužan i dovoljan uvjet da dvije strukture budu elementarno ekvivalentne. Roland Fraïssé, francusko-alžirski, prvi je pronašao potreban i dovoljan uvjet. Nekoliko godina kasnije ponovno ga je otkrio kazahstanski logičar AD Taimanov, a poljski logičar Andrzej Ehrenfeucht preformulirao je u smislu igara. Igre su danas poznate kao Ehrenfeucht-Fraïssé igre, ili ponekad kao igre naprijed i nazad. Pokazale su se kao jedna od najsvestranijih ideja logike dvadesetog stoljeća. Plodno se prilagođavaju širokom rasponu logike i struktura.

U igri za napred i nazad nalaze se dvije strukture (A) i (B) te dva igrača koja se obično naziva Spoiler i Duplicator. (Imena su zbog Joela Spencera početkom devedesetih. U novije vrijeme Neil Immerman predložio je Samsona i Delila, koristeći iste inicijale; ovo mjesto postavlja Spoiler kao muški igrač (forall) i umnožak kao žensko).) Svaki se korak u igri sastoji od poteza Spoilera, nakon čega slijedi potez Duplicatora. Spoiler bira element jedne od dviju struktura, a Duplicator tada mora odabrati element druge strukture. Nakon (n) koraka odabrane su dvije sekvence, jedna iz (A) i jedna iz (B):

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

Ovaj je položaj dobitak za Spoiler ako i samo ako neka atomska formula (jednog od oblika '(R (v_0, / ldots, v_ {k-1}))' ili '(mathrm {F} (v_0, / ldots, v_ {k-1}) = v_k) 'ili' (v_0 = v_1) ', ili jednu od njih s različitim varijablama) zadovoljava ((a_0, / ldots, a_ { n-1})) u (A), ali ne i ((b_0, / ldots, b_ {n-1})) u (B) ili obrnuto. Uvjet da Duplicator pobijedi je različit u različitim oblicima igre. U najjednostavnijem obliku, (EF (A, B)), igra je dobitak za Duplicator ako i samo ako nijedan početni dio nije pobjeda za Spoiler (tj. Ona pobjeđuje ako nije izgubila nijednog konačna faza). Za svaki prirodni broj (m) postoji igra (EF_m (A, B)); u ovoj igri Duplikator pobjeđuje nakon (m) koraka pod uvjetom da još nije izgubio. Sve te igre određuje Teorem Gale-Stewart. Kaže se da su dvije strukture (A) i (B) jednake i obrnuto ekvivalentne ako Duplikator ima pobjedničku strategiju za (EF (A, B)) i m-ekvivalent ako ima dobitna strategija za (EF_m (A, B)).

Može se dokazati da ako su (A) i (B) jednake (m) - ekvivalentne za svaki prirodni broj (m), onda su one elementarno jednake. U stvari, ako Eloise ima pobjedničku strategiju (tau) u igri Hintikka G ((phi)) na (A), gdje mjesto gniježenja kvantifikatorskih opsega (phi) ima na većina m razina i Duplicator ima pobjedničku strategiju (varrho) u igri (EF_m (A, B)), dvije strategije (tau) i (varrho) mogu se sastaviti u dobitna strategija Eloise u G ((phi)) na (B). S druge strane, pobjednička strategija za Spoiler u (EF_m (A, B)) može se pretvoriti u rečenicu prvog reda koja je istinita u točno jednom od (A) i (B), i u kojem gniježđenje mjerila kvantifikatora ima najviše (m) razina. Dakle, imamo potreban i dovoljan uvjet za elementarnu ekvivalentnost, a uz to i malo više.

Ako su (A) i (B) jednaki i obrnuto, onda su oni elementarno ekvivalentni; ali zapravo se ispostavlja da je jednakovrijednost unatrag i naprijed jednaka elementarnoj ekvivalentnosti u infinitarnoj logici koja je mnogo izražajnija od logike prvog reda. Postoje mnoga prilagođavanja u igri koja daju druge vrste ekvivalencije. Na primjer, Barwise, Immerman i Bruno Poizat neovisno su opisali igru u kojoj su dva igrača točno (p) brojala svaki kamenčić; svaki igrač mora svoje izbore označiti šljunkom, a dva izbora u istom koraku moraju biti označena šljunkom koji nose isti broj. Kako igra nastavlja, igračima će ostati bez kamenčića, pa će morati ponovno koristiti šljunak koji je već korišten. Uvjet da Spoiler pobijedi na poziciji (i svim narednim pozicijama) isti je kao i prije, osim što se računaju samo elementi koji nose oznake na toj poziciji. Postojanje pobjedničke strategije za Duplicator u ovoj igri znači da se dvije strukture slažu za rečenice koje koriste najviše (p) varijabli (omogućujući tim varijablama da se javljaju bilo koji broj puta).

Teorija koja stoji iza igara naprijed i naprijed koristi vrlo malo pretpostavki o logici o kojoj je riječ. Kao rezultat, ove su igre jedna od rijetkih model-teoretskih tehnika koje se primjenjuju i na ograničene strukture, kao i na beskonačne, a to ih čini jednim od temelja teorijske računalne znanosti. Pomoću njih se može mjeriti ekspresivna snaga formalnih jezika, na primjer jezici upita baze podataka. Tipičan rezultat mogao bi reći, na primjer, da određeni jezik ne može razlikovati između "parnog" i "neparnog"; to bismo dokazali pronalaženjem, za svaku razinu (n) složenosti formula jezika, par konačnih struktura za koje Duplicator ima pobjedničku strategiju u igri unazad i nazad razine (n), ali jedna od struktura ima parni broj elemenata, a druga ima neparan broj. Semantičari prirodnih jezika našli su napredne igre korisnim za uspoređivanje ekspresivnih snaga generaliziranih kvantifikatora. (Pogledajte na primjer Peters i Westerståhl 2006, odjeljak IV.)

Postoji i vrsta back-up igre koja odgovara našoj gornjoj modalnoj semantiki na isti način kao što igre Ehrenfeucht-Fraïssé odgovaraju Hintikkinoj semantiki igara za logiku prvog reda. Igrači počinju sa stanjem (s) u strukturi (A) i stanjem (t) u strukturi (B). Spojler i duplikator kreću se naizmjenično, kao i prije. Svaki put kad se kreće, Spoiler odabire hoće li se kretati u (A) ili u (B), a potom se Duplicator mora kretati u drugoj strukturi. Pomak se uvijek vrši pomicanjem prema naprijed strelicom iz trenutnog stanja. Ako su između njih dva igrača tek prešla u stanje (s) ´ u (A) i stanje (t) ´ u (B), a neki predikat (P_i) drži se na samo jedan od (s) ´ i (t) ´, a Duplikator odjednom gubi. Također izgubi ako nema dostupnih strelica za kretanje;ali ako Spoiler utvrdi da nema raspoloživih strelica za njega u bilo kojoj strukturi, tada Duplicator pobjeđuje. Ako dva igrača igraju ovu igru s zadanim početnim stanjima (s) u (A) i (t) u (B), a obje strukture imaju samo konačno mnogo stanja, onda se može pokazati da je Duplicator ima dobitnu strategiju ako i samo ako su iste modalne rečenice istinite u (s) u (A) kao i istina kod (t) u (B).

Mnogo je uopćenja ovog rezultata, a neke od njih uključuju sljedeći pojam. Neka je (Z) binarni odnos koji odnosi stanja (A) na stanja (B). Zatim nazivamo (Z) bisimulaciju između (A) i (B) ako Duplikator može upotrijebiti (Z) kao nesposobnu strategiju za pobjedu u igri unazad i nazad između (A) i (B) gdje je prvi par poteza dva igrača za odabir početnog stanja. U računalnoj znanosti pojam bisimulacije ključan je za razumijevanje (A) i (B) kao sustava; ona izražava da dva sustava međusobno djeluju na svoj način, korak po korak. No, malo prije nego što su računalni znanstvenici uveli pojam, u osnovi se isti koncept pojavio u doktorskom radu Johanna van Benthema o semantika modalne logike (1976).

7. Ostale model-teoretske igre

Logične igre u ovom dijelu su matematički alati, ali imaju neke konceptualno zanimljive značajke.

7.1 Prisiljavanje igara

Igre prisiljavanja također su poznate teoretičarima opisnih skupova kao Banach-Mazur igre; pogledajte reference Kechrisa ili Oxtobyja u nastavku za više detalja o matematičkoj podlozi. Teoretičari modela koriste ih kao način izgradnje beskonačnih struktura s kontroliranim svojstvima. U najjednostavnijem slučaju (forall) i (postoji) igraju takozvanu Model Existing Game, gdje (postoji) tvrdi da fiksna rečenica (phi) ima model dok (forall) tvrdi da on može proizvesti kontradikciju iz (phi). Na početku je fiksno brojčano beskonačan skup (C) novih konstantnih simbola (a_0, a_1, a_2) itd. (postoji) brani disjunku odabirom jedne disjunkcije, a egzistencijalnu izjavu odabirom konstante iz (C) kao svjedoka. (forall) može izazvati veznik odabirom bilo kojeg veznika,i univerzalnu izjavu odabirom proizvoljnog svjedoka iz (C). (postoji) pobjeđuje ako se ne igraju suprotne atomske rečenice. (postoji) ima pobjedničku strategiju (svojstvo dosljednosti jedan je način opisivanja dobitne strategije) ako i samo ako (phi) ima model. S druge strane, ako (forall) ima pobjedničku strategiju, stablo (koje se može učiniti konačnim) svih igra protiv njegove pobjedničke strategije povezano je sa gentzen-ovim dokazom negacije negacije (phi), Ova metoda analize rečenica usko je povezana s Beth-ovom metodom semantičkih tablica i dijaloškom igrom (vidi odjeljak 8).ako (forall) ima pobjedničku strategiju, stablo (koje se može učiniti konačnim) svih igra protiv njegove pobjedničke strategije povezano je s gentzen-ovim dokazom negacije negacije (phi). Ova metoda analize rečenica usko je povezana s Beth-ovom metodom semantičkih tablica i dijaloškom igrom (vidi odjeljak 8).ako (forall) ima pobjedničku strategiju, stablo (koje se može učiniti konačnim) svih igra protiv njegove pobjedničke strategije povezano je s gentzen-ovim dokazom negacije negacije (phi). Ova metoda analize rečenica usko je povezana s Beth-ovom metodom semantičkih tablica i dijaloškom igrom (vidi odjeljak 8).

Da biste skicirali ideju opće igre prisiljavanja, zamislite da prilični beskonačni tim graditelja gradi kuću (A). Svaki graditelj mora izvršiti svoju zadaću: na primjer, ugraditi kadu ili pozaditi predsoblje. Svaki graditelj ima beskonačno puno šansi za ulazak na gradilište i dodavanje neke ograničene količine materijala u kuću; ovi su slotovi za graditelje međusobno isprepleteni tako da se cijeli proces odvija u nizu koraka prebrojenih prirodnim brojevima.

Da bismo pokazali da se kuća može graditi po narudžbi, moramo pokazati da svaki graditelj zasebno može izvršiti svoj zadani zadatak, bez obzira na to što rade drugi graditelji. Stoga zamislimo svakog graditelja kao igrača (postoji) u igri u kojoj su svi ostali igrači skupa kao (forall), i želimo dokazati da (postoji) ima pobjedničku strategiju za to igra. Kad smo to dokazali za svakog graditelja posebno, možemo ih zamisliti kako rade, svaki sa svojom pobjedničkom strategijom. Svi pobjeđuju u svojim igrama, a rezultat je jedna prekrasna kuća.

Tehnički gledano, elementi strukture (A) su unaprijed fiksirani, recimo kao (a_0, a_1, a_2) itd., Ali svojstva tih elemenata moraju se izmiriti igranjem. Svaki igrač kreće se bacanjem u skup atomskih ili negiranih atomskih izjava o elementima, samo pod uvjetom da skup koji se sastoji od svih dosad iznesenih izjava mora biti u skladu s fiksnim setom aksioma zapisanih prije igre. (Dakle, bacanje negativne atomske rečenice (neg / phi) ima za posljedicu sprečavanje bilo kojeg igrača u dodavanju (phi) u kasnijoj fazi.) Na kraju zajedničke igre, skup atomskih rečenica bačen ima kanonski model, a ovo je struktura (A); postoje načini da se osigura da je to model fiksnog skupa aksioma. Kaže se da je moguće svojstvo P od (A) izvršno ako građevinar kojem je dodijeljen zadatak istiniti P iz (A) ima pobjedničku strategiju. Središnja točka (u osnovi Ehrenfeuchta) jest da je spajanje neizmjerno beskonačnog skupa izvršnih svojstava ponovno izvršljivo.

Različite teorije Löwenheim-Skolema teorije modela mogu se dokazati korištenjem varijanti igre prisiljavanja. U tim varijantama ne konstruiramo model već podmodel zadanog modela. Započinjemo s velikim modelom (M) za rečenicu (ili brojajući niz rečenica) (phi). Zatim nabrajamo podformule (phi) i svaki igrač ima podformule sa slobodnom varijablom kojoj će prisustvovati. Zadatak igrača je osigurati da čim se u igri pojave parametri podformula, a u velikom modelu bude svjedok istine formule, igra se jedan takav svjedok. Kad je igra gotova, brojivi podmodel (M) izgrađen je na način da zadovoljava (phi).

Naziv 'forsiranje' dolazi od primjene povezanih ideja Paul Cohen za konstruiranje modela teorije skupova u ranim 1960-ima. Abraham Robinson je to prilagodio tako da napravi opću metodu za izgradnju brojajućih struktura, a Martin Ziegler je predstavio postavku igre. Kasnije su Robin Hirsch i Ian Hodkinson koristili povezane igre da bi riješili neka stara pitanja o algebrama relacija.

Igre prisiljavanja zdrav su primjer koji treba imati na umu dok razmišljate o Dawkinsovom pitanju. Podsjećaju nas da u logičnim igrama ne mora biti korisno razmišljati o igračima kako se međusobno suprotstavljaju.

7.2 Igre rezanja i izbora

U tradicionalnoj igri "cut-and-select" uzimate komad torte i razrežete ga na dva manja komada; onda odaberem jedan komad i pojedem ga, a drugi ostavljam za tebe. Ovaj postupak trebao bi izvršiti pritisak na vas da pošteno narežete tortu. Matematičari, ne shvaćajući sasvim dobro svrhu vježbe, inzistiraju na tome da je ponovite. Stoga te natjeram da odrežeš komad koji sam odabrao na dva, a zatim izaberem jedan od ta dva; onda opet odrežete ovaj komad i tako u nedogled. Neki još nebeski matematičari natjeraju vas da kolač narežete na razmjerno puno komada umjesto na dva.

Ove su igre važne u teoriji definicija. Pretpostavimo da imamo kolekciju (A) objekata i obitelj (S) svojstava; svako svojstvo reže (A) u skup onih objekata koji imaju svojstvo i skup onih koji to nemaju. Neka se (postoji) seče, počevši od čitavog skupa (A) i koristeći svojstvo u (S) kao nož; neka (forall) odabere jedan od dijelova (koji su podskupovi (A)) i vratite ga / \ / \ postoji) da se ponovo reže, koristeći još jednom svojstvo u (S); i tako dalje. Neka se (postoji) izgubi čim (forall) odabere prazan komad. Kažemo da ((A, S)) ima rang najviše (m) ako (forall) ima strategiju koja osigurava da će (postoji) izgubiti prije nje (m) - potez. Poredak ((A, S)) daje vrijedne podatke o obitelji podskupina (A) koje se mogu definirati svojstvima u (S).

Varijacije ove igre, koje omogućavaju da se komad razreže na beskonačno mnogo manjih komada, temeljne su u grani teorije modela koja se naziva teorija stabilnosti. Općenito govoreći, teorija je "dobra" u smislu teorije stabilnosti ako, kad god uzmemo model (A) teorije i (S) skup formula prvog reda u jednoj slobodnoj varijabli s parametrima iz (A), struktura ((A, S)) ima "mali" rang. Drugačija varijacija je zahtijevati da se u svakom koraku (postoji) podijeli na dva dijela koja su preživjela iz prethodnih koraka, a ona opet izgubi čim se prazni jedan od izrezanih fragmenata. (U ovoj verziji (forall) je suvišan.) S ovom se varijacijom rang ((A), S) naziva svojom dimenzijom Vapnik-Chervonenkis; ovaj se pojam koristi u teoriji računalnog učenja.

7.3 Igre na drvetu dviju funkcija nasljednika

Zamislite stablo koje je izgrađeno u razinama. Na donjoj razini nalazi se jedan korijenski čvor, ali iz njega izlaze lijeva i desna grana. Na sljedećoj razini gore postoje dva čvora, po jedan na svakoj grani, a iz svakog od tih čvorova izrastaju lijeva i desna grana. Dakle, na sljedećoj razini gore postoje četiri čvora, a opet se drvo grana u lijevo i desno na svaki od tih čvorova. Nastavak do beskonačnosti, ovo se stablo naziva stablo dviju nasljednih funkcija (naime lijevog nasljednika i desnog nasljednika). Uzevši čvorove kao elemente i uvodeći dva funkcijska simbola za lijevog i desnog nasljednika, imamo strukturu. Snažni teorem Michaela Rabina kaže da postoji algoritam koji će nam reći za svaku monadsku rečenicu drugog reda (phi) na jeziku prikladnom za ovu strukturu,je li (phi) istina u strukturi. ("Monadički drugi red" znači da je logika poput prvog reda, osim što možemo kvantificirati i na skupove elemenata, ali ne i preko binarnih odnosa na elementima.)

Rabin teorem ima bilo koji broj korisnih posljedica. Na primjer, Dov Gabbay je to iskoristio kako bi dokazao odlučnost nekih modalnih logika. Ali Rabin je dokaz, koristeći automate, bio notorno teško slijediti. Yuri Gurevich i Leo Harrington, te neovisno Andrei Muchnik, pronašli su mnogo jednostavnije dokaze u kojima je automat igrač u igri.

Rezultat Rabina jedan je od nekoliko utjecajnih rezultata koji povezuju igre s automatima. Drugi primjer su paritetne igre koje se koriste za provjeru svojstava modalnih sustava. Vidi primjerice Stirling (2001) Poglavlje 6; Bradfield i Stirling (2006) razgovaraju o paritetnim igrama za modalni (mu) - račun.

8. Igre dijaloga, komunikacije i dokazivanja

Nekoliko srednjovjekovnih tekstova opisuje oblik rasprave koji se naziva obligationes. Bila su dva protivnika, protivnici i tuženi. Na početku zasjedanja, osporavatelji bi se složili o „pozitumu“, obično lažnoj izjavi. Zadatak ispitanika bio je da daju racionalne odgovore na pitanja protivnika, pretpostavljajući istinitost položaja; prije svega morao je izbjegavati nepotrebno suprotstavljanje sebi. Zadatak protivnika bio je pokušati natjerati ispitanike na kontradikcije. Tako znamo općenito odgovor na Dawkinsovo pitanje, ali ne znamo pravila igre! Srednjovjekovni udžbenici opisuju nekoliko pravila koja bi sporni sudionici trebali slijediti. Ali ta pravila nisu propisana pravila igre; oni su smjernice koje udžbenici proizlaze iz principa valjanog rasuđivanja pomoću primjera.(Pavao iz Venecije opravdava jedno pravilo praksom "velikih logičara, filozofa, geometra i teologa".) Posebno je učitelj obligationes bio otvoren za otkrivanje novih pravila. Ova otvorenost podrazumijeva da obligationes nisu logične igre u našem smislu.

Ne slažu se svi s prethodnom rečenicom. Na primjer, Catarina Dutilh Novaes (2007, 6) iznosi detaljnu obranu mišljenja da obligationes predstavljaju "izvanredan slučaj konceptualne sličnosti srednjovjekovnog i modernog teorijskog okvira". Ali bez obzira na to gledište zauzeli smo, ove rasprave potaknule su jednu važnu liniju modernog istraživanja u logičkim igrama.

Zamislite (postoji) polaganje usmenog ispita iz teorije dokaza. Ispitivač joj daje rečenicu i poziva je da je počne dokazivati. Ako rečenica ima oblik

) phi / vee / psi)

tada ona ima pravo odabrati jednu od rečenica i reći 'OK, ja ću dokazati ovu'. (U stvari, ako je ispitivač intuicionist, on može inzistirati da ona odabere jednu od rečenica koju će dokazati.) S druge strane, ako je rečenica

) phi / klin / psi)

tada bi ispitivač, kao ispitivač, mogao sam odabrati jedan od veznika i pozvati je da dokaže tu. Ako zna dokazati veznik, onda sigurno zna kako dokazati veznik.

Slučaj (phi / rightarrow / psi) je malo suptilniji. Vjerojatno će htjeti početi pretpostavljanjem (phi) da bi zaključio (psi); ali postoji određeni rizik od zbrke jer su rečenice koje je dosad napisala sve stvari koje treba dokazati, a (phi) nije stvar koju treba dokazati. Ispitivač joj može pomoći rekavši 'Pretpostavit ću (phi), pa da vidimo možete li stići do (psi) odatle'. U ovom trenutku postoji šansa da vidi način dolaska do (psi) izvodeći kontradikciju iz (phi); pa ona može okrenuti tablice ispitivaču i pozvati ga da pokaže da je njegova pretpostavka konzistentna, s ciljem da dokaže da nije. Simetrija nije savršena: tražio ju je da pokaže da je rečenica svugdje istinita, dok ga ona poziva da pokaže da je negdje ta rečenica istinita. Ipak možemo vidjeti jednu vrstu dualnosti.

Ovakve ideje stoje iza dijalektičkih igara Paula Lorenzena. Pokazao je da se uz određenu količinu guranja i guranja može napisati pravila za igru koja ima svojstvo koje (postoji) ima dobitnu strategiju ako i samo ako rečenica s kojom je izložena na početku bude teorem intuicionističke logike. U gesti prema srednjovjekovnim raspravama nazvao je (postoji) predlagatelja, a drugog igrača protivnika. Gotovo kao u srednjovjekovnim obligationesima, Protivnica pobjeđuje dovodeći predlagatelja do točke u kojoj su joj jedini pokreti dostupni oštre samo-proturječnosti.

Lorenzen je tvrdio da su njegove igre opravdavale i intuicijsku i klasičnu logiku (ili su ga, prema njegovim riječima, učinile 'gerechtfertigt', Lorenzen (1961,196)). Nažalost, svako 'opravdanje' uključuje uvjerljiv odgovor na Dawkinsovo pitanje, a ovo Lorenzen nikad nije pružio. Na primjer, on je govorio o potezima kao "napadima", čak i kada (poput izbora ispitivača u (phi / wedge / psi) gore) izgledaju više kao pomoć nego kao neprijateljstvo.

Dijaloška logika ulaza daje cjelovitiji prikaz Lorenzenovih igara i niza novijih inačica. U svom sadašnjem obliku (siječanj 2013.) staje u stranu tvrdnje Lorenzena o opravdanju logike. Umjesto toga, igre opisuje kao pružanje semantike za logiku (točka s kojom bi se Lorenzen sigurno složio) i dodaje da za razumijevanje razlika između logike može biti korisno usporediti njihovu semantiku.

S ove točke gledišta, Lorenzenove igre predstavljaju važnu paradigmu onoga što su nedavni teoretičari dokaza nazvali semantikom dokaza. Semantika dokaza daje 'značenje' ne samo pojmu da je moguće dokazati, već i svakom zasebnom koraku u dokazivanju. Ona odgovara na pitanje "Što postižemo tako da napravimo ovaj poseban potez u dokazu?" Tijekom devedesetih brojni radnici na logičnom kraju informatike tražili su igre koje bi se mogle prilagoditi linearnoj logici i neke druge sustave dokaza na isti način kao što su Lorenzen-ove igre stajale prema intuicijističkoj logici. Andreas Blass, a potom i Samson Abramsky sa kolegama, dali su igre koje su odgovarale dijelovima linearne logike, ali u trenutku pisanja još nemamo savršenu podudarnost između igre i logike. Ovaj je primjer posebno zanimljiv jer bi odgovor na Dawkinsovo pitanje trebao dati intuitivno tumačenje zakona linearne logike, što je ovoj logici prijeko potrebno. Igre Abramskog i sur. ispričati priču o dva interaktivna sustava. No dok je počeo sa igrama u kojima se igrači pristojno izmjenjuju, Abramsky je kasnije dopustio igračima da djeluju 'distribuirano, asinkrono', obazirući se jedni na druge samo kad to žele. Te igre više nisu u uobičajenom formatu logičkih igara, a njihova interpretacija u stvarnom životu postavlja mnoštvo novih pitanja. No dok je počeo sa igrama u kojima se igrači pristojno izmjenjuju, Abramsky je kasnije dozvolio igračima da djeluju 'distribuirano, asinkrono', obazirući se jedni na druge samo kad to žele. Te igre više nisu u uobičajenom formatu logičkih igara, a njihova interpretacija u stvarnom životu postavlja mnoštvo novih pitanja. No dok je počeo sa igrama u kojima se igrači pristojno izmjenjuju, Abramsky je kasnije dopustio igračima da djeluju 'distribuirano, asinkrono', obazirući se jedni na druge samo kad to žele. Te igre više nisu u uobičajenom formatu logičkih igara, a njihova interpretacija u stvarnom životu postavlja mnoštvo novih pitanja.

Giorgi Japaridze je predložio „logiku obračunavanja“za proučavanje računanja. Njegova je sintaksa logike prvog reda s nekim dodatnim stavkama koje podsjećaju na linearnu logiku. Njegova je semantika u smislu semantičkih igara s nekim neobičnim značajkama. Primjerice, nije uvijek određeno koji igrač sljedeći korak čini. Pojam strateških funkcija više nije prikladan za opis igrača; umjesto toga Japaridze opisuje načine čitanja drugog igrača (igrača (postoji) u našoj notaciji) kao svojevrsni računalni stroj. Daljnje informacije nalaze se na njegovoj web stranici.

Druga skupina igara iste opće obitelji kao i Lorenzen-ove su dokazne igre Pavla Pudlaka 2000. Ovdje je protivnik (zvan Prover) u ulozi odvjetnika na sudu, koji zna da je predlagatelj (zvan protivnik) kriv za neki prijestup. Predlagatelj će inzistirati na tome da je nevin i spreman je govoriti lažima da se brani. Cilj protivnika je prisiliti predlagatelja na proturječenje nečemu što je predlagatelj zabilježio, kao što je već rekao; ali protivnik vodi evidenciju i (kao u šljunčanim igrama gore) ponekad mora izbaciti predmete iz zapisa zbog nedostatka prostora ili memorije. Važno pitanje nije da li protivnik ima pobjedničku strategiju (od početka se pretpostavlja da ga ima), već koliko memorije treba za njegov zapis. Te su igre korisni uređaj za prikazivanje gornjih i donjih granica duljine dokaza u različitim sustavima provjere.

Druga vrsta logičke igre koja dopušta laži je Ulamova igra s lažima. Ovdje jedan igrač misli na broj u određenom rasponu. Cilj drugog igrača je saznati koliki je taj broj, postavljanjem prvog igrača da / ne pitanja; ali prvom igraču je dopušteno da kaže neki fiksni broj laži u svojim odgovorima. Kao i u Pudlakovim igrama, za drugog igrača sigurno je dobitna strategija, ali pitanje je koliko ovaj igrač mora raditi kako bi pobijedio. Mjera ovo vrijeme nije prostor ili memorija, nego vrijeme: koliko pitanja mora postaviti? Cignoli i sur. 2000. poglavlje 5, ovu igru vezuje za višestruku logiku.

Da se na trenutak vratim Lorenzenu: nije uspio razlikovati različite stavove koje bi osoba mogla zauzeti u argumentima: navodeći, pretpostavljajući, ustupajući, pitajući, napadajući, počinjući sebe. Je li zaista moguće definirati sve te pojmove bez pretpostavke neke logike pitanje je rasprava. Ali nemajte to na umu; pročišćavanje Lorenzenovih igara moglo bi poslužiti kao pristup neformalnoj logici, a posebno istraživanju koje ima za cilj sistematizirati moguće strukture zdravih neformalnih rasprava. S ove strane vidi Walton i Krabbe 1995. Radovi u Bench-Caponu i Dunneu 2007. također su relevantni.

Bibliografija

Neki seminarski radovi Henkina i Lorenzena, kao i neki od niže citiranih radova nalaze se u zbirci Beskonačne metode (Zbornik radova sa Simpozija o osnovama matematike, Varšava, 2. - 9. rujna 1959.), Oxford: Pergamon Press, 1961.. Urednici su neimenovani.

Igre u povijesti logike

  • Dutilh Novaes, Catarina, 2007., Formiranje srednjovjekovnih logičkih teorija: Suppositio, Consequentiae i Obligationes, New York: Springer-Verlag.
  • Hamblin, Charles, 1970, Fallacies, London: Methuen.
  • Hilbert, David, 1967, "Die Grundlagen der Mathematik", preveden kao "Temelji matematike", u Jean van Heijenoort (ur.), Od Fregea do Gödela, Cambridge Mass.: Harvard University Press, str. 464–479.
  • Paul of Venice, Logica Magna II (8), Tractatus de Obligationibus, E. Jennifer Ashworth (ur.), New York: British Academy i Oxford University Press, 1988. godine.
  • Weyl, Hermann, 1925–7, „Die heutige Erkenntnislage in der Mathematik“, prevedeno kao „Aktuelna epistemološka situacija u matematici“u Paolu Mancosu, Od Brouwera do Hilberta: Rasprava o osnovama matematike 1920-ih, New York: Oxford University Press, 1988., str. 123–142.
  • Zermelo, Ernst, 1913, „Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels“, u EW Hobson i AEH Love (ur.), Zbornik radova Petog međunarodnog kongresa matematičara, svezak II, Cambridge: Cambridge University Press.

Igre za podučavanje logike

  • Barwise, Jon i John Etchemendy, 1995, Jezik logike prvog reda, uključujući Tarski svijet 3.0, Cambridge: Cambridge University Press.
  • Carroll, Lewis, 1887, Igra logike, London: Macmillan.
  • Dienes, Zoltan P. i EW Golding, 1966, Logika učenja, Logičke igre, Harlow: Udruženje za obrazovnu opskrbu.
  • Havas, Katalin, 1999, „Učenje razmišljanja: Logika za djecu“, u Zborniku dvadesetog svjetskog filozofskog kongresa (svezak 3: Filozofija obrazovanja), David M. Steiner (ur.), Bowling Green Ohio: Bowling Green State Sveučilišna filozofija, str. 11-19.
  • Nifo, Agostino, 1521, Dialectica Ludicra (Logika kao igra), Firenca: Bindonis.
  • Weng, Jui-Feng, sa Shian-Shyong Tsengom i Tsung-Ju Lee, 2010, „Podučavanje logičke logike kroz podešavanje pravila igre“, IEEE transakcije, tehnologije učenja, 3 (4): 319–328. [Koristi igre Pac-Man za podučavanje logičke logike za učenike srednjih škola.]

Logičke igre

  • Gale, David i FM Stewart, 1953, "Beskonačne igre sa savršenim informacijama", u prilozima teoriji igara II (Anali matematičkih studija 28), HW Kuhn i AW Tucker (ur.), Princeton: Princeton University Press, pp 245–266.
  • Kechris, Alexander S., 1995, Klasična teorija opisnih skupova, New York: Springer-Verlag.
  • Marion, Mathieu, 2009., "Zašto igrati logične igre?", U Ondrej Majer, Ahti-Veikko Pietarinen i Tero Tulenheimo, igre: Objedinjavajuća logika, jezik i filozofija, New York: Springer-Verlag, str. 3-25,
  • Osbourne, Martin J. i Ariel Rubinstein, 1994., Tečaj teorije igara, Cambridge: MIT Press.
  • Väänänen, Jouko, 2011, Modeli i igre, Cambridge: Cambridge University Press.
  • van Benthem, Johan, 2011, Logička dinamika informacija i interakcija, Cambridge: Cambridge University Press, 2011.
  • –––, 2014., Logika u igrama, Cambridge, MA: MIT Press.

Semantičke igre za klasičnu logiku

  • Henkin, Leon, 1961., "Neke napomene o beskonačno dugim formulama", u Infinitističkim metodama, op. cit., str. 167–183.
  • Hintikka, Jaakko, 1973., Logika, Jezik-igre i informacije: Kantovske teme iz filozofije logike, Oxford: Clarendon Press.
  • Hintikka, Jaakko, 1996., Principles of Mathematics Revisited, New York: Cambridge University Press. [Vidi stranice 40, 82 o odabiru aksioma.]
  • Hodges, Wilfrid, 2001, "Elementarna predikatna logika 25: Skolemske funkcije", u Dov Gabbay, i Franz Guenthner (ur.), Priručnik filozofske logike I, drugo izdanje, Dordrecht: Kluwer, str. 86–91. [Dokaz ekvivalencije igre i Tarski semantike.]
  • Kolaitis, Ph. G., 1985., "Kvantifikacija igre", u J. Barwise i S. Feferman (ur.), Model-Theoretic Logics, New York: Springer-Verlag, str. 365-421.
  • Peirce, Charles Sanders, 1898., Reasoning and the Logic of Things: The Cambridge Conferences Lectures iz 1898, ed. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.

Semantičke igre sa nesavršenim informacijama

  • Hintikka, Jaakko i Gabriel Sandu, 1997, „Igra-teorijska semantika“, u Johan van Benthem i Alice ter Meulen (ur.), Priručnik za logiku i jezik, Amsterdam: Elsevier, str. 361–410.
  • Hodges, Wilfrid, 1997., „Sastavna semantika za jezik nesavršenih informacija“, Logički časopis IGPL, 5: 539–563.
  • Janssen, Theo MV i Francien Dechesne, 2006., "Signalizacija: lukav posao", u J. van Benthem i sur. (ur.), Doba alternativne logike: Procjena filozofije logike i matematike danas, Dordrecht: Kluwer, str. 223–242.
  • Mann, Allen L., Gabriel Sandu i Merlin Sevenster, 2011, Logika prilagođena neovisnosti: Teoretski pristup igri (Notebook Lecture London Series 386), Cambridge: Cambridge University Press.
  • von Neumann, John i Oskar Morgenstern, 1944., Teorija igara i ekonomsko ponašanje, Princeton: Princeton University Press.
  • Väänänen, Jouko, 2007, Logika ovisnosti: Novi pristup logici neovisnosti o neovisnosti, Cambridge: Cambridge University Press.

Semantičke igre za drugu logiku

  • Bradfield, Julian i Colin Stirling, 2006., "Modal mu-izračuna", P. Blackburn i sur. (ur.), Priručnik modalne logike, Amsterdam: Elsevier, str. 721–756.
  • Dekker, Paul i Marc Pauly (ur.), 2002, časopis za logiku, jezik i informacije, 11 (3): 287–387. [Posebno izdanje o logici i igrama.]
  • Hennessy, Matthew i Robin Milner, 1985., “Algebrski zakoni za indeterminizam i istodobnost”, Journal of the ACM, 32: 137–162.
  • Parikh, Rohit, 1985., "Logika igara i njezine primjene", u Mareku Karpinskom i Janu van Leeuwenu (ur.), "Teme iz teorije računanja", Anali diskretne matematike, 24: 111–140.
  • Pauly, Marc i Rohit Parikh (ur.), 2003., Studia Logica, 72 (2): 163–256 [Posebno izdanje o Game Logic.]
  • Stirling, Colin, 2001, modalna i vremenska svojstva procesa, New York: Springer-Verlag.
  • van Benthem, Johan, 2006, "Epistemička logika Igara IF-a", u knjizi Randall Auxier i Lewis Hahn (ur.), Filozofija Jaakka Hintikka, Chicago: Otvoreni sud, str. 481–513.
  • van Benthem, Johan s Amitabha Gupta i Rohit Parikh, 2011, Dokaz, računarstvo i agencija, Dordrecht: Springer-Verlag.

Igre unazad i naprijed

  • Blackburn, Patrick s Maarten de Rijke i Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press.
  • Doets, Kees, 1996, teorija osnovnog modela, Stanford: CSLI Publications i FoLLI.
  • Ebbinghaus, Heinz-Dieter i Jörg Flum, 1999., Teorija konačnih modela, drugo izdanje, New York: Springer.
  • Ehrenfeucht, Andrzej, 1961., „Primjena igara na problem cjelovitosti formaliziranih teorija“, Fundamenta Mathematicae, 49: 129–141.
  • Grädel, Erich s Phokion G. Kolaitisom, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema i Scott Weinstein, 2007., Teorija konačnih modela, Berlin: Springer-Verlag.
  • Libkin, Leonid, 2004., Elementi teorije konačnih modela, Berlin, Springer-Verlag.
  • Otto, Martin, 1997, Bounded Variable Logics and Counting-A Study u konačnim modelima (Bilješke predavanja u logici, 9), Berlin: Springer-Verlag.
  • Peters, Stanley i Dag Westerståhl, 2006, Kvantifikatori u jeziku i logici, Oxford: Clarendon Press.
  • Tarski, Alfred, 1946., „Govor na dvjestogodišnjoj konferenciji o problemima matematike na Sveučilištu Princeton (17-19. Prosinca 1946.)“, Hourya Sinaceur (ur.), Bilten simboličke logike, 6 (2000): 1–44.
  • van Benthem, Johan, 2001, "Teorija dopisivanja", u Dov Gabbay i Franz Guenthner (ur.), Priručnik filozofske logike III, drugo izdanje, Dordrecht: Kluwer.

Ostale Teoretske igre

  • Anthony, Martin i Norman Biggs, 1992, teorija računalnog učenja, Cambridge: Cambridge University Press. [Za dimenziju Vapnik-Chervonenkis.]
  • Gurevich, Yuri i Leo Harrington, 1984., „Drveće, automati i igre“, u HR Lewis (ur.), Zbornik radova sa simpozija ACM o teoriji računanja, San Francisco: ACM, str. 171–182.
  • Hirsch, Robin i Ian Hodkinson, 2002, odnosne algebre po igrama, New York: North-Holland.
  • Hodges, Wilfrid, 1985, Građenje modela prema igrama, Cambridge: Cambridge University Press.
  • Hodges, Wilfrid, 1993., Teorija modela, Cambridge: Cambridge University Press.
  • Oxtoby, JC, 1971., Mjera i kategorija, New York: Springer-Verlag.
  • Ziegler, Martin, 1980, "Algebraisch abgeschlossene Gruppen", u SI Adian i sur. (ur.), Problemi s riječima II: Knjiga Oxford, Amsterdam: Sjeverna Holandija, str. 449–576.

Igre dijaloga, komunikacije i dokazivanja

  • Abramsky, Samson i Radha Jagadeesan, 1994., „Igre i potpuna cjelovitost multiplikativne linearne logike“, Journal of Symbolic Logic, 59: 543–574.
  • Abramsky, Samson i Paul-André Melliès, 1999, "Istodobne igre i potpuna cjelovitost", Zbornik radova Četrnaestog međunarodnog simpozija o logici u računarstvu, Computer Science Press IEEE, str. 431–442.
  • Bench-Capon, TJM i Paul E. Dunne, 2007, „Argumentacija u umjetnoj inteligenciji“, Umjetna inteligencija, 171: 619–641. [Uvod u bogatu zbirku radova na istu temu, na stranicama 642–937.]
  • Blass, Andreas, 1992., “Semantika igara za linearnu logiku”, Anali čiste i primijenjene logike, 56: 183-220.
  • Cignoli, Roberto LO, Itala ML D'Ottaviano i Daniele Mundici, 2000, Algebraic Temelji za višestruko vrednovanje, Dordrecht: Kluwer.
  • Felscher, Walter, 2001., "Dijalozi kao temelj intuicijske logike", u Dov Gabbay i Franz Guenthner (ur.), Priručnik filozofske logike V, 2. izdanje, Dordrecht: Kluwer.
  • Hodges, Wilfrid i Erik CW Krabbe, 2001, "Temelji dijaloga", Zbornik Aristotelovskog društva (dopunski svezak), 75: 17–49.
  • Japaridze, Giorgi, 2003, „Uvod u logiku izračunavanja“, Anali čiste i primijenjene logike, 123: 1–99.
  • Lorenzen, Paul, 1961. "Ein dialogisches Konstruktivitätskriterium", u Infinitističkim metodama, op. cit., 1961, str. 193–200.
  • Pudlak, Pavel, 2000, „Dokazi kao igre“, Američki matematički mjesečnik, 107 (6): 541–550.
  • Walton, Douglas N. i Erik CW Krabbe, 1995, Zanimanje u dijalogu: osnovni pojmovi međuljudskog razmišljanja, Albany: Državno sveučilište New York Press.

Akademske alate

sep man ikona
sep man ikona
Kako navesti ovaj unos.
sep man ikona
sep man ikona
Pregledajte PDF verziju ovog unosa na Društvu prijatelja SEP-a.
inpho ikona
inpho ikona
Pogledajte ovu temu unosa na projektu Internet Filozofska ontologija (InPhO).
ikona papira phil
ikona papira phil
Poboljšana bibliografija za ovaj unos na PhilPapersu, s vezama na njegovu bazu podataka.

Ostali internetski resursi

Preporučeno: