A Gentle Introduction to the Art of Mathematics

2.1 Propositions and logical connectives

In every branch of mathematics, there are special atomic notion that defy precise definition. In geometry, for example, the atomic notions are points, lines and their incidence. Euclid defines a point as “that which has no part” — people can argue (and have argued) incessantly over what exactly is meant by this. Is it essentially saying that anything without volume, area or length of some sort is a point? In modern times it has been recognized that any formal system of argumentation has to have such elemental, undefined, concepts — and that Euclid’s apparent lapse in precision comes from an attempt to hide this basic fact. The notion of “point” can’t really be defined. All we can do is point (no joke intended) at a variety of points and hope that our audience will absorb the same concept of point that we hold via the process of induction¹⁷.

The atomic concepts in set theory are “set”, “element” and “membership”. The atomic concepts in logic are “true”, “false”, “sentence” and “statement”.

Regarding true and false, we hope there is no uncertainty as to their meanings. Sentence also has a well-understood meaning that most will agree on — a syntactically correct ordered collection of words such as “Johnny was a football player.” or “Red is a colour.” or “This is a sentence which does not refer to itself.”

A statement is a sentence which is either true or false. In other words, a statement is a sentence whose truth value is definite, in more other words, it is always possible to decide — one way or the other — whether a statement is true or false.¹⁸ The first example of a sentence given above (“Johnny was a football player”) is not a statement — the problem is that it is ambiguous unless we know who Johnny is. If it had said “Johnny Unitas was a football player.” then it would have been a statement. If it had said “Johnny Appleseed was a football player.” it would also have been a statement, just not a true one.

Ambiguity is only one reason that a sentence may not be a statement. As we consider more complex sentences, it may be the case that the truth value of a given sentence simply cannot be decided. One of the most celebrated mathematical results of the 20th century is Kurt Gödel’s “Incompleteness Theorem.” An important aspect of this theory is the proof that in any axiomatic system of mathematical thought there must be undecidable sentences — statements which can neither be proved nor disproved from the axioms¹⁹. Simple sentences (e.g. those of the form subject-verb-object) have little chance of being undecidable for this reason, so we will next look at ways of building more complex sentences from simple components.

Let’s start with an example. Suppose I come up to you in some windowless room and make the statement: “The sun is shining but it’s raining!” You decide to investigate my claim and determine its veracity. Upon reaching a room that has a view of the exterior, there are four possible combinations of sunniness and/or precipitation that you may find. That is, the atomic propositions “The sun is shining” and “It is raining” can each be true or false independently of one another. In the following table, we introduce a convention used throughout the remainder of this book — that true is indicated with 1 and false is indicated with 0.

The sun is shining	It is raining
1	1
1	0
0	1
0	0

Each row of the above table represents a possible state of the outside world. Suppose you observe the conditions given in the last row, namely that it is neither sunny, nor is it raining — you would certainly conclude that I am not to be trusted. That is, my statement, the compounding of “The sun is shining” and “It is raining” (with the word “but” in between as a connector) is false. If you think about it a bit, you’ll agree that this so-called compound sentence is true only in the case when both of its component pieces are true. This underscores an amusing linguistic point: “but” and “and” have exactly the same meaning! More precisely, they denote the same thing, they have subtly different connotations however — “but” indicates that both of the statements it connects are true and that the speaker is surprised by this state of affairs.

In mathematics we distinguish two main connectives for hooking up simple sentences into compound ones. The conjunction of two sentences is the compound sentence made by sticking the word “and” between them. The disjunction of two sentences is formed by placing an “or” between them. Conjunctions are true only when both components are true. Disjunctions are false only when both components are false.

As usual, mathematicians have developed an incredibly terse, compact notation for these ideas.²⁰ First, we represent an entire sentence by a single letter — traditionally, a capital letter. This is called a propositional variable (or a sentential variable). For example, following the example above, we could denote the sentence “The sun is shining” by the letter $S$. Similarly, we could make the assignment $R =$ “It is raining.” The conjunction and disjunction of these sentences can then be represented using the symbols $S \land R$ and $S \lor R$, respectively. As a mnemonic, note that the connective in $S \land R$ looks very much like the capital letter A (as in And).

To display, very succinctly, the effect of these two connectives, we can use so-called truth tables. In a truth table, we list all possible truth values of the propositional variables and then enumerate the truth values of some compound sentence. For the conjunction and disjunction connectors we have (respectively): \[\begin{array}{c|c||c} A & B & A \land B \\ \hline 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{array}\] and \[\begin{array}{c|c||c} A & B & A \lor B \\ \hline 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{array}\]

In addition to these connectors, we need a modifier (called negation) that acts on individual sentences. The negation of a sentence $A$ is denoted by ${\lnot}A$, and its truth value is exactly the opposite of $A$’s truth value. The negation of a sentence is also known as the denial of a sentence. A truth table for the negation operator is somewhat trivial but we include it here for completeness. \[\begin{array}{c||c} A & \lnot A \\ \hline 1 & 0 \\ 0 & 1 \end{array}\]

These three simple connectors are sufficient to create extraordinarily complex sentences out of basic components. The way these pieces interrelate is a bit reminiscent of algebra. In fact, the study of these logical operators (or any operators that act like them) is called Boolean algebra²¹. There are distinct differences between Boolean and ordinary algebra, however. In regular algebra, we have the binary connectors $+$ (plus) and $\cdot$ (times), and the unary negation operator $-$; these are certainly analogous to $\land$, $\lor$, and $\lnot$, but there are certain consequences of the fact that multiplication is effectively repeated addition that simply don’t hold for the Boolean operators. For example, there is a well-defined precedence between $\cdot$ and $+$. In parsing the expression $4 \cdot 5 + 3$ we all know that the multiplication is to be done first. There is no such rule governing order of operations between $\land$ and $\lor$. So an expression like $A \land B \lor C$ is simply ambiguous — it must have parentheses inserted in order to show the order, either $(A \land B) \lor C$ or $A \land (B \lor C)$. Another distinction between ordinary and Boolean algebra is exponentiation. If there were exponents in Boolean algebra, we’d need two different kinds — one for repeated conjunction and another for repeated disjunction.

Exercise 2.1 Why is it that there is no such thing as exponentiation in the algebra of logic?

While there are many differences between Boolean algebra and the usual, garden-variety algebra, there are also many similarities. For instance, the associative, commutative and distributive laws of algebra all have versions that work in the Boolean case.

2.1.1 Digital logic circuit diagrams

A very handy way of visualizing Boolean expressions is given by digital logic circuit diagrams. To discuss these diagrams we must make a brief digression into electronics. One of the most basic components inside an electronic device is a transistor, this is a component that acts like a switch for electricity, but the switch itself is controlled by electricity. In Figure 2.1 we see the usual schematic representation of a transistor. If voltage is applied to the wire labeled z, the transistor becomes conductive, and current may flow from x to y.

Figure 2.1: A schematic representation of a transistor.

Suppose that two transistors are connected as in Figure 2.2 (this is called a series connection). In order for current to flow from x to y we must have voltage applied to both the wires labeled z and w. In other words, this circuit effectively creates the AND operation — assuming voltage is always applied to x, if z AND w are energized then the output at y will be energized.

Figure 2.2: The connection of two transistors in series provides an implementation of the AND operator.

When two transistors are connected in parallel (this is illustrated in Figure 2.3) current can flow from x to y when either (or both) of the wires at z and w have voltage applied. This brings up a point which is confusing for some: in common speech the use of the word “or” often has the sense known as exclusive or (a.k.a. XOR), when we say “X OR Y” we mean “Either X or Y, but not both.” In electronics and mathematics, or always has the non-exclusive (better known as inclusive) sense.

Figure 2.3: The connection of two transistors in parallel provides an implementation of the OR operator.

As a sort of graphical shorthand, electronics engineers use the symbols shown in Figure 2.4 to indicate AND-gates, OR-gates, and NOT-gates (better known as negators).

Figure 2.4: Symbols for AND-gates, OR-gates, and NOT-gates.

An AND-gate has two transistors inside it that are wired in series — if both the inputs are energized, the output will be too. An OR-gate has two transistors in parallel inside it. NOT-gates involve magic — when their input is not on, their output is and vice versa.

Using this graphical “language” one can make schematic representations of logical expressions. Some find that tracing such diagrams makes understanding the structure of a Boolean expression easier. For example, in Figure 2.5 we illustrate two of the possible ways that the conjunction of four proprositional variables can be parenthesized. In fact, when a multitude of propositions are joined by the same connective, the way in which the expression is parenthesized is unimportant, thus one often sees a further shorthand — gates with more than two inputs.

Figure 2.5: Two of the possible ways to parenthesize the conjunction of four statement variables — expressed as digital logic circuits.

A common task for an electronics designer is to come up with a digital logic circuit having a prescribed input/output table. Note that an input/output table for a logic circuit is entirely analogous with a truth table for a compound sentence in logic.

Suppose that we wanted to design a circuit that would have the following input/output table. \[\begin{array}{c|c|c|c} x & y & z & \text{out} \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array}\]

A systematic method for accomplishing such a design task involves a notion called disjunctive normal form. A Boolean expression is in disjunctive normal form if it consists of the disjunction of one or more statements, each of which consists entirely of conjunctions of predicate variables and/or their negations. In other words, the or of a bunch of ands. In terms of digital logic circuits, the ands we’re talking about are called recognizers. For example, the 3-input and-gates shown in Figure 2.6 recognize the input states in the 4th, 7th and 8th rows of the input/output table above. (These are the rows where the output is supposed to be 1.)

Figure 2.6: Three recognizers.

Figure 2.7 illustrates how to create a circuit whose input/output table is as above using these recognizers.

$A digital logic circuit built using disjunctive normal form. The output of this circuit is $({\lnot}x \land y \land z) \lor (x \land y \land {\lnot}z) \lor (x \land y \land z)$.$

Figure 2.7: A digital logic circuit built using disjunctive normal form. The output of this circuit is $({\lnot}x \land y \land z) \lor (x \land y \land {\lnot}z) \lor (x \land y \land z)$.

2.1.2 Exercises

Design a digital logic circuit (using AND-, OR-, and NOT-gates) that implements an exclusive or.
Consider the sentence “This is a sentence which does not refer to itself.” which was given in the beginning of this chapter as an example. Is this sentence a statement? If so, what is its truth value?
Consider the sentence “This sentence is false.” Is this sentence a statement?
Complete truth tables for each of the sentences $(A \land B) \lor C$ and $A \land (B \lor C)$. Does it seem that these sentences have the same logical content?
There are two other logical connectives that are used somewhat less commonly than $\lor$ and $\land$. These are the Scheffer stroke and the Peirce arrow — written $\vert$ and $\downarrow$, respectively — they are also known as NAND and NOR.

The truth tables for these connectives are: \[\begin{array}{c|c||c} A & B & A \,\vert\, B \\ \hline 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array}\] and \[\begin{array}{c|c||c} A & B & A \downarrow B \\ \hline 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\]

Find an expression for $(A\, \land {\lnot}B) \lor C$ using only these new connectives (as well as negation and the variable symbols themselves).
The famous logician Raymond Smullyan devised a family of logical puzzles around a fictitious place he called “the Island of Knights and Knaves.” The inhabitants of the island are either knaves, who always make false statements, or knights, who always make truthful statements.

In the most famous knight/knave puzzle, you are in a room which has only two exits. One leads to certain death and the other to freedom. There are two individuals in the room, and you know that one of them is a knight and the other is a knave, but you don’t know which. Your challenge is to determine the door which leads to freedom by asking a single question.

inference of a generalized conclusion from particular instances — compare DEDUCTION↩
Although, as a practical matter it may be almost impossibly difficult to do so! For instance it is certainly either true or false that I ate eggs for breakfast on my 21st birthday — but I don’t remember, and short of building a time machine, I don’t know how you could find out.↩
There are trivial systems that are complete, but if a system is sufficiently complicated that it contains “interesting” statements it can’t be complete.↩
One begins to suspect that mathematicians form an unusually lazy sub-species of humanity.↩
In honour of George Boole, whose 1854 book An investigation into the Laws of Thought inaugurated the subject.↩