EQUIVALENCE RULES

(Rules of Replacement)

Whenever the truth table columns for the dominant operators in a pair of formulas are identical, those formulas are said to be equivalent.  Equivalence can be defined as truth under the same conditions (and, since truth is bivalent, falsity under the same conditions).  If two formulae are equivalent, one version may be substituted for the other without any loss of or change in meaning.  In the language of high school algebra, replacing one expression with an equivalent expression amounts to "replacing equals with equals."

Each of our equivalence rules can be verified as legitimate with a truth table.  Consider the equivalence rule known as DeMorgan's transformation:

~(p q) :: (~p  ~q)

The following truth table establishes that the equivalence is legitimate.

 1 2 3 4 5 6 7 8 9 10 11 p q ~ (p ● q) (~ p ▼ ~ q) T T ⊥ T T T ⊥ T ⊥ ⊥ T T ⊥ T T ⊥ ⊥ ⊥ T T T ⊥ ⊥ T T ⊥ ⊥ T T ⊥ T ⊥ T ⊥ ⊥ T ⊥ ⊥ ⊥ T ⊥ T T ⊥

Since columns 3 and 9 are identical, the formulas are equivalent and one can be substituted for the other.

Our system utilizes 11 different rules of equivalence.  They are:

 Rules of Equivalence Absorption (ABS) p → q Therefore: p → (p ● q) DeMorgan (DEM) ~ ( p ● q) :: (~p ▼ ~q) ~ (p ▼ q) ::(~p ● ~q) Commutation (COMM) (p ● q) :: (q ● p) (p ▼ q) :: (q ▼p) Association (ASSN) [p ▼ (q ▼ r)] :: [(p ▼q) ▼ r] [p● (q ● r)] :: [(p ● q) ● r] Distribution (DIST) [p ● (q ▼ r)] :: [(p ● q) ▼ (p ● r)] [p ▼ (q ● r)] :: [(p ▼q) ● (p ▼ r)] Double Negation (DN) p :: ~ ~p Contraposition (Contra) (p → q) :: (~ q → ~p) Material Implication (MI) (p → q) :: (~ p ▼ q) Exportation (EXP) [(p ● q) → r] :: [p → (q → r)] Material Equivalence (EQ) (p ↔ q) :: [(p → q) ● (q → p)] (p ↔ q) :: [(p ● q) ▼ ( ~ p ● ~ q)] Redundancy (Red) p :: (p ▼ p) p :: (p ● p)

In order to make use of our equivalence rules, we need to map the formula we wish to modify onto one side of of the equivalence rule and then using that mapping create a substitution instance of the other side of the rule.

For example, if we wish to apply the rule material implication to the formula (P  Q), we first need to map the formula onto the rule.  Since the rule states:

(p q) :: (~p ▼q)

we need to determine of which side is our original WFF a substitution instance.  In this case the mapping is obvious:  our WFF (P  Q) maps onto the left hand side of the rule (p q) :: (~p ▼q).  By replacing the sentential variables in the right hand side of the rule with the WFF's used in the mapping, and holding the constants constant, we get (~P Q).

Let's try a more complex example and apply a DeMorgan transformation to the following WFF:

~[(P Q) (R  ~S)]

The form of the rule is:

~(p q) ::  (~p ▼ ~q)

so the first task is to map the original WFF onto the rule.  In this case, the WFF maps onto the left hand side of the rule.

corresponds to ~(p q) ::  (~p ▼ ~q)

So, now we use the WFF's in the original WFF that correspond to the sentential variables in the side of the rule pattern that is matched to generate a substitution instance of the other side of the rule.  We get:

[~(P Q) ~ (R  ~S)]

so we know that ~[(P Q) (R  ~S)] can be replaced with [~(P Q) ▼~ (R  ~S)] and vice versa.