Signalointi IF-logiikassa

Abstract

Tutkielman aiheena on IF-logiikka (’Independence-Friendly logic’) ja siinä esiintyvä signaloinniksi kutsuttu ilmiö. IF- logiikka on tavallisen ensimmäisen kertaluvun predikaattilogiikan laajennus, jossa voidaan esittää monipuolisemmin kvanttoreiden välisiä riippumattomuuksia. Tutkielmassa käytetään peliteoreettista semantiikkaa, jossa logiikan kaavat tulkitaan kahden pelaajan, verifioijan ja falsifioijan pelaamana semanttisena pelinä.

Peliteoreettinen semantiikka määritellään ensin ensimmäisen kertaluvun logiikalle. Logiikan kaavoille merkityksen antava semanttinen peli määritellään ja annetaan pelin voittostrategiaan nojaava peliteoreettinen totuusmääritelmä. Tämän jälkeen esitellään IFlogiikan syntaksi ja riippumattomien kvanttorien vaikutus peliteoreettiseen semantiikkaan. Erona on, että IF-logiikan kaavojen semanttisissa peleissä pelaajien informaatiota pelin aiemmista siirroista voidaan rajoittaa.

Signaloinnilla tarkoitetaan sitä, että pelaaja välittää itselleen omien siirtojensa avulla sellaista informaatiota, jota hän ei jonkin myöhemmän siirtonsa aikana saisi tietää. Tutkielmassa tarkastellaan erilaisia signaloinnin muotoja: signalointia ylimääräisten kvanttorien avulla, signalointia konnektiivien avulla sekä mahdollisuutta hyödyntää vastapelaajan siirtoja signaloinnin tapaiseen informaatiorajoitusten kiertämiseen.

Tutkielman lopuksi tarkastellaan IF- logiikan ilmaisuvoimaa ja osoitetaan, että IF-logiikka on ilmaisuvoimaisempi kuin ensimmäisen kertaluvun logiikka. Signaloinnin mahdollisuus on yksi tekijä, jonka ansiosta IF-logiikka on ilmaisuvoimaltaan yhtä vahva kuin eksistentiaalinen toisen kertaluvun logiikka.