Abstract The Pigeonhole Principle for n is the statement that there is no one-to-one function
between a set of size n and a set of size n− 1. This statement can be formulated as an …

The method of analytic tableaux is a direct descendant of Gentzen's cut-free sequent
calculus and is regarded as a paradigm of the notion of analytic deduction in classical logic …

LK is a natural modification of Gentzen sequent calculus for propositional logic with
connectives¬ and∧,∨(both of bounded arity). Then for every d≥ 0 and n≥ 2, there is a set …

We study the complexity of cutting planes (CP) refutations, and tree-like CP refutations. Tree-
like CP proofs are natural and still quite powerful. In particular, the propositional pigeonhole …

The weak form of the Hilbert's Nullstellensatz says that a system of algebraic equations over
a field, Q/sub i/(x~)= 0, does not have a solution in the algebraic closure iff 1 is in the ideal …

In this paper we study the pairs (U, V) of disjoint NP-sets representable in a theory T of
Bounded Arithmetic in the sense that T proves U∩ V=∅. For a large variety of theories T we …

We analyze the search efficiency of a number of common refutational theorem proving
strategies for first-order logic. We show that most of them produce search spaces of …

If p is a prime and n is a positive integer then the mod p counting principle for n (CPp, n) is
the following statement: there are no two equivalence relations@ and@ on a set A of size n …

FIRST-ORDER LOGIC AND AUTOMATED THEOREM PROVING Page 1 AND
MONOGRAPHS IN COMPUTER SCIENCE FIRST-ORDER LOGIC AND AUTOMATED …

The forward chaining algorithm is perhaps the best-known algorithm in expert systems.
However, it is not complete because it cannot compute the two-valued consequence literals …