How to build the syntactic tree of this formula

391 Views Asked by At

Consider the following formula:

∃x(Ux & ∀y((Ay & Ixy) ⊃ Fxy))

I would like to build the syntactic tree of this formula but I'm getting confused about how to do it. In particular, I don't know how to treat operators like ∃: do I have to treat them as connectives like & or not?

With the expression "syntactic tree" I mean a tree-like diagram that traces the "syntactic history" of a formula by showing how the formula is constructed from atomic formulas by means of applications of the definition of a well-formed formula (in this case a well-formed formula of a predicate language).

The complexity of a formula is given by the number of connectives it contains (e.g.: formula which contains 3 connectives is a formula of a complexity 3). Here is an example: consider the formula Px ⊃ Qab. The "root" of the tree is Px ⊃ Qab itself, which has complexity 1, and the "leaves" are Px and Qab, two formulas of complexity 0.

2

There are 2 best solutions below

2
On

"$\exists x$" is not an operator.

The operator is "$\exists$" and it has two nodes: the first lists all the variables (in this case, just "x") and the second describes what is true about the variables.

5
On

The root must be $\exists x$ with only one child : $\land$ (conjunction).

The $\land$ node has to branches: the left one with $Ux$ and the right one with $\forall y$.

$\forall y$ has only the $\to$ child, which in turn has two branches : left one is $∧$ (conjunction) and right one is $Fxy$.

In turn, the $\land$ node has two children : left is $Ay$ and right is $Ixy$.

Now you can check it rebuilding the formula bottom-up...

You can see here for a similar example.