Logical Operators - Mathematical Sentences

Mathematical Writing - Vivaldi Franco 2014

Logical Operators
Mathematical Sentences

The following sentence is TRUE:

$$\begin{aligned} \textit{The\,integer}\,2^{57885161}-1\, \textit{is\, prime.} \end{aligned}$$

(4.7)

The proof requires a sophisticated theory and a lot of computer time.1 However, it is not difficult to see that this expression is decomposable into finitely many relational expressions. Indeed the primality of $$p=2^{\,57885161}-1$$ could in principle be established by verifying that $$p$$ is not divisible by any prime up to $$\sqrt{p}$$. (The locution ’in principle’ is cheeky; no computer present or future will ever complete such a brute-force computation within the lifetime of our Universe.)

This example motivates the introduction of the logical (or boolean) operators $${\textsc {not}}$$ and $${\textsc {and}}$$ (to be defined below), with which we rewrite (4.7) as follows:

$$ {\textsc {not}}\,(2\vert p)\,\,\,\,{{{\textsc {and}}}}\,\,\,\,{\textsc {not}}\,(3\vert p)\,\,\,\,\,{{{\textsc {and}}}}\,\,\,\,{\textsc {not}}\,(5\vert p)\,\,\,\,\,{{{\textsc {and}}}}\,\,\,\,\cdots . $$

We have produced a complex symbolic sentence by combining relational expressions with logical operators. This process is analogous to the construction of complex arithmetical expressions from arithmetical constants (numbers) and operators ($$+$$, $$-$$, etc.).

The operator $${\textsc {not}}$$ (represented by the symbol $$\lnot $$) is unary—it takes one boolean operand and produces a boolean value. In this respect $${\textsc {not}}$$ resembles the unary arithmetical operator ’$$-$$’, which changes the sign of a number. The operator $${\textsc {and}}$$ (represented by the symbol $$\wedge $$) is binary: think of it as a kind of multiplication.

The following truth tables define the operators $${\textsc {not}}$$ and $${\textsc {and}}$$ by specifying their action on all possible choices of operands:

(4.8)

The expression $$\lnot P$$ is called the negation of $$P$$. Negating relational expressions is straightforward, as we already have all the relevant symbols—see (4.3) and (4.5). Thus

$$ \lnot (x<y)\,=\,(x\geqslant y), \quad \qquad \lnot (x\in A)\,=\,(x\not \in A), \quad \qquad \lnot (A\not \subset B)\,=\,A\subset B. $$

The expression $$P\wedge Q$$ is called a conjunction or compound expression. In a compound expression the operator AND may appear implicitly. For instance, the expression $$0<x<1$$ is compound: $$(0<x) \, \wedge \, (x<1)$$.

Next we define the operator $${\textsc {or}}$$ (represented by the symbol $$\vee $$) and the implication operator (represented by the symbol $$\Rightarrow $$), as follows:

(4.9)

These operators could also be expressed in terms of $$\lnot $$ and $$\wedge $$, see Exercise 4.10. The operator $${\textsc {or}}$$ is inclusive, namely $${\textsc {t}}\vee {\textsc {t}}={\textsc {t}}$$, which is not the meaning usually attributed to the conjunction ’or’ in English usage.2

The expression

$$\begin{aligned} P\,\Rightarrow \, Q \end{aligned}$$

(4.10)

is called an implication, and it reads

The expression $$P$$ is the hypothesis (or antecedent) and $$Q$$ is the conclusion (or consequent). Many mathematical statements have this form, for example theorem (4.1).

According to the truth table (4.9), if $$P$$ is false, then the expression $$P\Rightarrow Q$$ is true for any $$Q$$. This convention, which is perhaps unexpected, is in fact in agreement with the common usage of an implication:

If 4 is a prime number, then I am a Martian. If I win the lottery, then I’ll buy you a Ferrari.

The meaning of these sentences is clear. In particular, if I don’t win the lottery, then I am free do what I want about the Ferrari.

From (4.9) we see that the expressions $$P \Rightarrow Q$$ and $$Q\Rightarrow P$$ are different. Accordingly, we introduce the operator $$\Leftarrow $$ as follows:

$$ P\Leftarrow Q \,\mathop {=}\limits ^\mathrm{def}\, Q\Rightarrow P. $$

The expression on the left is called the converse of the implication (4.10). It reads

The value of an implication and its converse are unrelated. In the following example the former is false and the latter is true:

$$\begin{aligned} (x^2=25) \,\Rightarrow \, (x=-5) \quad \qquad (x^{2}=25) \,\Leftarrow \, (x=-5). \end{aligned}$$

(4.11)

Inappropriate reversal of an implication is a common mistake in proofs—see Sect. 7.7.2.

Formulae (4.11) combine relational and boolean operators, and the parentheses suggest the order in which these operators are evaluated. In this case the parentheses are redundant, since relational operators must necessarily take precedence over boolean operators. Thus the expression $$x^2=25\Rightarrow x=-5$$ could not be interpreted as $$x^2=(25\Rightarrow x)=-5$$. However, when two or more boolean operators are present, parentheses may be inserted to change the meaning of an expression. For instance, the expressions

$$\begin{aligned} ({\textsc {f}}\wedge {\textsc {t}}) \Rightarrow {\textsc {t}}\quad \qquad {\textsc {f}}\wedge ({\textsc {t}}\Rightarrow {\textsc {t}}) \end{aligned}$$

evaluate to TRUE and FALSE respectively. As with arithmetical operators, there is an agreed order with which boolean operators are evaluated: first $$\lnot $$, then $$\wedge $$, then $$\vee $$, then $$\Rightarrow $$. Thus the expression $$P \vee \lnot Q \Rightarrow R \wedge S$$ is evaluated as $$(P \vee (\lnot Q)) \Rightarrow (R \wedge S)$$; we note that the redundant parentheses add clarity to the sentence.

The equivalence operator $$\Leftrightarrow $$ is the conjunction of the direct and converse implications:

$$\begin{aligned} P \Leftrightarrow Q\,\mathop {=}\limits ^\mathrm{def}\, (P\Rightarrow Q) \wedge (P\Leftarrow Q) \end{aligned}$$

(4.12)

and it corresponds to the following truth table:

The expression $$P\Leftrightarrow Q$$ is read aloud as

The awkward expression ’if and only if’ is quite common; the abbreviated form ’iff’ is found in formulae as an alternative to ’$$\Leftrightarrow $$’. So the expressions

$$ A=B \, \Leftrightarrow \, A\,\varDelta \,B=\emptyset \quad \qquad A=B \, \mathrm iff \, A\,\varDelta \, B=\emptyset $$

have the same meaning; we turn symbols into words:

Two sets are equal if and only if their symmetric difference is empty.

If—as in this example—the value of $$P\Leftrightarrow Q$$ is TRUE, then the statements $$P$$ and $$Q$$ are logically equivalent, meaning that one is is just a rewording of the other.

The contrapositive of the implication (4.10) is the implication

$$\begin{aligned} \lnot P \Leftarrow \lnot Q. \end{aligned}$$

(4.13)

The contrapositive is constructed by reversing the operator and negating the operands. Great care must be exercised in distinguishing between direct, converse, and contrapositive implications.

While the value of an implication and of its converse are unrelated, every implication is equivalent to its contrapositive. This is identity (iv) of the following theorem.

Theorem 4.1

For all $$P,Q\in \{{\textsc {t}},{\textsc {f}}\}$$, the following holds:

PROOF. We prove (iii), leaving the other cases as an exercise. We will show that the two sides of the equivalence (iii) have the same truth table. The truth table of the left-hand side is given in (4.9); that of the right-hand is computed as follows:

We see that the two truth tables are equal. $$\square $$

The statements (i) and (ii) are known as De Morgan’s laws.3 Using Theorem 4.1, one can express the operators $$\vee $$, $$\Rightarrow $$, $$\Leftrightarrow $$ in terms of $$\lnot $$ and $$\wedge $$ (Exercise 4.10).

All items in the theorem have the form $$A(P,Q)\Leftrightarrow B(P,Q)$$, where the statements $$A$$ and $$B$$ have the same value for any choice of $$P$$ and $$Q$$ and hence are equivalent. A statement of this kind is called a tautology. In logic a distinction is made between a tautology and a syntactically correct—but not necessarily true—double implication, by introducing the symbol $$\leftrightarrow $$ for the latter circumstance. So one would write $$(P \vee Q) \leftrightarrow (P \wedge Q)$$ rather than $$(P \vee Q) \Leftrightarrow (P \wedge Q)$$. A similar distinction exists between $$\Rightarrow $$ and $$\rightarrow $$. For our purpose these additional symbols are unnecessary.