Algebraic Fragments of First-Order Logic

Abstract

Tämän tutkielman tarkoitus on käsitellä algebrallista lähestymistapaa ensimmäisen kertaluvun logiikan fragmenttien luokitteluun niiden ratkeavuuden perusteella. Tutkielman alussa esittelemme relaatio-operaattorin käsitteen, ja näytämme, kuinka sen avulla voidaan määritellä algebrallisesti logiikoita. Osoitamme myös, kuinka ensimmäisen kertaluvun logiikan voi määritellä tätä kautta algebrallisesti käyttämällä vain äärellisen montaa relaatio-operaattoria. Tämän jälkeen siirrymme tarkastelemaan ensimmäisen kertaluvun logiikan fragmentteja. Osoitamme, että monet jo aikaisemmin tunnetut ensimmäisen kertaluvun logiikan fragmentit voidaan myös määritellä algebrallisesti ja jopa niin, että fragmentin ja sitä vastaavan algebran toteutuvuusongelman laskennallinen vaativuus on täsmälleen sama.

Seuraavaksi tarkastelemme erilaisten algebrallisesti määrättyjen fragmenttien toteutuvuusongelman kompleksisuutta. Aloitamme tarkastelemalla erään ensimmäisen kertaluvun logiikan algebrallisen karakterisoinnin fragmenttien toteutuvuusongelmien laskennallista vaativuutta. Tarkemmin sanottuna tarkastelemme, kuinka algebrallisen fragmentin toteutuvuusongelman laskennallinen vaativuus muuttuu, mikäli poistamme joitakin relaatio-operaattoreita sen syntaktista. Saamme luokiteltua melkein täydellisesti näin syntyvät fragmentit niiden laskennallisen vaativuuden mukaan.

Tämän jälkeen tutkimme järjestetyn logiikan ja sen laajennusten toteutuvuusongelmien laskennallista vaativuutta. Järjestetyssä logiikassa rajoitetaan muuttujien permutointia ja järjestystä, jossa niitä voidaan kvantifioida. Osoittautuu, että tutkielmassa käytetty algebrallinen lähestymistapa soveltuu poikkeuksellisen hyvin tämän kaltaisten fragmenttien tutkimiseen, sillä näiden logiikoiden syntaksi on luonnollisempaa esittää siten, että kaavoissa ei esiinny ollenkaan muuttujia. Onnistumme määrittämään järjestetyn logiikan toteutuvuusongelman tarkan kompleksisuuden, jonka lisäksi paikanamme tarkan rajan sille, kuinka paljon järjestetyn logiikan syntaktisia rajoituksia voidaan nostaa sillä tavalla, että logiikka pysyy ratkeavana.

Tutkielman lopussa tarkastelemme yleisellä tasolla ensimmäisen kertaluvun logiikan toteutuvuusongelmaa. Aloitamme osoittamalla, että annetun ensimmäisen kertaluvun logiikan fragmentin -- eli sen rekursiivinen osajoukon -- ratkeavuuden selvittämminen on Sigma-0-3 täydellinen ongelma. Tämän jälkeen tarkastelemme ilmaisuvoiman ja ratkeavuuden välistä suhdetta ensimmäisen kertaluvun logiikan fragmenttien tapauksessa. Osoitamme esimerkiksi, että ei ole olemassa ilmaisuvoiman suhteen maksimaalista ratkeavaa ensimmäisen kertaluvun logiikan fragmenttia.