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.

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.

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.

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?