Substitution (logic)

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

No literature is given. - Maformatiker ( discussion ) 18:02, 10 Dec. 2016 (CET)

In logic, substitution is the general term used to describe the replacement of one expression by another.

More precisely, four different expressions have to be distinguished from one another:

• the substituendum (Latin: "that to be replaced"): the term that is replaced
• the substituent (Latin: "the substitute"): the expression that replaces
• the substitution base: the term in which to replace
• the substitution result: the result of the substitution.

Example:

Let's replace in the expression

${\displaystyle a\Rightarrow (b\wedge c)}$

(read: "if , then and ") through the expression ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle b}$

${\displaystyle c\vee d}$

(read: " or "), we get: ${\displaystyle c}$ ${\displaystyle d}$

${\displaystyle a\Rightarrow ((c\vee d)\wedge c)}$.

Here is the substituent, the substituent, the substitution base and the substitution result. ${\displaystyle b}$ ${\displaystyle c\vee d}$ ${\displaystyle a\Rightarrow (b\wedge c)}$ ${\displaystyle a\Rightarrow ((c\vee d)\wedge c)}$

A distinction is made between universal and simple substitution, and the term “free to substitute” is also important in quantifier logic .

Universal and easy substitution

In the case of universal substitution, all occurrences of the substituent must be replaced; in the case of simple substitution, not all occurrences need to be replaced. The difference between the two types of substitution only becomes relevant when there are at least two occurrences of the substituent in the substitution base. With universal substitution, the substituent no longer appears in the substitution result, with simple substitution it can still occur.

Example:

Let's replace in the expression

${\displaystyle b\Rightarrow (b\wedge c)}$

the expression through ${\displaystyle b}$

${\displaystyle c\vee d}$,

so we get with universal substitution:

${\displaystyle (c\vee d)\Rightarrow ((c\vee d)\wedge c)}$.

With simple substitution we could also get the following:

${\displaystyle (c\vee d)\Rightarrow (b\wedge c)}$

Universal and simple substitution play a role in different laws:

Law of Universal Substitution

If a statement is a theorem and is the result of the universal substitution of by , then it is again a theorem. It is important here that universal substitution is made; a simple substitution does not guarantee that a theorem is. Another requirement is that the substituendum is a "sentence parameter", i. H. a non-complex formula which, moreover, does not appear in any axiom . There is no corresponding restriction on the substituent . ${\displaystyle A}$ ${\displaystyle A'}$ ${\displaystyle b}$ ${\displaystyle C}$ ${\displaystyle A'}$ ${\displaystyle A'}$ ${\displaystyle b}$ ${\displaystyle C}$

Example:

In the theorem

${\displaystyle b\Rightarrow b}$

we can replace the term universal with ${\displaystyle b}$

${\displaystyle c\vee d}$

and in turn get a theorem, namely:

${\displaystyle (c\vee d)\Rightarrow (c\vee d)}$

With simple substitution we could also get the following:

${\displaystyle (c\vee d)\Rightarrow b,}$

which is not a theorem. If we dropped the requirement that the substituent is a sentence parameter, we could replace the whole expression with a formula, for example , and get: ${\displaystyle b\Rightarrow b}$ ${\displaystyle c}$

${\displaystyle c,}$

which of course is not a theorem either.

The property that universal substitution gets the theorem property is exploited in some calculi by formulating this as a rule of inference. The rule of universal substitution states that in every formula that has been obtained with a proof, every sentence parameter can be universally replaced by any statement.

Law of Substitution of Equivalent Statements

If two statements and equivalent and is a result of the simple substitution of by in , then and also equivalent. ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A'}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A'}$

Example:

For example, two equivalent statements are:

${\displaystyle B:b\wedge c}$

and

${\displaystyle C:c\wedge b}$,

If we now in the statement

${\displaystyle A:(b\wedge c)\Rightarrow ((b\wedge c)\wedge d)}$

${\displaystyle B}$by simply substituting, we can get the following: ${\displaystyle C}$

${\displaystyle A':(c\wedge b)\Rightarrow ((b\wedge c)\wedge d)}$

${\displaystyle A}$and are now again equivalent. ${\displaystyle A'}$

The term "free for substitution"

A term can be substituted by a variable in a formula if it is not in the scope of a quantifier or . ${\displaystyle t}$ ${\displaystyle x}$ ${\displaystyle B}$ ${\displaystyle t}$ ${\displaystyle \forall x}$ ${\displaystyle \exists x}$

The background of this definition is as follows: In quantifier logic one wants to speak of the fact that one statement represents an all- or existential generalization of another. For example is

Someone smokes

formally:

${\displaystyle \exists xR(x)}$

an existence generalization of

Frank smokes,

formally:

${\displaystyle R(f)}$

It now seems as if one obtains a generalization if one replaces the occurrences of the term to be generalized (in the example "Frank" or ) with universal and puts a quantifier or in front of the statement. A generalization is only obtained under the additional condition that the term to be generalized is free for replacement by . ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle \forall x}$ ${\displaystyle \exists x}$ ${\displaystyle x}$

example

Look at the statement

When someone loves Frank, Frank is happy

formally

${\displaystyle A:\exists xL(x,f)\Rightarrow G(f)}$

Note that here there is no substitution by , since it occurs in the scope of the existential quantifier. Therefore the following statement is not an all-generalization of : ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle \exists x}$ ${\displaystyle A}$

${\displaystyle \forall x(\exists xL(x,x)\Rightarrow G(x))}$

because this statement means:

"If someone loves himself, everyone is happy"

and this completely misses the meaning of the original statement.

In such a case, however, you can always carry out a generalization with another variable. For example, in is free to substitute with , so the following all-generalization can be formed: ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle y}$

${\displaystyle \forall y(\exists xL(x,y)\Rightarrow G(y))}$

and this statement then has the desired meaning, namely:

“Everyone who loves someone is happy”.