Supplement to the Classical Algebra text

Chapter 0: Logic and Proofs

Mathematics makes precise use of language in stating and proving its results. We use the English language to express our ideas and arguments, though we give some common English words a more precise meaning so as to make them unambiguous. Good mathematical writing consists of complete sentences, allowing for the fact that symbols stand for words. For example, `A = B.' is a sentence in which the subject is A, the verb is `equals' and the object is B.

In mathematics, we tend to use more complicated and compound expressions than we do in everyday language, so this chapter explains some methods for dealing with these expressions. We also introduce the more common types of mathematical reasoning we use in proofs.

0.1    PROPOSITIONAL LOGIC

Logic is the study of correct reasoning. The rules of logic give precise meaning to mathematical statements and allow us to make correct arguments about these statements.

0.1.1 Definition

In mathematics, a statement, or proposition, is a sentence which is either TRUE or FALSE.

For example,

are statements, since they are sentences which are either TRUE or FALSE, though you most probably do not know the truth value of the last statement.

However the following sentences are not statements.

Questions are never statements. If we changed the last sentence to "It is Friday today." it would be a statement.

Propositional logic is that part of logic that deals with combining statements using connectives such as AND, OR, NOT, or implies. We use these connectives in everyday English, but in mathematics and computer science we tend to use them in more complex combinations. We (and the computers) need to know precisely what these combinations mean. For example, the Principle of Mathematical Induction says that: If P(1) is true and P(k+1) is true whenever P(k) is true, then P(n) is true for all positive integers n.

We can always combine any two statements using AND to form a third statement. For example

If P denotes the statement `Ottawa is the capital of Canada.' and Q denotes the statement `New York is the capital of the United States.' then the above statement will be denoted by P AND Q.

0.1.2 Definition

P AND Q is called the conjunction of P and Q. The statement P AND Q will be TRUE if P is TRUE and Q is TRUE, but will be FALSE otherwise.

P OR Q is called the disjunction of P and Q. The statement P OR Q will be TRUE if either P is TRUE or Q is TRUE, or both are TRUE.

We can define these relationships in the following truth tables, in which T stands for TRUE and F stands for FALSE.
P Q P AND Q
T
T
F
F 		T
F
T
F 		T
F
F
F
P Q P OR Q
T
T
F
F 		T
F
T
F 		T
F
F
F

In everyday English, the word `or' can be used in two different ways. Consider the meaning of `or' in the following two sentences.

Mathematics always uses the `inclusive OR' which means that P OR Q is true even if both P and Q are true. This is the use of `or' in the first sentence; you can still take the course if you have both algebra and trigonometry. However in the second sentence, `or' is used in an exclusive way; you are not expected to request tea and coffee.

Every statement has a negation. For example, if P is the statement `3 + 2 = 6.' then its negation is `It is not true that 3 + 2 = 6.' or more simply `3 + 2 not= 6.' In mathematics, we are always using conditional statements such as `If x > 2 then x 2 > 4.' or biconditional statements such as `x y = 0 if and only if x = 0 or y = 0.'

0.1.3 Definition

P NOT P
T
F 		F
T
P Q P => Q
T
T
F
F 		T
F
T
F 		T
F
T
T
P Q P <=> Q
T
T
F
F 		T
F
T
F 		T
F
F
T

The negation of the statement P is denoted by NOT P.

If P and Q are two statements, the conditional statement `If P then Q' is denoted by P => Q and is defined by the truth table above. This is sometimes expressed as `P implies Q' or `Q whenever P.'

The biconditional statement `P if and only if Q' is denoted by P <=> Q. The expression "if and only if" is used so often in mathematics that it is often abbreviated as "iff". If P <=> Q is TRUE, then P and Q have the same truth values and we say that P and Q are equivalent statements.

The conditional is an extension of everyday English usage, but it has some unusual consequences because P => Q is always true if P is false. For example, `If 5 > 7 then 2 + 2 = 3.' is a true statement.

0.1.4 Example

Show that the statement P <=> Q has the same truth table as the statement (P => Q) AND (Q => P).

This example shows that `P if and only if Q' has the same meaning as the statement `(If P then Q) and (if Q then P).'

Solution.
P Q P => Q Q => P (P => Q) AND (Q => P) P <=> Q
T
T
F
F 		T
F
T
F 		T
F
T
T 		T
T
F
T 		T
F
F
T 		T
F
F
T
The last two columns are the same, so the two statements have the same truth table.

The square box symbol denotes the end of a proof or solution.

0.1.5 Example

Show that the statement NOT (P AND Q) has the same truth table as the statement (NOT P) OR (NOT Q).

Solution.
P Q P AND Q NOT (P AND Q)
T
T
F
F 		T
F
T
F 		T
F
F
F 		F
T
T
T
P Q NOT P NOT Q (NOT P) OR (NOT Q)
T
T
F
F 		T
F
T
F 		F
F
T
T 		F
T
F
T 		F
T
T
T
The final two columns are the same, so the two statements have the same truth table.

0.1.6 Example

Show that the statement P => Q is equivalent to the statement Q OR NOT P.

Solution.
P Q P => Q NOT P Q OR NOT P
T
T
F
F 		T
F
T
F 		T
F
T
T 		F
F
T
T 		T
F
T
T
Since the statements P => Q and Q OR NOT P have the same truth tables, they are equivalent.

Alternative Notations for Connectives
Connective Propositional Logic C and Java syntax
AND
OR
NOT
=>
<=> 		wedge
V
¬  or  ~
->
<-> 		&&
||
!

© 1998 William J. Gilbert and Scott A. Vanstone, University of Waterloo

Supplement Contents   |   Next Section