|
|
Aspects of the Cut-Elimination Theorem
Rýdl, Jiří ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
I give a proof of the cut-elimination theorem (Gentzen's Hauptsatz ) for an intuitionistic multi-succedent calculus. The proof follows the strategy of eliminating topmost maximal-rank cuts that allows for a straightforward way to measure the upper bound of the increase of derivations during the procedure. The elimination of all cut inferences generates a superexponential increase. I follow the structure of the proof for classical logic given in Švejdar's [18], modifying only the critical cases related to two restricted rules. Motivated by the diversity found in the early literature on this topic, I survey selected aspects of various formulations of sequent calculi. These are reflected in the proof of the Hauptsatz and its preliminaries. In the end I give one corollary of cut elimination, the Midsequent theorem, which is one of the three applications to be found already in Gentzen's [10].
|
|
|
Usuzování s nekonzistentními informacemi
Přenosil, Adam ; Bílková, Marta (advisor) ; Noguera, Carles (referee) ; Jansana, Ramon (referee)
This thesis studies the extensions of the four-valued Belnap-Dunn logic, called super-Belnap logics, from the point of view of abstract algebraic logic. We describe the global structure of the lattice of super-Belnap logics and show that this lattice can be fully described in terms of classes of finite graphs satisfying some closure conditions. We also introduce a theory of so- called explosive extensions and use it to prove new completeness theorems for super-Belnap logics. A Gentzen-style proof theory for these logics is then developed and used to establish interpolation for many of them. Finally, we also study the expansion of the Belnap-Dunn logic by the truth operator ∆. Keywords: abstract algebraic logic, Belnap-Dunn logic, paraconsistent logic, super-Belnap logics
|
|
|
Fragments of intuitionistic logic, intermediate logics and substructural logics (selected problems).
Truhlář, Pavel ; Bílková, Marta (advisor) ; Sedlár, Igor (referee)
The abstract of the diploma thesis "Positive Formulas for Some Substructural Logics" by Pavel Truhlar We will examine which distributive substructural logics, as defined in the book of Restall "An Introduction to Substructural Logics" have the same positive fragment with and without the weak excluded middle axiom. The main result of this diploma thesis is that some substructural logics have this property. We repeat the basic notions as described in the Restall's book, especially the consecution, natural deduction, frame semantics, Hilbert system. We will use the soundness and completeness theorems. We also will use the equivalence of natural deduction systems and Hilbert systems. All these important theorems are in the above mentioned Restall's book. We make the proof of our main result in the next part. We will use the semantics of frames, similarly as de Jongh and Zhao in the article "Positive Formulas in Intuitionistic and Minimal Logic". We will define the top model. After, we define the construction which converts a model to the top model. We define for each formula the positive part of it; this is the formula, which behaves the same way on the top models as the original formula. We use Hilbert type calculus to formulate our main theorem. We prove our main result using the deduction theorem for certain...
|
|
|
Hypothetical Judgements, Truth and Assertibility
Punčochář, Vít ; Kolman, Vojtěch (advisor) ; Sedlár, Igor (referee) ; Bílková, Marta (referee)
Vít Punčochář Dissertation: Hypothetical Judgements, Truth and Assertibility Abstract: The main topic of this thesis is the logic of indicative conditionals, i.e. sentences of the form If A then B. In classical logic, these sentences are analysed with the help of the so- called material implication. However, the analysis is problematic in many respects. Some chapters of the thesis are devoted to the explanation of the problems, which one necessarily faces when analysing conditionals with the apparatus of standard classical logic. The stress is laid upon the fact that here we are led to a paradoxical situation: some general principles of classical logic (e.g. the principle according to which one can infer If not-A then B from A or B) seem to be unquestionable, but they have very controversial consequences. In the thesis, attempts are presented to defend classical logic as well as to revise it. The approaches to the logical analysis of conditionals are classified into two basic kinds: the first one might be called ontic and the second one epistemic. The ontic approach defines all crucial semantic notions in terms of the concept of truth that is modelled in logic as a relation between sentences of a given language and states of affairs. In contrast, the epistemic approach is not based on the concept of truth...
|
|
|
Arithmetical completeness of the logic R
Holík, Lukáš ; Švejdar, Vítězslav (advisor) ; Bílková, Marta (referee)
The aim of this work is to use contemporary notation to build theory of Rosser logic, explain in detail its relation to Peano arithmetic, show its Kripke semantics and finally using plural self-reference show the proof of arithmetical completeness. In the last chapter we show some of the properties of Rosser sentences. Powered by TCPDF (www.tcpdf.org)
|
|
|
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
|
|
| |
guest ::
RSS feed.