Formal Logic/Sentential Logic/Substitution and Interchange

From Wikibooks, open books for an open world
Jump to navigation Jump to search
← 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)   

This has the (informally written) form

(2)   

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

(3)   

is a tautology. This process is general. Take any tautology. Find its most fully explicitly 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[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 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 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 won't work. First we substitute for obtaining

Next we substitute for obtaining

(6)   

This is indeed a tautology, but it is not the one we wanted. Let's try again. In (1), we substitute for 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)       is equivalent to   

You then might expect the following equivalence:

   is equivalent to   

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)       is equivalent to   

We note the following equivalence:

(9)       is equivalent to   

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):

   is equivalent to   

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

   is equivalent to   

we get the substitution instance

   is equivalent to   

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

(11)   

The equivalence

is equivalent to

together with the appropriate substitution gives us

(12)   

as equivalent to (11).

Finally, applying

   EquivalenceSign.png   

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 →