# Rule of Substitution

## Theorem

Let $S$ be a sequent that has been proved.

Then a proof can be found for any substitution instance of $S$.

## Proof

This is apparent from inspection of the proof rules themselves.

The rules concern only the broad structure of the propositional formulas involved, and this structure is unaffected by substitution.

By performing the substitutions systematically throughout the given sequent, all applications of proof rules remain correct applications in the sequent.

## Also known as

Some sources amplify the name to **rule of uniform substitution**.

## Applications

This proof leads on to the Rule of Sequent Introduction.

## Technical Note

When invoking the **Rule of Substitution** in a tableau proof, use the `{{Substitution}}`

template:

`{{Substitution|line|pool|statement|depends|instance 1}}`

`{{Substitution|line|pool|statement|depends|instance 1|substitution 1}}`

`{{Substitution|line|pool|statement|depends|instance 1|substitution 1|instance 2|substitution 2}}`

`{{Substitution|line|pool|statement|depends|instance 1|substitution 1|instance 2|substitution 2|instance 3|substitution 3}}`

where:

`line`

is the number of the line on the tableau proof where the Rule of Substitution is to be invoked`pool`

is the pool of assumptions (comma-separated list) of the statement on which the Rule of Substitution is to be used`statement`

is the statement of logic that is to be displayed in the**Formula**column,**without**the`$ ... $`

delimiters`depends`

is the line of the tableau proof of the statement on which the Rule of Substitution is to be used

`instance 1`

is that which is being substituted`substitution 1`

is what it is being replaced with

Optionally you can perform up to $3$ substitutions:

`instance 2`

is that which is being substituted: instance 2`substitution 2`

is what it is being replaced with: instance 2

`instance 3`

is that which is being substituted: instance 3`substitution 3`

is what it is being replaced with: instance 3.

## Sources

- 1946: Alfred Tarski:
*Introduction to Logic and to the Methodology of Deductive Sciences*(2nd ed.) ... (previous) ... (next): $\S \text{II}.15$: Rules of inference - 1959: A.H. Basson and D.J. O'Connor:
*Introduction to Symbolic Logic*(3rd ed.) ... (previous) ... (next): $\S 4.2$: The Construction of an Axiom System: $RST \, 1$ - 1964: Donald Kalish and Richard Montague:
*Logic: Techniques of Formal Reasoning*... (previous) ... (next): $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 4$ - 1965: E.J. Lemmon:
*Beginning Logic*... (previous) ... (next): $\S 2.2$: Theorems and Derived Rules - 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*... (previous) ... (next): $\S 1.6$: Truth Tables and Tautologies