How Math Explains the World.pdf

(TRUE AND NOT TRUE) OR FALSE

(TRUE AND FALSE) OR FALSE

FALSE OR FALSE

FALSE

Finally, just as arithmetic statements such as x(yz)xyxz is univer-

sally true because no matter what values of x, y, and z are substituted, both

sides evaluate to the same number, it is possible for two compound state-

ments to have identical values no matter what the truth values of the indi-

vidual statements that make up the compound statements are. In this case,

the two statements are called logically equivalent; the truth tables below

shows that NOT (P OR Q) is logically equivalent to (NOT P) AND (NOT Q).

Row P Q P OR Q NOT (P OR Q)

(1) TRUE TRUE TRUE FALSE

(2) TRUE FALSE TRUE FALSE

(3) FALSE TRUE TRUE FALSE

(4) FALSE FALSE FALSE TRUE

The last column of this truth table has the same values as the last col-

umn of the following table.

Row P Q NOT P NOT Q (NOT P) AND

(NOT Q)

(1) TRUE TRUE FALSE FALSE FALSE

(2) TRUE FALSE FALSE TRUE FALSE

(3) FALSE TRUE TRUE FALSE FALSE

(4) FALSE FALSE TRUE TRUE TRUE

A situation in which this equivalence arises occurs when your server
asks you if you would like coffee or dessert, and you reply that you don’t.
The server does not bring you coffee and also does not bring you dessert.
Propositional logic was shown to be consistent in the early 1920s by Emil
Post, using a proof that could be followed by any high-school logic student.^3
Post showed that under the assumption that propositional logic was incon-
sistent, any proposition could be shown to be true, including propositions
such as P AND (NOT P), which is always false. The next step was to tackle
the problem of the consistency of other systems—which brings us back to
the second problem on Hilbert’s list, the consistency of arithmetic.

Even Logic Has Limits 119