Statements and Logic

Jim Hefferon · GFDL + CC BY-SA 2.5 · Introduction to Proofs

A proposition is a statement that is either true or false. Logical connectives (and, or, not, implies) combine propositions into compound statements. The truth value of any compound statement is determined entirely by the truth values of its parts.

Propositions

A proposition is a declarative sentence with a definite truth value. "5 is prime" is a proposition (true). "Close the door" is not. "x + 1 = 3" is not, until you fix x. Questions and commands are never propositions.

Scheme

; A proposition is true or false. We model them as booleans.
(define p #t)  ; "5 is prime" — true
(define q #f)  ; "4 is prime" — false

(display "p = ") (display p) (newline)
(display "q = ") (display q) (newline)

; Not a proposition: "x + 1 = 3" depends on x.
; Once we fix x, it becomes one:
(define (is-proposition? x) (= (+ x 1) 3))
(display "x=2: ") (display (is-proposition? 2)) (newline)
(display "x=5: ") (display (is-proposition? 5))

Connectives

The four main connectives: not (negation), and (conjunction), or (disjunction), and implies (conditional). "Or" in math is inclusive: P or Q is true when both are true.

Scheme

; Logical connectives
(define (my-not p) (not p))
(define (my-and p q) (and p q))
(define (my-or p q) (or p q))
(define (my-implies p q) (or (not p) q))

(define p #t)
(define q #f)

(display "not p       = ") (display (my-not p)) (newline)
(display "p and q     = ") (display (my-and p q)) (newline)
(display "p or q      = ") (display (my-or p q)) (newline)
(display "p implies q = ") (display (my-implies p q)) (newline)
(display "q implies p = ") (display (my-implies q p))
; False implies anything is true — this is the vacuous truth.

Truth tables

A truth table lists every possible combination of truth values for the inputs and shows the output. For two variables, that is four rows. The implication P implies Q is false only when P is true and Q is false. This is the row that trips everyone up.

Scheme

; Generate truth table for implication
(define (implies p q) (or (not p) q))

(display "P     Q     P->Q") (newline)
(display "---   ---   ----") (newline)

(define (show-row p q)
  (display (if p "T" "F"))
  (display "     ")
  (display (if q "T" "F"))
  (display "     ")
  (display (if (implies p q) "T" "F"))
  (newline))

(show-row #t #t)
(show-row #t #f)
(show-row #f #t)
(show-row #f #f)

Logical equivalence

Two compound statements are logically equivalent when they have the same truth value for every possible assignment. The most important equivalence: P implies Q is equivalent to (not Q) implies (not P). This is the contrapositive, and it is the basis of an entire proof technique.

Scheme

; Logical equivalence: P->Q is equivalent to (not Q)->(not P)
(define (implies p q) (or (not p) q))
(define (contrapositive p q) (implies (not q) (not p)))

(display "P->Q  vs  ~Q->~P") (newline)
(display "----      -------") (newline)

(define (check p q)
  (let ((orig (implies p q))
        (contra (contrapositive p q)))
    (display (if orig "T" "F"))
    (display "      ")
    (display (if contra "T" "F"))
    (display "      ")
    (display (if (eq? orig contra) "same" "DIFFERENT"))
    (newline)))

(check #t #t)
(check #t #f)
(check #f #t)
(check #f #f)
; Every row matches. They are logically equivalent.

The conditional — why "false implies anything" is true

The conditional P implies Q is a promise: "if P happens, then Q will happen." It can only be broken when P happens and Q does not. If P never happens, the promise is vacuously kept. "If pigs fly, I will eat my hat" is true, because pigs do not fly. This is vacuous truth.

Scheme

; Vacuous truth: false implies anything
(define (implies p q) (or (not p) q))

; "If pigs fly, I will eat my hat"
(define pigs-fly #f)

(display "Pigs fly -> eat hat: ")
(display (implies pigs-fly #t)) (newline)

(display "Pigs fly -> not eat hat: ")
(display (implies pigs-fly #f)) (newline)

; Both true! The promise is never tested.
(display "False -> True:  ") (display (implies #f #t)) (newline)
(display "False -> False: ") (display (implies #f #f))

Neighbors

🔑 Logic Ch.2 — propositional logic formalized
🔑 Logic Ch.3 — translation between English and formal logic
🔑 Logic Ch.2 — propositional logic formalized with syntax and rules
🔑 Logic Ch.3 — truth tables and semantic consequence
🔢 Discrete Math Ch.3 — symbolic logic from a different angle

by june.kim Direct Proof →