Naslov Složenost modalnih logika Naslov (engleski) Complexity of modal logics Autor Helena Marciuš Mentor Mladen Vuković (mentor)Član povjerenstva Mladen Vuković (predsjednik povjerenstva)Član povjerenstva Matej Mihelčić (član povjerenstva)Član povjerenstva Vedran Krčadinac (član povjerenstva)Član povjerenstva Miljenko Huzak (član povjerenstva)Ustanova koja je dodijelila Sveučilište u Zagrebu Datum i država obrane 2022-09-29, Hrvatska Znanstveno / umjetničko PRIRODNE ZNANOSTI Sažetak Glavni cilj ovog rada je dokazati nekoliko rezultata o složenosti modalnih logika. Rad je podijeljen u dva poglavlja. U prvom se poglavlju bavimo sintaksom i semantikom osnovnog modalnog jezika. Definiramo pojmove alfabeta i formula, Kripkeovih okvira i modela te istinitost i valjanost modalnih formula. Zatim definiramo najmanju normalnu modalnu logiku K te neka njezina proširenja - logike K4, T, S4, S5, te S4.3T. U prvom poglavlju dajemo i osnovne pojmove i rezultate teorije modela modalne
... Više logike. Definiramo redom sljedeće pojmove: generirani podmodel, izomorfizam i ograničeni morfizam. Za svaku od upravo navedenih konstrukcija modela dokazujemo da čuva istinitost. Definiramo i svojstvo konačnih modela i okvira. Na kraju poglavlja opisujemo karakteristične klase okvira pojedinih modalnih logika. U drugom poglavlju razmatramo složenost normalnih modalnih logika koje smo definirali u prvom poglavlju. Prvo definiramo pojam polinomnog svojstva konačnih modela te pojam definabilnosti klase okvira u logici prvog reda. Ti su pojmovi ključni za dokaz NP– potpunost logike S5 te za dokaz Hemaspaandrinog teorema o NP–potpunosti modalnih logika koje proširuju S4.3T. U drugom dijelu ovog poglavlja prvo definiramo pojam stabla koji će biti važan u ostatku poglavlja. Zatim dokazujemo da logika K nema polinomno svojstvo konačnih modela. Iz tog rezultata možemo naslutiti da logika K, nije NP –potpuna modalna logika. U nastavku definiramo pojam Hintikkinog skupa i pojam skupova svjedoka. Zatim dokazujemo tvrdnje koje nam daju sintaktički kriterij za provjeru ispunjivosti formule. Prvo navodimo algoritam S v j e d o k Λ Λ Sakrij dio sažetka Sažetak (engleski) The main goal of this thesis is to present some results about the complexity of modal logics. The thesis consists of two chapters. In the first chapter, we describe the syntax and semantics of the basic modal language. We define alphabet, formulas, Kripke frames and models, satisfiability, and validity. We then define smallest normal modal logic K and its extensions - K4, T, S4, S5 and S4.3. In this chapter we also present basic notions and results of the model theory of modal logic. We
... Više define the following notions: generated submodel, isomorphism and bounded morphism. We prove that each of the defined constructions preserves satisfiability. We also define a finite model and finite frame property. At the end of the first chapter, we describe characteristic frame classes of some modal logics. The second chapter is about the complexity of normal modal logics defined in the first chapter. First, we define polysize model property and frame definability by a first-order sentence. These are key notions for proving NP-completeness of S5 and for proving Hemaspaandra’s theorem about the NP–completeness of normal modal logics extending S4.3. The second part of the second chapter starts with the definition of trees as they are very useful in the rest of the chapter. Then we show that K lacks polysize model property. From this result we can assume that K is not NP–complete. Furthermore, we define Hintikka sets and witness sets and give a syntactic criterion for the satisfiability of a formula. We also present an algorithm called W i t n e s s Λ Λ Sakrij dio sažetka Ključne riječi
sintaksa osnovnog modalnog jezika
semantika osnovnog modalnog jezika
Kripkeovi okviri i modeli
normalna modalna logika K
generirani podmodel
izomorfizam
ograničeni morfizam
Hemaspaandrinov teorem
Hintikkinov skup
Turingov stroj
Ladnerov teorem
Ključne riječi (engleski)
syntax of basic modal language
semantics of basic modal language
Kripke frameworks and models
normal modal logic K
generated submodel
isomorphism
bounded morphism
Hemaspaandrin theorem
Hintikkin set
Turing machine
Ladner theorem
Jezik hrvatski URN:NBN urn:nbn:hr:217:221382 Studijski program Naziv: Računarstvo i matematika Vrsta resursa Tekst Način izrade datoteke Izvorno digitalna Prava pristupa Otvoreni pristup Uvjeti korištenja Datum i vrijeme pohrane 2022-10-28 12:33:48
