Formal Logic/Sentential Logic/Substitution and Interchange

← Properties of Sentential Connectives ↑ Sentential Logic Translations →



Substitution and Interchange

edit

This page will use the notions of occurrence 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

edit

Tautological forms

edit

We have introduced a number of tautologies, one example being

(1)     

Use the metavariables   and   to replace   and   in (1). This produces the form

(2)     

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

(3)     

is a tautology. This process can be generalized to all tautologies: for any tautology, find its explicit form by replacing each sentence letters with distinct metavariables (written as Greek letters, as shown in (2)). We can call this a tautological form, which is a metalogical expression rather than a formula. Any instance of this tautological form is a tautology.

Substitution instances

edit

The preceding illustrated how we can generate new tautologies from old ones via tautological forms. Here, we will show how to generate tautologies without resorting to tautological forms. To do this, we 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   and   be formulae and   be a sentence letter. The simple substitution instance   is the result of replacing every occurrence of   in   with an occurrence of  . 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   is a substitution instance and indeed is just   itself. Thus, any formula is a substitution instance of itself.

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

Substitution examples

edit

Consider (1) again. We substitute   for every occurrence of   in (1). This gives us the following simple substitution instance of (1):

(4)     

In this, we substitute   for  . 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

 

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

(5)     

Our first attempt might be to substitute   for  ,

(6)     

This is indeed a tautology, but it is not the one we wanted. Instead, we substitute   for   in (1), obtaining

 

Now substitute   for   obtaining

 

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

 

Simultaneous substitutions

edit

We can compress a chain of simple substitutions into a single complex substitution. Let  ,  ,  , ... be formulae; let  ,  , ... be sentence letters. We define a simultaneous substitution instance of formulas for sentence letters   be the result of starting with   and simultaneously replacing   with  ,   with  , .... We can regenerate our examples.

The previously generated formula (3) is

 

Similarly, (5) is

 

Finally (6) is

 


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

edit

Interchange of equivalent subformulae

edit

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

(7)               

You then might expect the following equivalence:

           

This expectation is correct; the two formulae are equivalent. Let   and   be equivalent formulae. Let   be a formula in which   occurs as a subformula. Finally, let   be the result of replacing in   at least one (not necessarily all) occurrences of   with  . Then   and   are equivalent. This replacement is called an interchange.

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

(8)               

We note the following equivalence:

(9)               

These two formulae can be confirmed to be equivalent either by truth table or, more easily, by substituting   for   in both formulae of (7).

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

 

Our substitution then yields

 

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

Based on (9), we can now replace the consequent of   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):

           

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

 

to obtain

 

as a new tautology.

Interchange example

edit

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

(10)     

using only conditionals and negations.

Based on

           

we get the substitution instance

           

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

(11)     

The equivalence

     

together with the appropriate substitution gives us

(12)     

as equivalent to (11).

Finally, applying

           

together with the appropriate substitution, yields our final result:

 

Summary

edit

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 truth table. They are substantial claims that need proof. Proofs are available in a number of standard metalogic textbooks, but are not presented here.


← Properties of Sentential Connectives ↑ Sentential Logic Translations →