|
|
Explicit fixed-points in provability logic
Chvalovský, Karel ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
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.
|
|
|
Proving by finite automata
Fišer, Jan ; Holub, Štěpán (advisor) ; Chvalovský, Karel (referee)
In 2016, Hamoon Mousavi published Walnut which is a program that implements automated theorem proving of propositions about automatic sequences. The main purpose of this thesis was to show the theoretical functi- onality of Walnut on the basis of the relation between automatic sequences and Presburger (resp. B¨uchi) arithmetic that is a decidable theory. Another goal was to describe adequately how the decision procedure of Walnut really works, and finally, to show the practical use of Walnut on several particular problems. One of these particular problems that are solved in the thesis is computation of the critical exponent of the Rudin-Shapiro sequence - this exercise was presented as an open problem in a book of 2003 (however, this exercise does not belong among open problems any more since Shallit proved in 2011 that the critical exponent is computable for all automatic sequences.) The last chapter itself can be also used as a brief manual for newcomers to Walnut that want to use this program for their own applications. 1
|
|
|
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.
|
|
|
Implicational fragments of intuitionistic propositional logic
Blicha, Martin ; Švejdar, Vítězslav (advisor) ; Chvalovský, Karel (referee)
In this thesis we study implicational fragments of intuitionistic propositional logic with finite number of atoms. The first part is dedicated to the fragment with only two atoms, which is simple enough to analyze the relations between it's formulas, but is not that trivial. In the next part, we introduce the terms prime node and prime model, which allow us to examine other fragments. In the last part, we find out how the results change when we add the constant into out language.
|
|
|
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.
|
|
| |
|
| |
|
|
Logic, Algebra and Truth Degrees 2010
Chvalovský, Karel ; Cintula, Petr ; Noguera, C.
Volume of abstracts from the conference Logic, Algebra and Truth Degrees 2010 (the second official meeting of the EUSFLAT Working Group on Mathematical Fuzzy Logic) which was held on 7-11 September 2010 in Prague. The volume was published by Institute of Theoretical informatics as volume 2010-502 of ITI Series and is available at http://iti.mff.cuni.cz/series/
|
|
| |
|
| |
guest ::
