## Section 1.2 Compound Statements

¶In Section 1.1 we defined a statement to be a sentence which is either true or false. Many statements we are interested in studying are actually combinations of several simpler ones. Then the problem of determining the truth value (truth or falsity) of such statements becomes one of discovering the truth value of the statements being combined as well as understanding the methods of combination. We will at this time consider the negation, conjunction, and disjunction of statements.

###### Definition 1.2.1.

Let \(p\) be a statement. The *negation* of \(p\text{,}\) denoted \(\negate p\text{,}\) is a statement forming the denial of \(p\text{.}\) The statement \(\negate p\text{,}\) read “not p,” has the opposite truth value of \(p\text{.}\)

###### Example 1.2.2.

- Consider the statement, “Austin is the capital of Texas.” The negation of that statement would be the statement, “Austin is not the capital of Texas.”
- The statement “\(2 + 3 = 5\)” has as its negation the statement “\(2 + 3 \neq 5\text{.}\)”

Since one of our stated concerns in this section is the determination of the truth value of a given statement based upon the truth values of its component statements, we consider the concept of a truth table. Very simply, a truth table is exactly a table which indicates the relationships between the truth values of the statements forming the table. Thus, the truth table below (Table 1.2.3) indicates the relationship between the statements \(p\) and \(\negate p\text{,}\) giving us the basic table for a negation.

\(p\) | \(\negate p\) |

T | F |

F | T |

Notice that the table shows that if \(p\) is true, then \(\negate p\) is false and if \(p\) is false, then \(\negate p\) is true. Truth tables become very useful when we deal with more complicated statements.

The first type of compound statement we consider is the conjunction. When combining statements in logic, the most important aspect of the definition is the truth value of the resulting statement in terms of the component statements.

###### Definition 1.2.4.

Let \(p\) and \(q\) be statements. The *conjunction* of \(p\) and \(q\text{,}\) denoted \(p \wedge q\text{,}\) is the compound statement obtained by connecting and with the English connective “and.” The conjunction is true only when both \(p\) and \(q\) are true.

###### Example 1.2.5.

The compound statement “Austin is the capital of Texas, and five is greater than two” is obtained by using “and” to connect the two statements “Austin is the capital of Texas” and “five is greater than two.”

The key to understanding the conjunction is the truth table below (Table 1.2.6), which systematically exhibits the four possible combinations of the truth values for \(p\) and \(q\text{.}\) Thus, we see that the conjunction of two statements is true only in the case when both statements are true.

\(p\) | \(q\) | \(p \wedge q\) |

T | T | T |

T | F | F |

F | T | F |

F | F | F |

###### Definition 1.2.7.

Let \(p\) and \(q\) be statements. The *disjunction* of \(p\) and \(q\text{,}\) denoted \(p \vee q\text{,}\) is the compound statement obtained by connecting and with the English connective “or.” The conjunction is true when at least one of the statements is true.

A brief comment about “or” must be noted. As used in a mathematical/logical sense, “or” is interpreted in the inclusive sense. That is, or is interpreted as and/or, meaning one and/or the other is true. Consider carefully the truth table for the disjunction (Table 1.2.8). So we see the disjunction is false only when both \(p\) and \(q\) are false. (The exclusive use of “or” would yield truth only if exactly one of the two statements were true.)

\(p\) | \(q\) | \(p \vee q\) |

T | T | T |

T | F | T |

F | T | T |

F | F | F |

###### Example 1.2.9.

Consider the four disjunctions.

- Austin is the capital of Texas or five is greater than two.
- Austin is the capital of Texas or five is less than two.
- Austin is not the capital of Texas or two is less than five.
- Austin is not the capital of Texas or five is less than two.

Here we see the first three compound sentences are disjunctions which are true, while the disjunction in (4) is false.

Another way of logically combining statements is the conditional statement, which is the heart of mathematical logic.

###### Definition 1.2.10.

Let \(p\) and \(q\) be statements. The *conditional statement* is the compound statement obtained by considering this statement: “if \(p\text{,}\) then \(q\)” or “\(p\) implies \(q\text{,}\)” and is denoted \(p \rightarrow q\text{.}\) The conditional is true unless \(p\) is true and \(q\) is false.

In mathematics/logic the truth table for a conditional statement is given in Table 1.2.11.

\(p\) | \(q\) | \(p \rightarrow q\) |

T | T | T |

T | F | F |

F | T | T |

F | F | T |

###### Example 1.2.12.

Consider the four conditional statements.

- If Austin is the capital of Texas, then five is greater than two.
- If Austin is the capital of Texas, then five is less than two.
- If Austin is not the capital of Texas, then two is less than five.
- If Austin is not the capital of Texas, then five is less than two.

Here we see the first three compound sentences are disjunctions which are true, while the disjunction in (4) is false. Here we see by the truth table defining the truth value of a conditional statement that (1), (3),and (4) are true conditional statements while (2) is a false conditional statement. Notice that we can determine the truth value of these statements even though the component statements appear to be totally unrelated in terms of cause and effect!

We emphasize that the student must understand that conditional statements have truth values precisely as assigned by the definition. That is, to determine truth value, we do not need to be able to “prove” or “disprove” the consequence from the hypothesis. Certainly “proving” things will be the ultimate focus of this course, but at this time we are simply discovering the ways of combining statements logically and the resulting truth values of such combinations.

The last compound statement we will introduce is the biconditional statement.

###### Definition 1.2.13.

Consider two statements \(p\) and \(q\text{.}\) The *biconditional statement* is the compound statement “\(p\) if and only if \(q\)” or “\(p\) is equivalent to \(q\text{,}\)” denoted \(p \leftrightarrow q\text{.}\) Frequently we write “\(p\) iff \(q\)” as a shorthand notation for “\(p\) if and only if \(q\text{.}\)”

Two statements, no matter how complicated, are equivalent when they have precisely the same truth value. You can find the truth table for the biconditional statement in Table 1.2.14.

\(p\) | \(q\) | \(p \leftrightarrow q\) |

T | T | T |

T | F | F |

F | T | F |

F | F | T |

###### Example 1.2.15.

Consider the four biconditional statements.

- If Austin is the capital of Texas if and only if five is greater than two.
- If Austin is the capital of Texas if and only if five is less than two.
- If Austin is not the capital of Texas if and only if two is less than five.
- If Austin is not the capital of Texas if and only if five is less than two.

Here we see that (1) and (4) are true biconditional statements while (2) and (3) are false.

Mathematicians often use other expressions to describe conditional type statements. A few of the most common such expressions are given below.

- \(p \leftrightarrow q\text{:}\) “\(p\) is a necessary and sufficient condition for \(q\text{.}\)”
- \(p \rightarrow q\text{:}\) “\(p\) is a sufficient condition for \(q\text{.}\)”
- \(q \rightarrow p\text{:}\) “\(p\) is a necessary condition for \(q\text{.}\)”

Since it is easy to confuse these expressions, you must always carefully identify the hypothesis and conclusion before working with any conditional type statement.

Again we stress that we are not attempting to “prove” anything yet, but rather only define a compound statement and its truth value in terms of the truth values of the statements used to obtain it.

In order to determine the truth values of more complicated statements, it is critical that you thoroughly understand and remember these five basic truth tables. That is, sufficient time must be spent digesting these tables and examples in order that you need not constantly refer back to the basic tables when working on more difficult ones.

Before going on to the last definition and fact of this section, we give an example of a more involved statement along with a step-by-step approach to constructing the associated table. We note that there are several methods available for constructing truth tables. We will exhibit one in the example below and employ an alternate approach in the proof of Fact 1.2.20 at the end of this section. You should adopt the one most comfortable and appropriate for dealing with the statement at hand.

###### Example 1.2.16.

Let us construct the truth table (Table 1.2.17) for the statement

After listing the component statements and all possible combinations of truth values associated with them in the table, the remaining compound statements should be given in the order in which they will be considered. This is done much like ordering of operations in an arithmetic problem or an algebraic expression.

\(p\) | \(q\) | \(\negate p\) | \(q \wedge p\) | \(q \wedge (\negate p)\) | \((q \wedge p) \vee [q \wedge (\negate p)]\) |

T | T | F | T | F | T |

T | F | F | F | F | F |

F | T | T | F | T | T |

F | F | T | F | F | F |

We now give a final definition that relates conditional statements and negation.

###### Definition 1.2.18.

Consider two statements \(p\) and \(q\text{.}\) The statement \(q \rightarrow p\) is the *converse* of \(p \rightarrow q\text{.}\) The statement \(\negate q \rightarrow \negate p\) is the *contrapositive* of \(p \rightarrow q\text{.}\) The statement \(\negate p \rightarrow \negate q\) is the *inverse* of \(p \rightarrow q\text{.}\)

It is worth noting that the converse of the inverse is the contrapositive. You should also note that the terms “inverse” and “negation” are not interchangeable.

###### Remark 1.2.19. About Notation.

You should be aware that there are conventions governing the use or lack of use of parentheses in logical statements that are similar to those used to interpret algebraic expressions. Although we sometimes use grouping symbols for emphasis, such grouping symbols are often unnecessary for clarity of meaning. For example, the expression \([ (\negate p) \wedge q] \rightarrow [(\negate r) \vee (\negate s)]\) could have been written \(\negate p \wedge q \rightarrow \negate r \vee \negate s\text{.}\) It is important for you to realize that the negation symbol preceding the \(p\) statement applies only to \(p\) unless indicated otherwise. However, the grouping symbols in the expressions \([ \negate (p \wedge q)] \rightarrow [(\negate r) \rightarrow (\negate s)]\) and \(\negate \{(p \wedge q) \rightarrow [(\negate r) \rightarrow (\negate s)]\}\) produce statements with entirely different meanings.

###### Fact 1.2.20.

Consider two statements \(p\) and \(q\text{.}\)

- \((p \rightarrow q) \leftrightarrow [(\negate q) \rightarrow (\negate p)]\text{;}\) that is, the conditional is equivalent to its contrapositive.
- \([(\negate p) \rightarrow (\negate q)] \leftrightarrow (q \rightarrow p) \text{;}\) that is, the inverse is equivalent to the converse.

###### Proof.

To demonstrate the proof of (1) in Fact 1.2.20, we need only examine the corresponding truth table Table 1.2.21. Since the last two columns are the same, the conditional statement and its contrapostive are equivalent.

\(p\) | \(q\) | \(\negate p\) | \(\negate q\) | \(p \rightarrow q\) | \(\negate q \rightarrow \negate p\) |

T | T | F | F | T | T |

T | F | F | T | F | F |

F | T | T | F | T | T |

F | F | T | T | T | T |

We will leave the proof of (2) as an exercise.

### Exercises 1.2.1 Exercises

###### 1.

Translate the following English statements using propositional notation.

- An integer is odd if and only if its square is odd.
- If I do not study, then I will fail this class.
- Either I will go shopping or I will go to a movie.
- I was well qualified, but I did not get the job.
- If \(n\) is an integer, then \(n\) is even or \(n\) is odd.
- The square of an even integer is an even integer.

###### 2.

Negate each of the following statements. (Refer to the definition of negation.)

- A positive number is larger than zero.
- If today is Saturday, then I do not have to go to work.
- Dogs can bark and cats can climb trees.
- If \(x^2 - 9 = 0\text{,}\)then either \(x = 3\) or \(x = -3\text{.}\)

Note: The difficulties of negating compound statements will be vastly simplified by the tautologies studied in the next section.

###### 3.

For the conditional statements given below, give the converse, the inverse, and the contrapositive.

- If I teach third grade, then I am an elementary school teacher.
- If I do not get to class on time, then I will not be allowed to take the exam.
- I will return the calls and dictate the letter when I arrive at the office.
- If \((x + 1)(x - 4) = 0\text{,}\) then \(x = -1\) or \(x = 4\text{.}\)
- If a number has a factor of \(4\text{,}\) then it has a factor of \(2\text{.}\)

###### 4.

Restate the following in a logically equivalent form.

- It is not true that both today is Wednesday and the month is June.
- It is not true that yesterday I both ate breakfast and watched television.
- It is not raining, or it is not July.

###### 5.

In the following statements, remove those grouping symbols which are unnecessary for clarity of meaning.

- \(\displaystyle p \vee [(\negate p) \wedge q]\)
- \(\displaystyle [\negate(p \rightarrow q)] \wedge q\)
- \(\displaystyle [p \wedge (\negate q)] \vee (p \wedge q)\)
- \(\displaystyle \{ \negate[ p \vee (\negate r) ] \vee (q \wedge p)\} \rightarrow p\)

###### 6.

Construct truth tables for the following compound statements.

- \(\displaystyle p \vee (\negate p \wedge q)\)
- \(\displaystyle \negate(p \rightarrow q) \wedge q\)
- \(\displaystyle (p \, \wedge \negate q) \vee (p \wedge q)\)
- \(\displaystyle [ \negate(p \, \vee \negate r) \wedge (p \vee q)] \rightarrow p\)

###### 7.

For integers \(x\) and \(y\text{,}\) find the inverse, the converse, the contrapositive, and the negation of each of the following statements.

- If \(x = 3\text{,}\) then \(x^4 = 81\text{.}\)
- If \(x \gt 0\text{,}\) then \(x \neq -4\text{.}\)
- If \(x\) is odd and \(y\) is even, then \(xy\) is even.
- If \(x^2 = x\text{,}\) then either \(x = 0\) or \(x = 1\text{.}\)
- If \(xy \neq 0\text{,}\) then \(x \neq 0\) and \(y \neq 0\text{.}\)

###### 8.

Give two examples from mathematics which satisfy the given conditions.

- A statement and its converse that are both true.
- A statement that is true, but its converse is false.
- A biconditional statement that is true.
- A biconditional statement that is false.

###### 9.

Decide if the conditional statements are true or false.

- If \(n\) is a natural number, then the last digit of \(n^4\) is \(0\text{,}\) \(1\text{,}\) \(5\text{,}\) or \(6\text{.}\)
- If the last digit of a natural number is \(0\text{,}\) \(1\text{,}\) \(5\text{,}\) or \(6\text{,}\) then it is a fourth power of some natural number.
- \(n\) is a natural number only if \(n + 1\) is a whole number.
- \(n + 1\) is a whole number if \(n\) is a natural number.

###### 10.

Let \(m\) and \(n\) be integers and consider the statement \(p \rightarrow q\) given by, “If \(m + n\) is even, then \(m\) and \(n\) are even.”

- Express the contrapositive, converse, and inverse of the given conditional.
- For the given conditional or any statements in part (a) that are false, give a counterexample.