Characteristic Formulas of Partial Heyting Algebras

The goal of this paper is to generalize a notion of characteristic (or Jankov) formula by using finite partial Heyting algebras instead of the finite subdirectly irreducible algebras: with every finite partial Heyting algebra we associate a characteristic formula, and we study the properties of these formulas. We prove that any intermediate logic can be axiomatized by such formulas. We further discuss the correlations between characteristic formulas of finite partial algebras and canonical formulas. Then with every well-connected Heyting algebra we associate a set of characteristic formulas that correspond to each finite relative subalgebra of this algebra. Finally, we demonstrate that in many respects these sets enjoy the same properties as regular characteristic formulas. In the last section we outline an approach how to generalize these obtained results to the broad classes of algebras.     

Kripke‐style semantics for many‐valued logics

This paper deals with Kripke‐style semantics for many‐valued logics. We introduce various types of Kripke semantics, and we connect them with algebraic semantics. As for modal logics, we relate the axioms of logics extending MTL to properties of the Kripke frames in which they are valid. We show that in the propositional case most logics are complete but not strongly complete with respect to the corresponding class of complete Kripke frames, whereas in the predicate case there are important many‐valued logics like BL, ? and Π, which are not even complete with respect to the class of all predicate Kripke frames in which they are valid. Thus although very natural, Kripke semantics seems to be slightly less powerful than algebraic semantics. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Presburger fragment of logics with multiteam semantics

In team semantics, which is the basis of modern logics of dependence and independence, formulae are evaluated on sets of assignments, called teams. Multiteam semantics instead takes mulitplicities of data into account and is based on multisets of assignments, called multiteams. Logics with multiteam semantics can be embedded into a two-sorted variant of existential second-order logics, with arithmetic operations on multiplicities. Here we study the Presburger fragment of such logics, permitting only addition, but not multiplication on multiplicities. It can be shown that this fragment corresponds to inclusion-exclusion logic in multiteam semantics, but, in contrast to the situation in team semantics, that it is strictly contained in independence logic. We give different characterisations of this fragment by various atomic dependency notions.     

On elementary logics for quantitative dependencies

We define and study logics in the framework of probabilistic team semantics and over metafinite structures. Our work is paralleled by the recent development of novel axiomatizable and tractable logics in team semantics that are closed under the Boolean negation. Our logics employ new probabilistic atoms that resemble so-called extended atoms from the team semantics literature. We also define counterparts of our logics over metafinite structures and show that all of our logics can be translated into functional fixed point logic implying a polynomial time upper bound for data complexity with respect to BSS-computations.     

On semilattice relevant logics

The semilattice relevant logics ^∪ R , ^∪ T , ^∪ RW , and ^∪ TW (slightly different from the orthodox relevant logics R , T , RW , and TW ) are defined by semilattice models in which conjunction and disjunction are interpreted in a natural way. For each of them, there is a cut‐free labelled sequent calculus with plural succedents (like LK ). We prove that these systems are equivalent, with respect to provable formulas, to the restricted systems with single succedents (like LJ ). Moreover, using this equivalence, we give a new Hilbert‐style axiomatizations for ^∪ R and ^∪ T and prove equivalence between two semantics (commutative monoid and distributive semilattice) for the contractionless logics ^∪ RW and ^∪ TW .     

Separation logic and logics with team semantics

Separation logic is a successful logical system for formal reasoning about programs that mutate their data structures. Team semantics, on the other side, is the basis of modern logics of dependence and independence. Separation logic and team semantics have been introduced with quite different motivations, and are investigated by research communities with rather different backgrounds and objectives. Nevertheless, there are obvious similarities between these formalisms. Both separation logic and logics with team semantics involve the manipulation of second-order objects, such as heaps and teams, by first-order syntax without reference to second-order variables. Moreover, these semantical objects are closely related; it is for instance obvious that a heap can be seen as a team, and the separating conjunction of separation logic is (essentially) the same as the team-semantical disjunction. Based on such similarities, the possible connections between separation logic and team semantics have been raised as a question at several occasions, and lead to informal discussions between these research communities. The objective of this paper is to make this connection precise, and to study its potential but also its obstacles and limitations.     

Incompleteness Results in Kripke Bundle Semantics

Kripke bundle and C-set semantics are known as semantics which generalize standard Kripke semantics. In [4] and in [1, 2] it is shown that Kripke bundle and C-set semantics are stronger than standard Kripke semantics. Also it is true that C-set semantics for superintuitionistic logics is stronger than Kripke bundle semantics ([6]). Modal predicate logic Q-S4.1 is not Kripke bundle complete ([3] - it is also yielded as a corollary to Theorem 6.1(a) of the present paper). This is shown by using difference of Kripke bundle semantics and C-set semantics. In this paper, by using the same idea we show that incompleteness results in Kripke bundle semantics which are extended versions of [2].     

Fibered universal algebra for first-order logics

We extend Lawvere-Pitts prop-categories (aka. hyperdoctrines) to develop a general framework for providing fibered algebraic semantics for general first-order logics. This framework includes a natural notion of substitution, which allows first-order logics to be considered as structural closure operators just as propositional logics are in abstract algebraic logic. We then establish an extension of the homomorphism theorem from universal algebra for generalized prop-categories and characterize two natural closure operators on the prop-categorical semantics. The first closes a class of structures (which are interpreted as morphisms of prop-categories) under the satisfaction of their common first-order theory and the second closes a class of prop-categories under their associated first-order consequence. It turns out that these closure operators have characterizations that closely mirror Birkhoff's characterization of the closure of a class of algebras under the satisfaction of their common equational theory and Blok and Jónsson's characterization of closure under equational consequence, respectively. These algebraic characterizations of the first-order closure operators are unique to the prop-categorical semantics. They do not have analogues, for example, in the Tarskian semantics for classical first-order logic. The prop-categories we consider are much more general than traditional intuitionistic prop-categories or triposes (i.e., topos representing indexed partially ordered sets). Nonetheless, to the best of our knowledge, our results are new, even when restricted to these special classes of prop-categories.     

Infinitary S5-Epistemic Logic

It is known that a theory in S5-epistemic logic with several agents may have numerous models. This is because each such model specifies also what an agent knows about infinite intersections of events, while the expressive power of the logic is limited to finite conjunctions of formulas. We show that this asymmetry between syntax and semantics persists also when infinite conjunctions (up to some given cardinality) are permitted in the language. We develop a strengthened S5-axiomatic system for such infinitary logics, and prove a strong completeness theorem for them. Then we show that in every such logic there is always a theory with more than one model.     

Properties of Tense Logics

Based on the results of [11] this paper delivers uniform algorithms for deciding whether a finitely axiomatizable tense logic

• has the finite model property,
• is complete with respect to Kripke semantics,
• is strongly complete with respect to Kripke semantics,
• is d-persistent,
• is r-persistent.

It is also proved that a tense logic is strongly complete iff the corresponding variety of bimodal algebras is complex, and that a tense logic is d-persistent iff it is complete and its Kripke frames form a first order definable class. From this we obtain many natural non-d-persistent tense logics whose corresponding varieties of bimodal algebras are complex. Mathematics Subject Classification: 03B45, 03B25.     

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.     

Sémantique algébrique ďun système logique basé sur un ensemble ordonné fini

In order to modelize the reasoning of an intelligent agent represented by a poset T, H. Rasiowa introduced logic systems called “Approximation Logics”. In these systems a set of constants constitutes a fundamental tool. In this papers, we consider logic systems called L′_T without this kind of constants but limited to the case where T is a finite poset. We prove a weak deduction theorem. We introduce also an algebraic semantics using Hey ting algebra with operators. To prove the completeness theorem of the L′_T system with respect to the algebraic semantics, we use the method of H. Rasiowa and R. Sikorski for first order logic. In the propositional case, a corollary allows us to assert that it is decidable to know “if a propositional formula is valid”. We study also certain relations between the L′_T logic and the intuitionistic and classical logics.     

A Sahlqvist theorem for distributive modal logic

In this paper we consider distributive modal logic, a setting in which we may add modalities, such as classical types of modalities as well as weak forms of negation, to the fragment of classical propositional logic given by conjunction, disjunction, true, and false. For these logics we define both algebraic semantics, in the form of distributive modal algebras, and relational semantics, in the form of ordered Kripke structures. The main contributions of this paper lie in extending the notion of Sahlqvist axioms to our generalized setting and proving both a correspondence and a canonicity result for distributive modal logics axiomatized by Sahlqvist axioms. Our proof of the correspondence result relies on a reduction to the classical case, but our canonicity proof departs from the traditional style and uses the newly extended algebraic theory of canonical extensions.     

Tableau method for residuated logic

Residuated logic is a generalization of intuitionistic logic, which does not assume the idempotence of the conjunction operator. Such generalized conjunction operators have proved important in expert systems (in the area of Approximate Reasoning) and in some areas of Theoretical Computer Science. Here we generalize the intuitionistic tableau procedure and prove that this generalized tableau method is sound for the semantics (the class of residuated algebras) of residuated propositional calculus (RPC). Since the axioms of RPC are complete for the semantics we may conclude that whenever a formula 0 is tableau provable, it is deducible in RPC. We present two different approaches for constructing residuated algebras which give us countermodels for some formulas φ which are not tableau provable. The first uses the fact that the theory of residuated algebras is equational, to construct quotients of free algebras. The second uses finite algebras. We end by discussing a number of open questions.     

Unifying hidden-variable problems from quantum mechanics by logics of dependence and independence

We study hidden-variable models from quantum mechanics and their abstractions in purely probabilistic and relational frameworks by means of logics of dependence and independence, which are based on team semantics. We show that common desirable properties of hidden-variable models can be defined in an elegant and concise way in dependence and independence logic. The relationship between different properties and their simultaneous realisability can thus be formulated and proven on a purely logical level, as problems of entailment and satisfiability of logical formulae. Connections between probabilistic and relational entailment in dependence and independence logic allow us to simplify proofs. In many cases, we can establish results on both probabilistic and relational hidden-variable models by a single proof, because one case implies the other, depending on purely syntactic criteria. We also discuss the ‘no-go’ theorems by Bell and Kochen-Specker and provide a purely logical variant of the latter, introducing non-contextual choice as a team-semantical property.     

Axiomatizations of team logics

In a modular approach, we lift Hilbert-style proof systems for propositional, modal and first-order logic to generalized systems for their respective team-based extensions. We obtain sound and complete axiomatizations for the dependence-free fragment FO(～) of Väänänen's first-order team logic TL, for propositional team logic PTL, quantified propositional team logic QPTL, modal team logic MTL, and for the corresponding logics of dependence, independence, inclusion and exclusion.As a crucial step in the completeness proof, we show that the above logics admit, in a particular sense, a semantics-preserving elimination of modalities and quantifiers from formulas.     

Exhibiting Wide Families of Maximal Intermediate Propositional Logics with the Disjunction Property

We provide results allowing to state, by the simple inspection of suitable classes of posets (propositional Kripke frames), that the corresponding intermediate propositional logics are maximal among the ones which satisfy the disjunction property. Starting from these results, we directly exhibit, without using the axiom of choice, the Kripke frames semantics of 2^No maximal intermediate propositional logics with the disjunction property. This improves previous evaluations, giving rise to the same conclusion but made with an essential use of the axiom of choice, of the cardinality of the set of the maximal intermediate propositional logics with the disjunction property. Mathematics Subject Classification: 03B55, 03C90.     

Propositional union closed team logics

In this paper, we study several propositional team logics that are closed under unions, including propositional inclusion logic. We show that all these logics are expressively complete, and we introduce sound and complete systems of natural deduction for these logics. We also discuss the locality property and its connection with interpolation in these logics.     

Iterated team semantics for a hierarchy of informational types

In this paper, we introduce and study a framework that is inspired by the team semantics for propositional dependence logic but deviates from it in several respects. Most importantly, instead of the two semantic layers used in dependence logic – possible worlds and teams – a whole hierarchy of contexts is introduced and different types of formulas are evaluated at different levels of this hierarchy. This leads to a rich stratification of informational types. In this framework, the dependence operator of dependence logic can be defined by the standard propositional connectives (negation, conjunction, disjunction and implication). We explore the formal aspects of this approach and apply it to a number of puzzling phenomena related to modalities and conditionals.