Bounded and Free Variables
Learn about bounded and free variables in quantified logical statements.
Precedence of quantifiers
The precedence of quantifiers is higher than all the logical operators. This means the quantifier takes immediate effect unless specified by using brackets.
Example
Assume two predicates, and .
On the left-hand side of the above inequality, only is quantified, while on the right-hand side, both and are quantified.
Consider the following sets:
- and .
Now, we look at the following proposition:
Which quantifier should be applied first? Let’s try it both ways. First, use the internal quantifier.
Now, apply the outer quantifier.
Let’s see what happens when we apply the quantifiers in reverse order. First, use the outer quantifier.
Now, apply the inner quantifier.
There is no difference. We can think it either way. Conventionally, we first apply the outer quantifier, which helps us when all the quantifiers are not identical.
Let’s look at the following case now:
Due to the commutativity and associativity of conjunction operation,
Similarly, we can write the following due to the commutativity and associativity of disjunction operation.
Be cautious that both the quantifiers are universal quantifiers. Do not assume anything about mixing different kinds of quantifiers.
Scope of a quantifier
The scope of a quantifier is the segment of the logical expression under its effect. This effect is only for the variable attached to the quantifier. We use brackets to specify the scope of a quantifier.
Examples
Consider the following statements:
-
The scope of the universal quantifier is only , and is not in its scope.
-
Both and are in the scope of the universal quantifier.
-
The variable , both in and , is in the scope of the outer existential quantifier. The variable in is not in the scope of any quantifier, while in , it is in the scope of the quantifier just preceding it.
Bounded variables
A variable is bounded if it is in the scope of a quantifier quantifying it. To make a proposition from a predicate, we either quantify or set a constant value for each variable in it. For a variable to be bounded, it has to be in the scope of some quantifier.
Free variables
A variable that is not in the scope of any quantifier and does not have a fixed value is free. In other words, a free variable is one that is not bounded, and no constant value is assigned to it.
Examples
Consider the following statements. Assume the domain is integers.
-
The scope of the universal quantifier is only up to . Therefore, the variable in is a free variable. The variable in is a bounded variable.
-
There are three variables in this statement. The variable in predicate is bounded by the existential quantifier. The variable is free and it is not bounded by any quantifier. The variable is bounded by the universal quantifier.
-
In this statement, there are six variables. The variables and are bounded by universal quantifiers. The variables and are bounded by existential quantifiers. The variables and are not bounded by any quantifier, therefore, they are free.
Get hands-on with 1200+ tech skills courses.