Class diagrams — the series

1. 

   Four circles cannot do it

   Three overlapping circles cut the plane into exactly the eight regions three sets need. Four circles cut it into fourteen, and sixteen are required — so the diagram everyone draws stops working at four, and the reason is a count.

   part 1 · logic
2. 

   Twenty-four out of two hundred and fifty-six

   Aristotle's syllogisms are four sentence forms in four arrangements, which makes 256 patterns of argument. Fifteen of them are valid. Nine more become valid if you assume the things being talked about exist, and the gap between those numbers is a two-thousand-year-old disagreement.

   part 2 · logic
3. 

   One thing in each region is enough

   Give first-order logic its full apparatus of nested quantifiers but only one-place predicates, and every question about truth is still settled by the regions of a diagram. A predicate cannot tell apart two things in the same region, so no model ever needs more than one thing per region — and with three predicates there are only 255 models to try.

   part 3 · logic
4. 

   The conclusion is what survives the erasing

   Lewis Carroll's puzzles give three premises about four classes — babies, logical people, the despised, crocodile-managers — and ask what follows. Draw all four, shade what the premises rule out, then erase the classes the conclusion is not about: a region survives as empty only if everything above it was. What is left is the conclusion, and erasing a class turns out to be exactly one step of resolution.

   part 4 · logic
5. 

   A walk that beats trying everything

   To decide whether clauses of three letters can all be satisfied, the obvious method tries all 2ⁿ assignments. Uwe Schöning's method, from 1999, starts at a random assignment and wanders: pick a clause that is false, flip one of its letters at random, and repeat three times as many times as there are letters. A single try usually fails, but it succeeds with chance at least about (3/4)ⁿ, so about (4/3)ⁿ tries are enough — and the reason is a walk on a line that goes the wrong way two times in three.

   part 5 · logic
6. 

   A letter the clauses already decide

   Set the letters of a formula one at a time, in a random order, and guess each one with a coin — unless some clause has already had its other two letters set to false, in which case the clause decides. A try succeeds when every guess is right, so what matters is how many letters get guessed. On a formula with one solution, every letter has a clause that forces it in at least one order out of three, so at most two thirds of the letters are guessed on average, and about 1.587ⁿ tries suffice. It is slower than the random walk. Refined, it is the fastest method known.

   part 6 · logic
7. 

   Syllogisms that say most

   The syllogism knew four words — all, no, some, some not — and two thousand years of logic decided which of its 256 forms were valid. Add 'most', a word everyone uses in arguments, and the 256 become 864. A diagram with marks for 'empty' and 'occupied' can no longer decide them, because 'most' compares sizes; but writing the number of things in each region turns every form into a linear programme, and the programme decides all of them at once. Thirty-one are valid, including one Augustus De Morgan found in 1847: if most M are S and most M are P, then some S are P. And 'most' cannot be passed along a chain: ninety-nine per cent of S can be M, ninety-nine per cent of M can be P, and no S be P at all.

   part 7 · logic
8. 

   Venn diagrams that turn into themselves

   A Venn diagram shows every combination of in and out exactly once. Ask for one that looks the same after a turn of 1/n, each curve rotating onto the next, and a counting argument forbids it unless n is prime. Five congruent ellipses manage it, certified by Euler's formula; four rotated copies cannot, and it took until 2004 to show that every prime can.

   part 8 · logic

All series