Modal Logics and Bisimulation Invariance

Show simple item record

dc.contributor Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta fi
dc.contributor University of Helsinki, Faculty of Science en
dc.contributor Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten sv
dc.contributor.author Sandström, Max
dc.date.issued 2019
dc.identifier.uri URN:NBN:fi:hulib-201908283352
dc.identifier.uri http://hdl.handle.net/10138/305041
dc.description.abstract Logiikan alalla eräs kiinnostava kysymys on minkälaisia malleja saadaan määriteltyä eri logiikoiden kaavoilla. Tätä kutsutaan logiikan ilmaisuvoimaksi. Modaalilogiikoille ilmaisuvoiman rajoja osoittavia lauseita kutsutaan van Benthemin lauseiksi. Modaalilogiikoiden ilmaisuvoimalle keskeinen piirre on bisimulaatioinvarianssi. Tässä tutkielmassa osoitetaan van Benthemin lause kahdelle logiikalle: modaalilogiikalle ja laajennetulle modaaliselle riippuvuuslogiikalle. Työssä esitellään myös modaalilogiikan ja riippuvuuslogiikan perusteita lyhyesti ennen kunkin logiikan van Benthem lauseen todistusta. Tässä tutkielmassa modaalilogiikan van Benthemin lause todistetaan peliteorian keinoin, mikä mahdollistaa todistuksen pelkästään äärellisiä malleja käyttäen, toisin kuin alkuperäinen malliteoreettinen todistus. Lause sanoo, että modaalilogiikka on ilmaisuvoimaltaan sama kuin ensimmäisen kertaluvun logiikan bisimulaatioinvariantti fragmentti. Kaikille logiikoille van Benthemin lauseen suora todistaminen ei onnistu yhtä vaivattomasti. Tällöin käytetään hyväksi välituloksia. Esimerkkinä tästä toimii laajennettu modaalinen riippuvuuslogiikka, jolle lause osoitetaan todistamalla se eri logiikalle, joka puolestaan todistetaan loogisesti ekvivalentiksi laajennetun modaalisen riippuvuuslogiikan kanssa. Tässä työssä van Benthem lause osoitetaan aluksi modaalilogiikalle, jota on laajennettu intuitionistisella disjunktiolla. Tämä logiikka todistetaan loogisesti ekvivalentiksi laajennetun modaalisen riipuvuuslogiikan kanssa. Näille logiikoille van Benthemin lause rajaa logiikan kykenevän määrittelemään alaspäin suljettuja, tyhjän tiimin ominaisuuden omaavia malleja jotka ovat bisimulaation suhteen invariantteja. fi
dc.language.iso eng
dc.publisher Helsingin yliopisto fi
dc.publisher University of Helsinki en
dc.publisher Helsingfors universitet sv
dc.subject modaalilogiikka fi
dc.subject riippuvuuslogiikka fi
dc.subject modaalinen riippuvuuslogiikka fi
dc.subject van Benthemin lause fi
dc.title Modal Logics and Bisimulation Invariance en
dc.type.ontasot pro gradu -tutkielmat fi
dc.type.ontasot master's thesis en
dc.type.ontasot pro gradu-avhandlingar sv
dc.subject.discipline Matematiikka und
dct.identifier.urn URN:NBN:fi:hulib-201908283352

Files in this item

Total number of downloads: Loading...

Files Size Format View
Sandstrom_Max_Pro_gradu_2019.pdf 503.9Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record