True, false, and, or, not

In a classroom in Hanoi, Ms Lan plays a game with her class. She reads out a sentence, and everyone holds up a green card for true or a red card for false.

• "7 is bigger than 4." Green cards everywhere.
• "10 is an odd number." Red cards.
• "Every number that ends in 2 can be shared equally between 4 people." Minh thinks: 12 can (3 each), 32 can (8 each), 52 can (13 each)… He holds up green. Linh holds up red. "What about 22?" she says. "22 shared between 4 is 5 each, with 2 left over."

One number was enough to win the argument. Minh had checked three numbers, and he was right about all three — but the sentence talked about every number that ends in 2, and 22 breaks it.

For hundreds of years, people in Europe used "all swans are white" as an example of something everybody knew. In Australia, black swans had been there all along: the Noongar people of the south-west knew them well. When Dutch sailors led by Willem de Vlamingh saw black swans on what is now called the Swan River in 1697, a single kind of bird was enough to show that the old sentence was false.

Some sentences are true or false. Mathematicians call them statements.

A false statement is still a statement. "3 + 4 = 8" is a perfectly good statement: it just happens to be false.

We can build bigger statements out of smaller ones with three little words: and, or and not. Think of two light switches and a lamp. If the switches are in a row, one after the other, the lamp lights only when switch $p$ and switch $q$ are both on. If they are side by side, the lamp lights when $p$ or $q$ is on — and of course also when both are.

We can show all of this in a truth table. Each row is one possible case. With two statements there are only four cases: both true, only the first true, only the second true, both false.

Now the other direction. Suppose you check a claim for $1, 2, 3, \dots$ up to a million and it always works. Have you proved it for every whole number? No — there are infinitely many whole numbers, and you have checked only a million of them. The next one might break the pattern.

This really happens. Try the rule "$n \times n + n + 11$ is a prime number":

Ten primes in a row — and then $121 = 11 \times 11$.

When checking every case is a proof. Sometimes there are only a few cases, and then we can check them all. Here is a famous law about "not", "and" and "or", called De Morgan's law:

In everyday words: "It is not true that the shop is open and has bread" means "the shop is closed, or it has no bread (or both)".

This truth-table machine fills in every row for you. It starts by comparing "$p$ or $q$" with "one or the other but not both", written (p or q) and not (p and q). Look for the row marked ≠: that is the only case where they disagree.

Now check De Morgan's law, and then try some of your own. Type not, and, or and the letters p, q, r.

What to notice:

• With two letters there are 4 rows; with three letters there are 8. Each new letter doubles the number of rows.
• If you change the second formula to not p and not q, the machine finds rows where the two formulas differ. "Not (p and q)" is not the same as "not p and not q".

The Venn diagram below shows the same ideas with sets. $A$ is the set of children who play football and $B$ is the set of children who play chess. Shade "plays football and chess", then "plays football or chess", then "does not play football".

Gideon plays only with statements. For each one, decide: true or false? Then give a reason.

1. "15 is odd and 15 is less than 10." — False. For "and", both parts must be true, and 15 is not less than 10.
2. "4 is even or 4 is bigger than 3." — True. Both parts are true, and "or" allows both.
3. "Every odd number bigger than 1 is prime." — False. 3, 5 and 7 fit, but $9 = 3 \times 3$ is a counterexample.
4. "I checked 100 numbers, so the double of every number is even." — The reason is not good enough! The statement is true, but only the "groups of 2" reason proves it for every number.
5. "Not all the mangoes are ripe" means the same as "none of the mangoes is ripe." — False. It means at least one is not ripe.

/-- "12 is even **and** 12 is bigger than 20" is false, because its second part is false.
"12 is even **and** 12 is smaller than 20" is true, because both parts are true. -/
theorem and_example : ¬ (12 % 2 = 0 ∧ 12 > 20) ∧ (12 % 2 = 0 ∧ 12 < 20) := by
  decide

/-- "Or" is inclusive. "6 is even **or** 6 is a multiple of 3" is true — and both of its parts
are true. "7 is even or 7 is bigger than 10" is false, because neither part is true. -/
theorem or_example : (6 % 2 = 0 ∨ 6 % 3 = 0) ∧ ¬ (7 % 2 = 0 ∨ 7 > 10) := by
  decide

/-- "Not" swaps true and false. "7 is even" is false, so "7 is **not** even" is true. -/
theorem not_example : ¬ (7 % 2 = 0) := by
  decide

/-- The whole truth table of **and**: `p && q` is true in just one row, the row where both are
true. -/
theorem and_table :
    (true && true) = true ∧ (true && false) = false ∧
    (false && true) = false ∧ (false && false) = false := by
  decide

/-- The whole truth table of **or**: `p || q` is false in just one row, the row where both are
false. In the first row both parts are true, and so is `p || q`: this "or" is inclusive. -/
theorem or_table :
    (true || true) = true ∧ (true || false) = true ∧
    (false || true) = true ∧ (false || false) = false := by
  decide

/-- **De Morgan's law for "and".** "Not (p and q)" has the same truth value as
"(not p) or (not q)" in every row. There are only four rows (`cases p <;> cases q`), so
checking all of them is a complete proof. -/
theorem de_morgan_and (p q : Bool) : (!(p && q)) = (!p || !q) := by
  cases p <;> cases q <;> rfl

/-- The same law for statements (`Prop`), proved by reasoning instead of a table. If neither
`P` nor `Q` may hold, then `P` fails and `Q` fails; and if both fail, "P or Q" cannot hold. -/
theorem not_or_iff (P Q : Prop) : ¬ (P ∨ Q) ↔ ¬ P ∧ ¬ Q :=
  ⟨fun h => ⟨fun hp => h (Or.inl hp), fun hq => h (Or.inr hq)⟩,
   fun ⟨hnp, hnq⟩ h => h.elim hnp hnq⟩

/-- Five confirming examples: 12, 32, 52, 72 and 92 all end in 2, and all of them are divisible
by 4. -/
theorem ending_in_two_examples : ∀ n ∈ [12, 32, 52, 72, 92], n % 10 = 2 ∧ n % 4 = 0 := by
  decide

/-- …and yet "every number that ends in 2 is divisible by 4" is **false**. One counterexample
is enough: 22 ends in 2, but 22 = 4 × 5 + 2 leaves a remainder. -/
theorem ending_in_two_counterexample : ¬ ∀ n : Nat, n % 10 = 2 → n % 4 = 0 :=
  fun h => absurd (h 22 rfl) (by decide)

/-- "Every odd number bigger than 1 is prime" (has no factors except 1 and itself) is false:
3, 5 and 7 fit, but 9 is odd and has the factor 3. -/
theorem odd_not_always_prime :
    ¬ ∀ n : Nat, n > 1 → n % 2 = 1 → ∀ d, d ∣ n → d = 1 ∨ d = n := by
  intro h
  have h3 := h 9 (by decide) (by decide) 3 ⟨3, rfl⟩
  omega

/-- A "some" statement needs just one example. "Some number is even and has no factors except 1
and itself" is true: 2 is such a number. -/
theorem even_prime_exists : ∃ n : Nat, n % 2 = 0 ∧ n > 1 ∧ ∀ d, d ∣ n → d = 1 ∨ d = n := by
  refine ⟨2, rfl, by decide, fun d hd => ?_⟩
  have hle : d ≤ 2 := Nat.le_of_dvd (by decide) hd
  have hpos : 0 < d := Nat.pos_of_dvd_of_pos hd (by decide)
  omega

/-- Checking 100 cases: for each of the numbers 0, 1, …, 99, the double is even. Lean checks
the cases one by one. This says nothing yet about 100, or 1000. -/
theorem double_checked_to_100 : ∀ n, n < 100 → (2 * n) % 2 = 0 := by
  decide

/-- Proving every case at once: for **every** whole number `n`, `2 × n` is even, because
`2 × n` is `n` groups of 2 with nothing left over. This applies core Lean's
`Nat.mul_mod_right`. -/
theorem double_is_even (n : Nat) : (2 * n) % 2 = 0 :=
  Nat.mul_mod_right 2 n

/-- **The opposite of "all pass" is "at least one fails"** — not "none pass". For any list of
things and any yes-or-no test `p`: it is *not* true that every item passes exactly when some
item fails. Proved for every list, by working through the list one item at a time. -/
theorem not_all_iff_exists_not {α : Type} (items : List α) (p : α → Bool) :
    ¬ (∀ x ∈ items, p x = true) ↔ ∃ x ∈ items, p x = false := by
  induction items with
  | nil => simp
  | cons a as ih =>
    cases h : p a <;> simp [h, ih]

/-- A basket of four mangoes, ripe or not. "All the mangoes are ripe" is false, but "none of the
mangoes is ripe" is false too: the opposite of "all" is "at least one is not". -/
theorem not_all_ripe :
    ¬ (∀ ripe ∈ [true, true, false, true], ripe = true) ∧
    ¬ (∀ ripe ∈ [true, true, false, true], ripe = false) ∧
    (∃ ripe ∈ [true, true, false, true], ripe = false) := by
  decide

"""Truth tables for and, or, not - and checking a law in every row.

Each of two statements p and q is either true or false, so there are only
four rows to consider. The program prints the truth tables of 'and', the
inclusive 'or', the exclusive 'one or the other but not both' and 'not'. It
then checks De Morgan's laws and 'not (not p) = p' in every row, and shows
the one row where the inclusive and exclusive 'or' disagree. Because there
are only four rows, checking all of them is a complete proof of these laws -
unlike checking examples of a claim about all whole numbers.
"""

import textwrap
from itertools import product

ROWS = list(product([True, False], repeat=2))

def word(value):
    """'T' for true and 'F' for false."""
    return "T" if value else "F"

def inclusive_or(p, q):
    """True when at least one of p, q is true (the mathematician's 'or')."""
    return p or q

def exclusive_or(p, q):
    """True when exactly one of p, q is true ('one or the other, not both')."""
    return p != q

def same_in_every_row(rule1, rule2):
    """Do two rules give the same truth value in all four rows?"""
    return all(rule1(p, q) == rule2(p, q) for p, q in ROWS)

def rows_that_differ(rule1, rule2):
    """The rows (p, q) in which two rules give different truth values."""
    return [(p, q) for p, q in ROWS if rule1(p, q) != rule2(p, q)]

def main():
    print("p  q  | p and q | p or q | one but not both | not p")
    for p, q in ROWS:
        print(f"{word(p)}  {word(q)}  |    {word(p and q)}    |"
              f"   {word(inclusive_or(p, q))}    |"
              f"        {word(exclusive_or(p, q))}         |   {word(not p)}")
    print()
    print("not (p and q) = (not p) or (not q) in all 4 rows:",
          same_in_every_row(lambda p, q: not (p and q),
                            lambda p, q: (not p) or (not q)))
    print("not (p or q) = (not p) and (not q) in all 4 rows:",
          same_in_every_row(lambda p, q: not (p or q),
                            lambda p, q: (not p) and (not q)))
    print("not (not p) = p in all 4 rows:",
          same_in_every_row(lambda p, q: not (not p), lambda p, q: p))
    differ = rows_that_differ(inclusive_or, exclusive_or)
    print("Rows where 'or' and 'one but not both' differ:",
          ", ".join(f"p={word(p)}, q={word(q)}" for p, q in differ))
    print()
    print(textwrap.fill(
        "Epistemic status: exact and exhaustive. Two statements can only be "
        "true or false in 4 combinations, and every combination was "
        "checked, so this is a complete proof of these laws. A check of "
        "many examples of a claim about all whole numbers is different: "
        "there are infinitely many cases, so examples cannot finish the job.",
        width=78,
    ))

if __name__ == "__main__":
    main()

"""Hunting for counterexamples to claims about every whole number.

The program tests five 'every' claims on the whole numbers up to 10000. For
each claim it counts the examples that fit and the counterexamples, and
reports the first counterexample. Some claims fail quickly; one fails only
after ten successes in a row; one (Goldbach's conjecture) has no
counterexample here or in far bigger computer searches, yet nobody has
proved it; one (the double of a number is even) is proved in the lesson.
A counterexample disproves a claim; a search without one proves nothing.
"""

import textwrap

LIMIT = 10000

def primes_up_to(n):
    """is_prime[k] for 0 <= k <= n, by the sieve of Eratosthenes."""
    is_prime = [False, False] + [True] * (n - 1)
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
    return is_prime

PRIME = primes_up_to(LIMIT + 200)

def is_prime(n):
    """Is n a prime number? (Uses the sieve, so n must be in its range.)"""
    return PRIME[n]

def sum_of_two_primes(n):
    """Can n be written as p + q with p and q prime?"""
    return any(is_prime(p) and is_prime(n - p) for p in range(2, n // 2 + 1))

# Each claim: (description, which numbers it is about, the property).
CLAIMS = [
    ("every number ending in 2 is divisible by 4",
     lambda n: n % 10 == 2, lambda n: n % 4 == 0),
    ("every odd number bigger than 1 is prime",
     lambda n: n > 1 and n % 2 == 1, is_prime),
    ("n x n + n + 11 is prime for every n (tested up to n = 100)",
     lambda n: n <= 100, lambda n: is_prime(n * n + n + 11)),
    ("every even number from 4 on is a sum of two primes",
     lambda n: n >= 4 and n % 2 == 0, sum_of_two_primes),
    ("the double of every number is even",
     lambda n: True, lambda n: (2 * n) % 2 == 0),
]

def hunt(about, holds, limit=LIMIT):
    """Count fits and counterexamples among n = 0..limit; first failure."""
    fits, counterexamples, first = 0, 0, None
    for n in range(limit + 1):
        if about(n):
            if holds(n):
                fits += 1
            else:
                counterexamples += 1
                if first is None:
                    first = n
    return fits, counterexamples, first

def main():
    print(f"Testing five claims on the whole numbers 0 to {LIMIT}.")
    for text, about, holds in CLAIMS:
        fits, bad, first = hunt(about, holds)
        print()
        print(f"Claim: {text}")
        if first is None:
            print(f"  {fits} examples fit; no counterexample found.")
        else:
            print(f"  {fits} examples fit, {bad} counterexamples;"
                  f" the first is {first}.")
    n = 10
    print()
    print(f"The n x n + n + 11 claim works for n = 0, 1, ..., 9, then fails:"
          f" {n * n + n + 11} = 11 x 11.")
    print()
    print(textwrap.fill(
        "Epistemic status: an exhaustive search of a finite range. Each "
        "counterexample found is a complete disproof of its claim. Finding "
        "no counterexample proves nothing: Goldbach's conjecture has been "
        "checked by computers far beyond this range and is still unproved, "
        "while 'the double of every number is even' is proved in the lesson "
        "by reasoning, not by checking.",
        width=78,
    ))

if __name__ == "__main__":
    main()

Look carefully at what the computer found. Three claims are disproved: a counterexample settles the matter for good. But for two claims it found no counterexample — and that does not make them proved:

• "The double of every number is even" is proved, but by the "groups of 2" reason, not by the computer.
• "Every even number from 4 on is the sum of two primes" ($4 = 2 + 2$, $6 = 3 + 3$, $8 = 3 + 5$, $10 = 5 + 5$, …) is called Goldbach's conjecture, after Christian Goldbach, who discussed claims like it in letters with Leonhard Euler in 1742. Computers have checked every even number up to 4,000,000,000,000,000,000. Nobody has ever found a counterexample — and nobody has ever proved it. It is one of the most famous unsolved problems in mathematics.

Read each sentence slowly. Is it a statement? Is it true? What is your reason? You can ask for a hint whenever you like.

The three little words match the three ways of making new sets that you can meet in the lesson on sets. Let $A$ be the set of numbers from 1 to 20 that are even, and $B$ the set of numbers from 1 to 20 that are multiples of 3.

• "even and a multiple of 3" picks out the intersection $A \cap B = \{6, 12, 18\}$;
• "even or a multiple of 3" picks out the union $A \cup B$: the 10 even numbers, plus the odd multiples of 3 (3, 9, 15) — 13 numbers in all, with 6, 12 and 18 counted once;
• "not even" picks out the complement of $A$: the odd numbers from 1 to 20.

The inclusive "or" is exactly why the union contains the overlap. And De Morgan's law for statements becomes a law for sets: the complement of $A \cap B$ is the union of the complements.

Later, in quantifiers and propositional logic, you will write "every" as $\forall$ and "some" as $\exists$, and work with truth tables for longer formulas.

• Ancient Greece. Aristotle (4th century BCE) studied arguments built from "all", "some" and "no" — for example "all … are …, and all … are …, so all … are …". A century later the Stoic thinker Chrysippus studied how whole statements are joined by words like "and", "or" and "if".
• Ancient India. The Nyāya school of philosophy developed a careful theory of anumāna, inference: how to reason correctly from what we know to something new, using general rules and examples.
• Ancient China. The Mohist Canon, written by followers of the philosopher Mozi around the 4th and 3rd centuries BCE, discusses how to make distinctions and argue correctly.
• Persia and the Islamic world. Ibn Sīnā (Avicenna, 980–1037) wrote at great length on logic, including statements joined by "if… then" and "either… or".
• Algebra of logic. In 1847 Augustus De Morgan, in London, wrote down the laws that now carry his name. In 1854 George Boole, working in Cork in Ireland, published The Laws of Thought, treating true and false like the numbers 1 and 0, and "and", "or", "not" like arithmetic.
• Logic in machines. In 1937 Claude Shannon, then a student in the United States, showed that circuits of switches — like the ones in the picture above — can carry out Boole's logic. Every modern computer is built on this idea.
• Black swans. The Roman poet Juvenal (around 100 CE) called something impossibly rare "a rare bird, very like a black swan". In Australia, black swans were an everyday sight.

• Raymond Smullyan, Alice in Puzzle-Land (1982) and What Is the Name of This Book? (1978) — logic puzzles that delight children and adults.
• Lewis Carroll, The Game of Logic (1886) — a playful introduction to reasoning with "all", "some" and "none".
• George Pólya, Mathematics and Plausible Reasoning, Volume 1: Induction and Analogy in Mathematics (1954) — on how examples suggest conjectures, and why only proofs settle them.
• Tim Bell, Ian H. Witten and Mike Fellows, Computer Science Unplugged (1998; later editions) — classroom activities, including how computers use true and false.