2

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?

Nubcake
  • 426
  • 1
  • 6
  • 17

2 Answers2

2

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.

Memming
  • 2,028
  • 15
  • 25
  • I sort of see what you mean here but can you tell me what would the formula look like bracketed? I'm a bit stuck with this when trying to understand the tree; does the $\exists x$ wrap only P(x,x) or not? Because of the $\lor$ I don't know what to bracket. – Nubcake Apr 09 '15 at 14:44
  • I think it's like this (∃xP(x,x)∨(Q(x)∧¬∀yR(x)))→(x=y) ? – Nubcake Apr 09 '15 at 14:53
  • Assumed that to omit the parentheses, in general, is a "bad habit", we have to note that the "standard" convention in first-order logic is that "¬, ∀, and ∃ apply to as little as possible" (Enderton) or that "the scope of an occurrence of a quantifier in a formula $\psi$ is the subformula of $\psi$ that starts at this occurrence" (Chiswell & Hodges). Thus, according to the convention, the "correct" reading of $∃xP(x,x)∨Q(x)∧ \ldots$ is : $(∃xP(x,x))∨Q(x)∧ \ldots$ and not $∃x[P(x,x)∨Q(x)∧ \ldots]$. – Mauro ALLEGRANZA Apr 09 '15 at 15:12
  • @MauroALLEGRANZA Good point. I think that's what the "correct" solution diagram is pointing at, so they agree with you. However, I've seen rules where quantifiers is global unless there are parentheses limiting them... – Memming Apr 09 '15 at 15:18
1

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.

Anon
  • 5,489