# Definition:Substitution (Formal Systems)

*This page is about Substitution in the context of Formal Language. For other uses, see Substitution.*

## Definition

### Substitution for Well-Formed Part

Let $\FF$ be a formal language with alphabet $\AA$.

Let $\mathbf B$ be a well-formed formula of $\FF$.

Let $\mathbf A$ be a well-formed part of $\mathbf B$.

Let $\mathbf A'$ be another well-formed formula.

Then the **substitution of $\mathbf A'$ for $\mathbf A$ in $\mathbf B$** is the collation resulting from $\mathbf B$ by replacing all occurrences of $\mathbf A$ in $\mathbf B$ by $\mathbf A'$.

It is denoted as $\map {\mathbf B} {\mathbf A' \mathbin {//} \mathbf A}$.

### Substitution for Letter

Let $\mathbf B$ be a well-formed formula of $\FF$.

Let $p$ be a letter of $\FF$.

Let $\mathbf A$ be another well-formed formula.

Then the **substitution of $\mathbf A$ for $p$ in $\mathbf B$** is the collation resulting from $\mathbf B$ by replacing all occurrences of $p$ in $\mathbf B$ by $\mathbf A$.

It is denoted as $\map {\mathbf B} {\mathbf A \mathbin {//} p}$.

### Substitution of Term for Variable

Let $\mathbf A$ be a WFF of predicate logic.

Let $\tau$ be a term of predicate logic.

Let $x \in \mathrm{VAR}$ be a variable.

Let $\mathbf A \left({x \gets \tau}\right)$ be the WFF resulting from $\mathbf A$ by replacing all free occurrences of $x$ by $\tau$.

Then $\mathbf A \left({x \gets \tau}\right)$ is called the **substitution instance of $\mathbf A$ substituting $\tau$ for $x$**.

### Substitution for Metasymbol

Let $S_1$ be a statement form.

Let $p$ be a metasymbol which occurs one or more times in $S_1$.

Let $T$ be a statement.

Let $S_2$ be the string formed by replacing *every* occurrence of $p$ in $S_1$ with $T$.

Then $S_2$ results from the **substitution of $p$ by $T$ in $S_1$**.

$S_2$ is called a **substitution instance** of $S_1$.

## Notation

There are many alternative notations for $\map {\mathbf B} {\mathbf A' \mathbin {//} \mathbf A}$.

These mainly concern the style of the brackets, and sometimes an alternative symbol (usually $\gets$ or a single $/$) for the slashes $//$.

For example:

- $\mathbf B \set {\mathbf A \gets \mathbf A'}$
- $\mathbf B \sqbrk {\mathbf A' \mathbin {//} \mathbf A}$
- $\map {\mathbf B} {\mathbf A \leadsto \mathbf A'}$