Essential Logic

There is a certain type of sentence which is either true or false. For example, the first of the following two sentences is true, the second false.^2.1

$$\mbox{There are two prime numbers whose sum is 24.}$$ (2.1)

$$\mbox{There is a prime number which is divisible by 6.}$$ (2.2)

Such sentences are said to be declarative in form; we will refer to them simply as statements, and will sometimes feel free to use synonyms like `proposition,' `claim,' and so on. The mark of a statement is that it must have a truth-value, where TRUE and FALSE are the two values in question. If we are careful and clever and energetic, our exploration should reveal that certain statements are (sometimes surprisingly) true and that certain others are (sometimes surprisingly) false.

But not all sentences can have truth-values; the following two, for instance, are neither true nor false.

$$\mbox{Read this chapter as soon as possible!}$$ (2.3)

$$\mbox{Is your assignment finished?}$$ (2.4)

The second of these is inquisitive in form, the first imperative. Sometimes inquisitives can be of great interest to mathematicians and logicians. Indeed, the following inquisitive sentence, if answered, would put to rest a longstanding unresolved question in number theory.^2.2

$$\mbox{Is every even number $\ge$\space 4 the sum of two primes?}$$ (2.5)

Of course, in mathematics and logic and related fields (e.g., computer science) it isn't enough to simply answer such a question; it isn't even enough to give an answer on the basis of some genuine evidence (such as that 6 = 5+1, 8 = 7+1, 10 = 5+5, and 12 = 7+5.) We must find proofs that certain answers are correct, and that certain others are wrong.

But proofs cannot be constructed without ways of connecting the statements involved. For example, suppose we wanted to prove (1); then we might reason as follows. ``Let n be some arbitrary prime number. We know that if some number is prime, then by definition it is divisible only by itself and 1. Hence n is divisible only by itself and 1. So it's not the case that n is divisible by 6, for if it were, we would have a contradiction: n would be divisible by itself and by 1 only, and by other numbers (like 3). It follows that no prime number is divisible by 6." In this little unassuming proof are found nearly all the essential logic required to initiate our project.

Notice first that in the proof of (1) there is an inference from

$$\mbox{If $n$\space is prime, then $n$\space is divisible only by itself and 1}$$ (2.6)

and

$$\mbox{$n$\space is prime}$$ (2.7)

to

$$\mbox{$n$\space is divisible only by itself and 1.}$$ (2.8)

The general form of this inference is known a modus ponens. Modus ponens permits us to derive from a pair of statements if p then q and p the conclusion that q.

There are five fundamental ways of connecting propositions; as it is often put in endeavors like the one we have launched here, there are five truth-functional connectives. Where p and q stand for propositions, the following list displays this quintet.

$$\begin{array}{\vert l\vert c\vert l\vert} \hline \mbox{{\bf ... ...rightarrow q & p \mbox{ if and only if }q\\ \hline \end{array}$$