Completely free variable

A variable is called completely free in a formula of predicate logic if it occurs in at least one place in the formula but is not quantified anywhere within the formula .

The distinction between free and fully free variables is of a technical nature. It is of no relevance to the logical meaning of a formula, as any formula can be converted into a logically equivalent one by renaming it, in which all free variables are actually completely free.

Examples

• Both and are completely free variables in the formula . ${\displaystyle P(x)\land Q(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$
• In the formula is completely free, but not, since it has both a free and a bound occurrence. ${\displaystyle P(x)\land \forall x\ Q(x,y)}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$

• The logically equivalent formula can be obtained from the formula by bound renaming , in which both variables are free and completely free. ${\displaystyle P(x)\land \forall x\ Q(x,y)}$ ${\displaystyle P(x)\land \forall z\ Q(z,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

Web links

• Lecture notes "Logical Foundations of Computer Science" (PDF file; 1.07 MB)