Logika I Gry

Spisu treści:

Logika I Gry
Logika I Gry

Wideo: Logika I Gry

Wideo: Logika I Gry
Wideo: Логика возрождений в ШУТЕРАХ 2024, Marzec
Anonim

Nawigacja wejścia

  • Treść wpisu
  • Bibliografia
  • Narzędzia akademickie
  • Podgląd PDF znajomych
  • Informacje o autorze i cytacie
  • Powrót do góry

Logika i gry

Po raz pierwszy opublikowano pt. 27 lipca 2001; rewizja merytoryczna pt 16.08.2019

Gry między dwoma graczami, w których jeden gracz wygrywa, a jeden przegrywa, stały się znanym narzędziem w wielu gałęziach logiki drugiej połowy XX wieku. Ważnymi przykładami są gry semantyczne używane do definiowania prawdy, gry tam iz powrotem używane do porównywania struktur oraz gry dialogowe do wyrażania (i być może wyjaśniania) formalnych dowodów.

  • 1. Gry w historii logiki
  • 2. Gry logiczne
  • 3. Gry semantyczne w logice klasycznej
  • 4. Gry semantyczne z niedoskonałą informacją
  • 5. Gry semantyczne dla innych logik
  • 6. Gry wstecz i do przodu
  • 7. Inne gry teoretyczne

    • 7.1 Gry wymuszające
    • 7.2 Gry typu „wytnij i wybierz”
    • 7.3 Gry na drzewie dwóch następnych funkcji
  • 8. Gry dialogu, komunikacji i dowodu
  • Bibliografia

    • Gry w historii logiki
    • Gry do nauczania logiki
    • Gry logiczne
    • Gry semantyczne w logice klasycznej
    • Gry semantyczne z niedoskonałymi informacjami
    • Gry semantyczne dla innych logik
    • Gry w przód i tył
    • Inne gry oparte na teorii modeli
    • Gry dialogu, komunikacji i dowodu
  • Narzędzia akademickie
  • Inne zasoby internetowe
  • Powiązane wpisy

1. Gry w historii logiki

Powiązania między logiką a grami mają długą historię. Jeśli ktoś myśli o debacie jako o rodzaju grze, to Arystoteles już to skojarzył; jego pisma o sylogizmie są ściśle powiązane z jego studiami nad celami i regułami debatowania. Punkt widzenia Arystotelesa przetrwał do potocznej średniowiecznej nazwy logiki: dialektyki. W połowie XX wieku Charles Hamblin ożywił związek między dialogiem a regułami zdrowego rozumowania, wkrótce po tym, jak Paul Lorenzen połączył dialog z konstruktywnymi podstawami logiki.

Gry i nauczanie są ściśle powiązane. Pisarze w całym okresie średniowiecza mówili o dialogach jako o sposobie „nauczania” lub „testowania” rozsądnego rozumowania. Mamy co najmniej dwa podręczniki logiki z początku XVI wieku, które przedstawiają ją jako grę dla indywidualnego ucznia, a The Game of Logic (1887) Lewisa Carrolla jest kolejnym przykładem z tego samego gatunku. Istnieje również wiele współczesnych przykładów, chociaż prawdopodobnie nie było wystarczającej ciągłości, aby uzasadnić mówienie o tradycji nauczania logiki przez gry.

Matematyczna teoria gier powstała na początku XX wieku. Chociaż żadne powiązania matematyczne z logiką nie pojawiły się aż do lat 50. XX wieku, uderzające jest, jak wielu z wczesnych pionierów teorii gier jest również znanych ze swojego wkładu w logikę: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo i inni. W 1953 roku David Gale i Frank Stewart stworzyli owocne połączenia między teorią mnogości i grami. Wkrótce potem Leon Henkin zasugerował sposób wykorzystania gier do nadania semantyki dla języków nieskończonych.

Pierwsza połowa XX wieku była epoką rosnącego rygoru i profesjonalizmu w logice i większości logików tamtego okresu używanie gier w logice prawdopodobnie wydawałoby się niepoważne. Intuicjonista LEJ Brouwer wyraził taką postawę, gdy oskarżył swoich przeciwników o spowodowanie, że matematyka „przekształciła się w grę” (jak cytował go David Hilbert w 1927 roku, cytowany w van Heijenoort 1967). Hermann Weyl (cytowany w Mancosu 1998) użył pojęcia gier do wyjaśnienia metamatematyki Hilberta: dowody matematyczne przebiegają jak rozgrywki bezsensownej gry, ale możemy stać poza grą i zadawać na jej temat znaczące pytania. Gry językowe Wittgensteina wywołały niewielką reakcję logików. Ale w drugiej połowie wieku środek ciężkości badań logicznych przeniósł się od podstaw do techniki,a od około 1960 roku gry coraz częściej pojawiały się w artykułach logicznych.

Na początku XXI wieku powszechnie akceptowano pogląd, że gry i logika idą w parze. Rezultatem było ogromne rozpowszechnienie nowych kombinacji logiki i gier, szczególnie w obszarach, w których stosuje się logikę. Wiele z tych nowych osiągnięć powstało pierwotnie w wyniku pracy w czystej logice, chociaż dzisiaj kierują się własnymi programami. Jedną z takich dziedzin jest teoria argumentacji, w której gry stanowią narzędzie analizy struktury debat.

Poniżej skoncentrujemy się na tych grach, które są najbardziej kojarzone z czystą logiką.

2. Gry logiczne

Z punktu widzenia teorii gier główne gry, które badają logicy, wcale nie są typowe. Zwykle obejmują tylko dwóch graczy, często mają nieskończoną długość, jedyne wyniki to wygrana i przegrana, a działania lub wyniki nie są związane z żadnym prawdopodobieństwem. Podstawowe elementy gry logicznej są następujące.

Jest dwóch graczy. Ogólnie możemy je nazwać (forall) i (istnieje). Wymowy „Abelard” i „Eloise” sięgają połowy lat 80. i pożytecznie utwierdzają graczy jako mężczyzn i kobiet, ułatwiając odniesienie: jej ruch, jego ruch. Inne nazwy są powszechnie używane przez graczy w poszczególnych typach gier logicznych.

Gracze grają wybierając elementy zbioru (Omega), zwanego domeną gry. Wybierając, tworzą sekwencję

[a_0, a_1, a_2, / ldots)

elementów (Omega). Nieskończone sekwencje elementów (Omega) nazywane są zabawami. Skończone sekwencje elementów (Omega) nazywane są pozycjami; zapisują, gdzie mogło dojść do przedstawienia w określonym czasie. Funkcja (tau) (funkcja tury lub funkcja gracza) zajmuje każdą pozycję (mathbf {a}) do (istnieje) lub (forall); jeśli (tau (mathbf {a}) = / istnieje), oznacza to, że kiedy gra osiągnęła (mathbf {a}), gracz (istnieje) dokonuje następnego wyboru (i podobnie z (forall)). Zasady gry definiują dwa zestawy (W _ { forall}) i (W _ { istnieje}) składające się z pozycji i rozgrywek, z następującymi właściwościami: jeśli pozycja (mathbf {a}) znajduje się w (W _ { forall}), to tak samo jak dowolna pozycja gry lub dłuższa, która zaczyna się od (mathbf {a}) (i podobnie z (W _ { istnieje}));i nie ma luzu w obu (W _ { forall}) i (W _ { istnieje}). Mówimy, że gracz (forall) wygrywa grę (mathbf {b}), a (mathbf {b}) jest wygraną dla (forall), jeśli (mathbf {b}) jest w (W _ { forall}); jeśli jakaś pozycja (mathbf {a}) będąca początkowym segmentem (mathbf {b}) znajduje się w (W _ { forall}), to mówimy, że gracz (forall) wygrywa już na (mathbf {a}). (I podobnie z (istnieje) i (W _ { istnieje}).) Podsumowując, gra logiczna to czteroosobowa krotka ((Omega, / tau), (W_ { forall}), (W _ { exist})) z właśnie opisanymi właściwościami.wtedy mówimy, że gracz (forall) wygrywa już na (mathbf {a}). (I podobnie z (istnieje) i (W _ { istnieje}).) Podsumowując, gra logiczna to czteroosobowa krotka ((Omega, / tau), (W_ { forall}), (W _ { exist})) z właśnie opisanymi właściwościami.wtedy mówimy, że gracz (forall) wygrywa już na (mathbf {a}). (I podobnie z (istnieje) i (W _ { istnieje}).) Podsumowując, gra logiczna to czteroosobowa krotka ((Omega, / tau), (W_ { forall}), (W _ { exist})) z właśnie opisanymi właściwościami.

Mówimy, że gra logiczna jest całkowita, jeśli każda gra jest w (W _ { forall}) lub (W _ { istnieje}), więc nie ma remisów. O ile nie zrobi się wyraźnego wyjątku, zakłada się, że gry logiczne są totalne. (Nie myl bycia totalnym ze znacznie silniejszą właściwością bycia zdeterminowanym - patrz poniżej).

Jedynie ze względów matematycznych powyższa definicja przewiduje, że gra będzie trwała w nieskończoność, nawet jeśli gracz wygrał na jakiejś skończonej pozycji; nie interesuje się niczym, co dzieje się po wygranej gracza. Wiele gier logicznych ma tę właściwość, że w każdej grze jeden z graczy wygrał już na określonej skończonej pozycji; gry tego rodzaju są dobrze uzasadnione. Jeszcze silniejszym warunkiem jest to, że istnieje pewna liczba skończona (n) taka, że w każdej grze jeden z graczy wygrał już na (n) - tej pozycji; w tym przypadku mówimy, że gra ma skończoną długość.

Strategia dla gracza to zestaw reguł, które dokładnie opisują, w jaki sposób ten gracz powinien wybrać, w zależności od tego, jak obaj gracze wybrali we wcześniejszych ruchach. Matematycznie strategia dla (forall) składa się z funkcji, która przyjmuje każdą pozycję (mathbf {a}) z (tau (mathbf {a}) = / forall) do elementu (b) z (Omega); traktujemy to jako instrukcję dla (forall), aby wybrać (b), gdy gra osiągnie pozycję (mathbf {a}). (Podobnie ze strategią dla (istnieje).) Mówi się, że strategia gracza wygrywa, jeśli ten gracz wygrywa każdą grę, w której używa strategii, niezależnie od tego, co robi inny gracz. Co najwyżej jeden z graczy ma zwycięską strategię (ponieważ w przeciwnym razie gracze mogliby rozgrywać swoje zwycięskie strategie przeciwko sobie i obaj wygrywaliby,zaprzeczając, że (W _ { forall}) i (W _ { istnieje}) nie mają wspólnych odtworzeń). Czasami spotyka się sytuacje, w których wydaje się, że dwóch graczy ma wygrywające strategie (na przykład w grach forsujących poniżej), ale bliższa analiza pokazuje, że obaj gracze faktycznie grają w różne gry.

Mówi się, że gra jest rozstrzygnięta, jeśli jeden z graczy ma zwycięską strategię. Istnieje wiele przykładów gier, które nie są zdeterminowane, jak wykazali Gale i Stewart w 1953 roku, używając aksjomatu wyboru. To odkrycie doprowadziło do ważnych zastosowań pojęcia determinacji w podstawach teorii mnogości (patrz wpis o dużych kardynałach i determinacji). Gale i Stewart udowodnili również ważne twierdzenie, które nosi ich imię: każda dobrze ugruntowana gra jest zdeterminowana. Wynika z tego, że każda gra o skończonej długości jest zdeterminowana - fakt znany już Zermelo w 1913 r. (Bardziej precyzyjnym stwierdzeniem twierdzenia Gale'a-Stewarta jest to. Mówi się, że gra (G) jest zamknięta, jeśli (istnieje) wygrywa każdą grę (G), w której nie przegrała już na żadnej skończonej pozycji. Twierdzenie mówi, że każda zamknięta gra jest zdeterminowana. Dowód twierdzenia jest w zasadzie łatwy: nazwijmy pozycję wygrywającą dla (forall), jeśli ma on zwycięską strategię zaczynającą się od tej pozycji. Załóżmy, że (forall) nie ma strategii wygrywającej w grze, to znaczy na początku pozycja nie wygrywa dla (forall). Jeśli pierwszy ruch to ruch (forall), po jego posunięciu pozycja nadal nie wygrywa dla niego. Jeśli pierwszy ruch to ruch (istnieje), musi mieć ruch, po którym pozycja nadal nie wygrywa dla (forall), w przeciwnym razie poprzednia pozycja byłaby wygrana za (forall). Gra toczy się w ten sposób nieskończenie wiele ruchów przez pozycje, które nie wygrywają dla (forall). Ponieważ gra jest zamknięta, (istnieje) wygrywa). Załóżmy, że (forall) nie ma strategii wygrywającej w grze, to znaczy na początku pozycja nie wygrywa dla (forall). Jeśli pierwszy ruch to ruch (forall), po jego posunięciu pozycja nadal nie wygrywa dla niego. Jeśli pierwszy ruch to ruch (istnieje), musi mieć ruch, po którym pozycja nadal nie wygrywa dla (forall), w przeciwnym razie poprzednia pozycja byłaby wygrana za (forall). Gra toczy się w ten sposób nieskończenie wiele ruchów przez pozycje, które nie wygrywają dla (forall). Ponieważ gra jest zamknięta, (istnieje) wygrywa). Załóżmy, że (forall) nie ma strategii wygrywającej w grze, to znaczy na początku pozycja nie wygrywa dla (forall). Jeśli pierwszy ruch to ruch (forall), po jego posunięciu pozycja nadal nie wygrywa dla niego. Jeśli pierwszy ruch to ruch (istnieje), musi mieć ruch, po którym pozycja nadal nie wygrywa dla (forall), w przeciwnym razie poprzednia pozycja byłaby wygrana za (forall). Gra toczy się w ten sposób nieskończenie wiele ruchów przez pozycje, które nie wygrywają dla (forall). Ponieważ gra jest zamknięta, (istnieje) wygrywa). Jeśli pierwszy ruch to ruch (istnieje), musi mieć ruch, po którym pozycja nadal nie wygrywa dla (forall), w przeciwnym razie poprzednia pozycja byłaby wygrana za (forall). Gra toczy się w ten sposób nieskończenie wiele ruchów przez pozycje, które nie wygrywają dla (forall). Ponieważ gra jest zamknięta, (istnieje) wygrywa). Jeśli pierwszy ruch to ruch (istnieje), musi mieć ruch, po którym pozycja nadal nie wygrywa dla (forall), w przeciwnym razie poprzednia pozycja byłaby wygrana za (forall). Gra toczy się w ten sposób nieskończenie wiele ruchów przez pozycje, które nie wygrywają dla (forall). Ponieważ gra jest zamknięta, (istnieje) wygrywa).

Podobnie jak w klasycznej teorii gier, powyższa definicja gier logicznych służy jako koń na ubrania, na którym możemy zawiesić inne koncepcje. Na przykład często istnieją prawa, które opisują, jakie elementy (Omega) są dostępne dla gracza do wyboru w danym ruchu. Ściśle rzecz biorąc, to udoskonalenie jest niepotrzebne, ponieważ nie ma to wpływu na zwycięskie strategie, jeśli zamiast tego zdecydujemy, że gracz, który łamie prawo, natychmiast przegrywa; ale w przypadku wielu gier ten sposób patrzenia na nie wydaje się nienaturalny. Poniżej zobaczymy kilka innych dodatkowych funkcji, które można dodać do gier.

Powyższe definicje gry i strategii były czysto matematyczne. Pominęli więc prawdopodobnie najważniejszą cechę gier, czyli to, że ludzie w nie grają (przynajmniej metaforycznie). Gracze dążą do zwycięstwa, a studiując otwarte dla nich strategie, badamy, jakie zachowanie jest racjonalne dla osoby mającej określony cel. W większości gier jest kilku graczy, więc możemy zbadać, jaka jest racjonalna reakcja na czyjeś zachowanie. Ograniczając ruchy graczy i możliwe strategie, możemy badać ograniczoną racjonalność, w której agent musi podejmować racjonalne decyzje w warunkach ograniczonej ilości informacji, pamięci lub czasu.

Krótko mówiąc, gry służą do modelowania racjonalności i ograniczonej racjonalności. Jest to niezależne od jakiegokolwiek związku z logiką. Jednak niektóre logiki zostały zaprojektowane do badania aspektów racjonalnego zachowania, aw ostatnich latach coraz częściej łączy się te logiki z odpowiednimi grami. Zobacz rozdział 5 („Gry semantyczne dla innych logiki”) i jego bibliografię.

Ale do niedawna gry logiczne wiązały się z racjonalnym zachowaniem w zupełnie inny sposób. Pozornie logika, o której mowa, nie miała bezpośredniego związku z zachowaniem. Jednak logicy i matematycy zauważyli, że niektóre idee można uczynić bardziej intuicyjnymi, gdyby były powiązane z możliwymi celami. Na przykład w wielu zastosowaniach gier logicznych głównym pojęciem jest zwycięska strategia gracza (istnieje). Często te strategie (lub ich istnienie) okazują się równoważne z czymś o logicznym znaczeniu, które można zdefiniować bez użycia gier - na przykład dowodu. Uważa się jednak, że gry dają lepszą definicję, ponieważ całkiem dosłownie dostarczają pewnej motywacji: (istnieje) próbuje wygrać.

Rodzi to pytanie mało interesujące matematycznie, ale powinno dotyczyć filozofów posługujących się grami logicznymi. Jeśli chcemy, aby motywacja (istnieje) w grze (G) miała jakąkolwiek wartość wyjaśniającą, to musimy zrozumieć, co jest osiągane, jeśli (istnieje) wygrywa. W szczególności powinniśmy być w stanie opowiedzieć realistyczną historię o sytuacji, w której jakiś agent o nazwie (istnieje) próbuje zrobić coś zrozumiałego, a zrobienie tego jest tym samym, co wygrana w grze. Jak powiedział Richard Dawkins, podnosząc odpowiednie pytanie dotyczące ewolucyjnych gier Maynarda Smitha,

Cały cel naszych poszukiwań… to znalezienie odpowiedniego aktora, który odegra główną rolę w naszych metaforach celu. Chcemy… powiedzieć: „To dla dobra…”. Naszym celem w tym rozdziale jest znalezienie właściwego sposobu dokończenia tego zdania. (The Extended Phenotype, Oxford University Press, Oxford 1982, strona 91).

Na przyszłość nazwijmy to pytaniem Dawkinsa. W wielu rodzajach gier logicznych odpowiedź na to pytanie jest zdecydowanie trudniejsza, niż sądzili pionierzy tych gier. (Marion 2009 omawia dalej kwestię Dawkinsa.)

3. Gry semantyczne w logice klasycznej

Na początku lat trzydziestych Alfred Tarski zaproponował definicję prawdy. Jego definicja obejmowała warunek konieczny i wystarczający, aby zdanie w języku typowej teorii formalnej było prawdziwe; jego warunek konieczny i dostateczny posługiwał się jedynie pojęciami z teorii składni i teorii mnogości, łącznie z prymitywnymi pojęciami omawianej teorii formalnej. W rzeczywistości Tarski zdefiniował bardziej ogólną relację „formuła (phi (x_1, / ldots, x_n)) jest prawdziwa dla elementów (a_1, / ldots, a_n)”; Prawdziwość zdania to szczególny przypadek, w którym (n = 0). Na przykład pytanie, czy

`` Dla wszystkich (x) jest (y) takie, że R ((x, y)) 'jest prawdziwe

sprowadza się do pytania, czy następujące blokady:

Dla każdego obiektu (a) zdanie „Jest (y) takie, że R ((a, y))” jest prawdziwe.

To z kolei sprowadza się do:

Dla każdego obiektu (a) istnieje obiekt (b) taki, że zdanie „R ((a, b))” jest prawdziwe.

W tym przykładzie to tyle, ile zajmie definicja prawdy Tarskiego.

Pod koniec lat pięćdziesiątych Leon Henkin zauważył, że możemy intuicyjnie zrozumieć niektóre zdania, których nie da się ująć w definicji Tarskiego. Weźmy na przykład nieskończenie długie zdanie

Dla wszystkich (x_0) jest (y_0) takie, że dla wszystkich (x_1) jest (y_1) takie, że… R ((x_0, y_0, x_1, y_1, / ldots)).

Podejście Tarskiego zawodzi, ponieważ ciąg kwantyfikatorów na początku jest nieskończony i nigdy nie doszlibyśmy do końca ich usuwania. Zamiast tego, zasugerował Henkin, powinniśmy rozważyć grę, w której osoba (forall) wybiera obiekt (a_0) dla (x_0), a następnie druga osoba (istnieje) wybiera obiekt (b_0) dla (y_0), wtedy (forall) wybiera (a_1) dla (x_1, / istnieje) wybiera (b_1) dla (y_1) i tak dalej. Zagranie w tę grę jest wygraną dla (istnieje) wtedy i tylko wtedy, gdy nieskończone zdanie atomowe

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

jest prawdziwy. Oryginalne zdanie jest prawdziwe wtedy i tylko wtedy, gdy gracz (istnieje) ma zwycięską strategię dla tej gry. Ściśle Henkin używał gry tylko jako metafory, a warunek prawdy, który zaproponował, był taki, że skolemizowana wersja zdania jest prawdziwa, tj. Że istnieją funkcje (f_0, f_1, / ldots) takie, że dla każdego wyboru (a_0, a_1, a_2) itd. mamy

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

Ale warunek ten natychmiast przekłada się na język gier; funkcje Skolema (f_0) itp. definiują zwycięską strategię dla (istnieje), mówiąc jej, jak wybrać w świetle wcześniejszych wyborów (forall). (Jakiś czas później wyszło na jaw, że CS Peirce zasugerował już wyjaśnienie różnicy między „każdym” a „niektórymi” w kategoriach tego, kto wybiera przedmiot; na przykład w swoim drugim wykładzie na konferencji w Cambridge w 1898 r.)

Wkrótce po pracy Henkina Jaakko Hintikka dodał, że ten sam pomysł dotyczy koniunkcji i rozłączeń. Możemy traktować koniunkcję '(phi / wedge / psi)' jako stwierdzenie wyrażone ilościowo, wyrażające 'Każde ze zdań (phi, / psi) zachowuje', więc powinno być dla gracza (forall), aby wybrać jedno ze zdań. Jak to ujął Hintikka, aby zagrać w grę (G (phi / wedge / psi), / forall) wybiera, czy gra ma przebiegać jako (G (phi)), czy (G (psi)). Podobnie dysjunkcje stają się egzystencjalnie wyrażonymi ilościowo stwierdzeniami dotyczącymi zestawów zdań i oznaczają ruchy, w których gracz (istnieje) wybiera, jak ma przebiegać gra. Aby wprowadzić kwantyfikatory w ten sam styl, zaproponował, aby gra (G (forall x / phi (x))) przebiegała w ten sposób: gracz (forall) wybiera obiekt i podaje nazwę (a) dla tego,a gra toczy się jako (G (phi (a))). (I podobnie z kwantyfikatorami egzystencjalnymi, z tym że (istnieje) wybiera). Hintikka również przedstawił genialną sugestię wprowadzenia negacji. Każda gra G ma podwójną grę, która jest taka sama jak G, z wyjątkiem tego, że gracze (forall) i (exist) są transponowani zarówno w zasadach gry, jak i zasadach wygrywania. Gra (G (neg / phi)) jest podwójną liczbą (G (phi)).

Można udowodnić, że dla każdego zdania pierwszego rzędu (phi), interpretowanego w ustalonej strukturze (A), gracz (istnieje) ma zwycięską strategię w grze Hintikki (G (phi)) wtedy i tylko wtedy, gdy (phi) jest prawdziwe w (A) w sensie Tarskiego. Ciekawe są dwie cechy tego dowodu. Po pierwsze, jeśli (phi) jest jakimkolwiek zdaniem pierwszego rzędu, to gra (G (phi)) ma skończoną długość, a więc twierdzenie Gale'a-Stewarta mówi nam, że jest określona. Wnioskujemy, że (istnieje) ma zwycięską strategię dokładnie w jednym z (G (phi)) i jej podwójnej; więc ma zwycięską strategię w (G (neg / phi)) wtedy i tylko wtedy, gdy nie ma jej w (G (phi)). To eliminuje negację. Po drugie, jeśli (istnieje) ma zwycięską strategię dla każdej gry (G (phi (a))), to po wybraniu jednej takiej strategii (f_a) dla każdej (a),może połączyć je w jedną zwycięską strategię dla (G (forall x / phi (x))) (mianowicie: 'Poczekaj i zobacz, jaki element (a / forall) wybierze, a następnie zagraj (f_a) '). Dba o klauzulę dotyczącą uniwersalnych kwantyfikatorów; ale argument posługuje się aksjomatem wyboru i faktycznie nietrudno zauważyć, że stwierdzenie, że definicje prawdy Hintikki i Tarskiego są równoważne, samo w sobie jest równoważne z aksjomatem wyboru (biorąc pod uwagę inne aksjomaty teorii mnogości Zermelo-Fraenkla). W istocie nietrudno zauważyć, że stwierdzenie, iż definicje prawdy Hintikki i Tarskiego są równoważne, samo w sobie jest równoważne z aksjomatem wyboru (biorąc pod uwagę inne aksjomaty teorii mnogości Zermelo-Fraenkla). W istocie nietrudno zauważyć, że stwierdzenie, iż definicje prawdy Hintikki i Tarskiego są równoważne, samo w sobie jest równoważne z aksjomatem wyboru (biorąc pod uwagę inne aksjomaty teorii mnogości Zermelo-Fraenkla).

Zaskakujące jest to, że mamy tutaj dwie teorie, kiedy zdanie jest prawdziwe, a teorie nie są równoważne, jeśli aksjomat wyboru zawodzi. W rzeczywistości powód nie jest zbyt głęboki. Aksjomat wyboru jest potrzebny nie dlatego, że definicja Hintikki używa gier, ale dlatego, że zakłada, że strategie są deterministyczne, tj. Są to funkcje jednowartościowe, które nie dają użytkownikowi możliwości wyboru. Bardziej naturalnym sposobem przełożenia definicji Tarskiego na terminy związane z grą jest użycie niedeterministycznych strategii, czasami nazywanych quasi-strategiami (szczegóły w Kolaitis 1985). (Jednak Hintikka 1996 podkreśla, że prawidłowa eksplikacja `` prawdy '' to ta, w której stosuje się strategie deterministyczne, a fakt ten potwierdza aksjomat wyboru).

Komputerowe implementacje tych gier Hintikki okazały się bardzo skutecznym sposobem uczenia znaczeń zdań pierwszego rzędu. Jeden taki pakiet został zaprojektowany przez Jona Barwise i Johna Etchemendy w Stanford i nosi nazwę „Tarski's World”. Niezależnie inny zespół z Uniwersytetu w Omsku skonstruował rosyjską wersję do użytku w szkołach dla uzdolnionych dzieci.

W opublikowanej wersji swoich wykładów Johna Locke'a w Oksfordzie Hintikka w 1973 roku podniósł kwestię Dawkinsa (patrz wyżej) w odniesieniu do tych gier. Jego odpowiedź brzmiała, że należy spojrzeć na gry językowe Wittgensteina, a gry językowe w celu zrozumienia kwantyfikatorów to te, które obracają się wokół poszukiwania i znajdowania. W odpowiednich grach logicznych należy myśleć o (istnieje) jako o sobie i (forall) jako o wrogiej Naturze, na której nigdy nie można polegać, przedstawiając przedmiot, który chcę; więc aby mieć pewność, że ją znajdę, potrzebuję zwycięskiej strategii. Ta historia nigdy nie była zbyt przekonująca; motywacja Natury jest nieistotna i nic w grze logicznej nie odpowiada poszukiwaniom. Z perspektywy czasu jest trochę rozczarowujące, że nikt nie zadał sobie trudu, aby znaleźć lepszą historię. Bardziej pomocne może być pomyślenie o zwycięskiej strategii dla (istnieje) w (G (phi)) jako o rodzaju dowodu (w odpowiednim systemie nieskończonym), że (phi) jest prawdą.

Później Jaakko Hintikka rozszerzył idee tej sekcji w dwóch kierunkach, a mianowicie do semantyki języka naturalnego i gier z niedoskonałą informacją (patrz następny rozdział). Nazwa Game-Theoretic Semantics, w skrócie GTS, została użyta do określenia obu tych rozszerzeń.

Gry opisane w tej sekcji prawie w trywialny sposób dostosowują się do logiki z wieloma posortowanymi wartościami: na przykład kwantyfikator (forall x _ { sigma}), gdzie (x _ { sigma}) jest zmienną typu (sigma), jest instrukcją dla gracza (forall), aby wybrał element sortowania (sigma). To natychmiast daje nam odpowiednie gry dla logiki drugiego rzędu, jeśli myślimy o elementach struktury jako jednym rodzaju, o zbiorach elementów jako o drugim rodzaju, o relacjach binarnych jako o trzecim i tak dalej. Wynika z tego, że mamy dość rutynowo reguły gry również dla większości uogólnionych kwantyfikatorów; możemy je znaleźć, najpierw tłumacząc uogólnione kwantyfikatory na logikę drugiego rzędu.

4. Gry semantyczne z niedoskonałą informacją

W tej i następnej sekcji przyjrzymy się pewnym adaptacjom gier semantycznych z poprzedniej sekcji do innych logik. W naszym pierwszym przykładzie logika (logika sprzyjająca niezależności Hintikki i Sandu 1997, lub w skrócie logika IF) została stworzona w celu dopasowania do gry. Zobacz wpis o logice przyjaznej niepodległości oraz Mann, Sandu i Sevenster 2011, aby zapoznać się z pełniejszymi opisami tej logiki.

Rozgrywki tutaj są takie same, jak w poprzedniej sekcji, z tym, że rezygnujemy z założenia, że każdy gracz zna wcześniejszą historię rozgrywki. Na przykład możemy wymagać, aby gracz dokonał wyboru, nie wiedząc, jakich wyborów dokonał inny gracz w niektórych wcześniejszych ruchach. Klasyczny sposób radzenia sobie z tym w teorii gier polega na ograniczaniu strategii graczy. Na przykład możemy wymagać, aby funkcja strategii mówiąca (istnieje) co robić w danym kroku, była funkcją, której dziedziną jest rodzina możliwych wyborów (forall) tylko w jego pierwszym i drugim ruchu; jest to sposób wyrażenia, że (istnieje) nie wie, jak (forall) wybrał swój trzeci i późniejszy ruch. Gry z tego rodzaju ograniczeniami w zakresie funkcji strategicznych są uważane za niepełne informacje,w przeciwieństwie do gier doskonałej informacji z poprzedniej sekcji.

Aby stworzyć logikę pasującą do tych gier, używamy tego samego języka pierwszego rzędu, co w poprzedniej sekcji, z wyjątkiem tego, że do niektórych kwantyfikatorów (i być może także niektórych łączników) dodaje się notację, aby pokazać, że Skolem działa dla tych kwantyfikatorów (lub łączniki) są niezależne od pewnych zmiennych. Na przykład zdanie

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

brzmi: „Dla każdego (x) istnieje (y), niezależne od (x), takie, że (R (x, y))”.

Istnieją trzy ważne uwagi dotyczące rozróżnienia między informacjami doskonałymi a niedoskonałymi. Po pierwsze, twierdzenie Gale'a-Stewarta odnosi się tylko do gier z doskonałą informacją. Załóżmy na przykład, że (forall) i (exist) grają w następującą grę. Najpierw (forall) wybiera jedną z liczb 0 i 1. Następnie (istnieje) wybiera jedną z tych dwóch liczb. Gracz (istnieje) wygrywa, jeśli dwie wybrane liczby są takie same, w przeciwnym razie gracz (forall) wygrywa. Wymagamy, aby (istnieje), kiedy dokonuje wyboru, nie wie, co (forall) wybrała; więc funkcja Skolem będzie dla niej stała. (Ta gra odpowiada powyższemu zdaniu IF z (R) odczytywanym jako równość, w strukturze z domeną składającą się z 0 i 1.) Jest jasne, że gracz (istnieje) nie ma stałej strategii wygrywającej,a także ten gracz (forall) w ogóle nie ma zwycięskiej strategii. Więc ta gra jest nieokreślona, chociaż jej długość wynosi tylko 2.

Jednym z następstw jest to, że uzasadnienie Hintikki dla odczytywania negacji jako dualizacji („gracze zamieniają się miejscami”), w jego grach dla logiki pierwszego rzędu, nie przenosi się do logiki IF. Hintikka odpowiedział, że dualizacja jest właściwym intuicyjnym znaczeniem negacji nawet w przypadku pierwszego rzędu, więc nie jest potrzebne uzasadnienie.

Druga uwaga dotyczy tego, że już w grach z doskonałą informacją może się zdarzyć, że zwycięskie strategie nie wykorzystają wszystkich dostępnych informacji. Na przykład w grze pełnej informacji, jeśli gracz (istnieje) ma strategię wygrywającą, to ma ona również strategię wygrywającą, w której funkcje strategii zależą tylko od wcześniejszych wyborów (forall). Dzieje się tak, ponieważ może zrekonstruować swoje własne poprzednie ruchy, używając swoich wcześniejszych funkcji strategicznych.

Kiedy Hintikka używał funkcji Skolem jako strategii w swoich grach dla logiki pierwszego rzędu, sprawił, że strategie gracza zależały tylko od poprzednich ruchów drugiego gracza. (Funkcja Skolema dla (istnieje) zależy tylko od uniwersalnych zmiennych ilościowych.) Ponieważ gry były grami doskonałej informacji, nie było w tym żadnej straty, zgodnie z drugim komentarzem powyżej. Ale kiedy przeszedł do logiki IF, wymóg, aby strategie zależały tylko od ruchów drugiego gracza, naprawdę zrobił różnicę. Hodges 1997 pokazał to, poprawiając notację, tak że na przykład ((istnieje y / x)) oznacza: „Istnieje (y) niezależnie od (x), niezależnie od tego, który gracz wybrał (x))”.

Rozważmy teraz zdanie

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

zagrał ponownie na strukturze z dwoma elementami 0 i 1. Gracz (istnieje) może wygrać w następujący sposób. Dla (z) wybiera to samo, co gracz (forall) wybrał dla (x); następnie dla (y) wybiera to samo, co wybrała dla (z). Ta zwycięska strategia działa tylko dlatego, że w tej grze (istnieje) może odwołać się do swoich wcześniejszych wyborów. Nie miałaby strategii wygrywającej, gdyby trzeci kwantyfikator był ((istnieje y / xz)), ponownie, ponieważ każda funkcja Skolema dla tego kwantyfikatora musiałaby być stała. Sposób, w jaki (istnieje) przekazuje sobie informacje, odwołując się do jej wcześniejszego wyboru, jest przykładem zjawiska sygnalizacji. John von Neumann i Oskar Morgenstern zilustrowali to na przykładzie Bridge, gdzie jeden gracz składa się z dwóch partnerów, którzy muszą dzielić się informacjami, wykorzystując swoje publiczne ruchy do sygnalizowania sobie nawzajem.

Trzecia uwaga dotyczy dyslokacji między intuicyjną ideą niedoskonałej informacji a jej teoretyczną definicją w kategoriach strategii. Intuicyjnie, niedoskonałe informacje są faktem o okolicznościach, w których toczy się gra, a nie o strategiach. Jest to bardzo trudna sprawa i nadal prowadzi do nieporozumień dotyczących IF i podobnej logiki. Weźmy na przykład zdanie

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

ponownie zagrał na strukturze z elementami 0 i 1. Intuicyjnie można by pomyśleć, że jeśli (istnieje) nie może zapamiętać przy drugim kwantyfikatorze tego, co wybrała za pierwszym, to z trudem może mieć zwycięską strategię. Ale w rzeczywistości ma bardzo proste: „Zawsze wybieraj 0”!

W porównaniu z logiką pierwszego rzędu w logice IF brakuje komponentu, którego semantyka gry nie zapewni. Semantyka gry mówi nam, kiedy zdanie jest prawdziwe w strukturze. Ale jeśli weźmiemy formułę z (n) wolnymi zmiennymi, co ta formuła wyraża na temat uporządkowanych (n) - krotek elementów struktury? W logice pierwszego rzędu zdefiniowałaby ich zbiór, tj. Relację (n) - ary na strukturze; definicja prawdy Tarskiego wyjaśnia, jak to zrobić. Czy istnieje podobna definicja dowolnych formuł logiki IF? Okazuje się, że istnieje jedna dla nieco innej logiki wprowadzonej przez Hodgesa 1997, co prowadzi do definicji prawdy w stylu Tarskiego dla języka tej logiki. Po niewielkim dostosowaniu tę definicję prawdy można dopasować również do logiki IF. Ale w przypadku obu tych nowych logik jest pewien haczyk:zamiast mówić, że przypisanie elementów do wolnych zmiennych sprawia, że formuła jest prawdziwa, mówimy, że zestaw przypisań elementów do wolnych zmiennych sprawia, że formuła jest prawdziwa. Väänänen 2007 uczynił ten pomysł podstawą dla szeregu nowych logik do badania pojęcia zależności (patrz wpis dotyczący logiki zależności). W tych logikach semantyka jest definiowana bez gier, chociaż oryginalna inspiracja pochodzi z twórczości Hintikki i Sandu.

W logice Väänänena łatwo zrozumieć, dlaczego potrzebne są zestawy zadań. Ma formułę atomową wyrażającą „(x) jest zależne od (y)”. Jak możemy to zinterpretować w strukturze, na przykład w strukturze liczb naturalnych? W ogóle nie ma sensu pytać, na przykład, czy 8 jest zależne od 37. Ale jeśli mamy zbiór X uporządkowanych par liczb naturalnych, warto zapytać, czy w X pierwszy członek każdej pary jest zależny od druga; odpowiedź Tak oznaczałaby, że istnieje funkcja (f) taka, że każda para ((a, b)) w X ma postać ((f (b), b)).

5. Gry semantyczne dla innych logik

Następujące struktury dają początek ciekawym grom. Struktura (A) składa się ze zbioru (S) elementów (które nazwiemy stanami, dodając, że często nazywa się je światami), relacji binarnej (R) na (S) (my oznacza (R) jako strzałkę) i rodzinę (P_1, / ldots, P_n) podzbiorów (S). Obaj gracze (forall) i (exist) grają w grę G na (A), zaczynając od stanu (s), który jest im dany, czytając odpowiednią formułę logiczną (phi) jako zestaw instrukcji do gry i do wygrywania.

Zatem jeśli (phi) to (P_i), to gracz (istnieje) wygrywa od razu, jeśli (s) jest w (P_i), w przeciwnym razie gracz (forall) wygrywa od razu. Formuły (psi / wedge / theta, / psi / vee / theta) i (neg / psi) zachowują się tak jak w powyższych grach Hintikki; na przykład (psi / wedge / theta) instruuje gracza (forall), aby wybrać, czy gra będzie kontynuowana jak w przypadku (psi) lub (theta). Jeśli formuła (phi) to (Box / psi), to gracz (forall) wybiera strzałkę od (s) do stanu (t) (tj. Stanu (t) taki, że para ((s, t)) jest w relacji (R)), a gra następnie przechodzi ze stanu (t) zgodnie z instrukcją (psi). Zasada dla (Diament / psi) jest taka sama, z tym że gracz (istnieje) dokonuje wyboru. Na koniec mówimy, że formuła (phi) jest prawdziwa przy s w A, jeśli gracz (istnieje) ma zwycięską strategię dla tej gry opartą na (phi) i zaczynającą się od (s).

Te gry są zgodne z logiką modalną w bardzo podobny sposób, jak gry Hintikki są zgodne z logiką pierwszego rzędu. W szczególności są one jednym ze sposobów nadania semantyki logiki modalnej i zgadzają się ze zwykłą semantyką typu Kripkego. Oczywiście istnieje wiele typów i uogólnień logiki modalnej (w tym logiki blisko spokrewnione, takie jak logika czasowa, epistemiczna i dynamiczna), a zatem odpowiadające im gry występują w wielu różnych formach. Jednym z interesujących przykładów jest logika komputerowo-teoretyczna Matthew Hennessy'ego i Robina Milnera, używana do opisu zachowania systemów; tutaj strzałki są w więcej niż jednym kolorze, a poruszanie się po strzałce o określonym kolorze oznacza wykonanie określonej „czynności” w celu zmiany stanu. Innym przykładem jest potężniejszy rachunek modalny (mu) - Dextera Kozena, który ma operatory punktów stałych;patrz Rozdział 5 Stirling 2001.

Interesującą cechą tych gier jest to, że jeśli gracz ma strategię wygrywającą od jakiejś pozycji w górę, to strategia ta nigdy nie musi odnosić się do niczego, co wydarzyło się wcześniej w grze. Nie ma znaczenia, jakich wyborów dokonano wcześniej, ani nawet ile kroków zostało rozegranych. Mamy więc coś, co informatycy nazywają czasami strategią zwycięstwa „bez pamięci”.

W pokrewnej „logice gier”, zaproponowanej przez Rohita Parikha, gry, które przenoszą nas między stanami, są tematem, a nie sposobem na określenie prawdy. Te gry mają wiele interesujących aspektów. W 2003 r. Czasopismo Studia Logica opublikowało poświęcony im numer pod redakcją Marca Pauly'ego i Parikha.

Wpływy ekonomii i informatyki skłoniły wielu logików do stosowania logiki do analizy procesu podejmowania decyzji w warunkach częściowej ignorancji. (Zobacz na przykład artykuł o logice epistemicznej). Istnieje kilka sposobów przedstawiania stanów wiedzy. Jednym z nich jest traktowanie ich jako stanów lub światów w rodzaju struktury modalnej, o której wspomnieliśmy na początku tego rozdziału. Innym jest użycie logiki IF lub jej wariantu. Jaki jest związek między tymi podejściami? Johan van Benthem 2006 przedstawia kilka przemyśleń i wyników dotyczących tego bardzo naturalnego pytania. Zobacz także artykuły Johana van Benthema, Kristera Segerberga, Erica Pacuita i K. Venkatesha oraz ich odniesienia w części IV „Logika, agencja i gry” Van Benthem, Gupta i Parikh 2011 oraz wpis dotyczący logiki do analizy gier dla próbka ostatnich prac w tej dziedzinie.

6. Gry wstecz i do przodu

W 1930 roku Alfred Tarski sformułował pojęcie dwóch struktur (A) i (B), które są elementarnie równoważne, tj. Dokładnie takie same zdania pierwszego rzędu są prawdziwe w (A), jak w (B)). Na konferencji w Princeton w 1946 r. Opisał to pojęcie i wyraził nadzieję, że uda się rozwinąć jego teorię, która byłaby „tak głęboka, jak pojęcia izomorfizmu itp., Które są obecnie używane” (Tarski 1946).

Naturalną częścią takiej teorii byłby czysto strukturalny warunek konieczny i wystarczający, aby dwie struktury były elementarnie równoważne. Roland Fraïssé, Francuz-Algierczyk, jako pierwszy znalazł przydatny warunek konieczny i wystarczający. Kilka lat później został ponownie odkryty przez kazachstańskiego logika AD Taimanova, a pod kątem gier został przeformułowany przez polskiego logika Andrzeja Ehrenfeuchta. Gry są teraz znane jako gry Ehrenfeucht-Fraïssé, a czasami jako gry tam iz powrotem. Okazały się jednym z najbardziej wszechstronnych pomysłów w logice XX wieku. Skutecznie dostosowują się do szerokiej gamy logiki i struktur.

W grze w tę iz powrotem istnieją dwie struktury (A) i (B) oraz dwóch graczy, którzy są powszechnie nazywani Spoiler i Duplicator. (Nazwiska pochodzą od Joela Spencera na początku lat 90. Niedawno Neil Immerman zasugerował Samsona i Delilah, używając tych samych inicjałów; to umieszcza Spoilera jako męskiego gracza (forall) i Duplicator jako kobietę (istnieje).) Każdy krok w grze składa się z ruchu Spoilera, po którym następuje ruch Powielacza. Spoiler wybiera element jednej z dwóch struktur, a Duplicator musi wtedy wybrać element drugiej konstrukcji. Tak więc po (n) krokach wybrano dwie sekwencje, jedną z (A) i jedną z (B):

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

Ta pozycja jest wygrana dla Spoilera wtedy i tylko wtedy, gdy jakaś formuła atomowa (jednej z form '(R (v_0, / ldots, v_ {k-1}))' lub '(mathrm {F} (v_0, / ldots, v_ {k-1}) = v_k) 'lub' (v_0 = v_1) 'lub jeden z nich z różnymi zmiennymi) spełnia ((a_0, / ldots, a_ { n-1})) w (A), ale nie przez ((b_0, / ldots, b_ {n-1})) w (B) lub odwrotnie. Warunek zwycięstwa Duplicatora jest różny w różnych formach gry. Mówiąc najprościej, (EF (A, B)), zagranie jest wygraną dla Duplicatora wtedy i tylko wtedy, gdy żadna jego początkowa część nie jest wygraną dla Spoilera (tj. Wygrywa, jeśli nie przegrała przez żadną etap skończony). Dla każdej liczby naturalnej (m) istnieje gra (EF_m (A, B)); w tej grze Duplicator wygrywa po (m) krokach, pod warunkiem, że jeszcze nie przegrała. Wszystkie te gry są określone przez twierdzenie Gale'a-Stewarta. O dwóch strukturach (A) i (B) mówi się, że są odpowiednikami w przód iw tył, jeśli Duplicator ma zwycięską strategię dla (EF (A, B)) i m-odpowiednik, jeśli ma zwycięska strategia dla (EF_m (A, B)).

Można udowodnić, że jeśli (A) i (B) są (m) - równoważne dla każdej liczby naturalnej (m), to są one elementarnie równoważne. W rzeczywistości, jeśli Eloise ma zwycięską strategię (tau) w grze Hintikka G ((phi)) na (A), gdzie zagnieżdżenie zakresów kwantyfikatora (phi) ma większość m poziomów, a Duplicator ma zwycięską strategię (varrho) w grze (EF_m (A, B)), dwie strategie (tau) i (varrho) można ułożyć w zwycięska strategia Eloise w G ((phi)) na (B). Z drugiej strony zwycięską strategię dla Spoilera w (EF_m (A, B)) można przekształcić w zdanie pierwszego rzędu, które jest prawdziwe dokładnie w jednym z (A) i (B), a w którym zagnieżdżenie zakresów kwantyfikatora ma najwyżej (m) poziomów. Mamy więc nasz konieczny i wystarczający warunek dla elementarnej równoważności i trochę więcej.

Jeśli (A) i (B) są równoważne w przód iw tył, to z pewnością są one elementarnie równoważne; ale w rzeczywistości równoważność w obie strony okazuje się być tym samym, co równoważność elementarna w logice nieskończonej, która jest znacznie bardziej wyrazista niż logika pierwszego rzędu. Istnieje wiele dostosowań w grze, które dają inne rodzaje równoważności. Na przykład Barwise, Immerman i Bruno Poizat niezależnie opisali grę, w której obaj gracze mają dokładnie (p) ponumerowane kamyki; każdy gracz musi oznaczyć swoje wybory kamyczkiem, a dwa wybory w tym samym kroku muszą być oznaczone kamykami z tym samym numerem. W trakcie gry graczom zabraknie kamyków i będą musieli ponownie wykorzystać te, które były już używane. Warunek wygrania Spoilera na danej pozycji (i wszystkich kolejnych pozycjach) jest taki sam, jak poprzednio, z tym wyjątkiem, że liczą się tylko elementy opatrzone etykietami na tej pozycji. Istnienie zwycięskiej strategii dla Duplicatora w tej grze oznacza, że obie struktury zgadzają się co do zdań, które używają co najwyżej (p) zmiennych (pozwalając tym zmiennym występować dowolną liczbę razy).

Teoria gier tam iz powrotem opiera się na bardzo niewielu założeniach dotyczących tej logiki. W rezultacie te gry są jedną z nielicznych technik teorii modeli, które mają zastosowanie zarówno do struktur skończonych, jak i do nieskończonych, co czyni je jednym z kamieni węgielnych informatyki teoretycznej. Można ich używać do pomiaru siły ekspresyjnej języków formalnych, na przykład języków zapytań do baz danych. Typowy wynik może na przykład powiedzieć, że określony język nie potrafi odróżnić „parzystego” od „nieparzystego”; udowodnilibyśmy to, znajdując dla każdego poziomu (n) złożoności formuł języka parę skończonych struktur, dla których Duplicator ma zwycięską strategię w grze tam iz powrotem na poziomie (n), ale jedna ze struktur ma parzystą liczbę elementów, a druga ma liczbę nieparzystą. Semantyści języków naturalnych odkryli, że gry w obie strony są przydatne do porównywania mocy ekspresyjnych uogólnionych kwantyfikatorów. (Patrz na przykład Peters i Westerståhl 2006, sekcja IV).

Istnieje również rodzaj gry tam iz powrotem, która odpowiada naszej semantyce modalnej powyżej w taki sam sposób, jak gry Ehrenfeucht-Fraïssé odpowiadają semantyce gry Hintikki dla logiki pierwszego rzędu. Gracze rozpoczynają od stanu (s) w strukturze (A) i stanu (t) w strukturze (B). Spoiler i Duplikator poruszają się naprzemiennie, jak poprzednio. Za każdym razem, gdy się porusza, Spoiler wybiera, czy porusza się w (A), czy w (B), a następnie Duplicator musi poruszać się w drugiej strukturze. Ruch jest zawsze wykonywany przez przejście do przodu wzdłuż strzałki od bieżącego stanu. Jeśli między nimi obaj gracze właśnie przeszli do stanu (s) ´ w (A) i stanu (t) ´ w (B), a jakiś predykat (P_i) utrzymuje się na tylko jeden z (s) ´ i (t) ´, a następnie Duplikator od razu przegrywa. Przegrywa również, jeśli nie ma dostępnych strzał, którymi mogłaby się poruszać;ale jeśli Spoiler stwierdzi, że nie ma dostępnych strzał, którymi mógłby się poruszać w żadnej ze struktur, wygrywa Duplikator. Jeśli dwaj gracze grają w tę grę z określonymi stanami początkowymi (s) w (A) i (t) w (B), a obie struktury mają tylko skończenie wiele stanów, to można pokazać, że Duplikator ma zwycięską strategię wtedy i tylko wtedy, gdy te same zdania modalne są prawdziwe w (s) w (A), co jest prawdą w (t) w (B).

Istnieje wiele uogólnień tego wyniku, niektóre z nich dotyczą następującego pojęcia. Niech (Z) będzie relacją binarną, która wiąże stany (A) ze stanami (B). Następnie nazywamy (Z) bisymulacją między (A) a (B), jeśli Duplikator może użyć (Z) jako niedeterministycznej strategii wygrywającej w grze tam iz powrotem pomiędzy (A) i (B), gdzie pierwsza para ruchów dwóch graczy polega na wybraniu ich stanów początkowych. W informatyce pojęcie bisymulacji jest kluczowe dla zrozumienia (A) i (B) jako systemów; wyraża, że oba systemy oddziałują ze swoim otoczeniem w taki sam sposób jak każdy inny, krok po kroku. Jednak na krótko przed wprowadzeniem tego pojęcia przez informatyków zasadniczo to samo pojęcie pojawiło się w rozprawie doktorskiej Johana van Benthema na temat semantyki logiki modalnej (1976).

7. Inne gry teoretyczne

Gry logiczne w tej sekcji są narzędziami matematyków, ale mają kilka interesujących koncepcyjnie funkcji.

7.1 Gry wymuszające

Gry wymuszające znane są również opisowym teoretykom zbiorów jako gry Banacha-Mazura; więcej szczegółów na temat tła matematycznego można znaleźć w odnośnikach Kechris lub Oxtoby poniżej. Teoretycy modeli używają ich jako sposobu budowania nieskończonych struktur o kontrolowanych właściwościach. W najprostszym przypadku (forall) i (istnieje) grają w tak zwaną Grę Istnienia Modelu, gdzie (istnieje) twierdzi, że ustalone zdanie (phi) ma model, podczas gdy (forall) twierdzi, że może wyprowadzić sprzeczność z (phi). Na początku ustalony jest policzalnie nieskończony zbiór (C) nowych symboli stałych (a_0, a_1, a_2) itd. (istnieje) broni dysjunkcji, wybierając jeden rozłącznik, a stwierdzenie egzystencjalne, wybierając stałą z (C) jako świadka. (forall) może zakwestionować koniunkcję, wybierając jeden z koniunkcji,i uniwersalne oświadczenie, wybierając dowolnego świadka z (C). (istnieje) wygrywa, jeśli nie są odtwarzane żadne sprzeczne zdania atomowe. (istnieje) ma zwycięską strategię (właściwość spójności jest jednym ze sposobów opisania zwycięskiej strategii) wtedy i tylko wtedy, gdy (phi) ma model. Z drugiej strony, jeśli (forall) ma zwycięską strategię, drzewo (które może być skończone) wszystkich rozgrywek przeciwko jego wygrywającej strategii jest powiązane z dowodem w stylu Gentzena na negację (phi). Ta metoda analizy zdań jest ściśle związana z metodą Beth dotyczącą semantycznych obrazów i gry dialogowej (patrz Rozdział 8).jeśli (forall) ma zwycięską strategię, drzewo (które może być skończone) wszystkich zagrań przeciwko jego wygrywającej strategii jest powiązane z dowodem w stylu Gentzena na negację (phi). Ta metoda analizy zdań jest ściśle związana z metodą Beth dotyczącą semantycznych obrazów i gry dialogowej (patrz Rozdział 8).jeśli (forall) ma zwycięską strategię, drzewo (które może być skończone) wszystkich zagrań przeciwko jego wygrywającej strategii jest powiązane z dowodem w stylu Gentzena na negację (phi). Ta metoda analizy zdań jest ściśle związana z metodą Beth dotyczącą semantycznych obrazów i gry dialogowej (patrz Rozdział 8).

Aby naszkicować ideę ogólnej gry wymuszającej, wyobraź sobie, że licznie nieskończony zespół budowniczych buduje dom (A). Każdy budowniczy ma swoje własne zadanie do wykonania: na przykład zainstalowanie wanny lub tapetowanie przedpokoju. Każdy budowniczy ma nieskończenie wiele szans na wejście na teren i dodanie skończonej ilości materiału do domu; te szczeliny dla budowniczych są przeplatane tak, że cały proces odbywa się w sekwencji kroków liczonych liczbami naturalnymi.

Aby pokazać, że dom można zbudować na zamówienie, musimy pokazać, że każdy budowniczy z osobna może wykonać swoje zadanie, niezależnie od tego, co robią inni budowniczowie. Więc wyobrażamy sobie każdego konstruktora jako gracza (istnieje) w grze, w której wszyscy pozostali gracze są traktowani jako (dla wszystkich) i staramy się udowodnić, że (istnieje) ma na to zwycięską strategię gra. Kiedy udowodnimy to każdemu konstruktorowi z osobna, możemy sobie wyobrazić, że idą do pracy, każdy z własną strategią wygrywania. Wszyscy wygrywają swoje mecze, a rezultatem jest jeden piękny dom.

Mówiąc bardziej technicznie, elementy konstrukcji (A) są z góry ustalane, powiedzmy jako (a_0, a_1, a_2) itd., Ale właściwości tych elementów muszą zostać ustalone przez grę. Każdy gracz porusza się wrzucając zestaw atomowych lub zanegowanych atomowych stwierdzeń o elementach, pod warunkiem, że zestaw składający się ze wszystkich wrzuconych do tej pory wypowiedzi musi być zgodny z ustalonym zestawem aksjomatów spisanych przed grą. (Tak więc wrzucenie zanegowanego zdania atomowego (neg / phi) uniemożliwia jakiemukolwiek graczowi dodanie (phi) na późniejszym etapie.) Na koniec wspólnej gry zestaw zdań atomowych wrzucony ma model kanoniczny, a to jest struktura (A); istnieją sposoby, aby zapewnić, że jest to model ustalonego zbioru aksjomatów. Mówi się, że możliwa właściwość P (A) jest egzekwowalna, jeśli budowniczy, któremu powierzono zadanie uczynienia P prawdziwym (A), ma zwycięską strategię. Głównym punktem (wynikającym zasadniczo z Ehrenfeuchta) jest to, że koniunkcja policzalnie nieskończonego zestawu możliwych do wyegzekwowania właściwości jest ponownie wykonalna.

Różne twierdzenia Löwenheima-Skolema teorii modeli można udowodnić za pomocą wariantów gry wymuszającej. W tych wariantach nie konstruujemy modelu, ale podmodel danego modelu. Zaczynamy od dużego modelu (M) zdania (lub policzalnego zestawu zdań) (phi). Następnie podajemy podformuły (phi), a każdy gracz ma podformułę z wolną zmienną do zajęcia się. Zadaniem gracza jest upewnienie się, że gdy tylko w grze pojawią się parametry podformuły i jest świadek prawdziwości formuły w dużym modelu, jeden taki świadek jest odgrywany. Po zakończeniu gry policzalny podmodel (M) został zbudowany w taki sposób, że spełnia (phi).

Nazwa „wymuszanie” pochodzi od zastosowania pokrewnych pomysłów Paula Cohena do konstruowania modeli teorii mnogości we wczesnych latach sześćdziesiątych. Abraham Robinson dostosował to, aby stworzyć ogólną metodę budowania policzalnych struktur, a Martin Ziegler przedstawił ustawienie gry. Później Robin Hirsch i Ian Hodkinson wykorzystali podobne gry, aby rozstrzygnąć niektóre stare pytania dotyczące algebr relacji.

Gry wymuszające to zdrowy przykład, o którym należy pamiętać, myśląc o kwestii Dawkinsa. Przypominają nam, że w grach logicznych myślenie o graczach jako o przeciwnikach nie musi być pomocne.

7.2 Gry typu „wytnij i wybierz”

W tradycyjnej grze typu „wytnij i wybierz” bierzesz kawałek ciasta i kroisz go na dwa mniejsze kawałki; potem wybieram jeden z kawałków i jem, a drugi zostawiam Wam. Ta procedura ma na celu wywarcie presji na sprawiedliwe pokrojenie ciasta. Matematycy, nie do końca rozumiejąc cel ćwiczenia, nalegają na jego powtórzenie. W ten sposób każę ci przeciąć kawałek, który wybrałem na dwie części, a potem wybiorę jeden z tych dwóch; potem znowu wycinasz ten kawałek i tak dalej w nieskończoność. Niektórzy jeszcze bardziej nieziemscy matematycy każą pokroić ciasto na niezliczone kawałki zamiast na dwa.

Te gry są ważne w teorii definicji. Załóżmy, że mamy zbiór (A) obiektów i rodzinę (S) właściwości; każda właściwość wycina (A) do zbioru tych obiektów, które mają tę właściwość, i zbioru tych, które jej nie posiadają. Niech (istnieje) tnie, zaczynając od całego zbioru (A) i używając właściwości (S) jako noża; niech (forall) wybierz jeden z kawałków (które są podzbiorami (A)) i wróć do (istnieje) do ponownego wycięcia, jeszcze raz używając właściwości (S); i tak dalej. Niech (istnieje) przegra, gdy (forall) wybierze pustą figurę. Mówimy, że ((A, S)) ma co najwyżej rangę (m), jeśli (forall) ma strategię, która zapewnia, że (istnieje) przegra przed nią (m) - ruch. Ranga ((A, S)) daje cenne informacje o rodzinie podzbiorów (A) definiowanych przez właściwości w (S).

Wariacje tej gry, pozwalające na pocięcie elementu na nieskończenie wiele mniejszych kawałków, są fundamentalne w gałęzi teorii modeli zwanej teorią stabilności. Mówiąc ogólnie, teoria jest „dobra” w sensie teorii stabilności, jeśli weźmiemy model (A) teorii i (S) zbiór formuł pierwszego rzędu w jednej zmiennej swobodnej z parametrami z (A), struktura ((A, S)) ma „małą” rangę. Inną odmianą jest wymaganie, aby na każdym kroku (istnieje) dzieliło się na dwie części, które przetrwały z wcześniejszych kroków, i ponownie przegrywa, gdy tylko jeden z wyciętych fragmentów jest pusty. (W tej wersji (forall) jest zbędne.) W tej wariacji ranga ((A), S) nazywana jest wymiarem Vapnik-Chervonenkis; pojęcie to jest używane w komputerowej teorii uczenia się.

7.3 Gry na drzewie dwóch następnych funkcji

Wyobraź sobie drzewo, które zostało zbudowane na poziomach. Na dolnym poziomie znajduje się pojedynczy węzeł główny, ale z niego wychodzi lewa gałąź i prawa gałąź. Na następnym poziomie w górę znajdują się dwa węzły, po jednym na każdej gałęzi, az każdego z tych węzłów wyrasta lewa gałąź i prawa gałąź. Tak więc na następnym poziomie w górę są cztery węzły i znowu drzewo rozgałęzia się w lewo i w prawo w każdym z tych węzłów. Kontynuując do nieskończoności, drzewo to nazywane jest drzewem dwóch następczych funkcji (czyli lewej następcy i prawej następcy). Biorąc węzły jako elementy i wprowadzając dwa symbole funkcyjne dla lewego i prawego następcy, mamy strukturę. Potężne twierdzenie Michaela Rabina głosi, że istnieje algorytm, który powie nam, dla każdego monadycznego zdania drugiego rzędu (phi) w języku odpowiednim dla tej struktury,czy (phi) jest prawdą w strukturze, czy nie. („Monadyczny drugi rząd” oznacza, że logika jest podobna do pierwszego rzędu, z tym wyjątkiem, że możemy również kwantyfikować zbiory elementów, ale nie np. Relacje binarne na elementach).

Twierdzenie Rabina ma wiele użytecznych konsekwencji. Na przykład Dov Gabbay użył go do udowodnienia rozstrzygalności niektórych logik modalnych. Ale dowód Rabina, za pomocą automatów, był bardzo trudny do naśladowania. Jurij Gurewicz i Leo Harrington oraz niezależnie Andrei Muchnik znaleźli znacznie prostsze dowody na to, że automat jest graczem w grze.

Ten wynik Rabina jest jednym z kilku wpływowych rezultatów, które łączą gry z automatami. Innym przykładem są gry parzystości, które służą do weryfikacji właściwości systemów modalnych. Na przykład Stirling (2001) Rozdział 6; Bradfield i Stirling (2006) omawiają gry z parzystością dla rachunku modalnego (mu) -.

8. Gry dialogu, komunikacji i dowodu

Kilka średniowiecznych tekstów opisuje formę debaty zwaną zobowiązaniami. Było dwóch sporów, Opponens i Respondens. Na początku sesji dyskutanci zgadzali się na „positum”, zazwyczaj fałszywe oświadczenie. Zadaniem Respondens było udzielanie racjonalnych odpowiedzi na pytania Opponensa, zakładając prawdziwość positum; przede wszystkim musiał unikać niepotrzebnego sobie zaprzeczania. Zadaniem Opponens była próba zmuszenia Respondens do sprzeczności. Więc ogólnie znamy odpowiedź na pytanie Dawkinsa, ale nie znamy zasad gry! Podręczniki średniowieczne opisują kilka zasad, których powinni przestrzegać dyskutanci. Ale te zasady nie są ustalonymi regułami gry; są wskazówkami, które podręczniki wyprowadzają z zasad rozsądnego rozumowania przy pomocy przykładów.(Paweł z Wenecji uzasadnia jedną regułę praktyką „wielkich logików, filozofów, geometrów i teologów”.) W szczególności była otwarta dla nauczyciela, który miał obowiązek odkrywania nowych reguł. Ta otwartość oznacza, że zobowiązania nie są grami logicznymi w naszym rozumieniu.

Nie wszyscy zgadzają się z poprzednim zdaniem. Na przykład Catarina Dutilh Novaes (2007, 6) szczegółowo broni poglądu, że Zobowiązania przedstawiają „niezwykły przykład konceptualnego podobieństwa między średniowiecznymi a nowoczesnymi ramami teoretycznymi”. Jednak niezależnie od poglądu, jaki przyjmiemy na tę kwestię, debaty te zainspirowały jedną ważną linię współczesnych badań w grach logicznych.

Wyobraź sobie, że (istnieje) zdaje egzamin ustny z teorii dowodu. Egzaminator wydaje jej wyrok i zaprasza ją, aby zaczęła to udowadniać. Jeśli zdanie ma formę

(phi / vee / psi)

wtedy ma prawo wybrać jedno ze zdań i powiedzieć „OK, to udowodnię”. (W rzeczywistości, jeśli egzaminator jest intuicjonistą, może nalegać, aby wybrała jedno ze zdań do udowodnienia). Z drugiej strony, jeśli zdanie jest

(phi / wedge / psi)

wówczas egzaminator, będąc egzaminatorem, mógłby równie dobrze wybrać jeden ze spojówek i zaprosić ją, aby to udowodniła. Jeśli wie, jak udowodnić koniunkcję, to z pewnością wie, jak udowodnić koniunkcję.

Przypadek (phi / rightarrow / psi) jest trochę subtelniejszy. Prawdopodobnie będzie chciała zacząć od założenia (phi), aby wydedukować (psi); ale istnieje pewne ryzyko pomyłki, ponieważ zdania, które zapisała do tej pory, to wszystkie rzeczy do udowodnienia, a (phi) nie jest rzeczą do udowodnienia. Egzaminator może jej pomóc, mówiąc „Zakładam (phi) i zobaczmy, czy stamtąd dotrzesz do (psi)”. W tym momencie jest szansa, że widzi sposób na dotarcie do (psi) poprzez wywnioskowanie sprzeczności z (phi); może więc odwrócić sytuację egzaminatora i poprosić go, aby pokazał, że jego założenie jest spójne, aby udowodnić, że tak nie jest. Symetria nie jest idealna: prosił ją, by pokazała, że zdanie jest prawdziwe wszędzie, podczas gdy ona zaprasza go, by pokazał, że gdzieś zdanie jest prawdziwe. Niemniej jednak możemy dostrzec rodzaj dwoistości.

Idee tego rodzaju leżą u podstaw dialektycznych gier Paula Lorenzena. Pokazał, że przy pewnej ilości pchnięć i pchnięć można napisać reguły gry, które mają tę właściwość, że (istnieje) ma strategię wygrywającą wtedy i tylko wtedy, gdy zdanie, które otrzymuje na początku, jest twierdzenie logiki intuicjonistycznej. W geście skierowanym do średniowiecznych debat nazwał (istnieje) Proponentem, a drugiego gracza Przeciwnikiem. Niemal jak w średniowiecznych zobowiązaniach, Przeciwnik wygrywa, doprowadzając Proponenta do punktu, w którym jedynymi dostępnymi jej ruchami są rażące sprzeczności.

Lorenzen twierdził, że jego gry dostarczają uzasadnienia zarówno dla logiki intuicjonistycznej, jak i klasycznej (lub, jego zdaniem, uczyniły je „gerechtfertigt”, Lorenzen (1961,196)). Niestety każde „uzasadnienie” zawiera przekonującą odpowiedź na pytanie Dawkinsa, a tego Lorenzena nigdy nie podał. Na przykład mówił o ruchach jako o „atakach”, nawet jeśli (jak wybór egzaminatora w (phi / wedge / psi) powyżej) wyglądają bardziej na pomoc niż wrogość.

Logika dialogowa wejścia daje pełniejszy opis gier Lorenzena i kilku nowszych wariantów. W swojej obecnej formie (styczeń 2013) omija twierdzenia Lorenzena o uzasadnianiu logiki. Zamiast tego opisuje gry jako zapewniające semantykę logikom (kwestia, z którą Lorenzen z pewnością zgodziłby się) i dodaje, że dla zrozumienia różnic między logikami pomocne może być porównanie ich semantyki.

Z tego punktu widzenia gry Lorenzena stanowią ważny paradygmat tego, co niedawni teoretycy dowodu nazwali semantyką dowodów. Semantyka dowodów nadaje „znaczenie” nie tylko pojęciu bycia możliwym do udowodnienia, ale każdemu oddzielnemu etapowi dowodu. Odpowiada na pytanie: „Co osiągamy, wykonując ten konkretny ruch w dowodzie?” W latach 90. wielu pracowników z logicznego końca informatyki szukało gier, które odpowiadałyby logice liniowej i niektórym innym systemom dowodowym w taki sam sposób, jak gry Lorenzena odpowiadały logice intuicjonistycznej. Andreas Blass, a później Samson Abramsky i jego koledzy, przedstawili gry, które odpowiadały elementom logiki liniowej, ale w chwili pisania tego tekstu nie mamy jeszcze doskonałej zgodności między grą a logiką. Ten przykład jest szczególnie interesujący, ponieważ odpowiedź na pytanie Dawkinsa powinna dać intuicyjną interpretację praw logiki liniowej, czego ta logika bardzo potrzebowała. Gry Abramsky'ego i in. opowiedz historię o dwóch współdziałających systemach. Ale kiedy zaczynał od gier, w których gracze grzecznie zmieniali się, Abramsky pozwolił później graczom działać „w sposób rozproszony, asynchroniczny”, zwracając na siebie uwagę tylko wtedy, gdy zechcą. Te gry nie są już w normalnym formacie gier logicznych, a ich rzeczywista interpretacja rodzi wiele nowych pytań. Ale kiedy zaczynał od gier, w których gracze grzecznie zmieniali się, Abramsky pozwolił później graczom działać „w sposób rozproszony, asynchroniczny”, zwracając na siebie uwagę tylko wtedy, gdy zechcą. Te gry nie są już w normalnym formacie gier logicznych, a ich rzeczywista interpretacja rodzi wiele nowych pytań. Ale kiedy zaczynał od gier, w których gracze grzecznie zmieniali się, Abramsky pozwolił później graczom działać „w sposób rozproszony, asynchroniczny”, zwracając na siebie uwagę tylko wtedy, gdy zechcą. Te gry nie są już w normalnym formacie gier logicznych, a ich rzeczywista interpretacja rodzi wiele nowych pytań.

Giorgi Japaridze zaproponował „logikę obliczalności” do badania obliczeń. Jego składnia jest logiką pierwszego rzędu z kilkoma dodatkowymi elementami przypominającymi logikę liniową. Jego semantyka dotyczy gier semantycznych z pewnymi niezwykłymi cechami. Na przykład nie zawsze jest określone, który gracz wykona następny ruch. Pojęcie funkcji strategicznych nie nadaje się już do opisywania graczy; Zamiast tego Japaridze opisuje sposoby odczytywania drugiego gracza (player (exist) w naszej notacji) jako rodzaj maszyny obliczeniowej. Więcej informacji znajduje się na jego stronie internetowej.

Inną grupą gier z tej samej rodziny generalnej co Lorenzena są gry dowodowe Pawła Pudlaka 2000. Tutaj przeciwnik (zwany Prover) pełni rolę adwokata w sądzie, który wie, że Proponent (zwany Adwersarzem) jest winny popełnienia przestępstwa. Zwolennik będzie twierdził, że jest niewinny i jest gotów kłamać, aby się bronić. Celem przeciwnika jest zmuszenie Proponenta do zaprzeczenia czemuś, o czym Proponent jest zarejestrowany, jak powiedział wcześniej; ale przeciwnik zachowuje rekord i (jak w powyższych grach w kamyczki) czasami musi upuszczać pozycje z rekordu z powodu braku miejsca lub pamięci. Ważną kwestią nie jest to, czy przeciwnik ma strategię wygrywającą (od początku zakłada się, że ją ma), ale ile pamięci potrzebuje do swojego rekordu. Te gry są użytecznym narzędziem do pokazywania górnych i dolnych granic długości dowodów w różnych systemach dowodowych.

Innym rodzajem gry logicznej, która pozwala na kłamstwa, jest Gra Ulama z kłamstwami. Tutaj jeden gracz myśli o liczbie w pewnym podanym zakresie. Celem drugiego gracza jest dowiedzieć się, jaka jest ta liczba, zadając pierwszemu graczowi pytania tak / nie; ale pierwszy gracz może podać określoną liczbę kłamstw w swoich odpowiedziach. Podobnie jak w grach Pudlaka, z pewnością istnieje strategia wygrywająca dla drugiego gracza, ale pytanie brzmi, jak ciężko ten gracz musi pracować, aby wygrać. Miarą tym razem nie jest przestrzeń czy pamięć, ale czas: ile pytań musi zadać? Cignoli i in. 2000 Rozdział 5 odnosi tę grę do logiki wielowartościowej.

Wracając na chwilę do Lorenzena: nie potrafił rozróżnić między różnymi postawami, które dana osoba może przyjąć w argumentacji: stwierdzenie, przypuszczenie, przyznanie się, kwestionowanie, atakowanie, angażowanie się. To, czy naprawdę możliwe jest zdefiniowanie wszystkich tych pojęć bez zakładania jakiejś logiki, jest kwestią sporną. Ale nieważne; udoskonalenie gier Lorenzena w ten sposób mogłoby posłużyć jako podejście do logiki nieformalnej, a zwłaszcza do badań, których celem jest usystematyzowanie możliwych struktur zdrowej, nieformalnej argumentacji. Na ten temat patrz Walton i Krabbe 1995. Odpowiednie są również artykuły w Bench-Capon i Dunne 2007.

Bibliografia

Niektóre z przełomowych artykułów Henkina i Lorenzena, a także niektóre cytowane poniżej, ukazują się w zbiorze Infinitistic Methods (Proceedings of the Foundations of Mathematics, Warszawa, 2–9 września 1959), Oxford: Pergamon Press, 1961, Redaktorzy nie mają nazw.

Gry w historii logiki

  • Dutilh Novaes, Catarina, 2007, Formalizing Medieval Logical Theories: Suppositio, Consequentiae and Obligationes, New York: Springer-Verlag.
  • Hamblin, Charles, 1970, Fallacies, Londyn: Methuen.
  • Hilbert, David, 1967, „Die Grundlagen der Mathematik”, przetłumaczone jako „Podstawy matematyki”, w: Jean van Heijenoort (red.), From Frege to Gödel, Cambridge Mass.: Harvard University Press, str. 464–479.
  • Paul of Venice, Logica Magna II (8), Tractatus de Obligationibus, E. Jennifer Ashworth (red.), New York: British Academy i Oxford University Press, 1988.
  • Weyl, Hermann, 1925–197, „Die heutige Erkenntnislage in der Mathematik”, przetłumaczone jako „Obecna sytuacja epistemologiczna w matematyce” w: Paolo Mancosu, From Brouwer to Hilbert: The Debate on the Foundations of Mathematics in the 1920s, New York: Oxford University Press, 1988, s. 123–142.
  • Zermelo, Ernst, 1913, „Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels”, w EW Hobson i AEH Love (red.), Proceedings of the Fifth International Congress of Mathematicians, tom II, Cambridge: Cambridge University Press.

Gry do nauczania logiki

  • Barwise, Jon and John Etchemendy, 1995, The Language of First-Order Logic, w tym Tarski's World 3.0, Cambridge: Cambridge University Press.
  • Carroll, Lewis, 1887, The Game of Logic, Londyn: Macmillan.
  • Dienes, Zoltan P. i EW Golding, 1966, Learning Logic, Logical Games, Harlow: Educational Supply Association.
  • Havas, Katalin, 1999, „Learning to think: Logic for children”, w: Proceedings of the Twentieth World Congress of Philosophy (tom 3: Philosophy of Education), David M. Steiner (red.), Bowling Green Ohio: Bowling Green State University Philosophy, s. 11–19.
  • Nifo, Agostino, 1521, Dialectica Ludicra (Logic as a game), Florence: Bindonis.
  • Weng, Jui-Feng, z Shian-Shyong Tseng i Tsung-Ju Lee, 2010, „Teaching Boolean logic through game rule tuning”, IEEE Transactions, Learning Technologies, 3 (4): 319–328. [Używa gier Pac-Mana do nauczania logiki Boole'a gimnazjalistów.]

Gry logiczne

  • Gale, David i FM Stewart, 1953, „Infinite games with perfect information”, w: Contributions to the Theory of Games II (Annals of Mathematics Studies 28), HW Kuhn i AW Tucker (red.), Princeton: Princeton University Press, str., 245–266.
  • Kechris, Alexander S., 1995, Classical Descriptive Set Theory, New York: Springer-Verlag.
  • Marion, Mathieu, 2009, „Why play logical games?”, W: Ondrej Majer, Ahti-Veikko Pietarinen i Tero Tulenheimo eds., Games: Unifying Logic, Language and Philosophy, New York: Springer-Verlag, str. 3-25.
  • Osbourne, Martin J. and Ariel Rubinstein, 1994, Kurs teorii gier, Cambridge: MIT Press.
  • Väänänen, Jouko, 2011, Modele i gry, Cambridge: Cambridge University Press.
  • van Benthem, Johan, 2011, Logiczna dynamika informacji i interakcji, Cambridge: Cambridge University Press, 2011.
  • –––, 2014, Logika w grach, Cambridge, MA: MIT Press.

Gry semantyczne w logice klasycznej

  • Henkin, Leon, 1961, „Kilka uwag o formułach nieskończenie długich”, w: Infinitistic Methods, op. cit., pp. 167–183.
  • Hintikka, Jaakko, 1973, Logic, Language-Games and Information: Kantian Themes in the Philosophy of Logic, Oxford: Clarendon Press.
  • Hintikka, Jaakko, 1996, The Principles of Mathematics Revisited, Nowy Jork: Cambridge University Press. [Zobacz na przykład strony 40, 82 na temat aksjomatu wyboru.]
  • Hodges, Wilfrid, 2001, „Elementary Predicate Logic 25: Skolem Functions”, w: Dov Gabbay i Franz Guenthner (red.), Handbook of Philosophical Logic I, wydanie 2, Dordrecht: Kluwer, str. 86–91. [Dowód równoważności gry i semantyki Tarskiego.]
  • Kolaitis, Ph. G., 1985, „Game quantification”, J. Barwise i S. Feferman (red.), Model-Theoretic Logics, New York: Springer-Verlag, str. 365-421.
  • Peirce, Charles Sanders, 1898, Reasoning and the Logic of Things: The Cambridge Conferences Lectures of 1898, wyd. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.

Gry semantyczne z niedoskonałymi informacjami

  • Hintikka, Jaakko and Gabriel Sandu, 1997, „Game-theoretical semantics”, w: Johan van Benthem i Alice ter Meulen (red.), Handbook of Logic and Language, Amsterdam: Elsevier, str. 361–410.
  • Hodges, Wilfrid, 1997, „Compositional semantics for a language of nonfect information”, Logic Journal of the IGPL, 5: 539–563.
  • Janssen, Theo MV and Francien Dechesne, 2006, „Signaling: a tricky business”, w: J. van Benthem i in. (red.), The Age of Alternative Logics: Assessing the Philosophy of Logic and Mathematics Today, Dordrecht: Kluwer, s. 223–242.
  • Mann, Allen L., Gabriel Sandu i Merlin Sevenster, 2011, Independence-Friendly Logic: A Game-Theoretic Approach (London Mathematical Society Lecture Note Series 386), Cambridge: Cambridge University Press.
  • von Neumann, John i Oskar Morgenstern, 1944, Theory of Games and Economic Behavior, Princeton: Princeton University Press.
  • Väänänen, Jouko, 2007, Dependence Logic: A New Approach to Independence Friendly Logic, Cambridge: Cambridge University Press.

Gry semantyczne dla innych logik

  • Bradfield, Julian i Colin Stirling, 2006, „Modal mu-calci”, w: P. Blackburn i in. (red.), Handbook of Modal Logic, Amsterdam: Elsevier, s. 721–756.
  • Dekker, Paul i Marc Pauly (red.), 2002, Journal of Logic, Language and Information, 11 (3): 287–387. [Wydanie specjalne dotyczące logiki i gier.]
  • Hennessy, Matthew i Robin Milner, 1985, „Algebraic law for indeterminism and concurrency”, Journal of the ACM, 32: 137–162.
  • Parikh, Rohit, 1985, „Logika gier i jej zastosowania”, w: Marek Karpiński i Jan van Leeuwen (red.), „Tematy w teorii obliczeń”, Annals of Discrete Mathematics, 24: 111–140.
  • Pauly, Marc i Rohit Parikh (red.), 2003, Studia Logica, 72 (2): 163–256 [wydanie specjalne dotyczące logiki gier].
  • Stirling, Colin, 2001, Modal and Temporal Properties of Processes, New York: Springer-Verlag.
  • van Benthem, Johan, 2006, „The epistemic logic of IF games”, w: Randall Auxier i Lewis Hahn (red.), The Philosophy of Jaakko Hintikka, Chicago: Open Court str. 481–513.
  • van Benthem, Johan with Amitabha Gupta i Rohit Parikh, 2011, Proof, Computation and Agency, Dordrecht: Springer-Verlag.

Gry w przód i tył

  • Blackburn, Patrick z Maartenem de Rijke i Yde Venema, 2001, Logika modalna, Cambridge: Cambridge University Press.
  • Doets, Kees, 1996, Basic Model Theory, Stanford: CSLI Publications and FoLLI.
  • Ebbinghaus, Heinz-Dieter and Jörg Flum, 1999, Finite Model Theory, 2. wydanie, New York: Springer.
  • Ehrenfeucht, Andrzej, 1961, „Zastosowanie gier do problemu zupełności dla teorii sformalizowanych”, Fundamenta Mathematicae, 49: 129–141.
  • Grädel, Erich with Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema i Scott Weinstein, 2007, Finite Model Theory, Berlin: Springer-Verlag.
  • Libkin, Leonid, 2004, Elementy teorii modeli skończonych, Berlin, Springer-Verlag.
  • Otto, Martin, 1997, Bounded Variable Logics and Counting-A Study in Finite Models (Lecture Notes in Logic, 9), Berlin: Springer-Verlag.
  • Peters, Stanley i Dag Westerståhl, 2006, Quantifiers in Language and Logic, Oxford: Clarendon Press.
  • Tarski, Alfred, 1946, „Przemówienie na konferencji dotyczącej problemów matematyki na Uniwersytecie Princeton (17–19 grudnia 1946)”, Hourya Sinaceur (red.), Bulletin of Symbolic Logic, 6 (2000): 1–44.
  • van Benthem, Johan, 2001, „Correspondence Theory”, w: Dov Gabbay i Franz Guenthner (red.), Handbook of Philosophical Logic III, wydanie 2, Dordrecht: Kluwer.

Inne gry oparte na teorii modeli

  • Anthony, Martin i Norman Biggs, 1992, Computational Learning Theory, Cambridge: Cambridge University Press. [Dla wymiaru Vapnik-Chervonenkis.]
  • Gurevich, Yuri i Leo Harrington, 1984, „Drzewa, automaty i gry” w HR Lewis (red.), Proceedings of the ACM Symposium on the Theory of Computing, San Francisco: ACM, str. 171–182.
  • Hirsch, Robin i Ian Hodkinson, 2002, Relation Algebras by Games, New York: North-Holland.
  • Hodges, Wilfrid, 1985, Building Models by Games, Cambridge: Cambridge University Press.
  • Hodges, Wilfrid, 1993, Model Theory, Cambridge: Cambridge University Press.
  • Oxtoby, JC, 1971, Measure and Category, New York: Springer-Verlag.
  • Ziegler, Martin, 1980, „Algebraisch abgeschlossene Gruppen”, w SI Adian et al. (red.), Word Problems II: The Oxford Book, Amsterdam: North-Holland, s. 449–576.

Gry dialogu, komunikacji i dowodu

  • Abramsky, Samson and Radha Jagadeesan, 1994, „Games and full completeeness for multiplicative linear logic”, Journal of Symbolic Logic, 59: 543–574.
  • Abramsky, Samson i Paul-André Melliès, 1999, „Concurrent games and full completeeness”, w: Proceedings of the Fourteenth International Symposium on Logic in Computer Science, Computer Science Press of the IEEE, str. 431–442.
  • Bench-Capon, TJM i Paul E. Dunne, 2007, „Argumentation in sztuczna inteligencja”, Artificial Intelligence, 171: 619–641. [Wprowadzenie do bogatego zbioru prac na ten sam temat na str. 642–937].
  • Blass, Andreas, 1992, „Semantyka gry dla logiki liniowej”, Annals of Pure and Applied Logic, 56: 183–220.
  • Cignoli, Roberto LO, Itala ML D'Ottaviano i Daniele Mundici, 2000, Algebraic Foundations of Many-Valued Reasoning, Dordrecht: Kluwer.
  • Felscher, Walter, 2001, „Dialogi jako podstawa logiki intuicjonistycznej”, w: Dov Gabbay i Franz Guenthner (red.), Handbook of Philosophical Logic V, wydanie 2, Dordrecht: Kluwer.
  • Hodges, Wilfrid i Erik CW Krabbe, 2001, „Fundamenty dialogu”, Proceedings of the Aristotelian Society (tom uzupełniający), 75: 17–49.
  • Japaridze, Giorgi, 2003, „Introduction to computability logic”, Annals of Pure and Applied Logic, 123: 1–99.
  • Lorenzen, Paul, 1961 „Ein dialogisches Konstruktivitätskriterium”, w: Infinitistic Methods, op. cit., 1961, s. 193–200.
  • Pudlak, Pavel, 2000, „Proofs as games”, American Mathematical Monthly, 107 (6): 541–550.
  • Walton, Douglas N. i Erik CW Krabbe, 1995, Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning, Albany: State University of New York Press.

Narzędzia akademickie

człowiek ikona
człowiek ikona
Jak cytować ten wpis.
człowiek ikona
człowiek ikona
Zobacz wersję PDF tego wpisu w Friends of the SEP Society.
ikona Inpho
ikona Inpho
Poszukaj tego tematu wpisu w Internet Philosophy Ontology Project (InPhO).
ikona dokumentów phil
ikona dokumentów phil
Ulepszona bibliografia tego wpisu na PhilPapers, z linkami do jego bazy danych.

Inne zasoby internetowe

Zalecane: