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 present a connection tableau based calculus extended by the possibility to exploit equivalences. By making equivalences explicit, it is on the one hand possible to apply well-known methods of equality reasoning, like demodulation, on the predicate level—even in top-down backward-chaining calculi. On the other hand, the explicit use of equivalences allows to strengthen calculi refinements. We show that such an approach has great potential to reduce the search space and to find proofs which are otherwise unobtainable in reasonable time. (...) Since many problems only contain equivalences implicitly, we propose a technique to generate them automatically in the course of the deduction process.1. (shrink)