User:Tizio/Tableau FO

From Wikipedia, the free encyclopedia

1 First-order tableau
- 1.1 First-order tableau without unification
- 1.2 First-order tableau with unification
2 Tableau calculi and their properties
3 Proof procedure
4 Searching for a tableau
- 4.1 Reducing search
5 To do
6 Examples

[edit] First-order tableau

Tableau are extended to first order by two rules for dealing with universal and existential quantifiers, respectively. Two different sets of rules can be used; both employ a form of Skolemization for handing existential quantifiers, but differ on the handling of universal quantifiers.

The set of formulae to check for validity is here supposed to contain no free variables; this is not a limitation as free variable are implicitely universally quantified, so universal quantifiers over these variables can be added, resulting in a formula with no free variables.

[edit] First-order tableau without unification

A first-order formula $\forall x . \gamma(x)$ implies all formulae $γ(t)$ where $t$ is a ground term. The following inference rule is therefore correct:

$\frac{\forall x . \gamma(x)}{\gamma(t)}$

where

t

is an arbitrary ground term

Contrarily to the rules for the propositional connectives, multiple applications of this rule to the same formula may be necessary. As an example, the set $\{\neg P(a) \vee \neg P(b), \forall x . P(x)\}$ can only be proved unsatisfiable if both $P (a)$ and $P (b)$ are generated from $\forall x . P(x)$ .

Existential quantifiers are dealt with Skolemization. In particular, a formula with a leading existential quantifier like $\exists x . \delta(x)$ generates its Skolemization $δ(c)$ , where $c$ is a new constant symbol.

$\frac{\exists x . \delta(x)}{\delta(c)}$

where

c

is a new constant symbol

The Skolem term $c$ is a constant (a function of arity 0) because the quantification over $x$ does not occur within the scope of any universal quantifier. If the original formula contained some universal quantifiers such that the quantification over $x$ was within their scope, these quantifiers have evidently been removed by the application of the rule for universal quantifiers.

The rule for existential quantifiers introduces new constant symbols. These symbols can be used by the rule for universal quantifiers, so that $\forall y . \gamma(y)$ can generate $γ(c)$ even if $c$ was not in the original formula but is a Skolem constant created by the rule for existential quantifiers.

The above two rules for univeral and existential quantifiers are correct, and so are the propositional rules: if a set of formulae generates a closed tableau, this set is unsatisfiable. Completeness can also be proved: if a set of formulae is unsatisfiable, there exists a closed tableau built from it by these rules. However, actually finding such a closed tableau requires a suitable policy of application of rules. Otherwise, an unsatisfiable set can generate an infinite-growing tableau. As an example, the set $\{\neg P(f(c)), \forall x . P(x)\}$ is unsatisfiable, but a closed tableau is never obtained if one unwisely keeps applying the rule for universal quantifiers to $\forall x . P(x)$ , generating for example $P(c), P(f(c)), P(f(f(c))), \ldots$ . A closed tableau can always be found by ruling out this and similar "unfair" policies of application of tableau rules.

[edit] First-order tableau with unification

The main problem of tableau without unifcation is how to choose a closed term $t$ for the universal quantifier rule. Indeed, every possible ground term can be used, but clearly most of them might be useless for closing the tableau.

A solution to this problem is to "delay" the choice of the term to the time when the consequent of the rule allows closing at least a branch of the tableau. This can be done by using a variable instead of a term, so that $\forall x . \gamma(x)$ generates $γ(x')$ , and then allowing substitutions to later replace $x'$ with a term. The rule for universal quantifiers becomes:

$\frac{\forall x . \gamma(x)}{\gamma(x')}$

where

x'

is a variable not occurring everywhere else in the tableau

While the initial set of formulae is supposed not to contain free variables, a formula of the tableau contain the free variables generated by this rule. These free variables are implicitely considered universally quantified.

This rule employs a variable instead of a ground term. The gain of this change is that these variables can be then given a value when a branch of the tableau can be closed, solving the problem of generating terms that might be useless.

σ

is the most general unifier of two literals

A

and

B

, where

A

and the negation of

B

occurr in the same branch of the tableau,

σ

can be applied at the same time to all formulae of the tableau

As an example, $\{\neg P(a), \forall x . P(x)\}$ can be proved unsatisfiable by first generating $P (x 1)$ ; the negation of this literal is unifiable with $\neg P(a)$ , the most general unifier being the substitution that replaces $x 1$ with $a$ ; applying this substituition results in replacing $P (x 1)$ with $P (a)$ , which closes the tableau.

This rule closes at least a branch of the tableau-the one containing the considered pair of literals. However, the substituion has to be applied to the whole tableau, not only on these two literals. This is expressed by saying that the free variables of the tableau are rigid: if an occurrence of a variable is replaced by something else, all other occurrences of the same variable must be replaced in the same way. Formally, the free variables are (implicitely) universally quantified and all formulae of the tableau are within the scope of these quantifiers.

Existential quantifiers are dealt with by Skolemization. Contrary to the tableauy without unification, Skolem terms may not be simple constant. Indeed, formulae in a tableau with unification may contain free variables, which are implicitely considered universally quantified. As a result, a formula like $\exists x . \delta(x)$ may be within the scope of universal quantifiers; if this is the case, the Skolem term is not a simple constant but a term made of a new function symbol and the free variables of the formula.

$\frac{\exists x . \delta(x)}{\delta(f(x_1,\ldots,x_n)}$

where

f

is a new function symbol and $x_1,\ldots,x_n$ the free variables of

δ

This rule incorporates a simplification over a rule where $x_1,\ldots,x_n$ are the free variables of the branch, not of $δ$ alone. This rule can be further simplfied by the reuse of a function symbol if it has already been used in a formula that is identical to $δ$ up to variable renaming.

The following apply to tableau with unification:

A substitution that is not the most general unifier of two literals as defined above could be used, provided that the substitution is free for the set of formulae of the tableau (it does not replace any free variable $x$ with a term containing a variable that is not free in one occurrence of $x$ ). Using most general unifiers automatically ensure this property.
Free variables in a tableau are implicitely considered universally quantified. This assumption makes the application of a substitution that is free for the tableau a sound rule: since $P (x)$ actually means that $P (x)$ is true for every $x$ , it follows that $P (t)$ is true as well.
Free variables in a tableau are considered rigid: all occurrences of the same variable have to be replaced all with the same term. However, there are some special cases where they can be replaced separately with two differing terms.
Free variables in a formula to check for validity are considered universally quantified. However, these variables cannot be left free when building a tableau, because tableau rules works on the converse of the formula but still treats free variables as universally quantified. For example, $P(x) \rightarrow P(c)$ is not valid (it is not true in the model where $D = {1,2}, P (1) = F, P (2) = T, c = 1, a n d t h e i n t e r p r e t a t i o n w h e r e < m a t h > x = 2$ ). Consequentely, $\{P(x),\neg P(c)\}$ is satisfiable (it is satisfied by the same model and interpretation). However, a closed tableau could be generated with $P (x)$ and $\neg P(c)$ , and substituting $x$ with $c$ would generate a closure. A valid proof requires first made universal quantifiers explicit, thus generating $\forall x . (P(x) \rightarrow P(c))$ .

Tableau with unification can be proved complete: if a set of formulae is unsatisfiable, it has a tableau-with-unification proof. However, actually finding such a proof may be a difficult problem. Contrarily to the case with unification, no policy of application of the rules is currently known that guarantees finding a proof for all unsatisfiable sets and works well in practice.

This problem is common to other tableau calculi; general solutions are outlined in the "Searching for a tableau" section. A solution that is instead specific to tableau with unification is that of delayed instantiation: no substitution is applied until one that closes all branches at the same time is found. With this variant, a proof for an unsatisfiable set can always be found by a suitable policy of application of the other rules. This method however requires the whole tableau to be kept in memory: the general method closes braches which can be then discarded, while this variant does not close any branch until the end.

[edit] Tableau calculi and their properties

A tableau calculus is a set of rules that allow building and modify a tableau. Propositional tableau rules, tableau rules without unification, and tableau rules with unification, are all tableau calculi. Some important property a tableau calculus may or may not posses are completeness, destructiveness, and proof confluence.

A tableau calculi is said complete if it allows building a tableau proof for every given unsatisfiable set of formulae. The tableau calculi mentioned above can be proved complete.

A remarkable difference between tableau with unification and the other two calculi is that the latter two calculi only modify a tableau by adding new nodes to it, while the former one allows substitutions to modify the existing part of the tableau. More generally, tableau calculi are classed as destructive or non-destructive depending on whether they only add new nodes to tableau or not. Tableau with unification is therefore destructive, while propositional tableau and tableau without unification are non-destructive.

Proof confluence is the property of a tableau calculus to obtain a proof for an arbitrary unsatisfiable set from an arbitrary tableau, assuming that this tableau has itself been obtained by applying the rules of the calculus. In other words, in a proof confluent tableau calculus, from an unsatisfiable set one can apply whatever set of rules and still obtain a tableau from which a closed one can be obtained by applying some other rules.

[edit] Proof procedure

A tableau calculi is only a set of rules that tells how a tableau can be modified. A proof procedure is a method for actually finding a proof (if one exists). In other words, a tableau calculi is a set of rules, while a proof procedure is a policy of application of these rules. Even if a calculi is complete, not every possible choice of application of rules leads to a proof of an unsatisfiable set. For example $\{P(f(x)), R(c), \neg P(f(c)) \vee \neg R(c), \forall x . Q(x)\}$ is unsatisfiable, but both tableau with unification and tableau without unification allows the rule for the universal quantifiers to be applied repeatedly to the last formula, while simply applying the rule for disjunction to the third one would directly lead to closure.

For proof procedures, a definition of completeness has been given: a proof procedure is strongly complete if it allows finding a closed tableau for any given unsatisfiable set of formulae. Proof confluence of the underlying calculus is relevant to completeness: proof confluence is the guarantee that a closed tableau can be always generated from an arbitrary partially constructed tableau (if the set is unsatisfiable). Without proof confluence, the application of a `wrong' rule may result in the impossibility of making the tableau complete by applying other rules.

Propositional tableau and tableau without unification have strongly complete proof procedures. In particular, a complete proof procedure is that of applying the rules in a fair way. This is because the only way such calculi cannot generate a closed tableau from an unsatisfiable set is by not applying some applicable rules.

For propositional tableau, fairness amounts to expanding every formula in every branch. More precisely, for every formula and every branch the formula is in, the rule having the formula has a precondition has been used to expand the branch. A fair proof procedure for propositional tableau is strongly complete.

For first-order tableau without unification, the condition of fairness is similar, with the exception that the rule for universal quantifier might require more than an application. Fairness amounts expanding every universal quantifier infinitely often. In other words, a fair policy of application of rules cannot keep applying other rules without expanding every universal quantifier in every branch that is still open once in a while.

[edit] Searching for a tableau

If a tableau calculus is complete, every unsatisfiable set of formula has an associated closed tableau that can be obtained by applying some of the rule of the calculus. However, this does not automatically implies that there is a feasible policy of application of rules that can always lead to building a closed tableau for every given unsatisfiable set of formulae.

While a fair proof procedure is complete for ground tableau and tableau with unification, this is not the case for tableau with unification. A general solution for this problem is that of searching the space of tableau until a closed one is found (if any exists, that is, the set is unsatisfiable). In this approach, one starts with an empty tableau and then recursively tries to apply every possible applicable rule. This procedure visit a (implicit) tree whose nodes are labeled with tableau, and such that the tableau in a node is obtained from the tableau in its parent by applying one of the valid rules.

Since one such branch can be infinite, this tree has to be visited breadth-first rather than depth-first. This requires a large amount of space, as the breadth of the tree can grow exponentially. A method that may visit some nodes more than once but works in polynomial space is to visit in a depth-first manner with iterative deepening: one first visits the tree up to a certain depth, then increases the depth and perform the visit again. This particular procedure uses the depth (which is also the number of tableau rules that have been applied) for deciding when to stop at each step. Various other parameters (such as the size of the tableau labeling a node) have been used instead.

[edit] Reducing search

The size of the search tree depends on the number of (children) tableau that can be generated from a given (parent) one. Reducing the number of such tableau therefore reduces the required search.

A way for reducing this number is to disallow the generation of some tableau based on their internal structure. An example is the condition of regularity: if a branch contains a literal, using an expansion rule that generates the same literal is useless because the branch containing two copies of the literals would have the same set of formulae of the original one. This expansion can be disallowed because if a closed tableau exists, it can be found without it. This restriction is structural because it can be checked by looking at the structure of the tableau to expand only.

Different methods for reducing search is to disallow the generation of some tableau on the ground that a closed tableau can still be found from some other tableau. These restrictions are called global.

[edit] To do

when rigid variables can be treated as non-rigid
clause tableau (combine "forall" and disjunction in one rule)
other possible parameters for iterative deepening
structural restrictions on tableau: regularity, connectedness, and other restrictions over a single tableau: avoid, as much as possible, the creation of nodes that are not necessary for getting a proof (note that any such nodes may be then expanded to multiple children/descendants, each one with it own subtree, so the saving of not generating the node may be more than just saving one node); connectivity and regularity have been defined to avoid redundancy; [place this on the propositional case; place what's to say about the first-order case before "tableau calculi" (or after search if it appears only relevant to search) to avoid breaking the flow calculi-proofprocedures-search]
reduce choices: reducing the number of ways a tableau can be modified reduces the search in the search space of the tableau (in eg. depth-first with iterative deepening); structural restrictions such as connectivity and regularity also have this consequence, as they disallow the generation of certain tableau; other methods instead disallow the generation of certain tableau on the ground that they are not needed if other ones are generated

for the propositional case:

connected tableau; even for the propositional case, it is not proof confluent, as for example choosing p as the initial node does not lead to closure if the formula for {p, q, -q}; this is a tableau calculi where search in the space of tableau is necessary;
binary split (disjunction)
pruning (backjumping)
simplification (if a formula occur in a branch, it can be replaced with true in its subtree)