0
$\begingroup$

I was reading a book on discrete mathematics by k. Rosen. One place in this book i found that

" When a quantifier is used on the variable x, we say that this occurrence of the variable is bound. An occurrence of a variable that is not bound by a quantifier or set equal to a particular value is said to be free"

Again another place it was said that

"The part of a logical expression to which a quantifier is applied is called the scope of this quantifier. Consequently, a variable is free if it is outside the scope of all quantifiers in the formula that specifies this variable."

It seems contradictory to me. Can you clearly explain what is free and bound variable in a quantified statemen. Also tell me what will be the free and bound variables of the statement $\exists x~(x + y = 1)$ and explain me with the proper definition of free and bound variable.

$\endgroup$
  • 1
    $\begingroup$ x is bound because it is within the scope of 3x. y is free because it is not in the scope of any quantifier. $\endgroup$ – William Elliot Oct 24 at 4:43
  • $\begingroup$ Is y outside the scope of the quantifiers. $\endgroup$ – play store Oct 24 at 4:49
  • $\begingroup$ The only quantifier is the 3 (which you are using for existential quantifier) and only vars in its scope are x,y. Only x is bound since that's the var immediately after the "3". $\endgroup$ – coffeemath Oct 24 at 4:58
0
$\begingroup$

In the statement $Q(x)\wedge \forall x~P(x)$, the term $x$ occurs free within the statement, even though it also occurs bound to a quantifier.

" When a quantifier is used on the variable x, we say that this occurrence of the variable is bound. An occurrence of a variable that is not bound by a quantifier or set equal to a particular value is said to be free"

The second occurrence of the term $x$ is bound by use of the universal quantifier. However the first occurrence of the term is not bound by this quantifier, and so it occurs free.

"The part of a logical expression to which a quantifier is applied is called the scope of this quantifier. Consequently, a variable is free if it is outside the scope of all quantifiers in the formula that specifies this variable."

The scope of the universal quantifier in the statement contains exactly the predicate $P(x)$. Hence $x$ is free in this statement as it does occur outside this scope; that is within the predicate $Q(x)$.

There is no contradiction.


The term following the quantifier sign indicates that the quantifier binds that term, and immediately following this is the scope of the quantifier (see "order of precedence" for clarification of where the scope lies ). Occurrences of this term within this scope are bound. Occurrences outside the scopes of all quantifiers which bind the term are free.


Also tell me what will be the free and bound variables of the statement $\exists x~(x + y = 1)$ and explain me with the proper definition of free and bound variable.

All occurrences of the terms are within the scope of the existential quantifier, however, it does not bind $y$, it only binds $x$.

So, because $x$ is bound by the existential quantifier and all occurrences of this term do occur within the scope of this quantification; therefore $x$ does not occur free within the statement.

However, $y$ is not bound by any quantifier, so the occurrence of $y$ is outside the scope of all quantifiers which bind $y$; therefore $y$ occurs free within the statement.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.