Beginning Rigorous Mathematics/Basic Logic

In the previous chapter we made clear what a logical statement is. In this chapter we will define and derive rules for working with compound logical statements. The symbols used to combining statements are called "logical operators".

In this section the symbols P and Q denote any logical statements.

Logical operators and Truth Tables

Truth tables are used in two ways. Firstly to define exactly what a certain compounded statement means, and secondly to derive the properties of more complicated compounded statements. Truth tables exhaust all possible combinations of the truth of falsehood of the constituent statements in the compounded statement to yield exactly under what combinations of truth and falsehood of the constituent statements, the compound statement is true or false.

Definitions

Not, Negation

We define the symbol "$\lnot$" to mean "not". If P is a statement then $\lnot P$ is also a statement. It inverts the truth or falsehood of logical statements. In other words, if the statement P is true, then the statement $\lnot P$ is false and if P is false, then $\lnot P$ is true. We call $\lnot P$ the negation of P.

We rigorously define the symbol "$\lnot$" by the following truth table

P	$\neg P$
T	F
F	T

Even though "not" simplest logical operator, the negation of statements is important when trying to prove that certain objects have or do not have certain properties. It makes the skill of being able to correctly negate statements an important one.

And, Conjunction

We define the symbol "$\land$" to mean "and". If P and Q are statements then $P\land Q$ is also a statement, is called the conjunction of P and Q, and it reads "P AND Q". The compound statement $P\land Q$ is true only when both statements P and Q are true.

We rigorously define the symbol "$\land$" by the following truth table

P	Q	$P\land Q$
T	T	T
T	F	F
F	T	F
F	F	F

Or, Disjunction

We define the symbol "$\lor$" to mean "or". If P and Q are statements then $P\lor Q$ is also a statement, is called the disjunction of P and Q, and it reads "P OR Q". The compound statement $P\lor Q$ is true only when either P or Q or both statements P and Q are true.

We rigorously define the symbol "$\lor$" by the following truth table

P	Q	$P\lor Q$
T	T	T
T	F	T
F	T	T
F	F	F

If ... then, Implication

We define the symbol "$\Rightarrow$" to mean "implies". If P and Q are statements then $P\Rightarrow Q$ is also a statement and it reads "P IMPLIES Q" or also "IF P THEN Q". The compound statement $P\Rightarrow Q$ is false only when P is true and Q is false. We call P the hypothesis and Q the Conclusion of the implication.

We rigorously define the symbol "$\Rightarrow$" by the following truth table

P	Q	$P\Rightarrow Q$
T	T	T
T	F	F
F	T	T
F	F	T

We call the statement "$Q\Rightarrow P$" the converse of "$P\Rightarrow Q$".

Logical implication plays an important role since most theorems take on the form of an implication.

If and only if, Equivalence

We define the symbol "$\Leftrightarrow$" to mean "if and only if". If P and Q are statements then $P\Leftrightarrow Q$ is also a statement and it reads "P is true if and only if Q is true".

We rigorously define the symbol "$\Leftrightarrow$" by the following truth table

P	Q	$P\Leftrightarrow Q$
T	T	T
T	F	F
F	T	F
F	F	T

Basic results

In this section we will prove some basic equivalences for compounded logical statements. We say that two (compound) statements are logically equivalent when written in the same truth table, their columns are identical. Knowing how to write statements into logically equivalent statements is very useful in the sense that a statement might be difficult to prove, yet a logically equivalent statement might be easier to prove.

Lemma 1 (DeMorgan's law, part 1)

$\lnot(P\land Q)$ is logically equivalent to $\lnot P \lor \lnot Q$

Proof

P	Q	$P\land Q$	$\lnot(P\land Q)$	$\lnot P$	$\lnot Q$	$\lnot P \lor \lnot Q$
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

Since the columns for the compound statements are identical, they are logically equivalent. QED

Proving the following theorems are left as exercises.

Lemma 2 (DeMorgan's law, part 2)

$\lnot(P\lor Q)$ is logically equivalent to $\lnot P \land \lnot Q$

Lemma 3

$P\Leftrightarrow Q$ is logically equivalent to $(P\Rightarrow Q)\land(Q\Rightarrow P)$

Lemma 4

$\lnot(P\Rightarrow Q)$ is logically equivalent to $P\land(\lnot Q)$

Lemma 5

$P\Rightarrow Q$ is logically equivalent to $\lnot P\lor Q$

Lemma 6 (Contrapositive)

$P\Rightarrow Q$ is logically equivalent to $\lnot Q \Rightarrow \lnot P$

Lemma 7

$P\Leftrightarrow Q$ is logically equivalent to $\lnot P \Leftrightarrow \lnot Q$

Predicates and Quantifiers

A predicate is defined to be a function mapping any set into the set {T,F} where the symbols T and F mean 'true' and 'false' respectively. A predicate can be thought of a collection of statements, one for each element of the domain of the predicate.

For example, we may define the predicate $P:\mathbb{Z}\to \{T,F\}$ by P(x): = "x is an even integer". Instead of writing "P(5) = F" and "P(16) = T" we will say and write "P(5) is false" and "P(16) is true".

If $P:A\to \{T,F\}$ is a predicate, then the predicate $\lnot P:A\to \{T,F\}$ defined to be such that $\lnot P(x)$ is true exactly when P(x) is false and $\lnot P(x)$ is false exactly when P(x) is true, is called the negation of P.

There are two quantifiers denoted by the symbols "$\forall$" and "$\exists$" which read "for all" and "there exists" respectively.

Let $P:A\to \{T,F\}$ be a predicate and let B be any subset of A (subsets are discussed in the next section). Then $\forall x\in B:P(x)$ which reads "For all elements x contained in B, P(x) is true." is a statement, and is defined to be true exactly when P(x) is true for every element x contained in B.

Similarly, $\exists x\in B:P(x)$ which reads "There exists an element x contained in B such that P(x) is true." is a statement, and is defined to be true exactly when P(x) is true for at least one element x contained in B.

We define the negation of statements involving quantifiers as follows $\lnot(\forall x\in B:P(x)):=\exists x\in B:\lnot P(x)$ and $\lnot(\exists x\in B:P(x)):=\forall x\in B:\lnot P(x)$

Logical rules of inferrence

Proving the truth of statements require knowledge of standard valid logical rules of inference, the most important of which are:

Adjunction

If P and Q are both true then so is $P\land Q$

Simplification

If $P\land Q$ is true then P is true.

If $P\land Q$ is true then Q is true.

Addition

If P is true then $P \lor Q$ is true (regardless of the truth or falsehood of Q).

Disjunctive syllogism

If $P \lor Q$ is true, and P is false then Q is true.

If $P \lor Q$ is true, and Q is false then P is true.

Modus Ponens

If $P \Rightarrow Q$ is true, and P is true, then Q is true.

Modus Tollens

If $P \Rightarrow Q$ is true, and Q is false, then P is false.

In a mathematical proof, these rules are usually not explicitly mentioned as they have become second nature to mature students and authors of mathematics. We will be very explicit and pedantic in the proofs of some results in the following chapters, so will mention them.