|
|
Undecidability of Some Substructural Logics
Chvalovský, Karel ; Bílková, Marta (advisor) ; Buszkowski, Vojciech (referee) ; Galatos, Nick (referee)
This thesis deals with the algorithmic undecidability (unsolvability) of provability in some non-classical logics. In fact, there are two natural variants of this problem. Fix a logic, we can study its set of theorems or its consequence relation, which is a more general problem. It is well-known that both these problems can be undecidable already for propositional logics and we provide further examples of such logics in this thesis. In particular, we study propositional substructural logics which are obtained from the sequent calculus LJ for intuitionistic logic by dropping structural rules. Our main results are the following. First, (finite) consequence relations in some basic non-associative substructural logics are shown to be undecidable. Second, we prove that a basic associative substructural logic with the contraction rule, which is notorious for being hard to handle, has an undecidable set of theorems. Since the studied logics have natural algebraic semantics, we also obtain corresponding algebraic results which are interesting in their own right.
|
|
|
A Four-Valued Kripke Semantics for Classical and Intuitionistic Logic
Přenosil, Adam ; Bílková, Marta (advisor) ; Cintula, Petr (referee)
The thesis introduces a logic which combines intuitionistic implication with de Morgan negation in a way which conservatively extends both classical and intuitionistic logic. This logic is the intuitionistic counterpart of the four-valued Belnap-Dunn logic. In relation to this logic, we study de Morgan algebras and their expansions, in particular their expansion with a constant representing inconsistency. We prove a duality for such algebras extending the Priestley duality. We also introduce a weak notion of modal algebra and prove a duality for such algebras. We then define analytic sequent calculi for various logics of de Morgan negation. Powered by TCPDF (www.tcpdf.org)
|
|
|
Algebraic and Kripke semantics of substructural logics
Arazim, Pavel ; Bílková, Marta (advisor) ; Běhounek, Libor (referee)
This thesis is about the distributive full Lambek calculus, i.e., intuicionistic logic without the structural rules of exchange, contraction and weakening and particularly about the two semantics of this logic, one of which is algebraic, the other one is a Kripke semantic. The two semantics are treated in separate chapters and some results about them are shown, for example the disjunction property is proven by amalgamation of Kripke models. The core of this thesis is nevertheless the relation of these two semantics, since it is interesting to study what do they have in common and how can they actually differ, both being a semantics of the same logic. We show how to translate frames to algebras and algebras to frames, and, moreover, we extend such translation to morphisms, thus constructing two functors between the two categories. Key words:distributive FL logic, distributive full Lambek calculus, structural rules, distributive residuated lattice, Kripke frames, frame morphisms, category, functor 2
|
|
|
Dynamic epistemic logics
Pivoňková, Martina ; Bílková, Marta (advisor) ; Sedlár, Igor (referee)
In this thesis we will deal with the logic of public announcement which is a dynamic extension of epistemic logic. First we will explain the logic of truthful public announcement for the multiagent S5 system. Then we will examine what the public announcement can look like in systems weaker than S5. We will focus namely on systems in which the T axiom is invalid and the epistemic modality is interpreted not as a "knowledge" but as a "belief". We will create new semantics of public announcement which is not necessarily truthful but it is believed to be true. We will also try to axiomatize systems that have arisen in this way. Keywords: public announcement logic, logic for belief
|
|
| |
|
|
Intuitionistic logic as a useful tool
Vachková, Eva ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
This work deals with intuitionistic logic and completness of Gentzen calculus with respect to its semantics. The completness proof uses saturated sequents. The language considered is at most countable. Furthermore, our work investigates one of the generalizations of intuitionistic logic, namely intuitionistic logic with constant domain, or Grzegorczyk's logic. We deal with Markov's principle and use it to prove that Gentzen calculus adapted to this logic is not cut-free complete with respect to Grzegorczyk's logic. Part of the work deals with Heyting algebras-one of the possible semantics of intuitionistic propositional logic. We show that the Rieger-Nishimura lattice is a Heyting algebra, too. For Heyting algebras, filters and prime filters are defined and used to obtain Kripke's frames. It is shown that the same formulas hold in these frames and in Heyting algebras.
|
|
|
Interpolation in modal logics
Bílková, Marta ; Pudlák, Pavel (advisor) ; Švejdar, Vítězslav (referee) ; Iemhoff, Rosalie (referee)
Since Craig's landmark result on interpolation for classical predicate logic, proved as the main technical lemma in [14], interpolation is considered one of the centra! concepts in pure logic. Various interpolation properties find their applications in computer science and have many deep purely logical consequences. We focus on two propositional versions of Craig interpolation property: Craig Interpolation Property: for every provable implication (A -+ B) there is an interpolant I containing only only common variables of A and B such that both implications (A -+ I) and (I-+ B) are provable. Craig interpolation, although it seems rather technical, is a deep logical property. It is dosely related to expressive power of a logic - as such it entails Beth's definability property, or forces functional completeness. It is also related to Robinson's joint consistency of two theories that agree on the common language. Craig interpolation has an important algebraic counterpart - it entails amalgamation or superamalgamation property of appropriate algebraic structures. In case of modal provability logics, Craig interpolation entails fixed point theorem. There are other interpolation properties, defined w.r.t. a consequence relation rather then w.r.t. a provable implication. In presence of deduction theorem the two...
|
|
|
Explicit fixed-points in provability logic
Chvalovský, Karel ; Bílková, Marta (referee) ; Švejdar, Vítězslav (advisor)
The aim of this diploma thesis is to discuss the explicit calculations of xed-points in provability logic GL. The xed-point theorem reads: For every modal formula A(p) such that each occurrence of p is under the scope of ¤, there is a formula D containing only sentence letters contained in A(p), not containing the sentence letter p, such that GL proves D ' A(D). Moreover, D is unique up to the provable equivalence. Firstly, we establish some special cases of the theorem and then we will look more closely at the full theorem. We show one semantic and two syntactic full xed-point constructions and prove their correctness. We also discuss some complexity aspects connected with the constructions and present basic upper bounds on length and modal depth of the constructed xed-points.
|
|
| |
|
|
Categories of fuzzy sets
Luhan, Ondřej ; Bílková, Marta (referee) ; Běhounek, Libor (advisor)
Category theory provides very useful tools for studying mathematical structures and phenomena. One of the structures that is studied in a category-theoretical manner are fuzzy sets. If we consider fuzzy sets as objects and set up certain kind of structure preserving mappings as morphisms, we can obtain a suitable category for our purposes. Goal of this work is to give an overview of preferably all important category-theoretical approaches to fuzzy sets that were done throughout relatively short history of category-theoretical modelling of fuzzy sets.
|
guest ::
RSS feed.