Equivalence

In this section, we will revisit the notion of equivalence. In chapter 2, we saw how we could use truth tables to show that two logical formulae are equivalent. Here, we will see that we can also show they are equivalent using our natural deduction proof rules.

Semantic equivalence

We saw in section 2.4 that two (or more) logical statements S1 and S2 were said to be semantically equivalent if and only if:

S1 ⊨ S2

and

S2 ⊨ S1

As a reminder, the S1 ⊨ S2 means S1 semantically entails S2, which means that every truth assignment that satisfies S1 also satisfies S2.

Semantic equivalence between S1 and S2 means that each proposition semantically entails the other – that S1 and S2 have the same truth value for every truth assignment; i.e., their truth tables evaluate exactly the same.

Showing semantic equivalence with two truth tables

For example, if we wished to show that the propositions p → ¬ q and ¬ (p ∧ q) were semantically equivalent, then we could create truth tables for each proposition:

        *
--------------
p q | p → ¬ q
--------------
T T |  F  F
T F |  T  T
F T |  T  F
F F |  T  T
--------------
Contingent

- T: [T F] [F T] [F F]
- F: [T T]

      *
----------------
p q | ¬ (p ∧ q)
----------------
T T | F    T
T F | T    F
F T | T    F
F F | T    F
----------------
Contingent

- T: [T F] [F T] [F F]
- F: [T T]

We see that the same set of truth assignments, [T F] [F T] [F F], satisfies both p → ¬ q and ¬ (p ∧ q).

Showing semantic equivalence with one truth table

To show that propositions S1 and S2 are semantically equivalent, we need to show that if S1 is true, then so is S2, and that if S2 is true, then so is S1. Instead of comparing the truth tables of both S1 and S2, we could instead express our requirements as a bi-implication: S1 ↔ S2. To express a bi-implication operator, we can use a conjunction of two implications: (S1 → S2) ∧ (S2 → S1). If this conjunction is a tautology, then we know that if one proposition is true, then the other one is too – that S1 and S2 are semantically equivalent.

Below, we show that p → ¬ q and ¬ (p ∧ q) are semantically equivalent using one truth table:

                              *
-------------------------------------------------------
p q | ((p → ¬ q) → ¬ (p ∧ q)) ∧ (¬ (p ∧ q) → (p → ¬ q))
-------------------------------------------------------
T T |     F F    T F    T     T  F    T    T    F F 
T F |     T T    T T    F     T  T    F    T    T T
F T |     T F    T T    F     T  T    F    T    T F
F F |     T T    T T    F     T  T    F    T    T T
-------------------------------------------------------
Tautology

Provable equivalence

Two propositional logic statements S1 and S2 are provably equivalent if and only if we can prove both of the following sequents:

S1 ⊢ S2

and

S2 ⊢ S1

We can also write:

S2 ⟛ S1

For example, suppose we wish to show that the propositions p → ¬ q and ¬ (p ∧ q) are provably equivalent. We must prove the following sequents:

p → ¬ q ⊢ ¬ (p ∧ q)

and

¬ (p ∧ q) ⊢ p → ¬ q

We complete both proofs below:

p → ¬ q ⊢ ¬ (p ∧ q)
{
    1. p → ¬ q              premise
    2. {
        3. p ∧ q            assume
        4. p                ∧e1 3
        5. q                ∧e2 3
        6. ¬ q              →e 1 4
        7. ⊥                ¬ e 5 6  
    }
    8. ¬ (p ∧ q)            ¬ i 2
}

¬ (p ∧ q) ⊢ p → ¬ q
{
    1. ¬ (p ∧ q)            premise
    2. {
        3. p                assume
        4. {
            5. q            assume
            6. p ∧ q        ∧i 3 5
            7. ⊥            ¬ e 6 1
        }
        8. ¬ q              ¬ i 4
    }
    9. p → ¬ q              →i 2
}