Hilbert-style axiomatization of first-degree entailment and a family of its extensions

This paper presents a Hilbert-style system for the logic of first-degree entailment defined in a Fmla-Fmla framework. The effective use of this formulation as a basis for a whole family of systems extending the logic of first-degree entailment in various directions is shown. By systematizing this family, some new systems are uncovered, and some other well-established logics (such as the first-degree entailment fragment of Priest's Logic of Paradox) obtain new axiomatization. Semantics for the key systems from the family is formulated.     

Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals

Probabilistic team semantics is a framework for logical analysis of probabilistic dependencies. Our focus is on the axiomatizability, complexity, and expressivity of probabilistic inclusion logic and its extensions. We identify a natural fragment of existential second-order logic with additive real arithmetic that captures exactly the expressivity of probabilistic inclusion logic. We furthermore relate these formalisms to linear programming, and doing so obtain PTIME data complexity for the logics. Moreover, on finite structures, we show that the full existential second-order logic with additive real arithmetic can only express NP properties. Lastly, we present a sound and complete axiomatization for probabilistic inclusion logic at the atomic level.     

QUANTIFIED MODAL LOGIC WITH NEIGHBORHOOD SEMANTICS

The paper presents a semantics for quantified modal logic which has a weaker axiomatization than the usual Kripke semantics. In particular, the Barcan Formula (BF) and its converse are not valid with the proposed semantics. Subclasses of models which validate BF and other interesting formulas are presented. A completeness theorem is proved, and the relation between this result and completeness with respect to Kripke models is investigated.     

An anytime deduction algorithm for the probabilistic logic and entailment problems

We study two basic problems of probabilistic reasoning: the probabilistic logic and the probabilistic entailment problems. The first one can be defined as follows. Given a set of logical sentences and probabilities that these sentences are true, the aim is to determine whether these probabilities are consistent or not. Given a consistent set of logical sentences and probabilities, the probabilistic entailment problem consists in determining the range of the possible values of the probability associated with additional sentences while maintaining a consistent set of sentences and probabilities.This paper proposes a general approach based on an anytime deduction method that allows the follow-up of the reasoning when checking consistency for the probabilistic logic problem or when determining the probability intervals for the probabilistic entailment problem. Considering a series of subsets of sentences and probabilities, the approach proceeds by computing increasingly narrow probability intervals that either show a contradiction or that contain the tightest entailed probability interval. Computational experience have been conducted to compare the proposed anytime deduction method, called ad-psat with an exact one, psatcol, using column generation techniques, both with respect to the range of the probability intervals and the computing times.     

Characterizing Belnap's Logic via De Morgan's Laws

The aim of this paper is technically to study Belnap's four-valued sentential logic (see [2]). First, we obtain a Gentzen-style axiomatization of this logic that contains no structural rules while all they are still admissible in the Gentzen system what is proved with using some algebraic tools. Further, the mentioned logic is proved to be the least closure operator on the set of {Λ, V, ?}-formulas satisfying Tarski's conditions for classical conjunction and disjunction together with De Morgan's laws for negation. It is also proved that Belnap's logic is the only sentential logic satisfying the above-mentioned conditions together with Anderson-Belnap's Variable-Sharing Property. Finally, we obtain a finite Hilbert-style axiomatization of this logic. As a consequence, we obtain a finite Hilbert-style axiomatization of Priest's logic of paradox (see [12]).     

A paraconsistent extension of Sylvan’s logic

We deal with Sylvan’s logic CC_ω. It is proved that this logic is a conservative extension of positive intuitionistic logic. Moreover, a paraconsistent extension of Sylvan’s logic is constructed, which is also a conservative extension of positive intuitionistic logic and has the property of being decidable. The constructed logic, in which negation is defined via a total accessibility relation, is a natural intuitionistic analog of the modal system S5. For this logic, an axiomatization is given and the completeness theorem is proved. Supported by RFBR grant No. 06-01-00358 and by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-4787.2006.1. __________ Translated from Algebra i Logika, Vol. 46, No. 5, pp. 533–547, September–October, 2007.     

Fuzzy inequational logic

We present a logic for reasoning about graded inequalities which generalizes the ordinary inequational logic used in universal algebra. The logic deals with atomic predicate formulas of the form of inequalities between terms and formalizes their semantic entailment and provability in graded setting which allows to draw partially true conclusions from partially true assumptions. We follow the Pavelka approach and define general degrees of semantic entailment and provability using complete residuated lattices as structures of truth degrees. We prove the logic is Pavelka-style complete. Furthermore, we present a logic for reasoning about graded if–then rules which is obtained as particular case of the general result.     

Test recognition

We describe the logic approach to pattern recognition; its key notion is a test. Analyzing the tests allows us to construct functionals characterizing the pattern, as well as procedures to compute them. We present qualitative and quantitative properties of tests, functionals, and recognition procedures. Solutions of a series of known problems are also given.     

Infinitary first-order categorical logic

We present a unified categorical treatment of completeness theorems for several classical and intuitionistic infinitary logics with a proposed axiomatization. This provides new completeness theorems and subsumes previous ones by Gödel, Kripke, Beth, Karp and Joyal. As an application we prove, using large cardinals assumptions, the disjunction and existence properties for infinitary intuitionistic first-order logics.     

On Binary Computation Structures

Based on a modification of Moss' and Parikh's topological modal language [8], we study a generalization of a weakly expressive fragment of a certain propositional modal logic of time. We define a bimodal logic comprising operators for knowledge and nexttime. These operators are interpreted in binary computation structures. We present an axiomatization of the set T of theorems valid for this class of semantical domains and prove – as the main result of this paper – its completeness. Moreover, the question of decidability of T is treated.     

Closure-based constraints in formal concept analysis

We present a method of imposing constraints in extracting formal concepts (equivalently, closed itemsets or fixpoints of Galois connections) from a binary relation. The constraints are represented by closure operators and their purpose is to mimic background knowledge a user may have of the data. The idea is to consider and extract only these itemsets that are compatible with the background knowledge. As a result, the method extracts less clusters, those that are interesting from the user point of view, in a shorter time. The method makes it also possible to extract minimal bases of attribute dependencies in the input data that are compatible with the background knowledge. We provide examples of several particular types of constraints including those that appeared in the literature in the past and present algorithms to compute the constrained formal concepts and attribute implications.     

A Sequent Calculus for Propositional Dynamic Logic for Agents

We consider propositional dynamic logic for agents. For this logic, we present a sequent calculus with a restricted cut rule and prove the soundness and completeness for the calculus.     

Lattice BCK logics with Modus Ponens as unique rule

Lattice BCK logic is the expansion of the well known Meredith implicational logic BCK expanded with lattice conjunction and disjunction. Although its natural axiomatization has three rules named modus ponens, ∨‐rule and ∧‐rule, we show that we can give an equivalent presentation with just modus ponens and ∧‐rule, however it is impossible to obtain an equivalent presentation with modus ponens as unique rule. In this paper we study and characterize all axiomatic extensions of lattice BCK logic with modus ponens as unique rule. We obtain an infinite chain of proper axiomatic extensions with this property. Moreover, we prove that there is no weakest axiomatic extension of Lattice BCK‐logic admitting modus ponens as unique rule.     

A sequent calculus for logic of knowledge and past time: Completeness and decidability

We consider logic of knowledge and past time. This logic involves the discrete-time linear temporal operators next, until, weak yesterday, and since. In addition, it contains an indexed set of unary modal operators agent i knows.We consider the semantic constraint of the unique initial states for this logic. For the logic, we present a sequent calculus with a restricted cut rule. We prove the soundness and completeness of the sequent calculus presented. We prove the decidability of provability in the considered calculus as well. So, this calculus can be used as a basis for automated theorem proving. The proof method for the completeness can be used to construct complete sequent calculi with a restricted cut rule for this logic with other semantical constraints as well. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 427–437, July–September, 2006.     

An infinite class of maximal intermediate propositional logics with the disjunction property

Summary Infinitely many intermediate propositional logics with the disjunction property are defined, each logic being characterized both in terms of a finite axiomatization and in terms of a Kripke semantics with the finite model property. The completeness theorems are used to prove that any two logics are constructively incompatible. As a consequence, one deduces that there are infinitely many maximal intermediate propositional logics with the disjunction property.     

Proofs and Countermodels in Non-Classical Logics

Proofs and countermodels are the two sides of completeness proofs, but, in general, failure to find one does not automatically give the other. The limitation is encountered also for decidable non-classical logics in traditional completeness proofs based on Henkin’s method of maximal consistent sets of formulas. A method is presented that makes it possible to establish completeness in a direct way: For any given sequent either a proof in the given logical system or a countermodel in the corresponding frame class is found. The method is a synthesis of a generation of calculi with internalized relational semantics, a Tait–Schütte–Takeuti style completeness proof, and procedures to finitize the countermodel construction. Finitizations for intuitionistic propositional logic are obtained through the search for a minimal derivation, through pruning of infinite branches in search trees by means of a suitable syntactic counterpart of semantic filtration, or through a proof-theoretic embedding into an appropriate provability logic. A number of examples illustrates the method, its subtleties, challenges, and present scope.     

What is a Logic Translation?

We study logic translations from an abstract perspective, without any commitment to the structure of sentences and the nature of logical entailment, which also means that we cover both proof- theoretic and model-theoretic entailment. We show how logic translations induce notions of logical expressiveness, consistency strength and sublogic, leading to an explanation of paradoxes that have been described in the literature. Connectives and quantifiers, although not present in the definition of logic and logic translation, can be recovered by their abstract properties and are preserved and reflected by translations under suitable conditions. In memoriam Joseph Goguen     

On a logic of involutive quantales

The logic just corresponding to (non‐commutative) involutive quantales, which was introduced by Wendy MacCaull, is reconsidered in order to obtain a cut‐free sequent calculus formulation, and the completeness theorem (with respect to the involutive quantale model ) for this logic is proved using a new admissible rule. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Classically complete modal relevant logics

A variety of modal logics based on the relevant logic R are presented. Models are given for each of these logics and completeness is shown. It is also shown that each of these logics admits Ackermann's rule γ and as a corollary of this it is proved that each logic is a conservative extension of its counterpart based on classical logic, hence we call them “classically complete”. MSC: 03B45, 03B46.     

A glimpse of deductive systems in algebra

The concept of a deductive system has been intensively studied in algebraic logic, per se and in connection with various types of filters. In this paper we introduce an axiomatization which shows how several resembling theorems that had been separately proved for various algebras of logic can be given unique proofs within this axiomatic framework. We thus recapture theorems already known in the literature, as well as new ones. As a by-product we introduce the class of pre-BCK algebras.