Counting Sub-Formula of this First-Order Formula

217 Views Asked by At

This formula has 8 sub-formula:

(∀x)(∃y A(x,y)→∃y(B(x,y,z)⋀D(z))))

I know every formula is a sub-formula of itself = +1

I know for every formula (A⧠B) sub-formula is sub-formula(A)+sub-formula(B)

so B(x,y,z)⋀D(z)= +2

A(x,y)→X=+2

but i just count 5 of them , i know i do it wrong but this is all i know, where i doing it wrong ?

1

There are 1 best solutions below

2
On BEST ANSWER

You are forgetting to apply the self-subformula property to the subformulas: $\exists y A(x,y)$ is not one subformula, but two (the existential subformula itself and the atom), and $\exists y (B(x,y,z) \land D(z))$ is not two formulas, but four (the existence, the conjunction, and the two atoms); this accounts for the three missing subformulas.

You also got the bracketing wrong: $A(x,y) \to \exists y ... $ is not a subformula. $A$ belongs to the left $\exists y$, and this toegether is the left-hand side of the implication. That is, the left $\exists y$ only has scope over $A(x,y)$, not over the whole implication.

$\newcommand{\fml}[1]{\underbrace{#1}_\text{formula}}$ $\newcommand{\Fml}[1]{\underbrace{#1}_\text{formula!}}$

$\fml{(∀x)\fml{(\Fml{∃y \fml{A(x,y)}}→\Fml{∃y\Fml{(\fml{B(x,y,z)}⋀\fml{D(z)})})})}}$.

BTW, it may be easier to count the subformulas inside out: Start with +1 for each atom, then add +1 for each complex statement the subformulas occur in. The number of subformulas is then just the number of atoms (3) + connectives (2) + quantifiers (3).