Short Proofs of TautologiesUsing the Schema of Equivalence?Matthias Baaz?? Richard Zach???Technische Universitat Wien, AustriaAbstract. It is shown how the schema of equivalence can be used to ob-tain short proofs of tautologies A, where the depth of proofs is linear in thenumber of variables in A.The schema of equivalence Eq(A, B)) C(A), C(B) Eq(A, B, C arbitrary formulas) is the propositional pendant of the schema of identity.It can be argued that, apart form the usual propositional tautologies and inferenceschemas which are given as axiomatizations of propositional logic (e.g., modus po-nens, modus tollens, case distinction, chain rule), the schema of equivalence is alsoused extensively in mathematical reasoning. However, it seems that Eq has not beenused or investigated in the proof theory of propositional logic to any signicant ex-tent. A related rule, which has been presented by Schutte [1960] (see Satz 2.9), isthe following: C(T ) C(F )C(A) Swhere A and C are formulas and T and F are the logical constants true and false,respectively. Using S, we can derive Eq uniformly for A, B, C in a constant numberof steps: (1) T , T ) C(T ), C(T )(2) F , T ) C(F ), C(T )(3) A, T ) C(T ), C(T ) from (1), (2) by S(4) T , F ) C(T ), C(F )(5) F , F ) C(F ), C(F )(6) A, F ) C(A), C(F ) from (4), (5) by S(7) A, B ) C(A), C(B) from (3), (6) by S? to appear in Computer Science Logic. Selected Papers from CSL'93, LNCS, Springer,1994?? Technische Universitat Wien, Institut fur Algebra und diskrete Mathematik E118.2,Wiedner Hauptstrae 8{10, A-1040 Wien, Austria, baaz@logic.tuwien.ac.at??? Technische Universitat Wien, Institut fur Computersprachen E185.2, Resselgasse 3/1,A-1040 Wien, Austria, zach@logic.tuwien.ac.at1 Eq can be used for the evaluation of complex propositional expressions in abounded number of steps: Let P be some sound and complete Hilbert-style calculusfor propositional classical logic (with an alphabet including T , F ,), _,, as prim-itive or derived constants) consisting of a nite number of axiom schemata and rules(one of which is assumed to be the modus ponens). Let Tn be the set of tautologiesin  n variables, and let `k denote derivability in depth  k (w.l.o.g. proofs areassumed to be tree-like).Theorem For all n the following holds:(1) there exists s.t. for all n and all A 2 Tn we have P + EQ `(n) A, where isa linear function and(2) for all k there is an A 2 T0 s.t. P 6`k A.Proof. If  = fA1; : : : ; Amg, then V ) B denotes (A1 ) (A2 ) : : : (Am )B) : : :).(1) First note that the k-times iterated schema of equivalence,mi=1(Ai , Bi)) C(A1; : : : ; Am), C(B1; : : : ; Bm)is derivable uniformly in  (m) steps from P + Eq. Now we use induction on n:n = 0: Let  = 2i(V1; : : : ; Vni) , V j Vj ; V 2 fT; Fg be all combinationsrepresenting the truth tables for the primitive connectives 2i. Furthermore, let  bean operator where B is obtained from a formula B by replacing every subformulaof the form 2i(V1; : : : ; Vni) (Vj 2 fT; Fg) by its value V 2 fT; Fg. By j we denotethe j-fold iteration of : 0B  B and j+1  jB. (Here and in the following denotes syntactic equality).Now A 2 T0 contains no variables, only T , F . Let r(A) be the minimal numbers.t. r(A)A  T . We use Yukami's Trick (from Yukami [1984]): The two formulas^ ) A, 1A,    (r(A)1A, Tz }| {r(A)A) : : :| {z }B ,, 1A, (2A,    ( Tz }| {r(A)A, Tz }| {r(A)+1A) : : : | {z }C and (T , T ), T )  Cz }| {1A, (2A,    r(A)1A, (T , T ) : : :,, 1A, (2A,    (r(A)1A, T  : : :| {z }B are instances of the (iterated) schema of equivalence, thus derivable independent of Afrom P +Eq. Since both  and T , T ), T  are tautologies, they can be derived2 in a constant number of steps independent of A. Hence, P +Eq `c (A, B), Band consequently also P + Eq `c0 A.n > 0: Let A(X) 2 Tn contain exactly n distinct variables. The following formulas(X , T )) A(X), A(T )(X , F )) A(X), A(F )are instances of Eq. By induction hypothesis, both A(T ) and A(F ) are derivable in(n 1) steps from P +Eq. Hence we haveP + Eq `(n1)+d (X , T )) A(X)P + Eq `(n1)+d (X , F )) A(X)and consequently P + Eq `(n1)+d0 A(X). (Note that the law of excluded middle(X , T ) _ (X , F ) is derivable.) Since d0 (and d) do not depend on either A(X)or n, is linear.(2) Note that there are only nitely many proof descriptions (or proof skeletons,see Krajicek and Pudlak [1988]) of bounded depth. Every proof description canbe realized by a most general proof: Write all axioms with dierent variables, applythe rules in the description and unify. So, for every k, there is a sequence of formulasA1, : : : , Ah(k) s.t.(1) P `k Ai for 1  i  h(k) and(2) if P `k A, then A = Ai for some Ai and substitution .If all tautologies of the form T , (T , (T ,    (T , T ) : : : were provable inbounded depth, then T , (T , (T ,    (T , X) : : : would also be provable,which is absurd. 2Three questions regarding the strength of these results remain open: In the induc-tion step of the proof, the law of the excluded middle was used essentially. Can theresult also be obtained without this? Does the result hold for intuitionistic proposi-tional calculus? Furthermore, does the rule of equivalenceA, BC(A), C(B)suce for the results to hold? Lastly, do the results hold uniformly for all tautologies,not only for those with a xed number of variables?ReferencesKrajicek, J. and P. Pudlak.[1988] The number of proof lines and the size of proofs in rst order logic. Arch.Math. Logic, 27, 69{84.Schutte, K.[1960] Beweistheorie. Springer, Berlin.Yukami, T.[1984] Some results on speed-up. Ann. Japan Assoc. Philos. Sci., 6, 195{205.