Finding the sub formula.

Question

Lets say I have the sentence

$$\phi=(p(x)\wedge(q(y)\supset R(z))) \supset (\forall u.\exists w.(T(u.w) \vee \neg(u=w)))$$

I am trying to find the sub formulae of this.

Is $$(\forall u.\exists w.(T(u.w) \vee \neg(u=w)))$$ a sub formula?

In the example I was given, substitutions had been made and they were also deemed to be sub formulae which is correct, but why would you make a substitution when finding the sub formulae?

Answer 1

The subformulae are also the sub-formulae of the subformulae ...

The set $Sub(\phi)$ of te subformulae of $\phi$ includes $\phi$ iteself.

Then the two subformuale "linked" by the main connective $\supset$, i.e. :

$(p(x)∧(q(y)⊃R(z)))$ and $∀u.∃w.(T(u,w)∨¬(u=w))$.

In turn, the first one has two subformulae :

$p(x)$ and $(q(y)⊃R(z))$

and the last one is again "decomposable" into : $q(y)$ and $R(z)$.

Regarding : $∀u.∃w.(T(u,w)∨¬(u=w))$, we have the subformula : $∃w.(T(u,w)∨¬(u=w))$ and this in turn has the subformula : $T(u,w)∨¬(u=w)$.

This one has two subformulae :

$T(u,w)$ and $¬(u=w)$

and finally we have : $(u=w)$.