Logical Equivalence

Craig DeLancey · A Concise Introduction to Logic, Ch. 4 · CC BY-SA 4.0

Two formulas are logically equivalent when they have the same truth value in every possible assignment. Equivalence laws let you rewrite formulas into simpler or more useful forms without changing their meaning.

De Morgan's laws

Negation distributes over conjunction and disjunction by flipping the connective. ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.

Scheme

; De Morgan's laws: verify by exhaustive check

(define (test-demorgan-and p q)
  ; not (P and Q) = (not P) or (not Q)
  (equal? (not (and p q))
          (or (not p) (not q))))

(define (test-demorgan-or p q)
  ; not (P or Q) = (not P) and (not Q)
  (equal? (not (or p q))
          (and (not p) (not q))))

(display "De Morgan (and) holds for all rows: ")
(display (and (test-demorgan-and #t #t)
              (test-demorgan-and #t #f)
              (test-demorgan-and #f #t)
              (test-demorgan-and #f #f))) (newline)

(display "De Morgan (or) holds for all rows: ")
(display (and (test-demorgan-or #t #t)
              (test-demorgan-or #t #f)
              (test-demorgan-or #f #t)
              (test-demorgan-or #f #f)))

Distribution

Conjunction distributes over disjunction and vice versa. P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R). P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).

Scheme

; Distribution laws
(define (test-dist-and p q r)
  (equal? (and p (or q r))
          (or (and p q) (and p r))))

(define (test-dist-or p q r)
  (equal? (or p (and q r))
          (and (or p q) (or p r))))

(define vals (list #t #f))
(define all-ok #t)

(for-each
  (lambda (p)
    (for-each
      (lambda (q)
        (for-each
          (lambda (r)
            (if (not (and (test-dist-and p q r)
                         (test-dist-or p q r)))
              (set! all-ok #f)))
          vals))
      vals))
  vals)

(display "Distribution laws hold for all 8 rows: ")
(display all-ok)

Contrapositive

The contrapositive of P → Q is ¬Q → ¬P. They are logically equivalent. The converse (Q → P) and inverse (¬P → ¬Q) are NOT equivalent to the original.

Scheme

; Contrapositive: P -> Q  equiv  not Q -> not P
(define (impl p q) (or (not p) q))

(define (test-contrapositive p q)
  (equal? (impl p q) (impl (not q) (not p))))

(define (test-converse p q)
  (equal? (impl p q) (impl q p)))

(display "Contrapositive holds: ")
(display (and (test-contrapositive #t #t)
              (test-contrapositive #t #f)
              (test-contrapositive #f #t)
              (test-contrapositive #f #f))) (newline)

(display "Converse holds: ")
(display (and (test-converse #t #t)
              (test-converse #t #f)
              (test-converse #f #t)
              (test-converse #f #f)))
(display " <- not equivalent!")

Biconditional elimination and simplification

P ↔ Q ≡ (P → Q) ∧ (Q → P). The biconditional is just two implications conjoined. Other useful equivalences: double negation (¬¬P ≡ P), idempotence (P ∧ P ≡ P), and absorption (P ∧ (P ∨ Q) ≡ P).

Scheme

; Biconditional elimination
(define (impl p q) (or (not p) q))
(define (bicond p q) (equal? p q))

(define (test-bicond-elim p q)
  (equal? (bicond p q)
          (and (impl p q) (impl q p))))

(display "Biconditional elimination holds: ")
(display (and (test-bicond-elim #t #t)
              (test-bicond-elim #t #f)
              (test-bicond-elim #f #t)
              (test-bicond-elim #f #f))) (newline)

; Double negation
(display "Double negation (not not T): ")
(display (not (not #t))) (newline)
(display "Double negation (not not F): ")
(display (not (not #f)))

Equivalence laws reference

Law	Equivalence
De Morgan	¬(P ∧ Q) ≡ ¬P ∨ ¬Q
De Morgan	¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Distribution	P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
Contrapositive	P → Q ≡ ¬Q → ¬P
Biconditional	P ↔ Q ≡ (P → Q) ∧ (Q → P)
Double negation	¬¬P ≡ P
Absorption	P ∧ (P ∨ Q) ≡ P

← Truth Tables by june.kim Natural Deduction →