Question

Check which terms are free in the following cases, and carry out the substitution: (a) \(x\) for \(x\) in \(x=x\), (f) \(x+w\) for \(z\) in \(\forall w(x+z=\overline{0})\), (b) \(y\) for \(x\) in \(x=x\) (g) \(x+y\) for \(z\) in \(\forall w(x+z=\overline{0}) \wedge\) (c) \(x+y\) for \(y\) in \(z=\overline{0}\) \(\exists y(z=x)\), (d) \(\overline{0}+y\) for \(y\) in \(\exists x(y=x)\), (h) \(x+y\) for \(z\) in \(\forall u(u=v) \rightarrow\) (e) \(x+y\) for \(z\) in \(\forall z(z=y)\). \(\exists w(w+x=\overline{0})\),

Short answer

Substitute terms as free or bound dictates; many expressions remain unchanged due to bound variables.

Step-by-step solution

Evaluate Substitution (a)

Substitute \(x\) for \(x\) in the expression \(x=x\). Since \(x\) is free everywhere in the expression, substituting \(x\) for \(x\) will result in the same expression \(x=x\). No variable replacement occurs.

Evaluate Substitution (b)

Substitute \(y\) for \(x\) in the expression \(x=x\). The free variable \(x\) is replaced by \(y\), resulting in the expression \(y=y\). \(y\) is free in the resulting expression.

Evaluate Substitution (c)

Substitute \(x+y\) for \(y\) in the expression \(z=\overline{0} \land \exists y(z=x)\). The free variable \(y\) in \(\exists y(z=x)\) is bound and will not be substituted. In the \(z=\overline{0}\) part, there is no occurrence of \(y\), so no substitution is necessary.

Evaluate Substitution (d)

Substitute \(\overline{0}+y\) for \(y\) in the expression \(\exists x(y=x)\). The free variable \(y\) is substituted by \(\overline{0}+y\), resulting in \(\exists x(\overline{0}+y=x)\). Here, \(y\) remains free in the expression.

Evaluate Substitution (e)

Substitute \(x+y\) for \(z\) in the expression \(\forall z(z=y) \land \exists w(w+x=\overline{0})\). In the quantified part \(\forall z(z=y)\), \(z\) is bound and will not be substituted. Only \(z\) outside this scope would be impacted, resulting in no change here since all \(z\) within the scope are bound.

Evaluate Substitution (f)

Substitute \(x+w\) for \(z\) in the expression \(\forall w(x+z=\overline{0})\). The variable \(z\) is replaced by \(x+w\), resulting in \(\forall w(x+(x+w)=\overline{0})\). \(w\) is free in the substituted expression.

Evaluate Substitution (g)

Substitute \(x+y\) for \(z\) in the expression \(\forall w(x+z=\overline{0}) \land \exists y(z=x)\). In the \(\forall w(x+z=\overline{0})\) part, substitute \(x+y\) for \(z\) leading to \(\forall w(x+(x+y)=\overline{0})\); in \(\exists y(z=x)\), \(z\) is replaced by \(x+y\) to yield \(\exists y(x+y=x)\). \(y\) remains free in the \(\forall w\) part, but is bound in the \(\exists y\) part.

Evaluate Substitution (h)

Substitute \(x+y\) for \(z\) in the expression \(\forall u(u=v) \rightarrow \exists w(w+x=\overline{0})\). The expression does not directly involve \(z\), thus the substitution \(x+y\) for \(z\) results in no change. The variables \(u\) in \(\forall u(u=v)\) and \(w\) in \(\exists w(w+x=\overline{0})\) are bound.

Key concepts

Free and Bound Variables

Grasping the distinction between free and bound variables is essential when working with logical expressions. A **free variable** is one that isn't tied down by any quantifier. It's essentially a placeholder that can be replaced or evaluated independently. For instance, in the expression \( x = y \), both \( x \) and \( y \) are free variables, meaning they can take any values that satisfy the equation.

On the other hand, **bound variables** are those that are quantified within an expression. They are essentially "tied" to their defining quantifier and don't operate independently. In the expression \( \forall x (x = y) \), the \( x \) is a bound variable because it is limited to the scope of the quantifier \( \forall \). Therefore, it cannot be freely substituted without respecting the boundaries set by the quantifier. Understanding this difference is critical for correct substitution in logical proofs.

Quantifiers

Quantifiers are symbols used in logic to specify the quantity of instances in a domain for which a predicate holds. They come in two primary forms: **universal** and **existential**.

The **universal quantifier**, denoted by \( \forall \), implies that the predicate following it applies to all elements within a certain set or domain. An expression such as \( \forall x P(x) \) is stating that \( P(x) \) is true for every possible value of \( x \).

By contrast, the **existential quantifier**, denoted by \( \exists \), indicates that there is at least one element in the domain for which the predicate holds true. For example, \( \exists x P(x) \) asserts that there exists some value of \( x \) for which \( P(x) \) is true.

In logical expressions, recognizing whether a variable is under the scope of a quantifier helps to determine if it's bound or free, influencing how substitutions are performed. Being sensitive to these distinctions ensures precise manipulation of logical statements.

Logical Expressions

Logical expressions are combinations of symbols and connectives used to formulate statements in formal logic. They are constructed using **variables**, **quantifiers**, and **connectives** such as \( \land \) (and), \( \lor \) (or), and \( \rightarrow \) (implies).

For instance, the expression \( \forall x (x > 0) \land \exists y (y < 0) \) combines both quantifiers and logical and, presenting a statement about numbers \( x \) and \( y \).

Logical expressions are central to proofs and problem-solving in mathematics and computer science. The proper manipulation and simplification of these expressions often involve substituting variables appropriately and recognizing the impact of free and bound variables. Understanding these fundamentals helps in constructing valid arguments and formal proofs effectively.