0

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.

user405159
  • 353
  • 2
  • 12
  • A quantifier has a scope, which is the subformula to which it applies. When drawing the syntax tree, make the quantifier a node with one child, namely the subformula that is its scope. – Fabio Somenzi Mar 12 '17 at 15:05
  • I also thought you had to do what you suggest but then in the lecture notes I'm reading I found this exercise: How many leaves has the syntactic tree of ∀x∀yAxy? Answer: 1. – user405159 Mar 12 '17 at 15:10
  • Also what would be the complexity of the formula I proposed in my question? – user405159 Mar 12 '17 at 15:10
  • It's possible that the lecture notes discuss rules to collapse certain subtrees. For instance, nodes with one child can be merges with their only child. The exercise may then refer to the size of the collapsed tree. I prefer, though, the syntax tree to reflect the definition of syntax and semantics of the language. As for the fomula at the top of your post, I count 15 nodes for a syntax tree. – Fabio Somenzi Mar 12 '17 at 15:17
  • If you count connectives, there are three of them in the formula above. – Fabio Somenzi Mar 12 '17 at 15:22
  • So ∃ wouldn't count as a connective? – user405159 Mar 12 '17 at 15:26
  • And ∀y neither. – user405159 Mar 12 '17 at 15:28
  • In most definitions, $\exists$ and $\forall$ are not considered connectives. They are simply called "quantifiers," and they form their own class of symbols. – Fabio Somenzi Mar 12 '17 at 15:29
  • So if I understand well what Fabio suggested in his first comment (so independently from what my lecture notes say) the "only child" of my formula would be Ux & ∀y((Ay & Ixy) ⊃ Fxy) – user405159 Mar 12 '17 at 15:33
  • Yes, you got what I meant. – Fabio Somenzi Mar 12 '17 at 15:38
  • If this is the case that means you can have a child of a node which has the same complexity as his father (the same number of connectives, as you don't count ∃ as a connective). – user405159 Mar 12 '17 at 15:42
  • According to that definition, yes. – Fabio Somenzi Mar 12 '17 at 15:47
  • As for me, I count 9 nodes for the formula I proposed! I think we adopted a different approach. – user405159 Mar 12 '17 at 15:53
  • You probably count $Ux$ as a single node. – Fabio Somenzi Mar 12 '17 at 15:54
  • Yes! Can you count it as something else? – user405159 Mar 12 '17 at 15:55

2 Answers2

0

"$\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.

marty cohen
  • 107,799
0

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.

Mauro ALLEGRANZA
  • 94,169