Counting with majority quantifiers

Näytä kaikki kuvailutiedot

Permalink

http://urn.fi/URN:NBN:fi-fe201804208631
Julkaisun nimi: Counting with majority quantifiers
Tekijä: Koskinen, Miikka
Muu tekijä: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Matematiikan ja tilastotieteen laitos
Opinnäytteen taso: pro gradu -tutkielmat
Tiivistelmä: Työssä tarkastellaan majoriteettikvanttorien ilmaisuvoimaa sanamallien kontekstissa. Kuten eksistenssikvanttori (∃) ja universaalikvanttori (∀), majoriteettikvanttori on looginen kvanttori. Sillä voidaan ilmaista väitteen pätevän yli puolelle tarkasteltavan mallin perusjoukon alkioista. Deskriptiivisen vaativuusteorian näkökulmasta uniformi TC⁰-piirivaativuusluokka vastaa ensimmäisen kertaluvun logiikkaa yhteenlaskulla, kertolaskulla ja majoriteettikvanttorilla varustettuna. Työssä tutkitaan TC⁰-luokan sisäistä rakennetta rajoittamalla tarkastelu loogiseen fragmenttiin, jossa käyttettävissä on vain majoriteettikvanttori ja järjestysrelaatio. Työssä osoitetaan, että sekä eksistenssi- että universaalikvanttoria voidaan simuloida majoriteettikvanttorin ja järjestysrelaation avulla. Myös yhteenlasku ja perusjoukon parillisuus ovat ilmaistavissa. Sen sijaan kertolasku ei ole ilmastavissa yksipaikkaisella majoriteettikvanttorilla. Lisäksi työssä osoitetaan, että kertolasku voidaan ilmaista kaksipaikkaisella majoriteettikvanttorilla. Tästä seuraa, että kaksipaikkainen majoriteettikvanttori on aidosti voimakkaampi kuin yksipaikkainen majoriteettikvanttori.
URI: URN:NBN:fi-fe201804208631
http://hdl.handle.net/10138/273540
Päiväys: 2018-09-24
Oppiaine: Mathematics
Matematiikka
Matematik


Tiedostot

Tiedosto(t) Koko Formaatti Näytä

Tähän julkaisuun ei ole liitetty tiedostoja

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot