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.

Succinct representation and fast access to large amounts of data are challenges of our time. This unique book suggests general approaches of 'complexity of descriptions'. It deals with a variety of concrete topics and bridges between them, while opening new perspectives and providing promising avenues for the 'complexity puzzle'.

This book introduces an important group of logics that have come to be known under the umbrella term 'susbstructural'. Substructural logics have independently led to significant developments in philosophy, computing and linguistics. _An Introduction to Substrucural Logics_ is the first book to systematically survey the new results and the significant impact that this class of logics has had on a wide range of fields.The following topics are covered: * Proof Theory * Propositional Structures * Frames * Decidability * Coda Both (...) students and professors of philosophy, computing, linguistics, and mathematics will find this to be an important addition to their reading. (shrink)

In spite of a powerful tradition, more than two thousand years old, that in a valid argument the premises must be relevant to the conclusion, twentieth-century logicians neglected the concept of relevance until the publication of Volume I of this monumental work. Since that time relevance logic has achieved an important place in the field of philosophy: Volume II of Entailment brings to a conclusion a powerful and authoritative presentation of the subject by most of the top people working in (...) the area. Originally the aim of Volume II was simply to cover certain topics not treated in the first volume--quantification, for example--or to extend the coverage of certain topics, such as semantics. However, because of the technical progress that has occurred since the publication of the first volume, Volume II now includes other material. The book contains the work of Alasdair Urquhart, who has shown that the principal sentential systems of relevance logic are undecidable, and of Kit Fine, who has demonstrated that, although the first-order systems are incomplete with respect to the conjectured constant domain semantics, they are still complete with respect to a semantics based on "arbitrary objects." Also presented is important work by the other contributing authors, who are Daniel Cohen, Steven Giambrone, Dorothy L. Grover, Anil Gupta, Glen Helman, Errol P. Martin, Michael A. McRobbie, and Stuart Shapiro. Robert G. Wolf's bibliography of 3000 items is a valuable addition to the volume. (shrink)