0

I've been doing Logic equivalences questions and I've been taught that a variable $x$ is bound if it is under any quantifier such as $ \exists $ or $ \forall$ however I've come across a question where in the answer it states that a variable is bound even though no quantifier exists to bound it:

$ \forall y [\exists x P(x,y) \Rightarrow \neg S(y)] $

$ \forall y \forall x [P(x,y) \Rightarrow \neg S(y)] $ by equivalence 37: note that $x$ is not free in $S(y)$.

Equivalence 37 in my notes states

Note: If $x$ does not occur free in $B$

$ \forall x (A\Rightarrow B) $ eqv $ \exists x A \Rightarrow B $

$ \exists x (A \Rightarrow B) $ eqv $ \forall x A \Rightarrow B $

Maybe I'm misunderstanding something here? Can someone please explain what it means?

Nubcake
  • 426
  • 1
  • 6
  • 17
  • The equivalence between the two first formulae holds because $x$ is not free in $S(y)$. In general (consider the last two formulae) we have that $x$ does not occur free in $B$ if : either (i) $x$ does not occur at all into $B$, or (ii) $x$ occurs only bound into $B$, i.e. $B$ is like : $\forall x C(x)$. – Mauro ALLEGRANZA Aug 18 '15 at 18:41
  • Regarding the question in the title : "If a variable does not exist is it bound?", the answer is : NO. But the restriction is : $x$ is not free in $S(y)$" and if the variable $x$ does not occur at all in $S(y)$, it is not free in it. – Mauro ALLEGRANZA Aug 18 '15 at 19:16
  • Doesn't bound mean "not free"? – Nubcake Aug 18 '15 at 20:08
  • YES... but "not free" means either (i) bound, or (ii) not occurring at all. – Mauro ALLEGRANZA Aug 18 '15 at 20:25
  • Ok i got it now , thank you. – Nubcake Aug 19 '15 at 15:25

0 Answers0