Lokaalisuus ja sisäänrakennetut relaatiot
Liuska, Ville (2024)
2024
Matematiikan maisteriohjelma - Master´s Programme in Mathematics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2024-06-26
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202406257381
https://urn.fi/URN:NBN:fi:tuni-202406257381
Tiivistelmä
Tässä tutkielmassa tarkastellaan predikaattilogiikan ilmaisuvoimaa, kun keskitytään tarkastelemaan pelkästään äärellisiä malleja. Eräs tapa tarkastella jonkin logiikan ilmaisuvoimaa on tutkia minkä tyyppisiä kyselyitä kyseisessä logiikassa voidaan määritellä. Eräs käyttökelpoisimmista kyselyiden ominaisuuksista määriteltävyyden kannalta on kyselyn lokaalisuus. Kyselyn lokaalisuus tarkoittaa sitä, että kysely ei kykene erottamaan sellaisia malleja toisistaan, joiden paikalliset piirteet vastaavat toisiaan.
Tutkielmassa todistetaan, että predikaattilogiikka on lokaali logiikka, joka tarkoittaa sitä, että predikaattilogiikassa voidaan pelkästään esittää lokaaleja kyselyitä. Predikaattilogiikan lokaalisuus myös mahdollistaa suoraviivaisen tavan osoittaa määrittelemättömyystuloksia predikaattilogiikassa. Kyselyn lokaalisuus on myös tärkeä ominaisuus tietokantakyselyiden kannalta, sillä usein lokaalin kyselyn suorittaminen vaatii vähemmän aikaa kuin sellainen kyselyn, joka ei ole lokaali.
Tutkielman lopussa tarkastellaan määriteltävyyttä arb-invariantissa predikaattilogiikassa. Arb-invariantti predikaattilogiikka on predikaattilogiikan laajennus, jonka ilmaisuvoimaa vastaa laskennan vaativuusluokka AC0. Kieli kuuluu luokkaan AC0, jos kieli voidaan hyväksyä sellaisella piiriperheellä, jossa jokaisen piirin syvyys on vakio, ja lisäksi jokaisen piirin koko on polynominen suhteessa syötteen kokoon. Vaativuusluokan AC0 ja arb-invariantin predikaattilogiikan välisellä yhteydellä tutkielmassa todistetaan määriteltävyyteen liittyviä tuloksia arb-invarianteille kyselyille.
Tutkielmassa todistetaan, että predikaattilogiikka on lokaali logiikka, joka tarkoittaa sitä, että predikaattilogiikassa voidaan pelkästään esittää lokaaleja kyselyitä. Predikaattilogiikan lokaalisuus myös mahdollistaa suoraviivaisen tavan osoittaa määrittelemättömyystuloksia predikaattilogiikassa. Kyselyn lokaalisuus on myös tärkeä ominaisuus tietokantakyselyiden kannalta, sillä usein lokaalin kyselyn suorittaminen vaatii vähemmän aikaa kuin sellainen kyselyn, joka ei ole lokaali.
Tutkielman lopussa tarkastellaan määriteltävyyttä arb-invariantissa predikaattilogiikassa. Arb-invariantti predikaattilogiikka on predikaattilogiikan laajennus, jonka ilmaisuvoimaa vastaa laskennan vaativuusluokka AC0. Kieli kuuluu luokkaan AC0, jos kieli voidaan hyväksyä sellaisella piiriperheellä, jossa jokaisen piirin syvyys on vakio, ja lisäksi jokaisen piirin koko on polynominen suhteessa syötteen kokoon. Vaativuusluokan AC0 ja arb-invariantin predikaattilogiikan välisellä yhteydellä tutkielmassa todistetaan määriteltävyyteen liittyviä tuloksia arb-invarianteille kyselyille.