Showing Web View For Page 806 | Show full page with images

So if one makes a list of all possible axiom systems—say starting with the simplest—where in such a list should one expect to see axiom systems that correspond to traditional areas of mathematics?

Most axiom systems as they are given in typical textbooks are sufficiently complicated that they will not show up at all early. And in fact the only immediate exception is the axiom system {(a b) c a (b c)} for what are known as semigroups—which ironically are usually viewed as rather advanced mathematical objects.

But just how complicated do the axiom systems for traditional areas of mathematics really need to be? Often it seems that they can be vastly simpler than their textbook forms. And so, for example, as page 773 indicates, interpreting the operator as division, {a (b (c (a b))) c} is known to be an axiom system for commutative group theory, and {a ((((a a) b) c) (((a a) a) c)) b} for general group theory.

So what about basic logic? How complicated an axiom system does one need for this? Textbook discussions of logic mostly use axiom systems at least as complicated as the first one on page 773. And such axiom systems not only involve several axioms—they also normally involve three separate operators: And (), Or () and Not (¬).

But is this in fact the only way to formulate logic?

As the picture below shows, there are 16 different possible operators that take two arguments and allow two values, say true and false. And of these And, Or and Not are certainly the most commonly used in both everyday language and most of mathematics.


Logical functions of two arguments and their common names. Black stands for True; white for False. And, Or, Not, and Implies are widely used in traditional logic. Equal (if and only if) is common in more mathematical settings, while Xor is widespread in discrete mathematics. Nand and Nor are mostly used only in circuit design and in a few foundational studies of logic. The first argument for each function appears on the left in the picture; the second argument on top. The functions are numbered like 2-neighbor analogs of the cellular automaton rules of page 53.

From Stephen Wolfram: A New Kind of Science [citation]