Formal Logic/Sentential Logic/Substitution and Interchange

Substitution and Interchange

This page will use the notions of occurance and subformula introduced at the Additional terminology section of Formal Syntax. These notions have been little used if at all since then, so you might want to review them.

Substitution

Tautological forms

We have introduced a number of tautologies, one example being

(1)    $\mathrm{Q}\to (\mathrm{P}\to \mathrm{Q})$

This has the (informally written) form

(2)    $\psi \to (\phi \to \psi )$

As it turns out, any formula matching this form is a tautology. Thus, for example,

(3)    $\mathrm{R}\wedge \mathrm{S}\to (\mathrm{P}\vee \mathrm{Q}\to \mathrm{R}\wedge \mathrm{S})$

is a tautology. This process is general. Take any tautology. Find its most fully explicity form by uniformly replacing distinct sentence letters with distinct Greek letters. We can call this a tautological form, which will not be a formula but rather a metalogical expression. Any instance of this tautological form is a tautology.

Substitution instances

The preceding illustrated how we can generate new tautologies from old ones via tautological forms. Here, we will show how to generate tautologies without resort to tautological forms. To do this, we will define a substitution instance of a formula. Any substitution instance of a tautology is also a tautology.

First, we define the simple substitution instance of a formula for a sentence letter. Let $\phi$ and $\psi$ be formulae and $\pi$ be a sentence letter. The simple substitution instance $\phi [\pi /\psi ]$ is the result of replacing every occurance of $\pi$ in $\phi$ with an occurance of $\psi$. A substitution instance of formulae for a sentence letters is the result of a chain of simple substitution instances. In particular, a chain of zero simple substitutions instances starting from $\phi$ is a substitution instance and indeed is just $\phi$ itself. Thus, any formula is a substitution instance of itself.

It turns out that if $\phi$ is a tautology, then so is any simple substitution instance $\phi [\pi /\psi ]$. If we start with a tautology and generate a chain of simple substitution instances, then every formula in the chain is also a a tautology. Thus any (not necessarily simple) substitution instance of a tautology is also a tautology.

Substitution examples

Consider (1) again. We substitute $\mathrm{R}\wedge \mathrm{S}$ for every occurance of $\mathrm{Q}$ in (1). This gives us the following simple substition instance of (1):

(4)    $\mathrm{R}\wedge \mathrm{S}\to (\mathrm{P}\to \mathrm{R}\wedge \mathrm{S})$

In this, we substitute $\mathrm{P}\vee \mathrm{Q}$ for $\mathrm{P}$. That gives us (3) as a simple substitution instance of (4). Since (3) is the result of a chain of two simple substitution instances, it is a (non-simple) substitution instance of (1) Since (1) is a tautology, so is (3). We can express the chain of substitutions as

$\mathrm{Q}\to (\mathrm{P}\to \mathrm{Q})[\mathrm{Q}/\mathrm{R}\wedge \mathrm{S}][\mathrm{P}/\mathrm{P}\vee \mathrm{Q}]$

Take another example, also starting from (1). We want to obtain

(5)    $\mathrm{P}\to (\mathrm{Q}\to \mathrm{P})$

Our first attempt won't work. First we substitue $\mathrm{Q}$ for $\mathrm{P}$ obtaining

$\mathrm{Q}\to (\mathrm{Q}\to \mathrm{Q})$

Next we substitue $\mathrm{P}$ for $\mathrm{Q}$ obtaining

(6)    $\mathrm{P}\to (\mathrm{P}\to \mathrm{P})$

This is indeed a tautology, but it is not the one we wanted. Let's try again. In (1), we substitute $\mathrm{R}$ for $\mathrm{P}$ obtaining

$\mathrm{Q}\to (\mathrm{R}\to \mathrm{Q})$

Now substitute $\mathrm{P}$ for $\mathrm{Q}$ obtaining

$\mathrm{P}\to (\mathrm{R}\to \mathrm{P})$

Finally, substituting $\mathrm{P}$ for $\mathrm{R}$ gets us the result we wanted, namely (5). Since (1) is a tautology, so is (5). We can express the chain of substitutions as

$\mathrm{Q}\to (\mathrm{P}\to \mathrm{Q})[\mathrm{P}/\mathrm{R}][\mathrm{Q}/\mathrm{P}][\mathrm{R}/\mathrm{P}]$

Simultaneous substitutions

We can compress a chain of simple substitutions into a single complex substitution. Let $\phi$, ${\psi }_1$, ${\psi }_2$, ... be formulae; let ${\pi }_1$, ${\pi }_2$, ... be sentence letters. We define a simultaneous substitution instance of formulas for sentence letters $\phi [{\pi }_1/{\psi }_1,{\pi }_2/{\psi }_2,...]$ be the result of starting with $\phi$ and simultaneously replacing ${\pi }_1$ with ${\psi }_1$, ${\pi }_2$ with ${\psi }_2$, .... We can regenerate our examples.

The previously generated formula (3) is

$\mathrm{Q}\to (\mathrm{P}\to \mathrm{Q})[\mathrm{P}/\mathrm{P}\vee \mathrm{Q},\mathrm{Q}/\mathrm{R}\wedge \mathrm{S}]$

Similarly, (5) is

$\mathrm{Q}\to (\mathrm{P}\to \mathrm{Q})[\mathrm{P}/\mathrm{Q},\mathrm{Q}/\mathrm{P}]$

Finally (6) is

$\mathrm{Q}\to (\mathrm{P}\to \mathrm{Q})[\mathrm{Q}/\mathrm{P}]$

When we get to predicate logic, simultaneous substitution instances will not be available. That is why we defined substitution instance by reference to a chain of simple substitution instances rather than as a simultaneous substitution instance.

Interchange

Interchange of equivalent subformulae

We previously saw the following equivalence at Properties of Sentential Connectives:

(7)    $\mathrm{P}$       $\mathrm{\neg }\mathrm{\neg }\mathrm{P}$

You then might expect the following equivalence:

$\mathrm{P}\to \mathrm{Q}\wedge \mathrm{R}$       $\mathrm{\neg }\mathrm{\neg }\mathrm{P}\to \mathrm{Q}\wedge \mathrm{R}$

This expectation is correct; the two formulae are equivalent. Let $\phi$ and $\psi$ be equivalent formulae. Let ${\chi }_1$ be a formula in which $\phi$ occurs as a subformula. Finally, let ${\chi }_2$ be the result of replacing in $\chi$ at least one (not necessarily all) occurances of $\phi$ with $\psi$. Then ${\chi }_1$ and ${\chi }_2$ are equivalent. This replacement is called an interchange.

For a second example, suppose we want to generate the equivalence

(8)    $\mathrm{P}\to \mathrm{Q}\wedge \mathrm{R}$       $\mathrm{P}\to \mathrm{\neg }\mathrm{\neg }(\mathrm{Q}\wedge \mathrm{R})$

We note the following equivalence:

(9)    $\mathrm{Q}\wedge \mathrm{R}$       $\mathrm{\neg }\mathrm{\neg }(\mathrm{Q}\wedge \mathrm{R})$

These two formulae can be confirmed to be equivalent either by truth table or, more easily, by substituting $\mathrm{Q}\wedge \mathrm{R}$ for $\mathrm{P}$ in both formulae of (7).

This substitution does indeed establish (9) as an equivalence. We already noted that $\phi$ and $\psi$ are equivalent if and only if $\phi \leftrightarrow \psi$ is a tautology. Based on (7), we get the tautology

$\mathrm{P}\leftrightarrow \mathrm{\neg }\mathrm{\neg }\mathrm{P}$

Our substitution then yeilds

$\mathrm{Q}\wedge \mathrm{R}\leftrightarrow \mathrm{\neg }\mathrm{\neg }(\mathrm{Q}\wedge \mathrm{R})$

which is also a tautology. The corresponding equivalence is then (9).

Based on (9), we can now replace the consequent of $\mathrm{P}\to \mathrm{Q}\wedge \mathrm{R}$ with its equivalent. This generates the desired equivalence, namely (8).

Every formula equivalent to a tautology is also a tautology. Thus an interchange of equivalent subformulae within a tautology results in a tautology. For example, we can use the substitution instance of (7):

$\mathrm{Q}$       $\mathrm{\neg }\mathrm{\neg }\mathrm{Q}$

together with the tautology previously seen at Properties of Sentential Connectives:

$(\mathrm{P}\to \mathrm{Q})\vee (\mathrm{Q}\to \mathrm{R})$

to obtain

$(\mathrm{P}\to \mathrm{\neg }\mathrm{\neg }\mathrm{Q})\vee (\mathrm{Q}\to \mathrm{R})$

as a new tautology.

Interchange example

As an example, we will use the interdefinability of connectives to express

(10)    $\mathrm{P}\leftrightarrow \mathrm{Q}\vee \mathrm{R}$

using only conditionals and negations.

Based on

$\mathrm{P}\vee \mathrm{Q}$       $\mathrm{\neg }\mathrm{P}\to \mathrm{Q}$

we get the substitution instance

$\mathrm{Q}\vee \mathrm{R}$       $\mathrm{\neg }\mathrm{Q}\to \mathrm{R}$

which in turn allows us to replace the appropriate subformula in (10) to get:

(11)    $\mathrm{P}\leftrightarrow \mathrm{\neg }\mathrm{Q}\to \mathrm{R}$

The equivalence

$\mathrm{P}\leftrightarrow \mathrm{Q}$ $(\mathrm{P}\to \mathrm{Q})\wedge (\mathrm{Q}\to \mathrm{P})$

together with the appropriate substitution gives us

(12)    $(\mathrm{P}\to (\mathrm{\neg }\mathrm{Q}\to \mathrm{R}))\wedge ((\mathrm{\neg }\mathrm{Q}\to \mathrm{R})\to \mathrm{P})$

as equivalent to (11).

Finally, applying

$\mathrm{P}\wedge \mathrm{Q}$       $\mathrm{\neg }(\mathrm{P}\to \mathrm{\neg }\mathrm{Q})$

together with the appropriate substitution, yeilds our final result:

$\mathrm{\neg }(\mathrm{P}\to (\mathrm{\neg }\mathrm{Q}\to \mathrm{R})\to \mathrm{\neg }((\mathrm{\neg }\mathrm{Q}\to \mathrm{R})\to \mathrm{P}))$

Summary

This page has presented two claims.

• A substitution instance of a tautology is also a tautology.

• Given a formula, the result of interchanging a subformula with an equivalent is a formula equivalent to the given formula.

These claims are not trivial observations or the result of a simple turth table. They are substantial claims that need proof. Proofs are available in a number of standard metalogic textbooks, but are not presented here.