How to correctly draw logic formation trees?
I had an exam on Logic and came across a question which asked me to draw the logic formation tree for the following:
$$\exists xP(x,x) \lor Q(x) \land \neg \forall y R(x) \to x = y$$
The formula was given exactly like this with no bracketing so my first thought was to bracket everything to disambiguate terms however it did not turn out too well I think.
I drew the formation tree like this:
V / \ E(x) A | / \ P(x,x) Q(x) -> / \ ¬ x = y | Vy | R(x)And got a red circle on my paper telling me that the way I drew the tree was incorrect. Later did I find out that the correct way to draw the tree was this:
-> / \ V x = y / \ E(x) A | / \ P(x,x) Q(x) ¬ | Vy | R(x)(Sorry for the poor tree diagrams; I can't seem to find a way to draw a tree in latex on SE)
I don't understand the difference between these two trees; to check whether my answer was correct I thought if I worked my way up from the bottom of the tree then I should arrive at the original formula , and this worked but it's apparently incorrect?
In my notes about drawing formation trees there are the following notes
Every non-atomic forula has a principal connective,which determines its overall logical
form. You will have to learn to recognise it.- $p \land q \to r$ has principial connective $\to$ . It's overall logical form is $ A \to B$
- $\neg (p \to \neg q)$ has principal connective $\neg$. It's logical form is $\neg A$.
But how do you recognise the logical form given a formula like the above? Do you always go with the weakest binding? This doesn't seem to always be the case. Can anyone tell me how I should approach this?
$\endgroup$ 32 Answers
$\begingroup$Your diagram corresponds to
$$(\exists x \; P(x,x)) \lor (Q(x) \land (\neg (\forall y\; R(x)) \to x = y))$$
which makes no sense.
Multiple problems here
- quantifier for x is only on P, so other x's are dangling.
- quantifier for y is only for R, so y in $x=y$ is dangling.
- 'implies' is weaker than anything else
In a well posed notation (language) parsing should be unique. You just need to learn the rigorous rules. Always go for the weakest binding first in this case.
$\endgroup$ 4 $\begingroup$This is a late answer, but it makes absolutely no sense to separate a variable from its quantifier. So the only correct way to parenthesize this statement is
$$\exists x (P(x) \vee (Q(x) \wedge \lnot\forall y(R(x)\rightarrow (x = y)))).$$
Both formation trees given in the question are therefore quite wrong. The $\exists x$ should be the root, and the whole tree should look very very right-heavy.
$\endgroup$
