Naslov Modalna potpunost logika interpretabilnosti
Autor Sebastijan Horvat
Mentor Mladen Vuković (mentor)
Član povjerenstva Mladen Vuković (predsjednik povjerenstva)
Član povjerenstva Tin Perkov (član povjerenstva)
Član povjerenstva Ivica Nakić (član povjerenstva)
Član povjerenstva Dijana Ilišević (član povjerenstva)
Ustanova koja je dodijelila akademski / stručni stupanj Sveučilište u Zagrebu Prirodoslovno-matematički fakultet (Matematički odsjek) Zagreb
Datum i država obrane 2018-07-16, Hrvatska
Znanstveno / umjetničko područje, polje i grana PRIRODNE ZNANOSTI Matematika
Sažetak Sistem \(IL\) je modalni sistem kojeg je 1988. uveo Albert Visser. Ovaj sistem sadrži jedan unarni modalni operator \(\Box\) i jedan binarni modalni operator \(\rhd\). Promatraju se i razna proširenja sistema \(IL\) s principima interpretabilnosti. Neka od tih proširenja su logike interpretabilnosti \(ILM\), \(ILP\), \(ILW\) i \(ILM_0\). De Jongh i Veltman su 1990. dokazali potpunost sistema \(IL\), \(ILM\) i \(ILP\), a nešto kasnije i potpunost sistema \(ILW\). Evan Goris i Joost Joosten su 2004. dali nove dokaze potpunosti sistema \(IL\) i \(ILM\) koristeći step-by-step metodu kojom su potom dokazali i modalnu potpunost sistema \(ILM_0\) i \(ILW^*\). Glavni cilj ovog rada je dokazati teoreme modalne potpunosti za logike interpretabilnosti \(IL\) i \(ILP\) koristeći step-by-step metodu. U prvom poglavlju bavimo se semantikom i sintaksom osnovne logike interpretabilnosti \(IL\). U ovom poglavlju dokazujemo adekvatnost sistema \(IL\) i teorem dedukcije za sistem \(IL\). Nakon što definiramo pojmove \(IL\)-konzistentnih i maksimalno \(IL\)-konzistentnih skupova, dokazujemo Lindenbaumovu lemu. U drugom poglavlju definiramo pojmove označenih, adekvatnih i kvazi--okvira, problema i nedostataka, te kritičnog i generaliziranog konusa. Dokazujemo lemu o egzistenciji i lemu o \(IL\)-proširenju. Osnovni cilj ovog poglavlja je dati dokaz potpunosti sistema \(IL\) korištenjem step-by-step metode. U trećem poglavlju dokazujemo potpunost sistema \(ILP\). Prvo dajemo definicije i rezultate vezane za logike interpretabilnosti \(ILX\). Potom navodimo glavne korake step-by-step metode, te formalno iskazujemo glavnu lemu. Dajemo detaljan dokaz potpunosti \(ILP\), pri čemu zapravo provjeravamo uvjete glavne leme kako bismo ju mogli primijeniti.
Sažetak (engleski) System \(IL\) is a system of modal logic introduced by Albert Visser in 1988. This system contains one unary modal operator \(\Box\) and one binary modal operator \(\rhd\). We also consider extensions of system \(IL\). They are given by the intepretability principles, and some of these extensions are interpretability logics \(ILM\), \(ILP\), \(ILW\) and \(ILM_0\). Modal completeness of logics \(IL\), \(ILM\) and \(ILP\) was proven in 1990. by De Jongh and Veltman. Later they also proved modal completeness of the logic \(ILW\). In 2004. Evan Goris and Joost Joosten gave new proofs of completeness of logics \(IL\) and \(ILM\) using their step-by-step method. Using that method, they also proved modal completeness of logics \(ILM_0\) and \(ILW^∗\). The main goal of this thesis is to present the proof of modal completeness of interpretability logics \(IL\) and \(ILP\) by using step–by–step method. In the first chapter, we deal with syntax and semantic of the interpretability logic \(IL\). In this chapter we present proof of soundness theorem for logic \(IL\) and proof of deduction theorem for logic \(IL\). After presenting the notion of \(IL\)–consistent and maximal \(IL\)–consistent set, we give proof of Lindenbaum’s lemma. In the second chapter, we define the following notions: labeled frame, adequate frame, quasi–frame, problems, deficiencies, critical cone and generalized cone. We also prove existence lemma and \(IL\)–closure lemma. The main goal of this chapter is to prove model completeness of the logic \(IL\) by using the step–by–step method. In the third chapter, we present the proof of completeness of the logic \(ILP\). We first present definitions and results that are related to interpretability logics \(ILX\). Then we describe main steps of the step–by–step method. Also, we give formal statement of the main lemma. Finally, we present detailed proof of completeness of the logic \(ILP\). We are doing that by checking requirements of the main lemma.
Ključne riječi
Visser
logika interpretabilnosti
De Jongh
Veltman
Goris
Joosten
step-by-step metoda
Lindenbaumova lema
Ključne riječi (engleski)
Visser
interpretability logic
De Jongh
Veltman
Goris
Joosten
step-by-step method
Lindenbaum’s lemma
Jezik hrvatski
URN:NBN urn:nbn:hr:217:831141
Studijski program Naziv: Računarstvo i matematika Vrsta studija: sveučilišni Stupanj studija: diplomski Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
Vrsta resursa Tekst
Način izrade datoteke Izvorno digitalna
Prava pristupa Otvoreni pristup
Uvjeti korištenja
Datum i vrijeme pohrane 2018-11-23 13:17:07