Logik Dan Permainan

Isi kandungan:

Logik Dan Permainan
Logik Dan Permainan

Video: Logik Dan Permainan

Video: Logik Dan Permainan
Video: Логика / Сборник развивающих игровых мультфильмов / Жили-были 2024, Mac
Anonim

Navigasi Masuk

  • Kandungan Penyertaan
  • Bibliografi
  • Alat Akademik
  • Pratonton PDF Rakan
  • Maklumat Pengarang dan Petikan
  • Kembali ke atas

Logik dan Permainan

Pertama kali diterbitkan pada Jum 27 Jul 2001; semakan substantif Jum 16 Ogos 2019

Permainan antara dua pemain, seperti mana satu pemain menang dan satu kalah, menjadi alat yang biasa di banyak cabang logik pada separuh kedua abad kedua puluh. Contoh penting adalah permainan semantik yang digunakan untuk menentukan kebenaran, permainan bolak-balik yang digunakan untuk membandingkan struktur, dan permainan dialog untuk menyatakan (dan mungkin menjelaskan) bukti formal.

  • 1. Permainan dalam Sejarah Logik
  • 2. Permainan Logik
  • 3. Permainan Semantik untuk Logik Klasik
  • 4. Permainan Semantik dengan Maklumat Tidak Sempurna
  • 5. Permainan Semantik untuk Logik Lain
  • 6. Permainan Belakang dan Ke Depan
  • 7. Permainan Model-teori lain

    • 7.1 Memaksa permainan
    • 7.2 Permainan potong dan pilih
    • 7.3 Permainan di atas pokok dua fungsi pengganti
  • 8. Permainan Dialog, Komunikasi dan Bukti
  • Bibliografi

    • Permainan dalam Sejarah Logik
    • Permainan untuk Logik Pengajaran
    • Permainan Logik
    • Permainan Semantik untuk Logik Klasik
    • Permainan Semantik dengan Maklumat Tidak Sempurna
    • Permainan Semantik untuk Logik Lain
    • Permainan Belakang dan Ke Depan
    • Permainan Model-Teori lain
    • Permainan Dialog, Komunikasi dan Bukti
  • Alat Akademik
  • Sumber Internet Lain
  • Penyertaan Berkaitan

1. Permainan dalam Sejarah Logik

Hubungan antara logik dan permainan sudah lama wujud. Sekiranya seseorang menganggap perdebatan sebagai sejenis permainan, maka Aristoteles sudah membuat hubungan; tulisannya mengenai silogisme saling berkaitan dengan kajiannya mengenai tujuan dan peraturan perbahasan. Pandangan Aristoteles bertahan menjadi nama biasa abad pertengahan untuk logik: dialektik. Pada pertengahan abad kedua puluh, Charles Hamblin menghidupkan kembali hubungan antara dialog dan peraturan pertimbangan akal, tidak lama setelah Paul Lorenzen menghubungkan dialog dengan asas logik yang membina.

Terdapat kaitan rapat antara permainan dan pengajaran. Penulis sepanjang abad pertengahan bercakap mengenai dialog sebagai cara 'mengajar' atau 'menguji' penggunaan penaakulan yang bernas. Kami mempunyai sekurang-kurangnya dua buku teks logik dari awal abad keenam belas yang menyajikannya sebagai permainan untuk pelajar individu, dan Lewis Carroll's The Game of Logic (1887) adalah contoh lain dalam genre yang sama. Terdapat banyak contoh moden juga, walaupun mungkin belum ada kesinambungan yang cukup untuk membenarkan pembicaraan tradisi pengajaran logik dengan permainan.

Teori permainan matematik diasaskan pada awal abad kedua puluh. Walaupun tidak ada hubungan matematik dengan logik yang muncul hingga tahun 1950-an, sangat mengejutkan berapa banyak pelopor awal teori permainan yang juga terkenal dengan sumbangan mereka terhadap logik: John Kemeny, JCC McKinsey, John von Neumann, Willard Quine, Julia Robinson, Ernst Zermelo dan lain lain. Pada tahun 1953 David Gale dan Frank Stewart membuat hubungan yang bermanfaat antara teori set dan permainan. Tidak lama kemudian, Leon Henkin mencadangkan cara menggunakan permainan untuk memberi semantik untuk bahasa infiniter.

Separuh pertama abad kedua puluh adalah era peningkatan ketegasan dan profesionalisme dalam logik, dan bagi kebanyakan ahli logika pada masa itu penggunaan permainan dalam logik mungkin kelihatan remeh. Ahli intuisi LEJ Brouwer menyatakan sikap ini ketika dia menuduh lawannya menyebabkan matematik 'merosot menjadi permainan' (seperti yang dikutip oleh David Hilbert pada tahun 1927, yang disebut dalam van Heijenoort 1967). Hermann Weyl (dikutip dalam Mancosu 1998) menggunakan konsep permainan untuk menjelaskan metamatematik Hilbert: bukti matematik diteruskan seperti permainan permainan yang tidak bermakna, tetapi kita boleh berdiri di luar permainan dan mengajukan soalan yang bermakna mengenainya. Permainan bahasa Wittgenstein menimbulkan sedikit tindak balas daripada para ahli logik. Tetapi pada separuh kedua abad ini pusat graviti penyelidikan logik beralih dari asas ke teknik,dan dari sekitar tahun 1960 permainan lebih kerap digunakan dalam kertas logik.

Pada awal abad kedua puluh satu telah diterima secara luas bahawa permainan dan logik berjalan bersama. Hasilnya adalah percambahan besar kombinasi logik dan permainan baru, terutama di daerah di mana logik diterapkan. Sebilangan besar perkembangan baru ini berasal dari kerja logik murni, walaupun hari ini mereka mengikuti agenda mereka sendiri. Salah satu bidang tersebut adalah teori hujah, di mana permainan membentuk alat untuk menganalisis struktur perbahasan.

Di bawah ini kita akan menumpukan perhatian pada permainan yang paling berkaitan dengan logik tulen.

2. Permainan Logik

Dari sudut teori permainan, permainan utama yang dikaji oleh ahli logik sama sekali tidak biasa. Mereka biasanya hanya melibatkan dua pemain, mereka mempunyai panjang yang tidak terbatas, satu-satunya hasil adalah menang dan kalah, dan tidak ada kemungkinan yang melekat pada tindakan atau hasil. Keperluan terbaik permainan logik adalah seperti berikut.

Terdapat dua pemain. Secara umum kita boleh memanggil mereka (forall) dan (wujud). Pengucapan 'Abelard' dan 'Eloise' kembali ke pertengahan 1980-an dan berguna memperbetulkan pemain sebagai lelaki dan wanita menjadikan rujukan lebih mudah: pergerakannya, pergerakannya. Nama lain biasa digunakan untuk pemain dalam jenis permainan logik tertentu.

Pemain bermain dengan memilih elemen satu set (Omega), yang disebut domain permainan. Semasa mereka memilih, mereka membina urutan

[a_0, a_1, a_2, / ldots)

unsur (Omega). Urutan unsur-unsur (Omega) yang tidak terhingga disebut lakon. Urutan terhingga unsur (Omega) dipanggil kedudukan; mereka merakam di mana permainan mungkin sampai pada waktu tertentu. Fungsi (tau) (fungsi giliran atau fungsi pemain) mengambil setiap kedudukan (mathbf {a}) ke (ada) atau (forall); jika (tau (mathbf {a}) = / ada), ini bermakna apabila permainan telah mencapai (mathbf {a}), pemain (ada) membuat pilihan seterusnya (dan juga dengan (forall)). Peraturan permainan menentukan dua set (W _ { forall}) dan (W _ { wujud}) yang terdiri daripada kedudukan dan permainan, dengan sifat berikut: jika kedudukan (mathbf {a}) berada di (W _ { forall}) maka begitu juga kedudukan main atau lebih lama yang dimulakan dengan (mathbf {a}) (dan begitu juga dengan (W _ { wujud}));dan tidak ada permainan di kedua (W _ { forall}) dan (W _ { wujud}). Kami mengatakan bahawa pemain (forall) memenangi permainan (mathbf {b}), dan (mathbf {b}) adalah kemenangan untuk (forall), jika (mathbf {b}) berada di (W _ { forall}); jika beberapa kedudukan (mathbf {a}) yang merupakan segmen awal (mathbf {b}) berada di (W _ { forall}), maka kita katakan pemain itu (forall) sudah menang di (mathbf {a}). (Dan begitu juga dengan (ada) dan (W _ { wujud}).) Jadi untuk meringkaskan, permainan logik adalah 4-tuple ((Omega, / tau), (W_ { forall}), (W _ { wujud})) dengan sifat yang baru dijelaskan.maka kita mengatakan bahawa pemain (forall) sudah menang di (mathbf {a}). (Dan begitu juga dengan (ada) dan (W _ { wujud}).) Jadi untuk meringkaskan, permainan logik adalah 4-tuple ((Omega, / tau), (W_ { forall}), (W _ { wujud})) dengan sifat yang baru dijelaskan.maka kita mengatakan bahawa pemain (forall) sudah menang di (mathbf {a}). (Dan begitu juga dengan (ada) dan (W _ { wujud}).) Jadi untuk meringkaskan, permainan logik adalah 4-tuple ((Omega, / tau), (W_ { forall}), (W _ { wujud})) dengan sifat yang baru dijelaskan.

Kami mengatakan bahawa permainan logik adalah jumlah keseluruhan jika setiap permainan dilakukan sama ada (W _ { forall}) atau (W _ { wujud}), sehingga tidak ada seri. Kecuali jika seseorang membuat pengecualian secara eksplisit, permainan logik selalu dianggap total. (Jangan mengelirukan dengan jumlah harta yang jauh lebih kuat yang ditentukan-lihat di bawah.)

Hanya untuk kemudahan matematik, definisi di atas mengharapkan permainan berterusan hingga tak terhingga walaupun pemain telah menang pada kedudukan tertentu; tidak ada minat terhadap apa-apa yang berlaku setelah pemain menang. Banyak permainan logik mempunyai sifat bahawa dalam setiap permainan, salah satu pemain telah menang pada kedudukan tertentu; permainan seperti ini dikatakan berlandaskan asas. Keadaan yang lebih kuat lagi ialah terdapat beberapa nombor terhingga (n) sehingga dalam setiap permainan, salah satu pemain telah menang dengan kedudukan (n) - th; dalam kes ini kita mengatakan bahawa permainan ini mempunyai panjang yang terhad.

Strategi untuk pemain adalah sekumpulan peraturan yang menggambarkan dengan tepat bagaimana pemain itu harus memilih, bergantung pada bagaimana kedua pemain telah memilih pada gerakan sebelumnya. Secara matematik, strategi untuk (forall) terdiri daripada fungsi yang mengambil setiap kedudukan (mathbf {a}) dengan (tau (mathbf {a}) = / forall) ke elemen (b) daripada (Omega); kami menganggapnya sebagai arahan untuk (forall) untuk memilih (b) apabila permainan telah mencapai kedudukan (mathbf {a}). (Begitu juga dengan strategi untuk (ada).) Strategi untuk pemain dikatakan akan menang jika pemain itu memenangi setiap permainan di mana dia menggunakan strategi, tidak kira apa yang pemain lain lakukan. Paling banyak salah satu pemain mempunyai strategi menang (kerana jika tidak, pemain dapat memainkan strategi menang mereka satu sama lain, dan keduanya akan menang,bertentangan bahawa (W _ { forall}) dan (W _ { wujud}) tidak mempunyai persamaan permainan). Kadang-kadang seseorang bertemu dengan situasi di mana nampaknya dua pemain mempunyai strategi menang (contohnya dalam permainan memaksa di bawah), tetapi pemeriksaan lebih dekat menunjukkan bahawa kedua-dua pemain itu sebenarnya bermain permainan yang berbeza.

Permainan dikatakan akan ditentukan jika satu atau pemain lain mempunyai strategi menang. Terdapat banyak contoh permainan yang tidak ditentukan, seperti yang ditunjukkan oleh Gale dan Stewart pada tahun 1953 menggunakan aksioma pilihan. Penemuan ini membawa kepada penerapan penting dari gagasan determinasi dalam asas teori set (lihat entri mengenai kardinal besar dan determinasi). Gale dan Stewart juga membuktikan teorema penting yang membawa nama mereka: Setiap permainan yang mantap ditentukan. Ini menunjukkan bahawa setiap permainan yang panjangnya ditentukan - fakta yang sudah diketahui oleh Zermelo pada tahun 1913. (Pernyataan yang lebih tepat mengenai teorema Gale-Stewart adalah ini. Permainan (G) dikatakan akan ditutup jika (ada) memenangi setiap permainan (G) di mana dia belum pernah kalah pada kedudukan terhingga. Teorema menyatakan bahawa setiap permainan tertutup ditentukan. Bukti teorema pada dasarnya mudah: Marilah kita menyebut kedudukan menang untuk (forall) jika dia mempunyai strategi menang bermula dari posisi ini. Andaikan (forall) tidak mempunyai strategi menang dalam permainan, iaitu pada awalnya kedudukan tidak menang untuk (forall). Sekiranya langkah pertama adalah pergerakan (forall), setelah pergerakannya kedudukannya masih belum menang untuknya. Sekiranya langkah pertama adalah gerakan (ada), dia mesti mempunyai gerakan setelah itu kedudukan masih belum menang untuk (forall), kerana jika tidak, kedudukan sebelumnya akan menang untuk (forall). Permainan diteruskan dengan cara ini tanpa henti banyak bergerak melalui kedudukan yang tidak menang untuk (forall). Kerana permainan ditutup, (ada) menang.)Andaikan (forall) tidak mempunyai strategi menang dalam permainan, iaitu pada awalnya kedudukan tidak menang untuk (forall). Sekiranya langkah pertama adalah pergerakan (forall), setelah pergerakannya kedudukannya masih belum menang untuknya. Sekiranya langkah pertama adalah gerakan (ada), dia mesti mempunyai gerakan setelah itu kedudukan masih belum menang untuk (forall), kerana jika tidak, kedudukan sebelumnya akan menang untuk (forall). Permainan diteruskan dengan cara ini tanpa henti banyak bergerak melalui kedudukan yang tidak menang untuk (forall). Kerana permainan ditutup, (ada) menang.)Andaikan (forall) tidak mempunyai strategi menang dalam permainan, iaitu pada awalnya kedudukan tidak menang untuk (forall). Sekiranya langkah pertama adalah pergerakan (forall), setelah pergerakannya kedudukannya masih belum menang untuknya. Sekiranya langkah pertama adalah gerakan (ada), dia mesti mempunyai gerakan setelah itu kedudukan masih belum menang untuk (forall), kerana jika tidak, kedudukan sebelumnya akan menang untuk (forall). Permainan diteruskan dengan cara ini tanpa henti banyak bergerak melalui kedudukan yang tidak menang untuk (forall). Kerana permainan ditutup, (ada) menang.)Sekiranya langkah pertama adalah pergerakan (ada), dia mesti mempunyai gerakan yang mana kedudukannya masih belum menang untuk (forall), kerana jika tidak, posisi sebelumnya akan menang untuk (forall). Permainan diteruskan dengan cara ini tanpa henti banyak bergerak melalui kedudukan yang tidak menang untuk (forall). Kerana permainan ditutup, (ada) menang.)Sekiranya langkah pertama adalah gerakan (ada), dia mesti mempunyai gerakan setelah itu kedudukan masih belum menang untuk (forall), kerana jika tidak, kedudukan sebelumnya akan menang untuk (forall). Permainan diteruskan dengan cara ini tanpa henti banyak bergerak melalui kedudukan yang tidak menang untuk (forall). Kerana permainan ditutup, (ada) menang.)

Sama seperti teori permainan klasik, definisi permainan logik di atas berfungsi sebagai kuda pakaian yang boleh kita gantungkan konsep lain. Sebagai contoh adalah lazim untuk mempunyai beberapa undang-undang yang menggambarkan elemen (Omega) apa yang tersedia untuk dipilih oleh pemain pada langkah tertentu. Tegasnya penyempurnaan ini tidak perlu, kerana strategi menang tidak akan terpengaruh jika kita memutuskan sebaliknya bahawa pemain yang melanggar undang-undang kalah dengan segera; tetapi bagi banyak permainan cara melihatnya nampak tidak wajar. Di bawah ini kita akan melihat beberapa ciri tambahan lain yang boleh ditambahkan pada permainan.

Definisi permainan dan strategi di atas adalah semata-mata matematik. Oleh itu, mereka meninggalkan satu-satunya ciri permainan yang paling penting, iaitu orang memainkannya (sekurang-kurangnya secara kiasan). Para pemain berhasrat untuk menang, dan dengan mempelajari strategi yang terbuka untuk mereka, kita mempelajari tingkah laku apa yang rasional bagi seseorang yang mempunyai tujuan tertentu. Di kebanyakan permainan terdapat beberapa pemain, jadi kami dapat mempelajari apakah respons rasional terhadap tingkah laku orang lain. Dengan menyekat pergerakan pemain dan strategi yang mungkin, kita dapat mempelajari rasionalitas terikat, di mana ejen harus membuat keputusan rasional dalam keadaan maklumat, ingatan atau masa yang terhad.

Ringkasnya, permainan digunakan untuk memodelkan rasionaliti dan rasionaliti terikat. Ini bebas dari sebarang hubungan dengan logik. Tetapi beberapa logik dirancang untuk mengkaji aspek tingkah laku rasional, dan dalam beberapa tahun kebelakangan ini menjadi umum untuk menghubungkan logik ini dengan permainan yang sesuai. Lihat Bahagian 5 ('Permainan semantik untuk logik lain') dan bibliografinya.

Tetapi sehingga baru-baru ini, permainan logik dihubungkan dengan tingkah laku rasional dengan cara yang sangat berbeza. Di permukaan, logika yang bersangkutan tidak mempunyai kaitan langsung dengan tingkah laku. Tetapi ahli logik dan ahli matematik menyedari bahawa beberapa idea boleh dibuat lebih intuitif jika dihubungkan dengan tujuan yang mungkin. Sebagai contoh dalam banyak aplikasi permainan logik, gagasan utamanya adalah strategi menang untuk pemain (ada). Selalunya strategi ini (atau keberadaannya) ternyata setara dengan sesuatu kepentingan logik yang mungkin dapat ditentukan tanpa menggunakan permainan-misalnya sebagai bukti. Tetapi permainan dirasakan dapat memberikan definisi yang lebih baik kerana secara harfiah memberikan beberapa motivasi: (ada) sedang berusaha untuk menang.

Ini menimbulkan persoalan yang tidak menarik secara matematis, tetapi harus menyangkut ahli falsafah yang menggunakan permainan logik. Sekiranya kita ingin motivasi (ada) dalam permainan (G) memiliki nilai penjelasan, maka kita perlu memahami apa yang dicapai jika (ada) menang. Khususnya kita harus dapat menceritakan kisah yang realistik mengenai situasi di mana beberapa ejen yang dipanggil (ada) sedang berusaha untuk melakukan sesuatu yang dapat difahami, dan melakukannya adalah sama dengan kemenangan dalam permainan. Seperti yang dikatakan oleh Richard Dawkins, mengemukakan persoalan yang sesuai untuk permainan evolusi Maynard Smith,

Keseluruhan tujuan pencarian kami … adalah untuk mencari pelakon yang sesuai untuk memainkan peranan utama dalam metafora tujuan kami. Kami … ingin mengatakan, 'Ini untuk kebaikan …'. Pencarian kami dalam bab ini adalah untuk cara yang tepat untuk menyelesaikan ayat itu. (The Extended Phenotype, Oxford University Press, Oxford 1982, halaman 91.)

Untuk rujukan masa depan mari kita sebut ini sebagai soalan Dawkins. Dalam banyak jenis permainan logik ternyata jauh lebih sukar untuk dijawab daripada yang disedari oleh pelopor permainan ini. (Marion 2009 membincangkan lebih lanjut mengenai pertanyaan Dawkins.)

3. Permainan Semantik untuk Logik Klasik

Pada awal tahun 1930-an Alfred Tarski mengemukakan definisi kebenaran. Pengertiannya terdiri daripada syarat yang perlu dan mencukupi agar ayat dalam bahasa teori formal khas menjadi kenyataan; keadaannya yang diperlukan dan mencukupi hanya menggunakan pengertian dari sintaksis dan teori set, bersama dengan konsep primitif teori formal yang dimaksudkan. Sebenarnya Tarski mendefinisikan hubungan yang lebih umum 'formula (phi (x_1, / ldots, x_n)) adalah benar bagi unsur-unsur (a_1, / ldots, a_n)' kebenaran ayat adalah kes khas di mana (n = 0). Contohnya persoalan adakah

'Untuk semua (x) ada (y) sehingga R ((x, y))' adalah benar

mengurangkan kepada persoalan sama ada perkara berikut:

Untuk setiap objek (a) kalimat 'Ada (y) sedemikian rupa sehingga R ((a, y))' adalah benar.

Ini seterusnya mengurangkan kepada:

Untuk setiap objek (a) ada objek (b) sehingga kalimat 'R ((a, b))' adalah benar.

Dalam contoh ini, sejauh mana definisi kebenaran Tarski akan membawa kita.

Pada akhir 1950-an Leon Henkin menyedari bahawa kita secara intuitif dapat memahami beberapa ayat yang tidak dapat ditangani oleh definisi Tarski. Contohnya, hukuman yang panjang

Untuk semua (x_0) ada (y_0) sehingga untuk semua (x_1) ada (y_1) sedemikian rupa sehingga … R ((x_0, y_0, x_1, y_1, / ldots)).

Pendekatan Tarski gagal kerana rentetan pengukur pada awalnya tidak terbatas, dan kami tidak akan pernah sampai ke penghapusannya. Sebaliknya, Henkin mencadangkan, kita harus mempertimbangkan permainan di mana seseorang (forall) memilih objek (a_0) untuk (x_0), kemudian orang kedua (ada) memilih objek (b_0) untuk (y_0), kemudian (forall) memilih (a_1) untuk (x_1, / ada) memilih (b_1) untuk (y_1) dan seterusnya. Main permainan ini adalah kemenangan untuk (ada) jika dan hanya jika ayat atom tidak terhingga

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

betul. Kalimat asal adalah benar jika dan hanya jika pemain (ada) mempunyai strategi menang untuk permainan ini. Henkin dengan tegas menggunakan permainan ini hanya sebagai metafora, dan syarat kebenaran yang dicadangkannya ialah versi kalimat skema itu benar, iaitu bahawa terdapat fungsi (f_0, f_1, / ldots) sedemikian rupa untuk setiap pilihan (a_0, a_1, a_2) dan lain-lain yang kita ada

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

Tetapi keadaan ini segera diterjemahkan ke dalam bahasa permainan; fungsi Skolem (f_0) dll menentukan strategi kemenangan untuk (ada), memberitahunya bagaimana untuk memilih berdasarkan pilihan sebelumnya oleh (forall). (Terungkap beberapa saat kemudian bahawa CS Peirce telah menyarankan untuk menjelaskan perbezaan antara 'setiap' dan 'beberapa' dari segi siapa yang memilih objek; misalnya dalam kuliah Cambridge Conference keduanya tahun 1898.)

Tidak lama selepas kerja Henkin, Jaakko Hintikka menambahkan bahawa idea yang sama berlaku dengan konjungsi dan pemisahan. Kita dapat menganggap konjungsi '(phi / wedge / psi)' sebagai pernyataan yang dikuantifikasi secara universal yang menyatakan 'Setiap kalimat (phi, / psi) tahan', jadi seharusnya untuk pemain (forall) untuk memilih salah satu ayat. Seperti yang dinyatakan oleh Hintikka, untuk memainkan permainan (G (phi / wedge / psi), / forall) memilih sama ada permainan harus diteruskan sebagai (G (phi)) atau sebagai (G (psi)). Perbezaan juga menjadi penyataan kuantitatif mengenai set ayat, dan ia menandakan pergerakan di mana pemain (ada) memilih bagaimana permainan harus diteruskan. Untuk membawa pengukur ke dalam gaya yang sama, dia mengusulkan agar permainan (G (forall x / phi (x))) diteruskan dengan demikian: pemain (forall) memilih objek dan memberikan nama (a) untuk ia,dan permainan diteruskan sebagai (G (phi (a))). (Dan begitu juga dengan pengukur eksistensial, kecuali yang dipilih oleh (ada).) Hintikka juga membuat cadangan bijak untuk memperkenalkan penolakan. Setiap permainan G mempunyai permainan ganda yang sama dengan G kecuali bahawa pemain (forall) dan (wujud) diubah dalam peraturan untuk bermain dan juga peraturan untuk menang. Permainan (G (neg / phi)) adalah dwi dari (G (phi)).

Seseorang dapat membuktikan bahawa untuk mana-mana ayat perintah pertama (phi), yang ditafsirkan dalam struktur tetap (A), pemain (ada) mempunyai strategi kemenangan untuk permainan Hintikka (G (phi) jika dan hanya jika (phi) benar dalam (A) dalam pengertian Tarski. Dua ciri bukti ini menarik. Pertama, jika (phi) adalah ayat perintah pertama maka permainan (G (phi)) mempunyai panjang yang terbatas, dan oleh itu teorema Gale-Stewart memberitahu kita bahawa itu ditentukan. Kami menyimpulkan bahawa (ada) mempunyai strategi menang tepat di salah satu (G (phi)) dan yang ganda; jadi dia mempunyai strategi menang di (G (neg / phi)) jika dan hanya jika dia tidak memiliki strategi di (G (phi)). Ini menjaga penolakan. Dan kedua, jika (ada) mempunyai strategi menang untuk setiap permainan (G (phi (a))), maka setelah memilih salah satu strategi tersebut (f_a) untuk setiap (a),dia dapat menggabungkannya menjadi satu strategi kemenangan untuk (G (forall x / phi (x))) (iaitu, 'Tunggu dan lihat elemen apa yang dipilih oleh (a / forall), kemudian mainkan (f_a) '). Ini menjaga klausa untuk pengukur universal; tetapi hujah menggunakan aksioma pilihan, dan sebenarnya tidak sukar untuk melihat bahawa pernyataan bahawa definisi kebenaran Hintikka dan Tarski adalah setara dengan setara dengan aksioma pilihan (memandangkan aksioma teori set Zermelo-Fraenkel yang lain).dan sebenarnya tidak sukar untuk melihat bahawa pernyataan bahawa definisi kebenaran Hintikka dan Tarski adalah setara dengan aksioma pilihan (memandangkan aksioma teori set Zermelo-Fraenkel yang lain).dan sebenarnya tidak sukar untuk melihat bahawa pernyataan bahawa definisi kebenaran Hintikka dan Tarski adalah setara dengan aksioma pilihan (memandangkan aksioma teori set Zermelo-Fraenkel yang lain).

Sungguh membingungkan bahawa kita ada di sini dua teori ketika kalimat itu benar, dan teori tidak setara jika aksioma pilihan gagal. Sebenarnya alasannya tidak terlalu mendalam. Aksioma pilihan diperlukan bukan kerana definisi Hintikka menggunakan permainan, tetapi kerana menganggap bahawa strategi adalah deterministik, iaitu bahawa ia adalah fungsi bernilai tunggal yang tidak memberikan pilihan kepada pengguna. Cara yang lebih semula jadi untuk menerjemahkan definisi Tarski ke dalam istilah permainan adalah dengan menggunakan strategi yang tidak menentu, kadang-kadang disebut quasistrategies (lihat Kolaitis 1985 untuk perinciannya). (Namun, Hintikka 1996 menegaskan bahawa penjelasan yang benar tentang 'benar' adalah yang menggunakan strategi deterministik, dan fakta ini membenarkan aksioma pilihan.)

Pelaksanaan komputer dari permainan Hintikka ini terbukti menjadi kaedah yang sangat berkesan untuk mengajar makna ayat perintah pertama. Satu pakej seperti itu dirancang oleh Jon Barwise dan John Etchemendy di Stanford, yang disebut 'Tarski's World'. Secara bebas pasukan lain di University of Omsk membina versi Rusia untuk digunakan di sekolah untuk kanak-kanak berbakat.

Dalam versi kuliah John Locke yang diterbitkan di Oxford, Hintikka pada tahun 1973 mengemukakan persoalan Dawkins (lihat di atas) untuk permainan ini. Jawapannya adalah bahawa seseorang harus melihat permainan bahasa Wittgenstein, dan permainan bahasa untuk memahami pengukur adalah permainan yang berkisar tentang mencari dan mencari. Dalam permainan logik yang sesuai, seseorang harus menganggap (ada) sebagai Diriku dan (forall) sebagai Alam yang bermusuhan yang tidak pernah boleh dipercayai untuk mempersembahkan objek yang aku mahukan; jadi untuk memastikan mencarinya, saya memerlukan strategi menang. Kisah ini tidak pernah meyakinkan; motivasi Alam tidak relevan, dan tidak ada dalam permainan logik yang sesuai dengan pencarian. Jika dilihat kembali, agak mengecewakan kerana tidak ada yang mengambil masalah untuk mencari cerita yang lebih baik. Mungkin lebih berguna untuk memikirkan strategi kemenangan untuk (ada) di (G (phi)) sebagai semacam bukti (dalam sistem infiniter yang sesuai) bahawa (phi) adalah benar.

Kemudian Jaakko Hintikka meluaskan idea bahagian ini dalam dua arah, iaitu untuk semantik bahasa semula jadi dan permainan maklumat yang tidak sempurna (lihat bahagian seterusnya). Nama Game-Theoretic Semantics, Singkatnya GTS, telah digunakan untuk menutup kedua-dua peluasan ini.

Permainan yang dijelaskan dalam bahagian ini menyesuaikan diri secara sepele dengan logik banyak jenis: contohnya pengukur (forall x _ { sigma}), di mana (x _ { sigma}) adalah pemboleh ubah jenis (sigma), adalah arahan untuk pemain (forall) untuk memilih elemen semacam (sigma). Ini dengan segera memberi kita permainan yang sesuai untuk logik pesanan kedua, jika kita memikirkan unsur-unsur struktur sebagai satu jenis, kumpulan elemen sebagai jenis kedua, hubungan binari sebagai ketiga dan seterusnya. Ini menunjukkan bahawa kita mempunyai peraturan permainan untuk pengukur yang paling umum juga; kita dapat menemuinya dengan menterjemahkan pengkuantiti umum ke dalam logik pesanan kedua.

4. Permainan Semantik dengan Maklumat Tidak Sempurna

Dalam bahagian ini dan seterusnya kita melihat beberapa penyesuaian permainan semantik bahagian sebelumnya kepada logik lain. Dalam contoh pertama kami, logik (logik mesra kemerdekaan Hintikka dan Sandu 1997, atau lebih ringkas lagi logik JIKA) diciptakan agar sesuai dengan permainan. Lihat entri mengenai logik mesra kemerdekaan dan Mann, Sandu dan Sevenster 2011 untuk akaun logik ini dengan lebih lengkap.

Permainan di sini sama seperti di bahagian sebelumnya, kecuali bahawa kami menjatuhkan anggapan bahawa setiap pemain mengetahui sejarah permainan sebelumnya. Sebagai contoh kita boleh meminta pemain membuat pilihan tanpa mengetahui pilihan apa yang telah dibuat oleh pemain lain pada pergerakan sebelumnya. Cara klasik untuk menangani ini dalam teori permainan adalah dengan membuat sekatan pada strategi pemain. Sebagai contoh kita boleh meminta agar fungsi strategi memberitahu (ada) apa yang harus dilakukan pada langkah tertentu adalah fungsi yang domainnya adalah keluarga dari kemungkinan pilihan (forall) hanya pada gerakan pertama dan kedua; ini adalah cara untuk menyatakan bahawa (ada) tidak tahu bagaimana (forall) memilih pada pergerakan ketiga dan kemudiannya. Permainan dengan sekatan semacam ini pada fungsi strategi dikatakan sebagai maklumat yang tidak sempurna,berbanding permainan maklumat yang sempurna di bahagian sebelumnya.

Untuk membuat logik yang sesuai dengan permainan ini, kami menggunakan bahasa orde pertama yang sama seperti di bahagian sebelumnya, kecuali notasi ditambahkan pada beberapa pengukur (dan mungkin juga beberapa penghubung), untuk menunjukkan bahawa Skolem berfungsi untuk pengukur ini (atau penghubung) tidak bergantung kepada pemboleh ubah tertentu. Contohnya ayat

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

dibaca sebagai: "Untuk setiap (x) ada (y), tidak bergantung pada (x), sehingga (R (x, y))".

Terdapat tiga komen penting yang perlu dibuat mengenai perbezaan antara maklumat yang sempurna dan tidak sempurna. Yang pertama ialah teorema Gale-Stewart hanya untuk permainan maklumat yang sempurna. Anggaplah bahawa (forall) dan (wujud) memainkan permainan berikut. Pertama, (forall) memilih salah satu nombor 0 dan 1. Kemudian (ada) memilih salah satu daripada dua nombor ini. Pemain (wujud) menang jika dua nombor yang dipilih adalah sama, dan sebaliknya pemain (forall) menang. Kami menghendaki (ada), ketika dia membuat pilihannya, tidak tahu apa yang dipilih oleh (forall); jadi fungsi Skolem untuknya akan menjadi pemalar. (Permainan ini sesuai dengan kalimat IF di atas dengan (R) dibaca sebagai persamaan, dalam struktur dengan domain yang terdiri dari 0 dan 1.) Jelas bahawa pemain (ada) tidak mempunyai strategi kemenangan berterusan,dan juga pemain (forall) sama sekali tidak mempunyai strategi menang. Jadi permainan ini tidak dapat ditentukan, walaupun panjangnya hanya 2.

Salah satu yang wajar adalah bahawa pembenaran Hintikka untuk membaca negasi sebagai pendua ('pemain menukar tempat'), dalam permainannya untuk logik pesanan pertama, tidak membawa kepada logik IF. Tanggapan Hintikka adalah bahawa dualisasi adalah makna intuitif yang betul dari penolakan walaupun dalam kes pertama, jadi tidak diperlukan pembenaran.

Komen kedua adalah bahawa dalam permainan maklumat yang sempurna, strategi menang tidak boleh menggunakan semua maklumat yang ada. Sebagai contoh dalam permainan maklumat yang sempurna, jika pemain (ada) memiliki strategi menang, maka dia juga memiliki strategi menang di mana fungsi strategi hanya bergantung pada pilihan sebelumnya (forall). Ini kerana dia dapat menyusun semula pergerakannya sebelumnya menggunakan fungsi strategi sebelumnya.

Ketika Hintikka menggunakan fungsi Skolem sebagai strategi dalam permainannya untuk logika orde pertama, dia membuat strategi untuk pemain hanya bergantung pada gerakan sebelumnya dari pemain lain. (Fungsi Skolem untuk (ada) hanya bergantung pada pemboleh ubah yang dihitung secara universal.) Oleh kerana permainan adalah permainan maklumat yang sempurna, tidak ada kerugian dalam hal ini, oleh komen kedua di atas. Tetapi ketika dia beralih ke logika IF, syarat strategi bergantung hanya pada pergerakan pemain lain benar-benar membuat perbezaan. Hodges 1997 menunjukkan ini dengan menyemak notasi, sehingga misalnya ((ada y / x)) bermaksud: "Ada (y) bebas dari (x), tanpa mengira pemain mana yang memilih (x) ".

Pertimbangkan sekarang hukumannya

[(forall x) (wujud z) (ada y / x) (x = y),)

dimainkan lagi pada struktur dengan dua elemen 0 dan 1. Pemain (wujud) boleh menang seperti berikut. Untuk (z) dia memilih sama seperti pemain (forall) memilih untuk (x); kemudian untuk (y) dia memilih yang sama seperti yang dia pilih untuk (z). Strategi menang ini hanya berfungsi kerana dalam permainan ini (ada) dapat merujuk kepada pilihannya sendiri sebelumnya. Dia tidak akan mempunyai strategi menang jika pengukur ketiga adalah ((ada y / xz)), sekali lagi kerana fungsi Skolem mana pun untuk pengukur ini harus tetap. Cara (wujud) menyampaikan maklumat kepada dirinya sendiri dengan merujuk kepada pilihan sebelumnya adalah contoh fenomena memberi isyarat. John von Neumann dan Oskar Morgenstern menggambarkannya dengan contoh Bridge, di mana pemain tunggal terdiri daripada dua rakan kongsi yang harus berkongsi maklumat dengan menggunakan gerakan awam mereka untuk memberi isyarat kepada satu sama lain.

Komen ketiga adalah bahawa ada dislokasi antara idea intuitif maklumat yang tidak sempurna dan definisi permainan-teori dari segi strategi. Secara intuitif, maklumat yang tidak sempurna adalah fakta mengenai keadaan di mana permainan dimainkan, bukan mengenai strategi. Ini adalah masalah yang sangat rumit, dan terus menimbulkan salah faham mengenai IF dan logik serupa. Ambil contoh ayat

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

sekali lagi bermain pada struktur dengan elemen 0 dan 1. Secara intuitif seseorang mungkin berfikir bahawa jika (ada) tidak diizinkan untuk mengingat pada pengukur kedua apa yang dia pilih pada awalnya, maka dia hampir tidak dapat memiliki strategi yang menang. Tetapi sebenarnya dia mempunyai yang sangat mudah: 'Selalu pilih 0'!

Berbanding dengan logik pesanan pertama, logik IF tidak mempunyai komponen yang tidak akan diberikan oleh semantik permainan. Semantik permainan memberitahu kita bila ayat itu benar dalam struktur. Tetapi jika kita mengambil formula dengan (n) pemboleh ubah bebas, apa yang dinyatakan oleh formula mengenai susunan elemen struktur (n) - tupel? Dalam logik orde pertama, ia akan menentukan satu set dari mereka, iaitu hubungan (n) - ary pada struktur; definisi kebenaran Tarski menerangkan bagaimana. Adakah definisi serupa untuk formula sewenang-wenangnya logik IF? Ternyata ada satu untuk logik yang sedikit berbeza yang diperkenalkan oleh Hodges 1997, dan ia membawa kepada definisi kebenaran gaya Tarski untuk bahasa logik itu. Dengan sedikit penyesuaian definisi kebenaran ini dapat dibuat agar sesuai dengan logik IF. Tetapi untuk kedua-dua logik baru ini terdapat tangkapan:bukannya mengatakan apabila penugasan elemen untuk membebaskan pemboleh ubah menjadikan formula benar, kita mengatakan apabila sekumpulan penugasan elemen untuk membebaskan pembolehubah menjadikan formula itu benar. Väänänen 2007 menjadikan idea ini sebagai asas untuk pelbagai logik baru untuk mengkaji konsep ketergantungan (lihat entri mengenai logik pergantungan). Dalam logik ini, semantik didefinisikan tanpa permainan, walaupun inspirasi asalnya berasal dari karya Hintikka dan Sandu.

Dalam logik Väänänen adalah mudah untuk melihat mengapa seseorang memerlukan set tugasan. Dia mempunyai formula atom yang menyatakan '(x) bergantung pada (y)'. Bagaimana kita dapat menafsirkan ini dalam struktur, misalnya struktur nombor semula jadi? Tidak masuk akal sama sekali untuk bertanya sama ada 8 bergantung pada 37. Tetapi jika kita mempunyai set X pasangan nombor semula jadi yang teratur, tidak masuk akal untuk bertanya sama ada di X anggota pertama setiap pasangan bergantung pada kedua; jawapannya Ya bermaksud ada fungsi (f) sehingga setiap pasangan ((a, b)) dalam X mempunyai bentuk ((f (b), b)).

5. Permainan Semantik untuk Logik Lain

Struktur seperti berikut menimbulkan permainan yang menarik. Struktur (A) terdiri daripada satu set elemen (yang akan kita panggil keadaan, sambil menambah bahawa mereka sering disebut dunia), hubungan binari (R) pada (S) (kami akan dibaca (R) sebagai anak panah), dan keluarga (P_1, / ldots, P_n) subset dari (S). Kedua-dua pemain (forall) dan (wujud) bermain permainan G on (A), bermula dari keadaan (s) yang diberikan kepada mereka, dengan membaca formula logik yang sesuai (phi) sebagai satu set arahan untuk bermain dan untuk menang.

Oleh itu jika (phi) adalah (P_i), maka pemain (wujud) menang sekaligus jika (s) berada di (P_i), dan jika tidak pemain (forall) menang sekaligus. Rumus (psi / wedge / theta, / psi / vee / theta) dan (neg / psi) berkelakuan seperti dalam permainan Hintikka di atas; sebagai contoh (psi / wedge / theta) memerintahkan pemain (forall) untuk memilih sama ada permainan akan diteruskan seperti (psi) atau (theta). Sekiranya formula (phi) adalah (Box / psi), maka pemain (forall) memilih anak panah dari (s) ke keadaan (t) (iaitu keadaan (t) sehingga pasangan ((s, t)) berada dalam hubungan (R)), dan permainan kemudian diteruskan dari keadaan (t) mengikut arahan (psi). Peraturan untuk (Diamond / psi) adalah sama kecuali pemain (ada) membuat pilihan. Akhirnya kami mengatakan bahawa formula (phi) adalah benar di s di A jika pemain (ada) mempunyai strategi menang untuk permainan ini berdasarkan (phi) dan bermula pada (s).

Permainan ini sesuai dengan logik modal dengan cara yang hampir sama dengan permainan Hintikka seperti logik pesanan pertama. Khususnya mereka adalah salah satu cara untuk memberi semantik untuk logik modal, dan mereka setuju dengan semantik jenis Kripke yang biasa. Sudah tentu terdapat banyak jenis dan generalisasi logik modal (termasuk logik yang berkait rapat seperti logik temporal, epistemik dan dinamik), dan oleh itu permainan yang sesuai terdapat dalam pelbagai bentuk. Salah satu contoh yang menarik ialah logik teori komputer Matthew Hennessy dan Robin Milner, yang digunakan untuk menggambarkan tingkah laku sistem; di sini anak panah datang dalam lebih dari satu warna, dan bergerak di sepanjang anak panah warna tertentu menunjukkan melakukan 'tindakan' tertentu untuk mengubah keadaan. Contoh lain ialah modal yang lebih kuat (mu) - kalkulus Dexter Kozen, yang mempunyai operator titik tetap;lihat Bab 5 Stirling 2001.

Salah satu ciri menarik dari permainan ini adalah jika pemain mempunyai strategi menang dari beberapa posisi dan seterusnya, maka strategi itu tidak perlu merujuk kepada apa-apa yang terjadi sebelumnya dalam permainan. Tidak relevan pilihan apa yang dibuat sebelumnya, atau berapa banyak langkah yang telah dimainkan. Oleh itu, kita mempunyai apa yang disebut oleh para saintis komputer sebagai strategi kemenangan 'tanpa memori'.

Dalam 'logik permainan' yang berkaitan, yang diusulkan oleh Rohit Parikh, permainan yang menggerakkan kita di antara negara adalah perkara pokok dan bukan cara memberi definisi kebenaran. Permainan ini mempunyai banyak aspek menarik. Pada tahun 2003 jurnal Studia Logica menerbitkan sebuah edisi yang dikhaskan untuk mereka, disunting oleh Marc Pauly dan Parikh.

Pengaruh dari ekonomi dan sains komputer menyebabkan sebilangan ahli logik menggunakan logik untuk menganalisis pembuatan keputusan dalam keadaan ketidaktahuan separa. (Lihat contoh artikel mengenai logik epistemik.) Terdapat beberapa cara untuk mewakili keadaan pengetahuan. Salah satunya adalah menjadikannya sebagai negara atau dunia dalam jenis struktur modal yang telah kita sebutkan pada awal bahagian ini. Yang lain adalah menggunakan logik IF atau variannya. Bagaimana pendekatan ini berkaitan? Johan van Benthem 2006 mengemukakan beberapa pemikiran dan hasil mengenai persoalan yang sangat wajar ini. Lihat juga makalah Johan van Benthem, Krister Segerberg, Eric Pacuit dan K. Venkatesh dan rujukan mereka, dalam Bahagian IV 'Logik, Agensi dan Permainan' Van Benthem, Gupta dan Parikh 2011 dan catatan logik untuk menganalisis permainan untuk contoh karya terbaru di kawasan ini.

6. Permainan Belakang dan Ke Depan

Pada tahun 1930 Alfred Tarski merumuskan pengertian dua struktur (A) dan (B) yang setara pada dasarnya, iaitu, bahawa ayat perintah pertama yang sama adalah benar di (A) seperti yang berlaku di (B). Pada sebuah persidangan di Princeton pada tahun 1946, dia menjelaskan gagasan ini dan menyatakan harapannya untuk mengembangkan teori yang akan 'sedalam pengertian isomorfisme, dan lain-lain yang sekarang digunakan' (Tarski 1946).

Satu bahagian semula jadi dari teori tersebut adalah struktur yang diperlukan dan keadaan yang murni untuk dua struktur yang setara. Roland Fraïssé, seorang Perancis-Algeria, adalah yang pertama menemui keadaan yang diperlukan dan mencukupi. Ia ditemui semula beberapa tahun kemudian oleh ahli logika Kazakhstan AD Taimanov, dan ia dirumuskan semula dari segi permainan oleh ahli logik Poland Andrzej Ehrenfeucht. Permainan ini sekarang dikenali sebagai permainan Ehrenfeucht-Fraïssé, atau kadang-kadang sebagai permainan bolak-balik. Mereka ternyata menjadi salah satu idea paling serba boleh dalam logik abad kedua puluh. Mereka menyesuaikan diri dengan pelbagai logik dan struktur.

Dalam permainan bolak-balik terdapat dua struktur (A) dan (B), dan dua pemain yang biasanya dipanggil Spoiler dan Duplicator. (Nama-nama itu disebabkan oleh Joel Spencer pada awal tahun 1990-an. Baru-baru ini Neil Immerman mencadangkan Samson dan Delilah, menggunakan inisial yang sama; ini meletakkan Spoiler sebagai pemain lelaki (forall) dan Duplicator sebagai wanita (ada / Setiap langkah dalam permainan terdiri daripada pergerakan Spoiler, diikuti oleh pergerakan Duplicator. Spoiler memilih elemen salah satu daripada dua struktur, dan Duplicator mesti memilih elemen struktur yang lain. Oleh itu setelah langkah (n), dua urutan telah dipilih, satu dari (A) dan satu dari (B):

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

Kedudukan ini adalah kemenangan untuk Spoiler jika dan hanya jika beberapa formula atom (salah satu bentuk '(R (v_0, / ldots, v_ {k-1}))' atau '(mathrm {F} (v_0, / ldots, v_ {k-1}) = v_k) 'atau' (v_0 = v_1) ', atau salah satu daripadanya dengan pemboleh ubah yang berbeza) dipenuhi oleh ((a_0, / ldots, a_ { n-1})) di (A) tetapi tidak oleh ((b_0, / ldots, b_ {n-1})) di (B), atau sebaliknya. Syarat untuk Duplicator menang adalah berbeza dalam pelbagai bentuk permainan. Dalam bentuk termudah, (EF (A, B)), permainan adalah kemenangan untuk Pendua sekiranya dan hanya jika tidak ada bahagian awalnya adalah kemenangan untuk Spoiler (iaitu dia menang jika dia tidak kalah tahap terhingga). Untuk setiap nombor semula jadi (m) terdapat permainan (EF_m (A, B)); dalam permainan ini Duplicator menang setelah (m) langkah dengan syarat dia belum kalah. Semua permainan ini ditentukan, oleh Gale-Stewart Theorem. Kedua-dua struktur (A) dan (B) dikatakan setaraf-balik jika Pendua mempunyai strategi menang untuk (EF (A, B)), dan setara m jika dia mempunyai strategi kemenangan untuk (EF_m (A, B)).

Seseorang dapat membuktikan bahawa jika (A) dan (B) adalah (m) - setara untuk setiap nombor semula jadi (m), maka pada asasnya mereka setara. Sebenarnya, jika Eloise mempunyai strategi menang (tau) dalam permainan Hintikka G ((phi)) di (A), di mana sarang lingkup pengkuantifikasi (phi) kebanyakan tahap m dan Pendua mempunyai strategi menang (varrho) dalam permainan (EF_m (A, B)), kedua strategi (tau) dan (varrho) dapat disusun menjadi strategi kemenangan Eloise di G ((phi)) pada (B). Sebaliknya strategi kemenangan untuk Spoiler di (EF_m (A, B)) dapat diubah menjadi ayat perintah pertama yang benar pada salah satu (A) dan (B), dan di mana bersarang skop pengukur mempunyai tahap paling banyak (m). Oleh itu, kita mempunyai syarat yang diperlukan dan mencukupi untuk kesetaraan dasar, dan sedikit lagi.

Sekiranya (A) dan (B) setara-balik, tentu saja mereka setara; tetapi sebenarnya kesetaraan bolak-balik ternyata sama dengan kesetaraan dasar dalam logik infiniter yang jauh lebih ekspresif daripada logik orde pertama. Terdapat banyak penyesuaian permainan yang memberikan persamaan jenis lain. Sebagai contoh Barwise, Immerman dan Bruno Poizat secara bebas menggambarkan permainan di mana kedua-dua pemain mempunyai (p) sebiji kerikil bernombor masing-masing; setiap pemain harus melabel pilihannya dengan kerikil, dan dua pilihan pada langkah yang sama mesti dilabel dengan kerikil yang membawa angka yang sama. Semasa permainan berjalan, para pemain akan kehabisan kerikil dan mereka harus menggunakan kembali kerikil yang sudah digunakan. Syarat untuk Spoiler menang di posisi (dan semua kedudukan berikutnya) adalah sama seperti sebelumnya, kecuali hanya elemen yang membawa label pada kedudukan itu sahaja yang dikira. Kewujudan strategi kemenangan untuk Pendua dalam permainan ini bermaksud bahawa kedua-dua struktur bersetuju untuk ayat yang menggunakan paling banyak (p) pemboleh ubah (membenarkan pemboleh ubah ini berlaku berkali-kali).

Teori di sebalik permainan bolak-balik menggunakan sedikit andaian mengenai logik yang dimaksudkan. Akibatnya, permainan ini adalah salah satu dari beberapa teknik teori-teori yang berlaku juga pada struktur terhingga seperti yang dilakukan untuk yang tidak terbatas, dan ini menjadikannya salah satu landasan sains komputer teoritis. Seseorang dapat menggunakannya untuk mengukur kekuatan ekspresif bahasa formal, misalnya bahasa pertanyaan pangkalan data. Hasil yang biasa dikatakan, misalnya, bahawa bahasa tertentu tidak dapat membezakan antara 'genap' dan 'ganjil' kami akan membuktikannya dengan mencari, untuk setiap tahap (n) kerumitan rumus bahasa, sepasang struktur terhingga yang Duplikator mempunyai strategi kemenangan dalam permainan tahap dan ke belakang (n), tetapi salah satu strukturnya mempunyai bilangan unsur genap dan yang lain mempunyai bilangan ganjil. Ahli semantik bahasa semula jadi telah menemui permainan bolak-balik yang berguna untuk membandingkan kekuatan ekspresif pengkuantiti umum. (Lihat contoh Peters dan Westerståhl 2006 Bahagian IV.)

Terdapat juga jenis permainan bolak-balik yang sesuai dengan semantik modal kami di atas dengan cara yang sama seperti permainan Ehrenfeucht-Fraïssé yang sesuai dengan semantik permainan Hintikka untuk logik pesanan pertama. Pemain bermula dengan keadaan (s) dalam struktur (A) dan keadaan (t) dalam struktur (B). Spoiler dan Duplicator bergerak secara bergantian, seperti sebelumnya. Setiap kali dia bergerak, Spoiler memilih sama ada mahu bergerak di (A) atau di (B), dan kemudian Pendua mesti bergerak di struktur yang lain. Pergerakan selalu dibuat dengan melangkah ke depan dengan anak panah dari keadaan semasa. Sekiranya di antara mereka kedua pemain baru saja berpindah ke keadaan (s) ´ di (A) dan keadaan (t) ´ di (B), dan beberapa predikat (P_i) bertahan di hanya salah satu dari (s) ´ dan (t) ´, kemudian Pendua hilang sekaligus. Dia juga kalah jika tidak ada anak panah yang tersedia untuknya bergerak;tetapi jika Spoiler mendapati tidak ada anak panah yang tersedia untuknya bergerak di kedua struktur tersebut, maka Duplicator akan menang. Sekiranya kedua-dua pemain memainkan permainan ini dengan keadaan awal yang diberikan (s) di (A) dan (t) di (B), dan kedua-dua struktur itu mempunyai banyak keadaan, maka seseorang dapat menunjukkan bahawa Pendua mempunyai strategi menang jika dan hanya jika ayat modal yang sama berlaku di (s) di (A) seperti yang berlaku di (t) di (B).

Terdapat banyak generalisasi hasil ini, beberapa di antaranya melibatkan pengertian berikut. Mari (Z) menjadi hubungan binari yang menghubungkan keadaan (A) dengan keadaan (B). Kemudian kita sebut (Z) sebagai bimulasi antara (A) dan (B) jika Penggandaan dapat menggunakan (Z) sebagai strategi menang yang tidak menentu dalam permainan bolak-balik antara (A) dan (B) di mana pasangan pertama pergerakan kedua-dua pemain adalah memilih keadaan permulaan mereka. Dalam sains komputer, konsep bisimulasi sangat penting untuk memahami (A) dan (B) sebagai sistem; ia menyatakan bahawa kedua-dua sistem itu berinteraksi dengan persekitaran mereka dengan cara yang sama antara satu sama lain, langkah demi langkah. Tetapi sedikit sebelum para saintis komputer memperkenalkan gagasan itu, pada dasarnya konsep yang sama muncul dalam tesis PhD Johan van Benthem mengenai semantik logik modal (1976).

7. Permainan Model-teori lain

Permainan logik di bahagian ini adalah alat ahli matematik, tetapi mereka mempunyai beberapa ciri menarik secara konseptual.

7.1 Memaksa permainan

Memaksa permainan juga dikenali sebagai teori set deskriptif sebagai permainan Banach-Mazur; lihat rujukan oleh Kechris atau Oxtoby di bawah untuk maklumat lanjut mengenai latar belakang matematik. Ahli teori model menggunakannya sebagai kaedah membina struktur tanpa batas dengan sifat terkawal. Dalam kes yang paling mudah (forall) dan (wujud) memainkan apa yang disebut Model Existence Game, di mana (ada) mendakwa bahawa ayat tetap (phi) mempunyai model sementara (forall) mendakwa bahawa dia dapat memperoleh percanggahan dari (phi). Pada mulanya satu set yang tidak terhingga (C) simbol pemalar baru (a_0, a_1, a_2) dll telah diperbaiki. (wujud) mempertahankan gangguan dengan memilih satu pemisah, dan pernyataan eksistensial dengan memilih pemalar dari (C) sebagai saksi. (forall) dapat mencabar hubungan dengan memilih salah satu sambungan,dan pernyataan universal dengan memilih saksi sewenang-wenang dari (C). (ada) menang jika tidak ada ayat atom yang bertentangan dimainkan. (ada) mempunyai strategi menang (Properti Konsistensi adalah salah satu cara untuk menggambarkan strategi menang) jika dan hanya jika (phi) mempunyai model. Sebaliknya, jika (forall) mempunyai strategi menang, pohon (yang dapat dibuat terbatas) dari semua permainan menentang strategi kemenangannya adalah berkaitan dengan bukti gaya Gentzen mengenai penolakan (phi). Kaedah menganalisis ayat ini berkait rapat dengan kaedah Bethantic semantic tableaux dan Dialogical Game (lihat Bahagian 8).jika (forall) mempunyai strategi kemenangan, pokok (yang dapat dibuat hingga akhir) dari semua permainan menentang strategi kemenangannya berkaitan dengan bukti gaya Gentzen mengenai penolakan (phi). Kaedah menganalisis ayat ini berkait rapat dengan kaedah Bethantic semantic tableaux dan Dialogical Game (lihat Bahagian 8).jika (forall) mempunyai strategi kemenangan, pokok (yang dapat dibuat hingga akhir) dari semua permainan menentang strategi kemenangannya berkaitan dengan bukti gaya Gentzen mengenai penolakan (phi). Kaedah menganalisis ayat ini berkait rapat dengan kaedah Bethantic semantic tableaux dan Dialogical Game (lihat Bahagian 8).

Untuk membuat sketsa gagasan General Forcing Game, bayangkan bahawa pasukan pembina yang tidak terhingga sedang membangun rumah (A). Setiap pembangun mempunyai tugasnya sendiri untuk dilaksanakan: misalnya memasang mandi atau melekap ruang masuk. Setiap pembangun mempunyai banyak peluang untuk memasuki laman web ini dan menambahkan sejumlah bahan yang terhad ke rumah; slot ini untuk pembina disisipkan sehingga keseluruhan proses berlaku dalam urutan langkah yang dikira oleh nombor semula jadi.

Untuk menunjukkan bahawa rumah itu boleh dibina mengikut pesanan, kita perlu menunjukkan bahawa setiap pembangun secara berasingan dapat menjalankan tugas yang ditentukan, tanpa mengira apa yang dilakukan oleh pembangun yang lain. Oleh itu, kami membayangkan setiap pembangun sebagai pemain (ada) dalam permainan di mana semua pemain lain disatukan sebagai (forall), dan kami bertujuan untuk membuktikan bahawa (ada) mempunyai strategi menang untuk ini permainan. Apabila kita membuktikan ini untuk setiap pembangun secara berasingan, kita dapat membayangkan mereka akan berjaya, masing-masing dengan strategi kemenangan mereka sendiri. Mereka semua memenangi permainan masing-masing dan hasilnya adalah satu rumah yang indah.

Secara teknikal, elemen struktur (A) diperbaiki terlebih dahulu, katakan sebagai (a_0, a_1, a_2) dan lain-lain, tetapi sifat elemen-elemen ini harus diselesaikan oleh permainan. Setiap pemain bergerak dengan melemparkan satu set pernyataan atom atau negatif mengenai unsur-unsur, hanya tertakluk kepada syarat bahawa set yang terdiri daripada semua pernyataan yang dilemparkan sejauh ini mestilah konsisten dengan satu set aksioma tetap yang ditulis sebelum permainan. (Oleh itu, melemparkan kalimat atom yang ditolak (neg / phi) mempunyai kesan untuk menghalang mana-mana pemain daripada menambah (phi) di peringkat kemudian.) Pada akhir permainan bersama, kumpulan ayat atom dilemparkan mempunyai model kanonik, dan ini adalah struktur (A); ada cara memastikan bahawa ia adalah model set aksioma tetap. Kemungkinan harta P (A) dikatakan dapat dilaksanakan jika pembangun yang diberi tugas untuk menjadikan P benar (A) mempunyai strategi yang menang. Titik utama (yang pada hakikatnya disebabkan oleh Ehrenfeucht) adalah bahawa penyatuan sekumpulan harta yang boleh dilaksanakan sekali lagi dapat dilaksanakan.

Pelbagai teori model Löwenheim-Skolem dapat dibuktikan dengan menggunakan varian Permainan Memaksa. Dalam varian ini, kita tidak membina model tetapi model dari model tertentu. Kita mulakan dengan model besar (M) untuk ayat (atau sekumpulan ayat yang boleh dikira) (phi). Kemudian kami senaraikan subformula (phi) dan setiap pemain mempunyai subformula dengan pemboleh ubah percuma untuk diikuti. Tugas pemain adalah memastikan bahawa sebaik sahaja parameter subformula berlaku dalam permainan, dan ada saksi kebenaran formula dalam model besar, saksi seperti itu dimainkan. Apabila permainan selesai, submodel yang dapat dihitung (M) telah dibangun sedemikian rupa sehingga memuaskan (phi).

Nama 'memaksa' berasal dari penerapan idea-idea yang berkaitan oleh Paul Cohen untuk membina model teori set pada awal 1960-an. Abraham Robinson menyesuaikannya untuk membuat metode umum untuk membangun struktur yang dapat dihitung, dan Martin Ziegler memperkenalkan pengaturan permainan. Kemudian Robin Hirsch dan Ian Hodkinson menggunakan permainan yang berkaitan untuk menyelesaikan beberapa soalan lama mengenai algebras hubungan.

Memaksa permainan adalah contoh yang sihat untuk diingat ketika memikirkan soalan Dawkins. Mereka mengingatkan kita bahawa dalam permainan logik tidak perlu menganggap pemain sebagai lawan satu sama lain.

7.2 Permainan potong dan pilih

Dalam permainan potong dan pilih tradisional anda mengambil sekeping kek dan memotongnya menjadi dua kepingan yang lebih kecil; maka saya memilih salah satu kepingan dan memakannya, meninggalkan yang lain untuk anda. Prosedur ini seharusnya memberi tekanan kepada anda untuk memotong kek dengan adil. Ahli matematik, yang tidak memahami tujuan latihan, berkeras untuk mengulanginya. Oleh itu, saya membuat anda memotong bahagian yang saya pilih menjadi dua, kemudian saya memilih salah satu dari dua; kemudian anda memotong lagi ini, dan seterusnya selama-lamanya. Sebilangan lagi ahli matematik yang tidak berpengalaman membuat anda memotong kek menjadi lebih banyak daripada dua.

Permainan ini penting dalam teori definisi. Katakan kita mempunyai koleksi objek (A) objek dan keluarga (S) sifat; setiap harta memotong (A) ke dalam set objek yang mempunyai harta dan kumpulan yang tidak. Mari (ada) memotong, bermula dengan keseluruhan set (A) dan menggunakan harta di (S) sebagai pisau; mari (forall) memilih salah satu bahagian (yang merupakan subset dari (A)) dan mengembalikannya ke (ada) untuk memotong lagi, sekali lagi menggunakan harta di (S); dan sebagainya. Biarkan (ada) kalah sebaik sahaja (forall) memilih bahagian kosong. Kami mengatakan bahawa ((A, S)) mempunyai kedudukan paling banyak (m) jika (forall) mempunyai strategi yang memastikan bahawa (ada) akan kalah sebelum dia (m) - bergerak. Kedudukan ((A, S)) memberikan maklumat berharga mengenai keluarga subset (A) yang dapat ditentukan oleh sifat di (S).

Variasi permainan ini, yang memungkinkan sekeping dipotong menjadi potongan yang jauh lebih kecil, adalah asas dalam cabang teori model yang disebut teori kestabilan. Secara garis besar, teori 'baik' dalam erti teori kestabilan jika, setiap kali kita mengambil model (A) teori dan (S) kumpulan formula pertama dalam satu pemboleh ubah bebas dengan parameter dari (A), struktur ((A, S)) mempunyai peringkat 'kecil'. Variasi yang berbeza adalah mewajibkan bahawa pada setiap langkah, (ada) membahagi menjadi dua setiap potongan yang telah bertahan dari langkah sebelumnya, dan sekali lagi dia kehilangan sebaik sahaja salah satu serpihan yang dipotong kosong. (Dalam versi ini (forall) berlebihan.) Dengan variasi ini, kedudukan ((A), S) disebut dimensi Vapnik-Chervonenkis; tanggapan ini digunakan dalam teori pembelajaran komputasi.

7.3 Permainan di atas pokok dua fungsi pengganti

Bayangkan sebatang pokok yang telah dibina bertingkat. Di tingkat bawah terdapat simpul akar tunggal, tetapi cabang kiri dan cabang kanan muncul darinya. Di tingkat seterusnya terdapat dua nod, satu di setiap cabang, dan dari setiap simpul ini cabang kiri dan cabang kanan tumbuh. Jadi di tingkat seterusnya terdapat empat simpul, dan sekali lagi pokok bercabang ke kiri dan kanan di setiap nod ini. Terus sampai tak terhingga, pohon ini disebut pohon dua fungsi pengganti (iaitu pengganti kiri dan pengganti kanan). Mengambil nod sebagai elemen dan memperkenalkan dua simbol fungsi untuk pengganti kiri dan kanan, kami mempunyai struktur. Teorem Michael Rabin yang kuat menyatakan bahawa ada algoritma yang akan memberitahu kita, untuk setiap ayat perintah kedua monadik (phi) dalam bahasa yang sesuai untuk struktur ini,betul atau tidak (phi) betul dalam struktur. ('Monadic second-order' bermaksud logiknya seperti orde pertama, kecuali kita juga dapat mengukur lebih banyak set elemen-tetapi tidak lebih dari hubungan binari pada elemen, misalnya.)

Teorema Rabin mempunyai sejumlah akibat yang berguna. Contohnya Dov Gabbay menggunakannya untuk membuktikan kebolehtentuan beberapa logik modal. Tetapi bukti Rabin, menggunakan automata, sangat sukar untuk diikuti. Yuri Gurevich dan Leo Harrington, dan secara bebas Andrei Muchnik, menemui bukti yang lebih mudah di mana automaton adalah pemain dalam permainan.

Hasil Rabin ini adalah salah satu daripada beberapa keputusan berpengaruh yang menghubungkan permainan dengan automata. Contoh lain adalah permainan pariti yang digunakan untuk mengesahkan sifat sistem modal. Lihat sebagai contoh Stirling (2001) Bab 6; Bradfield dan Stirling (2006) membincangkan permainan pariti untuk modal (mu) - kalkulus.

8. Permainan dialog, komunikasi dan bukti

Beberapa teks abad pertengahan menggambarkan bentuk perdebatan yang disebut obligasi. Terdapat dua orang yang bersengketa, lawan dan responden. Pada awal sesi, pihak yang bersengketa akan menyetujui 'positum', biasanya pernyataan yang salah. Tugas Responden adalah memberikan jawapan yang rasional terhadap pertanyaan dari Opponens, dengan anggapan kebenaran positum; di atas semua itu dia harus mengelakkan bertentangan dengan dirinya sendiri tanpa perlu. Tugas Opponens adalah berusaha memaksa Responden menjadi kontradiksi. Oleh itu, kita secara luas mengetahui jawapan untuk pertanyaan Dawkins, tetapi kita tidak tahu peraturan permainannya! Buku teks abad pertengahan memang menggambarkan beberapa peraturan yang harus dipatuhi oleh pihak yang bersengketa. Tetapi peraturan ini bukan peraturan permainan yang ditetapkan; buku-buku tersebut merupakan panduan yang diturunkan oleh buku teks dari prinsip penaakulan yang bernas dengan contoh.(Paul of Venice membenarkan satu peraturan dengan praktik 'ahli logik, ahli falsafah, ahli geografi dan ahli teologi'.) Khususnya terbuka bagi seorang guru kewajiban untuk menemukan peraturan baru. Kesimpulan terbuka ini menunjukkan bahawa tanggungjawab bukan permainan logik dalam pengertian kita.

Tidak semua orang bersetuju dengan ayat sebelumnya. Sebagai contoh Catarina Dutilh Novaes (2007, 6) membuat pembelaan terperinci mengenai pandangan bahawa kewajipan menyajikan “kesamaan kesamaan konseptual yang luar biasa antara kerangka teori abad pertengahan dan moden”. Tetapi apa sahaja pandangan yang kita ambil mengenai persoalan ini, perbahasan ini telah mengilhami satu garis penting penyelidikan moden dalam permainan logik.

Bayangkan (ada) mengambil peperiksaan lisan dalam teori bukti. Pemeriksa memberinya hukuman dan mengajaknya untuk mula membuktikannya. Sekiranya ayat itu mempunyai bentuk

(phi / vee / psi)

maka dia berhak memilih salah satu ayat dan berkata 'OK, saya akan membuktikannya'. (Sebenarnya jika pemeriksa adalah seorang intuisi, dia mungkin menegaskan bahawa dia memilih salah satu ayat untuk dibuktikan.) Sebaliknya jika hukuman itu

(phi / baji / psi)

maka pemeriksa, sebagai pemeriksa, mungkin memilih salah satu konjungnya sendiri dan mengajaknya membuktikannya. Sekiranya dia tahu bagaimana membuktikan hubungannya maka dia pasti tahu bagaimana membuktikan konjungsi itu.

Kes (phi / rightarrow / psi) agak halus. Dia mungkin mahu memulakan dengan menganggap (phi) untuk membuat kesimpulan (psi); tetapi ada beberapa risiko kekeliruan kerana ayat-ayat yang telah ditulisnya sejauh ini semuanya harus dibuktikan, dan (phi) bukanlah perkara yang dapat dibuktikan. Pemeriksa dapat membantunya dengan mengatakan 'Saya akan menganggap (phi), dan mari kita lihat apakah anda boleh sampai ke (psi) dari sana'. Pada saat ini ada kemungkinan dia melihat cara untuk mendapatkan (psi) dengan menyimpulkan percanggahan dari (phi); jadi dia boleh mengubah jadual pemeriksa dan mengundangnya untuk menunjukkan bahawa anggapannya konsisten, dengan tujuan untuk membuktikan bahawa tidak. Simetri tidak sempurna: dia memintanya menunjukkan bahawa ayat itu benar di mana-mana, sementara dia mengajaknya menunjukkan bahawa ayat itu benar di suatu tempat. Walaupun begitu kita dapat melihat sejenis dualitas.

Idea seperti ini terletak di sebalik permainan dialektik Paul Lorenzen. Dia menunjukkan bahawa dengan sejumlah mendorong dan mendorong, seseorang dapat menulis peraturan untuk permainan yang memiliki sifat yang (ada) mempunyai strategi menang jika dan hanya jika kalimat yang dia sampaikan pada awalnya adalah teorema logik intuisi. Dalam gerakan menuju perdebatan abad pertengahan, dia memanggil (ada) Penyokong dan pemain lain sebagai Lawan. Hampir seperti pada kewajiban abad pertengahan, Lawan menang dengan mendorong Penyokong ke titik di mana satu-satunya gerakan yang ada padanya adalah percanggahan diri yang terang-terangan.

Lorenzen mendakwa bahawa permainannya memberikan justifikasi untuk logik intuisi dan klasik (atau dalam kata-katanya, menjadikannya 'gerechtfertigt', Lorenzen (1961,196)). Malangnya sebarang 'pembenaran' melibatkan jawapan yang meyakinkan untuk pertanyaan Dawkins, dan Lorenzen ini tidak pernah diberikan. Sebagai contoh, dia bercakap tentang gerakan sebagai 'serangan', walaupun ketika (seperti pilihan pemeriksa di (phi / wedge / psi) di atas) mereka lebih mirip pertolongan daripada permusuhan.

Logik dialog kemasukan memberikan akaun yang lebih lengkap mengenai permainan Lorenzen dan sejumlah varian yang lebih baru. Dalam bentuknya sekarang (Januari 2013) mengesampingkan tuntutan Lorenzen tentang membenarkan logik. Sebaliknya ia menggambarkan permainan sebagai penyediaan semantik untuk logik (satu titik yang pasti disetujui oleh Lorenzen), dan menambah bahawa untuk memahami perbezaan antara logik, dapat membantu membandingkan semantik mereka.

Dari sudut pandang ini, permainan Lorenzen berdiri sebagai paradigma penting dari apa yang disebut oleh teori bukti baru-baru ini sebagai semantik bukti. Semantik bukti memberikan 'makna' bukan hanya kepada gagasan yang dapat dibuktikan, tetapi untuk setiap langkah terpisah dalam bukti. Ini menjawab soalan 'Apa yang kita capai dengan membuat langkah ini sebagai bukti?' Selama tahun 1990-an sebilangan pekerja di akhir logik sains komputer mencari permainan yang sesuai dengan logik linier dan beberapa sistem bukti lain dengan cara yang sama seperti permainan Lorenzen dengan logik intuisi. Andreas Blass, dan kemudian Samson Abramsky dan rakan-rakannya, memberikan permainan yang sesuai dengan bahagian logik linier, tetapi pada masa penulisan kita belum memiliki persamaan yang sempurna antara permainan dan logik. Contoh ini sangat menarik kerana jawapan kepada soalan Dawkins harus memberikan tafsiran intuitif mengenai hukum logik linier, suatu perkara yang sangat diperlukan oleh logik ini. Permainan Abramsky et al. bercerita mengenai dua sistem berinteraksi. Tetapi ketika dia memulakan dengan permainan di mana para pemain bergilir-gilir dengan sopan, Abramsky kemudian membenarkan para pemain untuk bertindak 'secara tersebar, tidak segerak', dengan memperhatikan satu sama lain hanya ketika mereka memilih. Permainan ini tidak lagi dalam format permainan logik yang normal, dan tafsiran kehidupan sebenar mereka menimbulkan pelbagai persoalan baru. Tetapi ketika dia memulakan dengan permainan di mana para pemain bergilir-gilir dengan sopan, Abramsky kemudian membenarkan para pemain untuk bertindak 'secara tersebar, tidak segerak', dengan memperhatikan satu sama lain hanya ketika mereka memilih. Permainan ini tidak lagi dalam format permainan logik yang normal, dan tafsiran kehidupan sebenar mereka menimbulkan pelbagai persoalan baru. Tetapi ketika dia bermula dengan permainan di mana para pemain bergilir-gilir dengan sopan, Abramsky kemudian membenarkan pemain untuk bertindak 'dengan cara yang tidak diedarkan dan tidak segerak', dengan memperhatikan satu sama lain hanya ketika mereka memilih. Permainan ini tidak lagi dalam format permainan logik yang normal, dan tafsiran kehidupan sebenar mereka menimbulkan pelbagai persoalan baru.

Giorgi Japaridze telah mencadangkan 'logik pengiraan' untuk mempelajari pengiraan. Sintaksnya adalah logik pesanan pertama dengan beberapa item tambahan yang mengingatkan pada logik linear. Semantiknya adalah dari segi permainan semantik dengan beberapa ciri yang tidak biasa. Contohnya, tidak selalu ditentukan pemain mana yang membuat langkah seterusnya. Gagasan fungsi strategi tidak lagi memadai untuk menggambarkan pemain; sebaliknya Japaridze menerangkan cara membaca pemain kedua (pemain (ada) dalam notasi kami) sebagai sejenis mesin pengkomputeran. Maklumat lebih lanjut terdapat di laman webnya.

Kumpulan permainan keluarga lain yang sama dengan Lorenzen adalah permainan bukti Pavel Pudlak 2000. Di sini pihak lawan (disebut Perwira) berperanan sebagai pengacara di pengadilan, yang mengetahui bahawa Penyokong (disebut Adversary) adalah bersalah atas beberapa kesalahan. Penyokong akan menegaskan bahawa dia tidak bersalah, dan bersedia untuk berbohong untuk membela diri. Tujuan lawan adalah untuk memaksa Proponent untuk bertentangan dengan sesuatu yang dicatat oleh Proponent sebelumnya; tetapi Lawan menyimpan catatan dan (seperti dalam permainan kerikil di atas) dia kadang-kadang harus menjatuhkan item dari catatan kerana kekurangan ruang atau ingatan. Pertanyaan pentingnya bukan apakah lawan mempunyai strategi menang (diasumsikan sejak awal dia memiliki strategi), tetapi berapa banyak memori yang dia perlukan untuk catatannya. Permainan ini adalah alat yang berguna untuk menunjukkan batas atas dan bawah pada panjang bukti dalam pelbagai sistem bukti.

Jenis permainan logik lain yang membenarkan pembohongan adalah Ulam's Game with Lies. Di sini satu pemain memikirkan nombor dalam julat tertentu. Tujuan pemain kedua adalah untuk mengetahui berapa nombor itu, dengan bertanya kepada pemain pertama ya / tidak soalan; tetapi pemain pertama dibenarkan untuk memberitahu sebilangan besar pembohongan dalam jawapannya. Seperti dalam permainan Pudlak, sudah tentu ada strategi kemenangan untuk pemain kedua, tetapi persoalannya adalah betapa sukarnya pemain ini bekerja untuk menang. Ukuran kali ini bukan ruang atau ingatan tetapi masa: berapa banyak soalan yang harus dia ajukan? Cignoli et al. 2000 Bab 5 mengaitkan permainan ini dengan logik yang bernilai tinggi.

Untuk kembali sejenak kepada Lorenzen: dia gagal membezakan antara pendirian yang berbeza yang mungkin diambil oleh seseorang dalam argumen: menyatakan, menganggap, mengakui, bertanya, menyerang, melakukan diri sendiri. Sama ada mustahil untuk mendefinisikan semua pengertian ini tanpa mengandaikan logik adalah titik pertimbangan. Tetapi tidak kisah; penyempurnaan permainan Lorenzen di sepanjang garis ini dapat berfungsi sebagai pendekatan untuk logik informal, dan terutama untuk penyelidikan yang bertujuan untuk sistematisasi kemungkinan struktur argumen tidak formal yang tepat. Pada pandangan ini lihat Walton dan Krabbe 1995. Kertas kerja di Bench-Capon dan Dunne 2007 juga relevan.

Bibliografi

Sebilangan makalah mani oleh Henkin dan Lorenzen, dan beberapa makalah yang dikutip di bawah, terdapat dalam koleksi Metode Infinitistik (Prosiding Simposium Pengasas Matematik, Warsawa, 2-9 September 1959), Oxford: Pergamon Press, 1961 Penyunting tidak disebutkan namanya.

Permainan dalam Sejarah Logik

  • Dutilh Novaes, Catarina, 2007, Memformalkan Teori Logik Abad Pertengahan: Suppositio, Consequentiae and Obligationes, New York: Springer-Verlag.
  • Hamblin, Charles, 1970, Fallacies, London: Methuen.
  • Hilbert, David, 1967, "Die Grundlagen der Mathematik", diterjemahkan sebagai "Asas-asas matematik," dalam Jean van Heijenoort (ed.), Dari Frege ke Gödel, Cambridge Mass.: Harvard University Press, hlm. 464–479.
  • Paul of Venice, Logica Magna II (8), Tractatus de Obligationibus, E. Jennifer Ashworth (ed.), New York: Akademi British dan Oxford University Press, 1988.
  • Weyl, Hermann, 1925–7, "Die heutige Erkenntnislage in der Mathematik,", diterjemahkan sebagai "Situasi epistemologi semasa dalam matematik" dalam Paolo Mancosu, Dari Brouwer ke Hilbert: Perbahasan mengenai Asas Matematik pada tahun 1920-an, New York: Oxford University Press, 1988, hlm. 123–142.
  • Zermelo, Ernst, 1913, “Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels,” dalam EW Hobson dan AEH Love (ed.), Prosiding Kongres Matematik Antarabangsa Kelima, Jilid II, Cambridge: Cambridge University Press.

Permainan untuk Logik Pengajaran

  • Barwise, Jon dan John Etchemendy, 1995, The Language of First-Order Logic, termasuk Tarski's World 3.0, Cambridge: Cambridge University Press.
  • Carroll, Lewis, 1887, Permainan Logik, London: Macmillan.
  • Dienes, Zoltan P., dan EW Golding, 1966, Pembelajaran Logik, Permainan Logik, Harlow: Persatuan Bekalan Pendidikan.
  • Havas, Katalin, 1999, “Belajar berfikir: Logik untuk kanak-kanak,” dalam Prosiding Kongres Falsafah Dunia Kedua Puluh (Jilid 3: Falsafah Pendidikan), David M. Steiner (ed.), Bowling Green Ohio: Bowling Green State Falsafah Universiti, ms 11–19.
  • Nifo, Agostino, 1521, Dialectica Ludicra (Logik sebagai permainan), Florence: Bindonis.
  • Weng, Jui-Feng, dengan Shian-Shyong Tseng dan Tsung-Ju Lee, 2010, "Mengajar logika Boolean melalui pengaturan aturan permainan," Transaksi IEEE, Teknologi Pembelajaran, 3 (4): 319–328. [Menggunakan permainan Pac-Man untuk mengajar logik Boolean kepada pelajar sekolah menengah pertama.]

Permainan Logik

  • Gale, David dan FM Stewart, 1953, "Permainan tanpa batas dengan maklumat yang sempurna," dalam Sumbangan untuk Teori Permainan II (Annals of Mathematics Studies 28), HW Kuhn dan AW Tucker (eds.), Princeton: Princeton University Press, pp 245–266.
  • Kechris, Alexander S., 1995, Teori Set Deskriptif Klasik, New York: Springer-Verlag.
  • Marion, Mathieu, 2009, "Mengapa bermain permainan logik ?," dalam edisi Ondrej Majer, Ahti-Veikko Pietarinen, dan Tero Tulenheimo., Permainan: Logika Penyatuan, Bahasa dan Falsafah, New York: Springer-Verlag, hlm. 3-25.
  • Osbourne, Martin J. dan Ariel Rubinstein, 1994, Kursus dalam Teori Permainan, Cambridge: MIT Press.
  • Väänänen, Jouko, 2011, Model dan Permainan, Cambridge: Cambridge University Press.
  • van Benthem, Johan, 2011, Dinamika logik maklumat dan interaksi, Cambridge: Cambridge University Press, 2011.
  • –––, 2014, Logik dalam permainan, Cambridge, MA: MIT Press.

Permainan Semantik untuk Logik Klasik

  • Henkin, Leon, 1961, "Beberapa pernyataan mengenai formula panjang yang panjang," dalam Kaedah Infinitistik, op. cit., hlm.167–183.
  • Hintikka, Jaakko, 1973, Logik, Permainan Bahasa dan Maklumat: Tema Kantian dalam Falsafah Logik, Oxford: Clarendon Press.
  • Hintikka, Jaakko, 1996, The Principles of Mathematics Revisited, New York: Cambridge University Press. [Lihat contoh halaman 40, 82 mengenai aksioma pilihan.]
  • Hodges, Wilfrid, 2001, “Elementary Predicate Logic 25: Skolem Functions,” dalam Dov Gabbay, dan Franz Guenthner (eds.), Buku Panduan Logik Falsafah I, edisi ke-2, Dordrecht: Kluwer, hlm. 86–91. [Bukti kesetaraan permainan dan semantik Tarski.]
  • Kolaitis, Ph. G., 1985, "Kuantiti permainan," dalam J. Barwise dan S. Feferman (ed.), Model-Teoretik Logik, New York: Springer-Verlag, hlm. 365-421.
  • Peirce, Charles Sanders, 1898, Penalaran dan Logik Perkara: Kuliah Persidangan Cambridge tahun 1898, ed. Kenneth Laine Ketner, Cambridge Mass., Harvard University Press, 1992.

Permainan Semantik dengan Maklumat Tidak Sempurna

  • Hintikka, Jaakko dan Gabriel Sandu, 1997, "Semantik teori-permainan," dalam Johan van Benthem dan Alice ter Meulen (ed.), Buku Panduan Logik dan Bahasa, Amsterdam: Elsevier, hlm. 361–410.
  • Hodges, Wilfrid, 1997, “Semantik komposisi untuk bahasa maklumat yang tidak sempurna,” Logic Journal of the IGPL, 5: 539–563.
  • Janssen, Theo MV dan Francien Dechesne, 2006, "Isyarat: perniagaan yang rumit," dalam J. van Benthem et al. (eds.), Zaman Logik Alternatif: Menilai Falsafah Logik dan Matematik Hari Ini, Dordrecht: Kluwer, hlm. 223–242.
  • Mann, Allen L., Gabriel Sandu, dan Merlin Sevenster, 2011, Logik Mesra Kemerdekaan: Pendekatan Teoretik Permainan (London Mathematical Society Lecture Note Series 386), Cambridge: Cambridge University Press.
  • von Neumann, John dan Oskar Morgenstern, 1944, Teori Permainan dan Tingkah Laku Ekonomi, Princeton: Princeton University Press.
  • Väänänen, Jouko, 2007, Logic Dependence: Pendekatan Baru untuk Logik Mesra Kemerdekaan, Cambridge: Cambridge University Press.

Permainan Semantik untuk Logik Lain

  • Bradfield, Julian dan Colin Stirling, 2006, "Modal mu-calculi," dalam P. Blackburn et al. (eds.), Buku Panduan Modal Logic, Amsterdam: Elsevier, hlm. 721–756.
  • Dekker, Paul, dan Marc Pauly (ed.), 2002, Jurnal Logik, Bahasa dan Maklumat, 11 (3): 287–387. [Isu khas mengenai Logik dan Permainan.]
  • Hennessy, Matthew, dan Robin Milner, 1985, “Undang-undang aljabar untuk ketidakpastian dan kesesuaian,” Jurnal ACM, 32: 137–162.
  • Parikh, Rohit, 1985, "Logik permainan dan aplikasinya," dalam Marek Karpinski dan Jan van Leeuwen (ed.), "Topik dalam Teori Pengiraan," Annals of Discrete Mathematics, 24: 111-140.
  • Pauly, Marc, dan Rohit Parikh (ed.), 2003, Studia Logica, 72 (2): 163–256 [Isu khas mengenai Logik Permainan.]
  • Stirling, Colin, 2001, Modal dan Temporal Properties of Processes, New York: Springer-Verlag.
  • van Benthem, Johan, 2006, "Logik epistemik permainan IF," dalam Randall Auxier dan Lewis Hahn (ed.), Filosofi Jaakko Hintikka, Chicago: Open Court ms 481–513.
  • van Benthem, Johan bersama Amitabha Gupta dan Rohit Parikh, 2011, Bukti, Pengiraan dan Agensi, Dordrecht: Springer-Verlag.

Permainan Belakang dan Ke Depan

  • Blackburn, Patrick bersama Maarten de Rijke dan Yde Venema, 2001, Modal Logic, Cambridge: Cambridge University Press.
  • Doets, Kees, 1996, Teori Model Asas, Stanford: Penerbitan CSLI dan FoLLI.
  • Ebbinghaus, Heinz-Dieter dan Jörg Flum, 1999, Teori Model Terhingga, edisi ke-2, New York: Springer.
  • Ehrenfeucht, Andrzej, 1961, “Aplikasi permainan untuk masalah kelengkapan untuk teori formal,” Fundamenta Mathematicae, 49: 129–141.
  • Grädel, Erich dengan Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, dan Scott Weinstein, 2007, Teori Model Terhingga, Berlin: Springer-Verlag.
  • Libkin, Leonid, 2004, Elemen Teori Model Terhingga, 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 dan Dag Westerståhl, 2006, Quantifiers in Language and Logic, Oxford: Clarendon Press.
  • Tarski, Alfred, 1946, “Ucapan di Persidangan Bicentennial Universiti Princeton mengenai Masalah Matematik (17-19 Disember 1946),” Hourya Sinaceur (ed.), Buletin Logik Simbol, 6 (2000): 1–44.
  • van Benthem, Johan, 2001, “Correspondence Theory,” dalam Dov Gabbay dan Franz Guenthner (ed.), Buku Panduan Logik Falsafah III, edisi ke-2, Dordrecht: Kluwer.

Permainan Model-Teori lain

  • Anthony, Martin, dan Norman Biggs, 1992, Teori Pembelajaran Komputasi, Cambridge: Cambridge University Press. [Untuk dimensi Vapnik-Chervonenkis.]
  • Gurevich, Yuri dan Leo Harrington, 1984, "Pohon, automata, dan permainan," dalam HR Lewis (ed.), Prosiding Simposium ACM pada Teori Pengkomputeran, San Francisco: ACM, hlm. 171–182.
  • Hirsch, Robin dan Ian Hodkinson, 2002, Relasi Algebras oleh Games, New York: Belanda Utara.
  • Hodges, Wilfrid, 1985, Building Model by Games, Cambridge: Cambridge University Press.
  • Hodges, Wilfrid, 1993, Model Theory, Cambridge: Cambridge University Press.
  • Oxtoby, JC, 1971, Ukur dan Kategori, New York: Springer-Verlag.
  • Ziegler, Martin, 1980, "Algebraisch abgeschlossene Gruppen," dalam SI Adian et al. (eds.), Word Problems II: The Oxford Book, Amsterdam: North-Holland, hlm. 449–576.

Permainan Dialog, Komunikasi dan Bukti

  • Abramsky, Samson dan Radha Jagadeesan, 1994, "Permainan dan kelengkapan penuh untuk logik linear pendaraban," Jurnal Logik Simbolik, 59: 543-574.
  • Abramsky, Samson dan Paul-André Melliès, 1999, "Permainan serentak dan kelengkapan penuh," dalam Prosiding Simposium Antarabangsa Keempat Belas mengenai Logik dalam Sains Komputer, Akhbar Sains Komputer IEEE, hlm. 431–442.
  • Bench-Capon, TJM dan Paul E. Dunne, 2007, “Argumentasi dalam kecerdasan buatan,” Kecerdasan Buatan, 171: 619–641. [Pengenalan koleksi kaya kertas dengan tema yang sama di halaman 642-937.]
  • Blass, Andreas, 1992, “Semantik permainan untuk logik linier,” Annals of Pure and Applied Logic, 56: 183–220.
  • Cignoli, Roberto LO, Itala ML D'Ottaviano, dan Daniele Mundici, 2000, Algebra Yayasan Penalaran Berharga, Dordrecht: Kluwer.
  • Felscher, Walter, 2001, “Dialog sebagai landasan untuk logik intuisi,” dalam Dov Gabbay dan Franz Guenthner (ed.), Buku Panduan Logik Falsafah V, edisi ke-2, Dordrecht: Kluwer.
  • Hodges, Wilfrid dan Erik CW Krabbe, 2001, “Asas dialog,” Prosiding Masyarakat Aristotelian (Volume Tambahan), 75: 17–49.
  • Japaridze, Giorgi, 2003, "Pengenalan logik pengiraan," Annals of Mure and Applied Logic, 123: 1–99.
  • Lorenzen, Paul, 1961 "Ein dialogis Konstruktivitätskriterium," dalam Infinitistic Methods, op. cit., 1961, hlm.193–200.
  • Pudlak, Pavel, 2000, “Bukti sebagai permainan,” Bulanan Matematik Amerika, 107 (6): 541–550.
  • Walton, Douglas N. dan Erik CW Krabbe, 1995, Komitmen dalam Dialog: Konsep Asas Penalaran Interpersonal, Albany: State University of New York Press.

Alat Akademik

ikon sep lelaki
ikon sep lelaki
Cara memetik entri ini.
ikon sep lelaki
ikon sep lelaki
Pratonton versi PDF entri ini di Friends of the SEP Society.
ikon inpho
ikon inpho
Cari topik entri ini di Projek Ontologi Falsafah Internet (InPhO).
ikon kertas phil
ikon kertas phil
Bibliografi yang dipertingkatkan untuk entri ini di PhilPapers, dengan pautan ke pangkalan data.

Sumber Internet Lain

Disyorkan: