Van Benthem-Rosenov teorem

diplomski rad

• Autor: Martin Brkić
• Mentor: Mladen Vuković (mentor)
• Član povjerenstva: Mladen Vuković (predsjednik povjerenstva)
• Član povjerenstva: Marko Tadić (član povjerenstva)
• Član povjerenstva: Eduard Marušić-Paloka (član povjerenstva)
• Član povjerenstva: Nela Bosner (č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-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu smo ustanovili koja je veza između modalne logike i logike prvog reda. Nakon što smo definirali osnovni modalni jezik i Kripkeovu semantiku, u prvom smo poglavlju definirali bisimulaciju, koja se pokazala kao ključan koncept u modalnoj logici. Ključna stvar u drugom poglavlju je uvođenje bisimulacijskih igara kao jednog načina karakteriziranja bisimuliranosti u smislu teorije igara. Kasnije proučavanje stablastih struktura i \(l\)-okolina na Kripkeovim strukturama nam je pomoglo kod uvođenja koncepta \(l\)-lokalnosti. U trećem poglavlju smo definirali standardnu translaciju, koja nam je omogućila promatranje modalne logike kao fragmenta logike prvog reda. U proučavanje Ehrenfeucht – Fraïsséovih igara se nismo dublje upustili, nego smo definirali i iskazali ono što nam je potrebno za dokaz Van Benthem - Rosenovog teorema. Također smo definirali i vrlo jednostavan koncept \(l\)-lokalnosti na Kripkeovim strukturama. Vrlo je važno naglasiti da dokaz Van Benthem - Rosenovog teorema kojeg smo iznijeli u četvrtom poglavlju funkcionira i na konačnim i na općenitim Kripkeovim strukturama.

Sažetak (engleski)

In this paper we established connection between modal logic and first order logic. In first chapter, after defining basic modal language and Kripke semantics, we introduced the notion of bisimulation, which happens to be the key concept in modal logic. Crucial thing in second chapter was introduction of bisimulation games as one way to characterize bisimilarity in game theoretic way. Latter investigation of tree structures and \(l\)-neighbourhoods on Kripke structures helped us to introduce notion of \(l\)-locality. Introduction of standard translation made possible for us to look at modal logic as a fragment of first order logic. We didn’t take deeper look at Ehrenfeucht - Fraïssé games, having defined and stated only what we needed to prove Van Benthem - Rosen theorem. We also defined basic concept of \(l\)-locality of Kripke structures. It is important to emphasize that proof of Van Benthem - Rosen theorem that we presented in final chapter is good in both finite and general case of Kripke structures.

• Ključne riječi: modalna logika; logika prvog reda; Kripkeova semantika; bisimulacija; bisimulacijske igre; Van Bentheem-Rosenov teorem
• Ključne riječi (engleski): modal logic; first order logic; Kripke semantics; bisimulation; bisimulation games; Van Benthem-Rosen theorem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:791641
• Studijski program: Naziv: Teorijska matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-03-04 12:04:50