From: AAAI Technical Report FS-93-01. Compilation copyright 1993, AAAI (www.aaai.org). All rights reserved.

A Tableau-Based Theorem Proving Methodfor Intuitionistic

OliverBittel Fachhochschule Konstanz* Abstract
A newtableau-based calculus for first-order intuitionistic logic is proposed. The calculus is obtained from the tableau calculus for classical logic by extending its rules by A-terms. Aterms are seen as compact representation of natural deduction proofs. The benefits from that approach are two-fold. First, proof search methods knownfor classical logic can be adopted: Run-time-Skolemization and unification. In contrast to the conventional tableau, sequent, or natural deduction calculus for intuitionistic logic we get no problem with order dependance of rule applications in our calculus. Therefore, backtrackingis only necessaryin the selection of unifiers. Second, as a by-product A-terms are synthesiszed for free during proof search. A-terms are important, whenintuitionistic logic is applied in a programsynthesis framework. Weimplementedthe calculus in Prolog. A strategy which is similar to model elimination has been built in. Several formulas (including program synthesis problems) have been proven automatically.

Logic

Introduction

In many papers, the intuitionistic logic has been proposed as a logic for program synthesis (see e.g. [Mar82], [Con86], [BSII90]). A formula of the form Vx.3y.P(x, y) specifies a program, which takes an input z and yields an output y such that the condition P(z,y) holds. A constructive (intuitionistic) proof of such a specification can be seen as a program satisfying this specification. E.g. the following formula specifies the integer square root function: Vn G Nat. 3r E Nat. 2 r 2 < n < (r + l)

A proof of this formula consists of a function f mapping a natural number n to a pair (r, M), whereby r is the integer square root of n and Mis a proof for that. The main characteristic of this program synthesis paradigm is that proofs are performed in the natural deduction calculus. Instead of taking a natural deduction proof as program, it is more appropriate to use a more compact representation, usually a A-term. There is a direct correspondence 1 In intuitionistic logic a prooffor a A13 is a pair consisting of a between proof rules and program constructs: case analy- proof for c~ and a proof for 13. Toget the components of the pair sis in proofs and A-terms, inductions and recursions, and the projectionsfst and and are used. 2Aclosed tableau for -M: c~ means,that the assumption ".~v/ finally lemmas and subroutines. is not a proof for a" leads to a contradiction. Thus, Mis a prcof *Authors address: FachhochschuleKonstanz, Fachbereich In- for a. 3Theusual term unification is meant. Weneed no unification formatik, Postfach 10 05 43, D-78405 Konstanz, Germany,E-mail: modolo/~-.reduction or anything else. [email protected]

In order to solve realistic problems, it is important to automate at least the trivial parts of a proof. For that, we need an automatic theorem prover for the intuitionistic logic which is efficient and yields A-terms if formulas are valid. Our approach is based on a signed version of a tableau calculus for classical logic. Its rules are extended by Aterms. Two kind of formulas may occur in a tableau: +M : a means that (the A-term) M is a proof for and-M : ~ means that M is not aprooffor c~. Most of the extended tableau rules are straightforward translations of the natural deduction rules with A-terms. E.g., if +M: c~ A ~ occurs in a branch, then +fst(M) : ~ and +snd(M) : /~ may added to the branch; 1 if-(M, N) A fl occurs in a branch, then a branching may be introduced with -M : a as new left node and -N :/~ as new right node. Itowever, the translation is not straightforward for the disjunction rules. If we have +M: aVfl, then Mrepresents either a prcof for c~ or one for ~. But we have no linguistic means (Aterm constructs) to express this. For that, we introduce some new A-term constructs: partially defined A-terr~s and implicit case analysis. In the case of +M: a V ~, v e get partially defined A-terms as proofs for a and for ft. Implicit case analysis is a list of A-terms and is usefull for formulas, whose proofs consist of several cases. There is some simalarity between guarded commandsand implicit case analysis. Our calculus is presented in two versions. The ground version is helpful for making soundness and completeness proofs easier. If a formula a has to be proven in that calculus, one must guess a A-term Mand search a closed tableau for -M : a.2 The second version is a lifted version of the ground calculus. Guessing A-terms and individual terms are not necessary any longer. Meta-variables 3 are used which are instantiated by unification. One of the main drawbacks of the conventional tableau, sequent or natural deduction calculus is the strong ord Jr dependance of rule applications. The problem is wellknown for quantifier rules in classical logic. There, the

problem can be solved by Skolemization, which is not possible for intuitionistic logic. Moreover, in intuitionistic logic the problem already exists on the propositional level as the following example shows.4 If we want to prove a V b,a ~ c,b --* d b- c V d, we have several possibilities to apply a rule. Decomposing the right-hand side yields the two subgoals a V b,a --* c,b --* d ~- c and aVb, a ~ c,b ~ d I- d and leads to a dead end as it can be easily seen. The only way to succeed is to decompose a V b first. Note, that decomposing one of the implications on the left-hand side would also lead to a dead end. In the sequent calculus for classical logic in contrast, several formulas on the right-hand side are allowed. A decomposition of e V d leads to two new fomulas on the right-hand side: a V b,a -* e, b --* d l- c,d. So, we can not choose wrong. That is the reason, why there is no dead ends problem in classical propositional logic. In our calculus we have the same situation: several negativly signed formulas are allowed to occur in a tableau branch, s A decomposition of -c V d extends the branch by two new nodes -c and -d. Therefore, in our calculus there is no bracktracking necessary for that example. In literature, there are mainly two approaches for automatic theorem proving in intuitionistic logic: 1. Systems such as NUPRL [Con86] and OYSTER [BSII90] are based on tile sequent or the natural deduction calculus. They provide tactics and tacticals for conducting backward proofs. The calculi are very much appropriate for synthesizing A-terms. But as discussed above, the main problem is the strong order dependence of the rules. In [Sha92] a kind of Herbrandization is used to record the impermutabilities of some of the intuitionistic sequent rules. The amount of backtracking could be reduced. But the problem with the disjunction (see example above) still exists. 2. In the last years, several proof methods for modal and intuitionistic logics have been proposed. Among them are matrix-based proof methods [Wa188] and resolution calculi [Oh188]. Both approaches are based on Kripke-style semantics and refutation theorem proving. The main idea is that the formula to be proven is translated to a matrix [Wa188]or a set of clauses [Oh188] such that it can be handled like in the classical logic. The Kripke-style semantics is taken into account by introducing so-called world paths in predicates and functions and to use a specific unification procedure for the world paths. These proof procedures work well if only the question of validity of a formula is interesting. However, in order to integrate an automatic theorem prover in the program synthesis approach considered here it is mandatory to get 4 A sequent style formulation is used. The same problemalso occurs in the tableau and the natural deductioncalculus. 5There is also no branchmodification rule as it is the case in the conventionaltableau calculus for intultionistic logic [Fit83]. The branchmodificationrule deletes all negativly signed formulasin a branch and must be applied additionally by somerule applications. eThere is a strong correspondencebetweenthe modallogic $4 andthe intuitionistic logic [Fit83].

a A-term (or proof in the natural deduction calculus) case a formula is proven valid. At this point it should be mentioned that in classical logic there are some methods which allow the transformation from matrix and resolution proofs to natural deduction proofs (see [Wos90] as overview). However, these translations generate nonconstructive proofs in some cases.

First-Order Intuitionistic

Logic

In this section, a first-order language, A-terms and the calculus of natural deduction with A-terms are defined. This calculus can be seen as a subset of Martin-L5fs intuitionistic type theory [Mar82]. The definition is very similar to the one found in [Coqg0]. Let V be a set of variables. An individual term is either a variable or of the form f(t 1 .... , tn), wheref is a function symbol with arity n > 0 and ti are individual terms. The set of all individual terms are named by 7-. Fomulas are defined in the usual way by using relation symbols, individual terms and the logical connectives A (and), (or), -- (implies), (falsity), quantifier symbols 3. -,a is defined as a --~ . For a formula a, a variable x and a term t, c~[x/t] denotes the result of substituting each free occurrence of x in a by t. 7 FV(a) is defined to be the set of all free variables in a. The set A of all A-terms is defined by the following ~ Ainductive definition. Let x E 12, t E 7- and M, N, N terms. Then the following expressions are also A-terms. z t MN ~z.M ( M, N) fst(M), sad(M) split(M, N) inl(M), inr(M) when(M, N, N) absurd(M) variable individual term application abstraction pairing projections pair application injections case analysis

For a A-term M, a variable x and a A-term N, M[x/N] denotes the result of substituting each free occurrence of x in Mby N. 7 FV(M) means the set of all free variables s in M. There are also some conversion rules (Ax.M)N t> M[x/N] when(inl(N), Ax.M, O) I> MIx~N] when(inr(N), ~x. M) l> M[x /N] split((N1, N2), ~xl .)~x2.U) I> M[x~/N1][x2/N2] A context is a finite set {xl : al .... ,x, : a,}, where cq, ..., c~n are formulas and x 1,..., xn are pairwise distinct variables which must not occur in al,..., an. An expression like M: a is also called a proof relation. 9 For any rWeassumethat renamingof bounded variables is done in order to avoid nameclashes. awehave omitted the so-called commuting conversions. For a complete definition see e.g. [Gir89], [Bit91]. 9I.e. M is proof for c~. It is also known as type relation, i.e. M is of type c~. Thereis an isomorphism between types and formtdas (see e.g. [t..ow80]).

10

want to motivate some of them. If Ax.M is not a proof for a -+ /~ (i.e. -Ax.M : c~ --. /~) then by the (- -+)rule, Mcan not be a proof for fl (i.e. -M : F) under the assumption that x is a proof for ot (i.e. +x : a). If know Mto be a proof for c~ --./~ (i.e. +M: a -+/~) may introduce a branching using the (+ -+)-rule. For arbitrary A-term N, we may assume that either N is not Remark: If the A-terms in the rules are omitted we ex- a proof for a (i.e. -N : c~; left branch) or N is a proof for a. In the latter case, we infer that MNis a proof for actly get the usual natural deduction calculus for intu/~ (i.e. +MN :/~; right branch). itionistic logic. However, the calculus with A-terms offers The most complicated rules are the disjunction rules the possibilty not only to check the validity of a formula and the rules for the existential quantifier. This is not a but also to construct a A-term which can be seen as the so much surprising, since disjunction and existence are desired program satisfying a. known to be the two most typically intuitionistic connectors [Gir89]. If we have a proof Mfor aV/~, then Mrepresents either 3 The Ground Calculus a proof for a or one for/~. But we have no linguistic means In this section a tableau-based calculus is presented which (A-term constructs) to express this. For that, we introallows to prove relations like E ~- M : a. During proof duce two new constructors 1 and r. I(M) is only defined search A-terms and individual terms have to be guessed. if Mrepresents a proof for the left part of a disjunction. defined whereas l(inr(N))is not. Therefore, we call it ground calculus. It is obtained from Thus, l(inl(N))is the tableau calculus for classical logic by extending its property is expressed by the following conversion rules: rules by A-terms. For that, we introduce projections l(inl(N)) for existentially bounded formulas and some new A-term l(inr(g)) I> T (undefined) constructs which we call implicit case analysis and inr(M) can be considered analogously. Thus, l(M) verses to the injections. The inverses lead to partially defined A-terms. With the help of a transformation proce- r(M) are partially defined A-terms. In some sense, 1 and dure, projections and implicit case analysis (together with r is inverse to inl and inr, respectively. With the new the inverses) can be replaced by pair-application (splitconstructors, the formulation of the (+V)-rule becomes straightforward. construct) and explicit case analysis (when-construct), Next, we introduce the implicit case analysis, which is respectively. a list of partially or totally defined A-terms: context E, the set of all free variables occuring in E is denoted by FV(E). For any context I], A-term M and formula a, we define the relation E ~- M: a by the rules shown in table 1. If ]E }- M: a holds we also say that a is (intuitionistically) valid under the context ~ and the A-term M is a proof for that. If 0 I- M: a, then a is (intuitionistically) valid. 3.1 Informal Description of the Calculus [M1, M2, ..., M,]

Tableaux are trees labeled with signed proof relations of the form +M: a and -M : a. The intuitive meaning is the following: occurs in a tableau branch 7r +M : a -M:a meaning E~ I- M: a ~v E~[/M:a

Each Mi represents one case. If one of the cases is totally defined, the implicit case analysis can be reduced to that case: [M1, M2, ..., M,] 1> Mi, if not Mi !> T

In order to check {xl : 71 .... ,x, : 7-} I- M: ~r, we start with the following intitial tableau which consists of one branch with n + 1 nodes: +xl : 71
-I-Zn : 7n --M " oI

The implicit case analysis is very similar to a guarded command, where the conditions are left implicit. The usual (explicit) case analysis when(M, Apl .N1, Ap2.N2) can be expressed by an implicit case analysis [NI[Pl/I( M)], N2~2/r( M)]]

The (-V)-rule can now be read in the following way: [inl(M), inr(g)] is not a proof for c~V/~, then both To this initial tableau several tableau rules (shown in ta- not a proof for c~ and N is not a proof for/~. ble 2) are applied until a closed tableau is reached, i.e. Since a proof for an arbitrary formula may be a case a tableau where each branch contains a complementary analysis, the rule (-[])is also needed. pair +N : 7 and -N : 7. As we will see in the following section A-terms with Most of tile tableau rules are straightforward translaimplicit case analysis can easily be transformed to those tions of the natural deduction rules with A-terms. We with the usual explicit case analysis. At last, the (+B)-rule shall be considered. If M is l~,r is the context that corresponds to the branch r, i.e. ~ = proof for qx.a, then M represents a pair, consisting of {x : c~ I +x:aE r and x E V}.

11

Table 1: Natural deduction calculus with A-terms 3.2

(-^) -(M,N) :a ^/3 -M:~ [ -N:B -[inl(M),inr(N)] : ~ -M : a -N:~ +M:avB +I(M): a I +r(M): -~x.M: c~ ---. B (+^) -}-M: o~ ^/3 +fat(M): +snd(M)

Formal

Definition

of the

Calculus

(-V)

Definition 1 (Extended A-terms) The set AE of all extended A-terms is defined inductively as follows. Let f be a function symbol with arity n > O, x ~ V and M, N, M1, ..., ~[n extended A-terms. Then the following

expressions are also extended A-terms:

x variable individual term f(M1, ..., M,) M N application ),x. abstraction pairing (M, N) fat(M), and(M) projections for proofs of A-formulas projections for proofs of S-formulas rata(M), anda(M) injections lnl(M), inr(M) inverses to the injections l(M), r(M) [M~,...,M,],n >_ 0 implicit case analysis absurd(M)

(+v) (- -) (-v)
(-~)

+x:~,
-M :[3 -Ax.M : Vxc~ -M : c~ -(t, M): ~x.c~ -M : o[x/t] -[MI,M2 ..... -MI :a -M2 : -M, :

(+ -.) (+v)

+M : ~ ~/3 -N : c~ I +MN: I3

+M: Vxc~ +Mr: c~[x/t] +M : ~x.c~ (+:~) +snd](M) : a[x/fst](M)]

M.I:

(-ll)

Definition 2 (Extended individual terms) The set TE of all extended individual terms is defined inductively
as follows. Let x ~ V, M ~ AE, f a function symbol with arity n > 0 and Q,...,tn extended individual terms. Then x,f(G,...,t,),fst~(M) are extended individual terms, too. Definition 3 (Extended formula) The set of all extended formulas is defined inductively. Each formula is also an extended formula. If c~ is an extended formula and t ~ TE, then c~[x/t] is an extended formula.

Table 2: Tableau calculus with A-terms

a term t and a proof for a[x/t]. We use the projection functions fat~ and snd~ to access to the pair components. Thus, the formulation of the (+q)-rule becomes straightforward. The index ~ in the projection functions is used to distinguish them from the projections used for conjunctions. Now, A-terms of the form fst~(M) are also allowed to occur in formulas. They denote in some way constants These terms together with individual terms will be called extended individual terms, t in the rules (-2) and (+V) is restricted to be an extended individual term.

Definition 4 (Tableau)A tableau is a binary tree which is labeled with signed proof relations of the form +M : c~ and -M : a where M ~ AE and c~ is an extended formula. Let F be a set of signed proof relations. An initial tableau for F consists of exactly one branch rr such that F is the set of all labels in ~r. If no confusion is possible, we identify F with some initial tableau for F. ~Wewrite ~,x : c~ instead of E u {x : a}. ~2x must not occur free in the branch where the rule is applied.

12

A branch ~r is called closed if both +M: a and -M : c~ or if both +M : .1_ and -absurd(M) : (c omplementary pairs) occur in 7r for some M E As and some extended formula a. A tableau is closed if all its branches are closed. Definition 5 (Tableau extension) Let T, T~ be tableau~: and r one of the tableau rules. We define the relation T ~ T~ (7" is extended to ~ by r ule r ). I general, r is either a branching or a non-branching rule of the following form:

An

right way would be to carry out first a case analysis using the assumption b V c and the (VE)-rule. It is clear that this property of the natural deduction calculus becomes worse if E increases in size or nested case analysis are required. On the contrary, the tableau calculus is free from dead end. It does not matter in which order rules are applied. As we can see in the example, first +aAb--* g was decomposed before we introduce a case analysis by decomposing +b V e. The tableau would also be closed if the rule order would be changed. The order of the rule applications in the example comes up if a strategy is used which requires branches to be closed as soon as possible. 15 E.g. after node (8)., the decomposition of +a A b --~ g was chosen, because it leads to two closed branches (see node (11) (10)).

T __L. T holds if there exists some branch zr in T such that A (the upper part of r) occurs in r and ~ i s o btained from T by extending r in the following way:

In order to define the notion of validity some global constraints on tableaux are necessary. As the example above shows, the tableau T would remain closed if the implicit case analysis in node (4) and (6) would be If r is a branching rule of the form (1), then zr 16 extended by a branching with one left and one right tented by a further arbitrary ,Lterm N. Since we want to transform ,~-terms of AE to usual ,Lterms of A, such node labeled with A1 and A2, respectively. an additional arbitrary ,~-term N would have a disturbing lfr is a non-branching rule of the form (2), then 7r effect. Thus, we require each negatively signed proof reextended by n nodes which are labeled with AI,..., An. lation to be participated either in a rule application or in a complementary pair. Another problem comes from the The proviso of the rules (- ---,) and (-V) must be taken fact that in the (+V)-rule t may contain a ~-term fst3(N), into account. We write T g~, T~ if there exists a rule r where N can be a completely senseless term. However, if such that T r , T~" g~. is defined to be the reflexive and a node labeled with +N : qx.a appears in the tableau, transitive closure of ge,. the term fst3(N) would make sense. We comprise these global constraints in the following minimality condition. Example: Let IC = {Y0: a A b ~ g, Yl : c ---, g, Y2 : b V c} be a context. The figure 1 shows a closed tableau T where Definition 6 (Minimal tableaux) A tableau T is q-~ u {-),x.lylr(y2), y0(z,l(y2))] : a --* g} called minimal iff two conditions hold: By the soundness result EI- a ---* g (see below), we also get: (i) For each -M : ~ occuring in T the following is true:

Thenodes (5) and(6) in result from no de (4 ) by app licationof (- ---,). Note, that the pairs of nodes (9),
and (15), (16) result from the application of (+ --*). that, the ,Lterms in node (9) and (15) were guessed.

= I] - M

(empty case analysis),

- a tableau rule is applied to -M : a, or - there exists some +M: a in T, such that both -M : a and +M : a occur in the same branch (complementary pair),

Comparison between tableau calculus and natural deduction calculus: Suppose we want to find a proof in - there exists some +N : _k in T, such that M = the natural deduction calculus for Z I- a ---* g.14 For that, absurd(N) and both -M : a and +N : _k occur it is appropriate to start with the goal sequent E I- a ~ g in the same branch (complementary pair). and apply rules in a backward manner. Using the (---q) rule we obtain the subgoal E, a I- g. Now,there are sev- (it} For each fst~(N) occuring in T there exists some forn:ula 3x.a and some node in T which is labeled eral possibilities to continue. If we decide to decompose with + N : 3x.~. aAb --* g G E with the (---~E)-rule, we get the two subgoals E,ataAb---* g and E,ataAb. Definition 7 (go-Validity) Let ~ be any context, M E AE and (~ any formula. We define ~ ~-g~ M : c~ if there eziMs some closed and minimal tableau T such that +E U {-M : or} g*, T.

The first sequent is trivially true but the second sequent can not be derived. Thus, we went into a dead end. The

lSActually, this strategy is taken form [Sch85]and is similar to 13+I~={+M:aIM:c~G~}. 14We choose~ as in the exampleabove. For simplicity, A-terms modelelimination. 16An extensionby N would lead to [yl r(y~), Yo (x, I(y2 )), are omitted.

13

(1) +yo aAb-.-+g

(2)+yi :c~o (4) --~=.[~lr(u2),~0(x,l(~2))! :a (5) +=.", from (4)

(6) - [Yl r(y2), Y0(w, l(y2))! : g (3) +Y2 : bVc

(r) -y~r(y2) : o from

(8) -Yo(x,l(y2)) : g from

(9) -(x,l(y~)) : a A b from

(10) 4-y0(x,l(y2)) : g from (8) and (10)

(11) -x : a from (9) (5) and (11)

(12) -1(92) : b from (9)

(13) +l(y2) : b from (12) and (13)

(14) q-r(y2) : c from

(15) -r(y2) : c from (1"4) and (15)

(16) +ylr(y2) : g from (7) and (16)

Figure 1: Closed tableau T 3.3 Soundness

h (inr(M)) = inr(t(M)) h (absurd(M)) = absurd(t(M))
tl (](M1, Ms..... Mn)) = f(t(M1), t 1 (fst(M)) = fst(t(M)) t I (snd(M)) = snd(t(M))

As we have seen in the previous section extended A-terms are an appropriate meansfor representing tableau proofs. ExtendedA-terms can also be seen as programswhich can be evaluated by somespecial conversion rules. However for efficiency, A-termswith explicit case analysis are more suitable for programs. Therefore, we give a procedure which transfoms extended A-terms to usual A-terms with explicit case analysis (instead of implicit) and pair applications (instead of projections). This transformation also used to establish a soundnessresult. The idea of the transformation is simple: the A-termis visited from outermost to innermost. As far as A-terms l(N) and r(N) are detected, where the transformation ~ E A, we replace I(N) and N E AEleads to a A-term N r(N) by introducing a when-construct with N as first argument. Similarly, projections are handled. Definition 8 (Transfomation t)

t~([M~,Mz ..... M.]) = rain{t(M~) I 1 < i < n and t(M0

t(M2) t(Mn))

/l(fst3(M)) : c, where c is any constant

q (x) Note, that the function t is partial; e.g. t(Ax.l(x)) is not defined. Theorem 9 (Soundness) If~,, }-ac M: o~ then ~ 1- t(M): o~. In the example above we have shown that r, ~-g. Ax.iy,r(yz),t/o(x,l(y2))] -~ o By transformation t and the soundnessresult it follows

~ when(yz, Xx,.~x.(u0(x, ~,)), Xxz.Xx.(wxz))

This A-term corresponds to a natural deduction proof, wherefirst a case analysis is carried out by applying the (VE)-rule to the assumption b V e. Then in each case, a --* g on the right-hand side is decomposed by (--d). 3.4 Completeness

t(iH) = when(t(N), AXl .t(M[I(N)/=I]), Ax2.t(M[r(g)/x~])) if SIr(M ) lr ~ $, N = rain(Sir(M)) = min(S(M)) t(M) = split(t(N),AXl.AX2.t(M[fst~(N)/xl][snd3(N)/x2])) if Sfstsnd(M ) lr ~ 0, N = min(Sfstsnd(hI)) = min(S(M)) t(ltf) tl (M), if S(M )=0 SIr(M ) = {P [l(P) F(M),r(P) F(M) and t( P) A} is Sfstsnd(M) = {P [ fst3(P) f( ~I) an d t( P) A} U {P [ snd3(P) F(M) and t( P) A}

S(M) = SIr(M) U Sm,.d(M)

t1(Ax.M) = Ax.t(M) q(MN) = t(M)t(N) q((M,N)) = (t(M),t(N)) h (inl(M)) = inl(t(M))

The main key to prove completeness is the normalization theorem(see e.g. [Gir89]), whichsays that each typed term ME A (i.e. ~ I- M: a, for some~ and a), can
17=1, =2 are new. rain is defined wrt. any given term ordering. 18F(M)= {N [ occurs in M a ndno f ree varia ble of N is bound in M}. E.g., F(Ax.x(yz)) {y, z, yz, Ax.x(yz)}. 19This case is helpful in the proof of soundness.

14

brought into a normal form M such that M I>* M and Here, f is a new Skolem function, and VL is the set E I- M : a. Then, by using a function t : A ) AE, we of all metavariables occuring in the branch where the I : a it follows E l-go t(M) : can show that from E l- M rule is applied. So, the Skolem expression f(VL) can be understood as a new variable. In order to avoid Definition 10 (Transformation t) conflicts with substitutions, we use a non-binding abt(X~.M) = ~=.e(M) straction lambda(N, M). As far as tableaux are closed, t(MN) = t(M)t(N) non-binding abstractions lambda(N, M) are replaced f((M,N)) = (F(M), t(inl(M)) = [inl(F(M)), inr([ usual abstractions Ax.M[N/x]. t(inr(M))= [|nl([ I), inr(t(M))! The main difficulty arises from the implicit case analt(fst(M)) = fst(t(M)) ysis. If the (-[])-rule would be applied the number t(snd(M)) = snd(t(M)) eases n would have to be guessed. For that reason, this t(absurd(M)) absurd(t(M)) rule is omitted and we presume that the A-term in each t(split(M, AXl.Ax2.N)) negatively signed proof relation is a priori an implicit case = t(N)[xl/fst3(F(M))][x2/snd3(t(M))] analysis. In general, a negatively signed proof relation is t(when(M, Axl .N1. Ax2.Na)) t (N 1 )[xl /l(t(M))], of the following form: t(Ns)[x2/r(t(M))] t($(M1,Ms..... M,)) = f(t(M1), t(M2) t(M,~)) -[M1,Ms..... M, IL] : ct, s0 wheren > 0. (,) t(x) = L is a metavariable which stands for a list of further Lemma 11 IfZF" M : c~ then E~-ac t(M) : c~, for any cases. L can be refined by rule applications and closM E A in normal form (wrt. t>). ing of branches. If c~ in (,) would be /~ A 7, then (--A) may be applied. That would lead to a refinement of (,) From this, the completeness result is obtained by the by one further case normalization theorem. -IMp, Ms..... M,, (L~, Ls)[Ls] : ~ Theorem 12 (Completeness) If~ F M : ct then there and to a tableau extension by a branching with two new nodes labeled with ezists some M E AE such that ~ I-ge M : c~. -L1 : f~ and -L2 : 7 Now, L1, L2, Ls are metavariables which may be refined 4 The Lifted Calculus later. Similarly, L would have been refined if (*) would have In contrast to the ground calculus, guessing A-terms and individual terms is avoided by using metavariables, which been involved in closing a branch. The other tableau rules are defined as described for the may be instantiated during tableau extensions. The instantiations result from applications of tableau rules and conjunction. Rules for positively signed proof relations closing of branches. This technique is also knownas liftremain as before (see table 2). The only exception is for ing technique. Actually, the lifted calculus is not a proper the rules (+ --*) and (+V), where metavariables L X are used instead of N and t, respectively. Rules for lifted version of the ground calculus, because the (-[])rule has been made implicit for some reasons which shall negatively signed proof relations are modified by using metavariables instead of A-terms. Skolem expressions are be discussed later. E.g., the rules for the conjunction are as follows introduced in the rules (- ---~) and (-V). The rule (-[])is +M :c~AB omitted. Weleave out a complete definition of the lifted -(X,Y) : c~AB (+A) (--A) +fst(M) : calculus and finally mention the main result. -X:c* [ -Y:/~ +snd(M): where X and Y are metavariables. (+A) works as before whereas applications of (-A) lead to instantiations. order to synthesize a A-term Msuch that x : a A b t-#e M : b A a we start with the initial tableau T1 (shown in figure 2), where Xl is a metavariable. By application of (+A) to (1) we get tableau T~. Applying (-A) (2), the tableau is extended to T3 and X1 is instantiated by (X2, X3), where X2, Xs are new metavariables. Both branches can be closed by the substitutions [X2/snd(x)] and [Xz/fst(x)] (see T4). The substitutions are found unification. The desired A-term (snd(x), fst(x)) can be picked up at node (2). In order to fulfill the proviso for the rules (- ---~) and (-V), we employ Skolemization technique. -lambda(f(VL), X): a ---* (---*) +f(VL) -X:B Theorem 13 (Soundness and Completeness) The lifted calculus is sound and complete wrt. the ground calculus.

Conclusions

There are two worlds of proof methods for the intuitonistic first-order logic: proof-theoretic calculi and semanticbased calculi. The natural deduction calculus and the lelated sequent calculus come from the proof theory area. Because of the strong order-dependence of rule applications, the dead ends problem arises which results in a big amount of backtracking. However, A-terms are given easily, when a formula is proven valid. Resolution and matrix 2o[Ml,his ..... gin IL] is an abbreviation for [M1,M2 ..... where-- meansconcatination. Mn]+ L,

15

(1) +x : a^b (2)-Xz :bAa

7"1

(4) +snd(x)

(1) +x a^b (2)-Xz: b^a (3) +fst(x) : a

(2) -(x~,x3): b (4) +s.d(x)

(3) -I-fst(x)

(1) +x : a

(1) +x : a ^ (2)-(snd(x),fst(x)) :bAa (3) -I-fst(x) (4) +snd(x)

(5) -X2 : b (6) -X3

(5) -snd(x): b (6) --fst(x)

Figure 2: Some tableau extensions with the lifted method are semantic-based proof methods, dedicated to automatic reasoning. They do not have dead ends problem. Itowever, synthesis of A-terms is not considered. Tile tableau calculus presented here subsumes the advantages of both worlds: it is automatic and efficient (free from dead ends) and allows the synthesis of A-terms. One of the key notions is case analysis. In natural deduction proofs case analysis ((VE)-rule) has often to be done fore other rule applications, while in tableau proofs case analysis ((+V)-rule) can be arbitrarily delayed. property of the tableau calculus is reflected by a new A-term construct, which we call implicit case analysis. Therefore and because of the use of metavariables and unification, tile order of rule applications does not play any role. Since the new calculus is based on the one for classical logic, all the techniques developed in the area of automated tableau-based theorem proving for classical logic (e.g. [Sch85], [OpSu88], [Fit90]) can be carried over. have implemented the calculus in Prolog. A strategy [Sch85] which is similar to model elimination has been built in. Several formulas like the maximumof two and of three numbers and integer square root were proven automatically. 21 It is clear that this theorem prover can easily be integrated as automatic tool in a more interactive system like NUPRLand OYSTER. There is an interesting relation to the deductive program synthesis approach of Manna and Waldinger [MaWa80]. Their approach is also based on the classical tableau calculus, but branching (splitting) is not allowed. E.g. a goal a A fl (in our calculus -a A fl) is not allowed to be decomposed. This property lies inherently in their calculus. In contrary, in our calculus branching is allowed and therefore decompostion of all formula kinds is possible. The advantage is more flexibility in integrating different proof search strategies.

calculus

198, Oldenbourg-Verlag, 1991. [Bit92] Bittel, O., The A-Tableau Calculus: A new approach to Theorem Proving in the Intuitionistic Logic, Workshop on TheoremProving with Analytic Tableaux and Related Methods,Universitt Karlsruhe, Fakultt ffir Informatik, Interner Bericht 8/92, 1992. [BSHg0] Bundy, A., Smaill, A. Hesketh, J., Turning Eureka Steps into Calculations in Automatic Programm Syntesis, in Proceedings of the First Workshopon Logical Frameworks, Antibes, 1990. ICon86] Constable, R. L. et al., Implementing Mathematics with the Nuprl Proof DevelopmentSystem, Prentice-Hall, 1986. [Coqg0] Coquand, T., On the Analogy Between Propositions and Types, in Logical Foundations of Functional Programming, G. Huet led.), Addison-Wesley, 1990. [Fit83] Fitting, M., Proof Methodsfor Modaland Intuitionistic Logics, Holland, 1983. [Fitg0] Fitting, M., First-Order Logic and Automated Theorem Proving, Springer-Verlag, 1990. [Gir89] C-irard, J.-Y., Lafont, Y., Taylor, P., Proofs and Types, Cambridge Tracts in Theoretical Computer Science 7, 1989. [How80] Itoward, W. h., The Formulae as Types Notion of Construction, in H. B. Curry - essays on Combinatc.=y Logic, A -calculus and Formalism, Seldin/Hindley (Eds.), 579-606, AcademicPress, 1980. [Mar82] Martin-LSf, P., Constructive Mathematics and Computer Programming, in I. J. Cohen,J. Los, H. Pfeiffer and K. D. Podewski (Eds.), Logic, Methodologyand Phylosophy of Science VI, 153-179, North-Holland, 1982. [MaWaS0] Manna, Z., Waldinger, R., A Deductive Approach to Program Synthesis, ACM TOPLAS Vol. 2, No. 1, 90121, 1980. [Oh188] Ohlbach, H. J., A Resolution Calculus for ModalLogics, 9. CADE,LNCS 310, 1988. [OpSu88] Oppacher, F., Suen, E., HARP:A Tableau-Based TheoremProver, Journal of AutomatedReasoning, Vol. 4, 69 - 100, 1988. [Sch85] S(:h6nfeld, W., Prolog Extensions Based on Tableeu Calculus, IJCAI, 1985. [Sha92] Shankar, N., Proof Search in the Intuitionistic Sequent Calculus, 11. CADE,LNCS 607, 1992. References [Wa188]Wallen, L. A., Matrix Proof Methods for Modal Log[Bitgl] Bittel, O., Ein tableaubasierter Theorembeweiser fiir ics, IJCAI, 1988. die intuitionistische Logik, Ph.D. thesis, GMD-Report [Wosg0] Wos, L., The Problem of Finding a Mapping between Clause Representation and Natural-Deduction Represen21 For the last example induction on natural numbers is necessary. tation, Journal of AutomatedReasoning6,211-212, 1999. Theinduction step was provenfully automatic.

16