3.1: Propositions from Propositions

In English, we can modify, combine, and relate propositions with words such as “not,” “and,” “or,” “implies,” and “if-then.” For example, we can combine three propositions into one like this:

If all humans are mortal and all Greeks are human, then all Greeks are mortal.

For the next while, we won’t be much concerned with the internals of propositions— whether they involve mathematics or Greek mortality—but rather with how propositions are combined and related. So, we’ll frequently use variables such as \(P\) and \(Q\) in place of specific propositions such as “All humans are mortal” and “2 + 3 = 5.” The understanding is that these propositional variables, like propositions, can take on only the values \(\textbf{T}\) (true) and \(\textbf{F}\) (false). Propositional variables are also called Boolean variables after their inventor, the nineteenth century mathematician George—you guessed it—Boole.

\(\textbf{NOT}, \textbf{AND},\) and \(\textbf{OR}\)

Mathematicians use the words \(\textbf{NOT}, \textbf{AND},\) and \(\textbf{OR}\) for operations that change or combine propositions. The precise mathematical meaning of these special words can be specified by truth tables. For example, if \(P\) is a proposition, then so is “\(\text{NOT} (P)\)” and the truth value of the proposition “\(\text{NOT} (P)\)” is determined by the truth value of \(P\) according to the following truth table:

\[\nonumber \begin{array}{c|c} 
P & \text{NOT}(P) \\ \hline \mathbf{T} & \mathbf{F} \\ \mathbf{F} & \mathbf{T} \end{array}\]

The first row of the table indicates that when proposition \(P\) is true, the proposition “\(\text{NOT} (P)\)” is false. The second line indicates that when \(P\) is false, “\(\text{NOT} (P)\)” is true. This is probably what you would expect.

In general, a truth table indicates the true/false value of a proposition for each possible set of truth values for the variables. For example, the truth table for the proposition “\(P \text{ AND } Q\)” has four lines, since there are four settings of truth values for the two variables:

\[\nonumber \begin{array}{cc|c} 
P & Q & P \text{ AND } Q \\ \hline \mathbf{T} & \mathbf{T} & \mathbf{T} \\ \mathbf{T} & \mathbf{F} & \mathbf{F} \\ \mathbf{F} & \mathbf{T} & \mathbf{F} \\ \mathbf{F} & \mathbf{F} & \mathbf{F} \end{array}\]

According to this table, the proposition “\(P \text{ AND } Q\)” is true only when \(P\) and \(Q\) are both true. This is probably the way you ordinarily think about the word “and.”

There is a subtlety in the truth table for “\(P \text{ OR } Q\)”:

\[\nonumber \begin{array}{cc|c} 
P & Q & P \text{ OR } Q \\ \hline \mathbf{T} & \mathbf{T} & \mathbf{T} \\ \mathbf{T} & \mathbf{F} & \mathbf{T} \\ \mathbf{F} & \mathbf{T} & \mathbf{T} \\ \mathbf{F} & \mathbf{F} & \mathbf{F} \end{array}\]

The first row of this table says that “\(P \text{ OR } Q\)” is true even if both \(P\) and \(Q\) are true. This isn’t always the intended meaning of “or” in everyday speech, but this is the standard definition in mathematical writing. So if a mathematician says, “You may have cake, or you may have ice cream,” he means that you could have both.

If you want to exclude the possibility of having both cake and ice cream, you should combine them with the exclusive-or operation, \(text{XOR}\):

\[\nonumber \begin{array}{cc|c} 
P & Q & P \text{ XOR } Q \\ \hline \mathbf{T} & \mathbf{T} & \mathbf{F} \\ \mathbf{T} & \mathbf{F} & \mathbf{T} \\ \mathbf{F} & \mathbf{T} & \mathbf{T} \\ \mathbf{F} & \mathbf{F} & \mathbf{F} \end{array}\]

IMPLIES

The combining operation with the least intuitive technical meaning is “implies.” Here is its truth table, with the lines labeled so we can refer to them later.

\[\nonumber \begin{array}{cc|cc} 
P & Q & P \text{ IMPLIES } Q & \\ \hline \mathbf{T} & \mathbf{T} & \mathbf{T} & \text{(tt)}\\ \mathbf{T} & \mathbf{F} & \mathbf{F} & \text{(tf)}\\ \mathbf{F} & \mathbf{T} & \mathbf{T} & \text{(ft)}\\ \mathbf{F} & \mathbf{F} & \mathbf{T} & \text{(ff)} \end{array}\]

The truth table for implications can be summarized in words as follows:

An implication is true exactly when the if-part is false or the then-part is true.

This sentence is worth remembering; a large fraction of all mathematical statements are of the if-then form!

Let’s experiment with this definition. For example, is the following proposition true or false?

“If Goldbach’s Conjecture is true, then \(x^2 \geq 0\) for every real number \(x\).”

Now, we already mentioned that no one knows whether Goldbach’s Conjecture, Proposition 1.1.8, is true or false. But that doesn’t prevent you from answering the question! This proposition has the form \(P \text{ IMPLIES } Q\) where the hypothesis, \(P\), is “Goldbach’s Conjecture is true” and the conclusion, \(Q\), is “\(x^2 \geq 0\) for every real number \(x\).” Since the conclusion is definitely true, we’re on either line (tt) or line (ft) of the truth table. Either way, the proposition as a whole is true!

One of our original examples demonstrates an even stranger side of implications.

“If pigs fly, then you can understand the Chebyshev bound.”

Don’t take this as an insult; we just need to figure out whether this proposition is true or false. Curiously, the answer has nothing to do with whether or not you can understand the Chebyshev bound. Pigs do not fly, so we’re on either line (ft) or line (ff) of the truth table. In both cases, the proposition is true!

In contrast, here’s an example of a false implication:

“If the moon shines white, then the moon is made of white cheddar.”

Yes, the moon shines white. But, no, the moon is not made of white cheddar cheese. So we’re on line (tf) of the truth table, and the proposition is false.

False Hypotheses

It often bothers people when they first learn that implications which have false hypotheses are considered to be true. But implications with false hypotheses hardly ever come up in ordinary settings, so there’s not much reason to be bothered by whatever truth assignment logicians and mathematicians choose to give them.

There are, of course, good reasons for the mathematical convention that implications are true when their hypotheses are false. An illustrative example is a system specification (see Problem 3.12) which consisted of a series of, say, a dozen rules,

if \(C_i\) : the system sensors are in condition \(i\), then \(A_i\) : the system takes action \(i\),

or more concisely,

\[\nonumber C_i \text{ IMPLIES } A_i\]

for \(1 \leq i \leq 12\). Then the fact that the system obeys the specification would be expressed by saying that the AND

\[\label{3.1.1} [C_1 \text{ IMPLIES } A_1] \text{ AND } [C_2 \text{ IMPLIES } A_2] \text{ AND} \cdots \text{ AND } [C_{12} \text{ IMPLIES } A_{12}]\]

of these rules was always true.

For example, suppose only conditions \(C_2\) and \(C_5\) are true, and the system indeed takes the specified actions \(A_2\) and \(A_5\). This means that in this case the system is behaving according to specification, and accordingly we want the formula (\ref{3.1.1}) to come out true. Now the implications \(C_2 \text{ IMPLIES } A_2\) and \(C_5 \text{ IMPLIES } A_5\) are both true because both their hypotheses and their conclusions are true. But in order for (\ref{3.1.1}) to be true, we need all the other implications with the false hypotheses \(C_i\) for \(i \neq 2, 5\) to be true. This is exactly what the rule for implications with false hypotheses accomplishes.

If and Only If

Mathematicians commonly join propositions in one additional way that doesn’t arise in ordinary speech. The proposition “\(P\) if and only if \(Q\)” asserts that \(P\) and \(Q\) have the same truth value. Either both are true or both are false.

\[\nonumber \begin{array}{cc|c} 
P & Q & P \text{ IFF } Q \\ \hline \mathbf{T} & \mathbf{T} & \mathbf{T} \\ \mathbf{T} & \mathbf{F} & \mathbf{F} \\ \mathbf{F} & \mathbf{T} & \mathbf{F} \\ \mathbf{F} & \mathbf{F} & \mathbf{T} \end{array}\]

For example, the following if-and-only-if statement is true for every real number \(x\):

\[\nonumber x^2 - 4 \geq 0 \text{ IFF } |x| \geq 2.\]

For some values of \(x\), both inequalities are true. For other values of \(x\), neither inequality is true. In every case, however, the \(\text{IFF}\) proposition as a whole is true.