We show that Smullyan's analytic tableaux cannot p-simulate the truth-tables. We identify the cause of this computational breakdown and relate it to an underlying semantic difficulty which is common to the whole tradition originating in Gentzen's sequent calculus, namely the dissonance between cut-free proofs and the Principle of Bivalence. Finally we discuss some ways in which this principle can be built into a tableau-like method without affecting its analytic nature.

We extend BDDs for plain propositional logic to the fragment of first order logic, consisting of quantifier free logic with zero, successor and equality. We allow equations with zero and successor in the nodes of a BDD, and call such objects -BDDs. We extend the notion of Ordered BDDs in the presence of zero, successor and equality. -BDDs can be transformed to equivalent Ordered -BDDs by applying a number of rewrite rules until a normal form is reached. All paths in (...) these ordered -BDDs represent satisfiable conjunctions. The major advantage of transforming a formula to an equivalent Ordered -BDD is that on the latter it can be observed in constant time whether the formula is a tautology, a contradiction, or just satisfiable. (shrink)

The paper deals with polymodal languages combined with standard semantics defined by means of some conditions on the frames. So, a notion of "polymodal base" arises which provides various enrichments of the classical modal language. One of these enrichments, viz. the base £(R,-R), with modalities over a relation and over its complement, is the paper's main paradigm. The modal definability (in the spirit of van Benthem's correspondence theory) of arbitrary and ~-elementary classes of frames in this base and in some (...) of its extensions, e.g., £(R,-R,R-1 ,_R-1), £(R,-R,=I=) etc., is described, and numerous examples of conditions definable there, as well as undefinable ones, are adduced. (shrink)

A method is presented for constructing natural deduction-style systems for propositional relevant logics. The method consists in first translating formulas of relevant logics into ternary relations, and then defining deduction rules for a corresponding logic of ternary relations. Proof systems of that form are given for various relevant logics. A class of algebras of ternary relations is introduced that provides a relation-algebraic semantics for relevant logics.

The calculus of relations was created and developed in the second half of the nineteenth century by Augustus De Morgan, Charles Sanders Peirce, and Ernst Schröder. In 1940 Alfred Tarski proposed an axiomatization for a large part of the calculus of relations. In the next decade Tarski's axiomatization led to the creation of the theory of relation algebras, and was shown to be incomplete by Roger Lyndon's discovery of nonrepresentable relation algebras. This paper introduces the calculus of relations and the (...) theory of relation algebras through a review of these historical developments. (shrink)

We introduce a new technique to simplify and skolemize first-order formulas, based on binary decision diagrams, or BDDs. This technique is more computation-intensive than previously known ones, but in general provides better skolemized forms that attempt to reduce the number of false dependencies. This technique can also be seen as a practical way of simplifying first-order formulas before feeding them to an automated theorem prover.

Contact relations have been studied in the context of qualitative geometry and physics since the early 1920s, and have recently received attention in qualitative spatial reasoning. In this paper, we present a sound and complete proof system in the style of Rasiowa and Sikorski (1963) for relation algebras generated by a contact relation.