Rule of Substitution

Theorem

Let $S$ be a sequent of propositional logic that has been proved.

Then we may infer any sequent $S'$ resulting from $S$ by substitutions for letters.

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 of letters.

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

This article contains statements that are justified by handwavery. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding precise reasons why such statements hold. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Handwaving}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

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): Chapter $2$: The Propositional Calculus $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