Completeness Theorem for Semantic Tableaus

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathbf A$ be a WFF of propositional logic.

Let $\mathbf A$ be unsatisfiable for boolean interpretations.


Then every completed tableau for $\mathbf A$ is closed.


Proof

The proof proceeds by contradiction.

That is, we assume that some open tableau $T$ for $\mathbf A$ exists, and prove that $\mathbf A$ must be satisfiable.


This claim is proved by inductively establishing the following claim for all nodes $t$ of $T$:

If a descendant leaf node of $t$ is marked open, then $U \left({t}\right)$ is satisfiable.


By the Semantic Tableau Algorithm, this statement is immediate for leaf nodes.

For, sought satisfiability is the condition for a leaf to be marked open.


Inductively suppose that all children of $t$ satisfy the mentioned condition.

Now suppose that $t$ has a descendant marked open leaf.

Then obviously some child $t'$ of $t$ also has a descendant marked open leaf.

By induction hypothesis, $U \left({t'}\right)$ is satisfiable.


First, the case that the formula $\mathbf B$ used at $t$ by the Semantic Tableau Algorithm is an $\alpha$-formula.

Then $U \left({t'}\right)$ is obtained from $U \left({t}\right)$ by replacing $\mathbf B$ by $\mathbf B_1$ and $\mathbf B_2$.

Here, $\mathbf B_1$ and $\mathbf B_2$ are the formulas such that $\mathbf B$ is semantically equivalent to $\mathbf B_1 \land \mathbf B_2$.


It follows that if:

$v \models_{\mathrm{BI}} U \left({t'}\right)$

for some boolean interpretation $v$, then also:

$v \models_{\mathrm{BI}} U \left({t}\right)$

by the boolean interpretation of $\land$.

Consequently, $U \left({t}\right)$ is satisfiable.


Next, the case that $\mathbf B$ is a $\beta$-formula.

Then $\mathbf B$ is semantically equivalent to $\mathbf B_1 \lor \mathbf B_2$.

Then, by the Rule of Addition:

$\mathbf B_1 \models_{\mathrm{BI}} \mathbf B$
$\mathbf B_2 \models_{\mathrm{BI}} \mathbf B$

Consequently, by the definitions of $U \left({t'}\right)$ and $U \left({t''}\right)$:

$U \left({t'}\right) \models_{\mathrm{BI}} U \left({t}\right)$
$U \left({t''}\right) \models_{\mathrm{BI}} U \left({t}\right)$

By hypothesis, one of $U \left({t'}\right)$ and $U \left({t''}\right)$ must be satisfiable.

Hence, so must $U \left({t}\right)$ be.


This establishes our claim.

Applying the claim to the root node, i.e., to the whole tableau, we obtain the result.

$\blacksquare$


Sources