Number 49

Norihiro Kamide

Reports on Mathematical Logic, Number 49, 2014, pp. 3-21

https://doi.org/10.4467/20842589RM.14.001.2271

It is known that many-valued paraconsistent logics are useful for expressing uncertain and inconsistency-tolerant reasoning in a wide range of Computer Science. Some four-valued and sixteen-valued logics have especially been well-studied. Some four-valued logics are not so ﬁne-grained, and some sixteen-valued logics are enough ﬁne-grained, but rather complex. In this paper, a natural eight-valued paraconsistent logic rather than four-valued and sixteen-valued logics is introduced as a Gentzen-type sequent calculus. This eight-valued logic is enough ﬁne-grained and simpler than sixteen-valued logic. A triplet valuation semantics is introduced for this logic, and the completeness theorem for this semantics is proved. The cut-elimination theorem for this logic is proved, and this logic is shown to be decidable.

PDF

Rafael Grimson, Bart Kuijpers

Reports on Mathematical Logic, Number 49, 2014, pp. 23-34

https://doi.org/10.4467/20842589RM.14.002.2272

We consider the Σ1-fragment of second-order logic over the vocabulary (+, ×, 0, 1, <, S1, ..., Sk), interpreted over the reals, where the predicate symbols Si are interpreted as semi- algebraic sets. We show that, in this context, satisfiability of formulas is decidable for the first-order ∃∗-quantifier fragment and undecidable for the ∃∗∀- and ∀∗-fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas.

PDF

On Ordered Minimal Structures

Grzegorz Jagiella, Ludomir Newelski

Reports on Mathematical Logic, Number 49, 2014, pp. 35-46

https://doi.org/10.4467/20842589RM.14.003.2273

We investigate minimal first-order structures and consider interpretability and definability of orderings on them. We also prove the minimality of their canonical substructures.

PDF

Sergio A. Celani, Daniela Montangie

Reports on Mathematical Logic, Number 49, 2014, pp. 47-77

https://doi.org/10.4467/20842589RM.14.004.2274

We introduce the variety of Hilbert algebras with a modal operator D, called HD-algebras. The variety of HD-alge- bras is the algebraic counterpart of the {→, D}-fragment of the intuitionitic modal logic IntK_D. We will study the theory of representation and we will give a topological duality for the variety of HD-algebras. We are going to use these results to prove that the basic implicative modal logic IntK^→ and some axiomatic extensions are canonical. We shall also to determine the simple and subdirectly irreducible algebras in some subvarieties of HD-algebras.

PDF

Jerzy Mycka

Reports on Mathematical Logic, Number 49, 2014, pp. 79-97

https://doi.org/10.4467/20842589RM.14.005.2275

We will introduce the special kind of the order relations into recursively enumerable sets and prove that they can be used to distinguish (albeit in a non-constructive way) between recursive and non-recursive sets.

PDF

Grzegorz Herman

Reports on Mathematical Logic, Number 49, 2014, pp. 99-117

https://doi.org/10.4467/20842589RM.14.006.2276

We study the problem of deciding, whether a given partial order is embeddable into two consecutive layers of a Boolean lattice. Employing an equivalent condition for such em- beddability similar to the one given by J. Mittas and K. Reuter [5], we prove that the decision problem is NP-complete by showing a polynomial-time reduction from the not-all-equal variant of the Satisfiability problem.

PDF

Number 49

2014 Next

Issue content

2014