Mathematics typically involves combining true (or hypothetically true) statements in various ways to produce (or prove) new true statements. We begin by clarifying some of these fundamental ideas.
By a sentence we mean a statement that has a definite truth value, true (T) or false (F)—for example,
"In 1492 Columbus sailed the ocean blue.'' (T)
"Napoleon won the battle of Waterloo.'' (F)
More generally, by a formula we mean a statement, possibly involving some variables, which is either true or false whenever we assign particular values to each of the variables. We will use capital letters to designate formulas. If the truth of a formula depends on the values of, say, $x$, $y$ and $z$, we will use notation like $P(x,y,z)$ to denote the formula.
Example 1.1.1 If $P(x,y)$ is "$x^2+y = 12$'', then $P(2,8)$ and $P(3,3)$ are true, while $P(1,4)$ and $P(0,6)$ are false. If $Q(x,y,z)$ is "$x+y< z$'', then $Q(1,2,4)$ is true and $Q(2,3,4)$ is false. $\square$
Whether a sentence is true or false usually depends on what we are talking about—exactly the same sentence may be true or false depending on the context; for example, the formula $x|y$ means `$x$ divides $y$'. That is, $x|y$ if there is some $z$ so that $y=x\cdot z$. Now, is it true that $3|2$? It depends: if we are talking about integers, the answer is no; if we are talking about rational numbers, the answer is yes, because $2=3\cdot(2/3)$. (Of course, if $x\not=0$ and $y$ are any rational numbers then $x|y$, so that it is not a very useful notion. In normal usage, the appearance of the formula "$x|y$'' implies that $x$ and $y$ are integers.)
The universe of discourse for a particular branch of mathematics is a set that contains everything of interest for that subject. When we are studying mathematical formulas like `$x$ divides $y$' the variables are assumed to take values in whatever universe of discourse is appropriate for the particular subject. The universe of discourse usually is clear from the discussion, but occasionally we will need to identify it explicitly for clarity. The universe of discourse is usually denoted by $U$.
Complicated sentences and formulas are put together from simpler ones, using a small number of logical operations. Just a handful of these operations will let us say everything we need to say in mathematics.
If $P$ is a formula, then "not $P$'' is another formula, which we write symbolically as $\lnot P$. Of course, $\lnot P$ is false if $P$ is true and vice versa—for example,
"6 is not a prime number'' or "It is not true that 6 is prime'' or "$\lnot(\hbox{6 is prime})$'' (T)
"Ronald Reagan was not a president.'' (F)
Suppose that $P$ and $Q$ are formulas. Then "$P$ and $Q$'' is a formula written symbolically as $P\land Q$, called the conjunction of $P$ and $Q$. For $P\land Q$ to be true both $P$ and $Q$ must be true, otherwise it is false—for example,
"$5=6$ and $7=8$.'' (F)
"Seattle is in Washington and Boise is in Idaho.'' (T)
"Tolstoy was Russian and Dickens was French.'' (F)
If $P$ and $Q$ are formulas, then the formula "$P$ or $Q$'' is written symbolically as $P\lor Q$, called the disjunction of $P$ and $Q$. It is important to note that this is an inclusive or, that is, "either or both''. So if $P$, $Q$ or both $P$ and $Q$ are true, so is $P\lor Q$. The only way $P\lor Q$ can be false is if both $P$ and $Q$ are false—for example,
"Washington is in Canada or London is in England.'' (T)
"$5< 7$ or $8< 10$.'' (T)
"Lenin was Spanish or Ghandi was Italian.'' (F)
If $P$ and $Q$ are formulas, then "if $P$ then $Q$'' or "$P$ implies $Q$'' is written $P\implies Q$, using the conditional symbol, $\implies$. It is not obvious (at least, not to most people) under what circumstances $P\implies Q$ should be true. In part this is because "if… then'' is used in more than one way in ordinary English, yet we need to fix a rule that will let us know precisely when $P\implies Q$ is true. Certainly, if $P$ is true and $Q$ is false, $P$ cannot imply $Q$, so $P\implies Q$ is false in this case. To help us with the other cases, consider the following statement:
"If $x$ is less than 2 then $x$ is less than 4.''
This statement should be true regardless of the value of $x$ (assuming that the universe of discourse is something familiar, like the integers). If $x$ is 1, it evaluates to $\rm T\implies T$, if $x$ is 3, it becomes $\rm F\implies T$, and if $x$ is 5, it becomes $\rm F\implies F$. So it appears that $P\implies Q$ is true unless $P$ is true and $Q$ is false. This is the rule that we adopt.
Finally, the biconditional, written $\Leftrightarrow$, corresponds to the phrase "if and only if'' or "iff'' for short. So $P \Leftrightarrow Q$ is true when both $P$ and $Q$ have the same truth value, otherwise it is false.
Example 1.1.2 Suppose $P(x,y)$ is "$x+y=2$'' and $Q(x,y)$ is "$xy>1$.'' Then when $x=1$ and $y=1$, $\lnot P(x,y)$, $P(x,y)\land Q(x,y)$, $P(x,y)\lor Q(x,y)$, $P(x,y)\implies Q(x,y)$ and $P(x,y)\Leftrightarrow Q(x,y)$ have truth values F, F, T, F, F, respectively, and when $x=2$ and $y=3$ they have truth values T, F, T, T, F, respectively. $\square$
Using the operations $\lnot$, $\land$, $\lor$, $\implies$, $\Leftrightarrow$, we can construct compound expressions such as $$ (P\land (\lnot Q))\implies ((\lnot R)\lor ((\lnot P)\land Q)). $$ As this example illustrates, it is sometimes necessary to include many parentheses to make the grouping of terms in a formula clear. Just as in algebra, where multiplication takes precedence over addition, we can eliminate some parentheses by agreeing on a particular order in which logical operations are performed. We will apply the operations in this order, from first to last: $\lnot$, $\land$, $\lor$, $\implies$ and $\Leftrightarrow$. So $$A\implies B\lor C\land \lnot D $$ is short for $$A\implies (B\lor (C\land (\lnot D))). $$ Just as in algebra, it often is wise to include some extra parentheses to make certain the intended meaning is clear. Much of the information we have discussed can be summarized in truth tables. For example, the truth table for $\lnot P$ is:
| $P$ | $\lnot P$ |
|---|---|
| T | F |
| F | T |
This table has two rows because there are only two possibilities for the truth value of $P$. The other logical operations use two variables, so they require 4 rows in their truth tables.
| $P$ | $Q$ | $P\land Q$ | $P \lor Q$ | $P\Rightarrow Q$ | $P\Leftrightarrow Q$ |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| F | T | F | T | T | F |
| T | F | F | T | F | F |
| F | F | F | F | T | T |
Any compound expression has a truth table. If there are $n$ simple (that is, not compound) formulas in the expression there will be $2^n$ rows in the table, because there are this many different ways to assign T's and F's to the $n$ simple formulas in the compound expression. The truth table for $(P\land Q)\lor \lnot R$ is
| $P$ | $Q$ | $R$ | $P \land Q$ | $\lnot R$ | $(P \land Q)\lor\lnot R$ |
|---|---|---|---|---|---|
| T | T | T | T | F | T |
| F | T | T | F | F | F |
| T | F | T | F | F | F |
| F | F | T | F | F | F |
| T | T | F | T | T | T |
| F | T | F | F | T | T |
| T | F | F | F | T | T |
| F | F | F | F | T | T |
Observe how the inclusion of intermediate steps makes the table easier to calculate and read.
A tautology is a logical expression that always evaluates to T, that is, the last column of its truth table consists of nothing but T's. A tautology is sometimes said to be valid; although "valid'' is used in other contexts as well, this should cause no confusion. For example, $(P\land Q)\lor P\Leftrightarrow P$ is a tautology, since its truth table is:
| $P$ | $Q$ | $P\land Q$ | $(P\land Q)\lor P$ | $(P\land Q)\lor P\Leftrightarrow P$ |
|---|---|---|---|---|
| T | T | T | T | T |
| F | T | F | F | T |
| T | F | F | T | T |
| F | F | F | F | T |
We list a few important tautologies in the following theorem.
Theorem 1.1.3 The following are valid:
a) $P\Leftrightarrow \lnot\lnot P$
b) $P\lor Q\Leftrightarrow Q\lor P$
c) $P\land Q\Leftrightarrow Q\land P$
d) $(P\land Q)\land R\Leftrightarrow P\land(Q\land R)$
e) $(P\lor Q)\lor R\Leftrightarrow P\lor(Q\lor R)$
f) $P\land (Q\lor R)\Leftrightarrow (P\land Q)\lor (P\land R)$
g) $P\lor (Q\land R)\Leftrightarrow (P\lor Q)\land (P\lor R)$
h) $(P\implies Q)\Leftrightarrow (\lnot P\lor Q)$
i) $P\implies (P\lor Q)$
j) $P\land Q\implies Q$
k) $(P\Leftrightarrow Q)\Leftrightarrow ((P\implies Q)\land (Q\implies P))$
l) $(P\implies Q)\Leftrightarrow (\lnot Q\implies \lnot P)$
Proof. The proofs are left as exercises. $\qed$
Observe that (b) and (c) are commutative laws, (d) and (e) are associative laws and (f) and (g) say that $\land$ and $\lor$ distribute over each other. This suggests that there is a form of algebra for logical expressions similar to the algebra for numerical expressions. This subject is called Boolean Algebra, and has many uses, particularly in computer science.
If two formulas always take on the same truth value no matter what elements from the universe of discourse we substitute for the various variables, then we say they are equivalent. The value of equivalent formulas is that they say the same thing. It is always a valid step in a proof to replace some formula by an equivalent one. In addition, many tautologies contain important ideas for constructing proofs. For example, (k) says that if you wish to show that $P\Leftrightarrow Q$, it is possible (and often advisable) to break the proof into two parts, one proving the implication $P\implies Q$ and the second proving the converse, $Q\implies P$.
In reading through theorem 1.1.3 you may have noticed that $\land$ and $\lor$ satisfy many similar properties. These are called "dual'' notions—for any property of one, there is a nearly identical property that the other satisfies, with the instances of the two operations interchanged. This often means that when we prove a result involving one notion, we get the corresponding result for its dual with no additional work.
George Boole. Boole (1815–1864) had only a common school education, though he learned Greek and Latin on his own. He began his career as an elementary school teacher, but decided that he needed to know more about mathematics, so he began studying mathematics, as well as the languages he needed to read contemporary literature in mathematics. In 1847, he published a short book, The Mathematical Analysis of Logic, which may fairly be said to have founded the study of mathematical logic. The key contribution of the work was in redefining `mathematics' to mean not simply the `study of number and magnitude,' but the study of symbols and their manipulation according to certain rules. The importance of this level of abstraction for the future of mathematics would be difficult to overstate. Probably on the strength of this work, he moved into a position at Queens College in Cork.
In Investigation of the Laws of Thought, published in 1854, Boole established a real formal logic, developing what today is called Boolean Algebra, or sometimes the algebra of sets. He used the symbols for addition and multiplication as operators, but in a wholly abstract sense. Today these symbols are still sometimes used in Boolean algebra, though the symbols `$\land$' and `$\lor$', and `$\cap$' and `$\cup$', are also used. Boole applied algebraic manipulation to the process of reasoning. Here's a simple example of the sort of manipulation he did: The equation $xy=x$ (which today might be written $x\land y = x$ or $x\cap y = x$) means that `all things that satisfy $x$ satisfy $y$,' or in our terms, $x\implies y$. If also $yz=y$ (that is, $y\implies z$) then substituting $y=yz$ into $xy=x$ gives $x(yz)=x$ or $(xy)z=x$. Replacing $xy$ by $x$, we get $xz=x$, or $x\implies z$. This simple example of logical reasoning is used over and over in mathematics.
In 1859, Boole wrote Treatise on Differential Equations, in which he introduced the algebra of differential operators. Using $D$ to stand for `the derivative of,' the differential equation $ay''+by'+cy=0$ may be written as $aD^2(y)+bD(y)+cy=0$, or as $(aD^2+bD+c)y=0$. Remarkably, the solution to $aD^2+bD+c=0$, treating $D$ as a number, provides information about the solutions to the differential equation.
The information here is taken from A History of Mathematics, by Carl B. Boyer, New York: John Wiley and Sons, 1968. For more information, see Lectures on Ten British Mathematicians, by Alexander Macfarlane, New York: John Wiley & Sons, 1916.
Exercises 1.1
Ex 1.1.1 Construct truth tables for the following logical expressions:
a) $(P\land Q)\lor \lnot P$
b) $P\implies (Q\land P)$
c) $(P\land Q)\Leftrightarrow (P\lor \lnot R)$
d) $\lnot P\implies \lnot(Q\lor R)$
Ex 1.1.2 Verify the tautologies in Theorem 1.1.3.
Ex 1.1.3 Suppose $P(x,y)$ is the formula "$x+y=4$'' and $Q(x,y)$ is the formula "$x< y$''. Find the truth values for the formulas
$P(x,y)\land Q(x,y)$, $\lnot P(x,y)\lor Q(x,y)$,
$P(x,y)\implies \lnot Q(x,y)$, $\lnot(P(x,y)\Leftrightarrow Q(x,y))$,
using the values:
| a) $x=1, y=3$ | c) $x=1, y=2$ |
| b) $x=3, y=1$ | d) $x=2, y=1$ |
Ex 1.1.4
a) Find truth tables for $$ P\land (\lnot Q)\land R, \quad\quad (\lnot P)\land Q\land (\lnot R) $$
b) Use these to find a truth table for $$ (P\land (\lnot Q)\land R)\lor ((\lnot P)\land Q\land (\lnot R)) $$
c) Use the method suggested by parts (a) and (b) to find a formula with the following truth table.
| $P$ | $Q$ | $R$ | ??? |
|---|---|---|---|
| T | T | T | T |
| F | T | T | F |
| T | F | T | F |
| F | F | T | F |
| T | T | F | T |
| F | T | F | T |
| T | F | F | F |
| F | F | F | F |
d) Use the method suggested by parts (a)-(c) to explain why any list of $2^n$ T's and F's is the final column of the truth table for some formula with $n$ letters.
Ex 1.1.5 If $P_1, P_2,\ldots, P_n$ is a list of $n$ formulas, at most how many compound formulas using this list can be constructed, no two of which are equivalent?