Craig DeLancey · A Concise Introduction to Logic, Ch. 3 · CC BY-SA 4.0
A truth table lists every possible assignment of truth values to the atoms and computes the result. A formula true in every row is a tautology. False in every row: contradiction. Mixed: contingency.
Truth values of connectives
Each connective has a fixed truth table. The surprising one: implication is false only when the premise is true and the conclusion is false. A false premise implies anything. This is called "vacuous truth."
Scheme
; Define the five connectives as functions on booleans
(define (neg p) (not p))
(define (conj p q) (and p q))
(define (disj p q) (or p q))
(define (impl p q) (or (not p) q))
(define (bicond p q) (equal? p q))
; Print truth table for implication
(define (show-row p q)
(display (if p "T""F"))
(display " -> ")
(display (if q "T""F"))
(display " = ")
(display (if (impl p q) "T""F"))
(newline))
(display "P -> Q = result") (newline)
(display "---") (newline)
(show-row #t#t)
(show-row #t#f)
(show-row #f#t)
(show-row #f#f)
Python
# Truth tables for all connectivesfromitertoolsimport product
def impl(p, q): return (not p) or q
def bicond(p, q): return p == q
print("P | Q | not P | P and Q | P or Q | P->Q | P<->Q")
print("-" * 52)
for p, q in product([True, False], repeat=2):
t = lambda b: "T"if b else"F"print(f"{t(p)} | {t(q)} | {t(not p)} | {t(p and q)} | {t(p or q)} | {t(impl(p,q))} | {t(bicond(p,q))}")
Evaluating compound formulas
To evaluate a compound formula, recursively evaluate subformulas bottom-up, applying each connective's truth table.
Scheme
; Evaluate a formula given an environment (assoc list)
(define (eval-formula f env)
(cond
((symbol? f) (cdr (assoc f env)))
((equal? (car f) (quote neg))
(not (eval-formula (cadr f) env)))
((equal? (car f) (quote and))
(and (eval-formula (cadr f) env)
(eval-formula (caddr f) env)))
((equal? (car f) (quote or))
(or (eval-formula (cadr f) env)
(eval-formula (caddr f) env)))
((equal? (car f) (quote implies))
(or (not (eval-formula (cadr f) env))
(eval-formula (caddr f) env)))
((equal? (car f) (quote iff))
(equal? (eval-formula (cadr f) env)
(eval-formula (caddr f) env)))))
; Evaluate (P and Q) implies R
(define formula
(list (quote implies) (list (quote and) (quote P) (quote Q)) (quote R)))
(define env1 (list (cons (quote P) #t) (cons (quote Q) #t) (cons (quote R) #f)))
(define env2 (list (cons (quote P) #t) (cons (quote Q) #f) (cons (quote R) #f)))
(display "(P and Q) -> R with P=T,Q=T,R=F: ")
(display (eval-formula formula env1)) (newline)
(display "(P and Q) -> R with P=T,Q=F,R=F: ")
(display (eval-formula formula env2))
Tautology, contradiction, contingency
Scheme
; A tautology is true in ALL rows.; A contradiction is false in ALL rows.; A contingency is true in some, false in others.
(define (impl p q) (or (not p) q))
; Check P or (not P) -- law of excluded middle
(define (excluded-middle p) (or p (not p)))
; Check P and (not P) -- contradiction
(define (contra p) (and p (not p)))
; Check all truth values
(display "P or (not P): ")
(display (list (excluded-middle #t) (excluded-middle #f)))
(display " <- tautology") (newline)
(display "P and (not P): ")
(display (list (contra #t) (contra #f)))
(display " <- contradiction") (newline)
(display "P -> Q: ")
(define results
(list (impl #t#t) (impl #t#f) (impl #f#t) (impl #f#f)))
(display results)
(display " <- contingency")
Neighbors
🔀 ToC Ch.3 — regular expressions as logical formulas over strings