1 Logic 1 Logic 1.2 Well-formed formulas

1.1 Propositional calculus

We begin with propositional calculus, the study of propositions. A proposition is a mathematical statement which is either true or false.¹¹ 1 Sometimes people use the word proposition for something that’s a bit like a theorem but not quite as important. That’s not what we’re talking about here.

Here are some example propositions.

•

34043 is the sum of two square numbers.
•

The function $f(x)=\sin(x)$ is continuous.
•

The square root of 2 is not a rational number.
•

$1111111111111111111$ is a prime number.
•

$1+1=3$ .
•

$1+1=2$ .
•

The Riemann hypothesis is false.
•

25 is a square and 26 is a square.

Some of these are true and some are false, but each has a well-defined truth value, even if we don’t know what it is. On the other hand, something like “ $n$ is even” is not a proposition, because it doesn’t have a truth value until we know what $n$ is.

1.1.1 Logical connectives

Connectives combine simpler logical statements into more more complex ones. We use them to build complex propositions out of simpler ones. The standard connectives are ‘and’, ‘or’, ‘not’, ‘implies’, ‘if and only if’ (iff, for short).

Here are some examples of propositions which contain connectives.

•

and: “34043 is a sum of two squares and 34043 is divisible by 17”
•

or: “34043 is a sum of two squares or 34043 is divisible by 17”
•

not: “it is not true that 34043 is a sum of two squares”
•

implies: “34043 is odd implies 34043 is divisible by 3”
•

if and only if: “an odd prime number is a sum of two squares if and only if it leaves remainder 1 when you divide it by 4”

Implies is often expressed as “if…then”. The sentence “if 34043 is odd then 34043 is divisible by 3” means the same thing as “34043 is odd implies 34043 is divisible by 3.”

You might wonder if there are any more interesting “exotic connectives” that would allow us to create new statements not expressible using the connectives above. There are other connectives — common examples are exclusive or (written XOR), NAND (sometimes called Sheffer stroke), and NOR — but it’s a theorem that any connective you invent can be expressed in an equivalent way using just the connectives above (in fact, you don’t even need all of them).