Skip to main content

Section 5.1 Logical Connectives

Many mathematical statements use the logical connectives “and” and “or”. In this section we discuss when such statements are true or false, along with the proof formats to prove such statements are true. We introduce truth tables, a tool for understanding the logic of complicated statements and use truth tables to determine whether two statements have the same truth values (logical equivalence). Lastly, we introduce the logical negation, the statement having the opposite truth value, and explore how to negate statements involving “and” and “or”.

Subsection 5.1.A True or False?

Let’s warm up our logical thinking by considering some true/false questions.

Activity 5.1.A True or false?

Decide if each statement is true or false and discuss how to justify your answer.
  1. There are three distinct digits whose sum is 23.
  2. There are three distinct digits whose sum is 25.
  3. Every integer is positive or negative.
  4. Some integers are divisible by three and five.
  5. Some integers are divisible by six but not by three.
  6. A graph with five vertices is the cycle \(C_5\) or the complete graph \(K_5\text{.}\)
  7. Every graph is a tree, which means that it is connected and acyclic.
  8. Every bit string of length five begins or ends with \(\bs{0}\text{.}\)
  9. Every bit string of length five has at least three \(\bs{0}\) s or at least three \(\bs{1}\) s.

Subsection 5.1.B And and Or

In Activity 5.1.A, there are many words that indicate the logical structure of a statement. Two important such words are “and” and “or”, each of which has a specific technical meaning in mathematics and computer science.

Definition 5.1.2 And, or, and xor.

 
  1. A statement is a sentence that is either true or false. For example, if the statement \(P\) is “the integer six has exactly four positive divisors”, then \(P\) happens to be true because the positive divisors of six are 1, 2, 3, and 6. If the statement \(Q\) is “the cycle \(C_5\) has a vertex of degree three”, then \(Q\) is false because all the vertices of \(C_5\) have degree two.
  2. For statements \(P\) and \(Q\text{,}\) the statement “\(P\) and \(Q\)”, denoted \(P \land Q\text{,}\) is true if both \(P\) and \(Q\) are true and false otherwise. For example, the statement “the integer seven is positive and odd” is true because seven is positive and seven is odd. The statement “the integer six is positive and odd” is false, even though six is positive because six is not odd.
  3. For statements \(P\) and \(Q\text{,}\) the statement “\(P\) or \(Q\)”, denoted \(P \lor Q\text{,}\) is true if at least one of \(P\) and \(Q\) are true and false otherwise. For example, the statement “the integer six is positive or odd” is true, because six is positive. The statement “a graph with five vertices is either the cycle \(C_5\) or the complete graph \(K_5\)” from Activity 5.1.A (f) is false because, for example, the graph \(P_5\) has five vertices but it is not a cycle and it is not complete.
  4. Note that \(P \lor Q\) is true if both \(P\) and \(Q\) are true. For example, the statement “the integer seven is positive or odd” is true. This use of “or” is the inclusive or because it includes the possibility of both statements being true.
  5. When we want to exclude the possibility of both statements being true, we use the exclusive or instead. For statements \(P\) and \(Q\text{,}\) the statement “\(P\) xor \(Q\)”, denoted \(P \oplus Q\text{,}\) is true if one of \(P\) and \(Q\) is true and the other is false and false otherwise. For example, when I told my kids “you can have ice cream or brownies for dessert” they suggested brownies with ice cream (the inclusive or), but I probably meant one or the other but not both (the exclusive or). As another example, in Example 4.2.11 we showed that “every integer is either even or odd, but never both” which we could write more concisely as “every integer is even xor odd”.
  6. One way to summarize when a compound statement is true or false is to use a truth table which includes a column for each component of the compound statement (such as \(P\text{,}\) \(Q\)) and for the full compound statement (such as \(P \land Q\)) and a row for each possible combination of true or false for the component statements. For example, if our components are \(P\) and \(Q\text{,}\) then the truth table will have four rows corresponding to the four possibilities:
    • \(P\) is true and \(Q\) is true;
    • \(P\) is true and \(Q\) is false;
    • \(P\) is false and \(Q\) is true; and
    • \(P\) is false and \(Q\) is false.
    In this textbook we abbreviate true as \(\str{T}\) and false as \(\str{F}\text{.}\) Some computer science textbooks use \(\bs{1}\) for true and \(\bs{0}\) for false instead.
We show the truth tables for the compound statements \(P \land Q\text{,}\) \(P \lor Q\text{,}\) and \(P \oplus Q\) in our next example.

Example 5.1.3 Truth tables for and, or, and xor.

 
  1. Use a truth table to illustrate the meaning of the logical connective \(\land\) (and).
    Solution.
    Table 5.1.4 shows the truth table for \(P \land Q\text{.}\) Since the only time \(P \land Q\) is true is when both \(P\) and \(Q\) are true, the only \(\str{T}\) in the \(P \land Q\) column is in the first row. The other entries in the \(P \land Q\) column are all \(\str{F}\text{.}\)
    Table 5.1.4. Truth table for the logical connective and
    \(P\) \(Q\) \(P \land Q\)
    \(\str{T}\) \(\str{T}\) \(\str{T}\)
    \(\str{T}\) \(\str{F}\) \(\str{F}\)
    \(\str{F}\) \(\str{T}\) \(\str{F}\)
    \(\str{F}\) \(\str{F}\) \(\str{F}\)
  2. Use a truth table to illustrate the meaning of the logical connective \(\lor\) (or).
    Solution.
    Table 5.1.5 shows the truth table for \(P \lor Q\text{.}\) Since \(P \lor Q\) is true is whenever \(P\) is true, the first two entries in the \(P \land Q\) column are \(\str{T}\text{.}\) Since \(P \lor Q\) is true whenever \(Q\) is true, the third entry in the \(P \land Q\) column is also \(\str{T}\text{.}\) The final entry in the \(P \land Q\) column is \(\str{F}\) because neither \(P\) nor \(Q\) are true.
    Table 5.1.5. Truth table for the logical connective or
    \(P\) \(Q\) \(P \lor Q\)
    \(\str{T}\) \(\str{T}\) \(\str{T}\)
    \(\str{T}\) \(\str{F}\) \(\str{T}\)
    \(\str{F}\) \(\str{T}\) \(\str{T}\)
    \(\str{F}\) \(\str{F}\) \(\str{F}\)
  3. Use a truth table to illustrate the meaning of the logical connective \(\oplus\) (xor).
    Solution.
    Table 5.1.6 shows the truth table for \(P \oplus Q\text{.}\) Since \(P \oplus Q\) is true exactly when one of \(P\) or \(Q\) is true, the \(P \oplus Q\) column has \(\str{T}\) in the second and third rows only.
    Table 5.1.6. Truth table for the logical connective xor
    \(P\) \(Q\) \(P \oplus Q\)
    \(\str{T}\) \(\str{T}\) \(\str{F}\)
    \(\str{T}\) \(\str{F}\) \(\str{T}\)
    \(\str{F}\) \(\str{T}\) \(\str{T}\)
    \(\str{F}\) \(\str{F}\) \(\str{F}\)
It is your turn to create a truth table.

Activity 5.1.B Truth tables with and and or.

Table 5.1.8 shows the beginning of the truth table for the compound statement \((P \lor Q) \land R\text{.}\)
Table 5.1.8. Part of the truth table for \((P \lor Q) \land R\)
\(P\) \(Q\) \(R\) \(P \lor Q\) \((P \lor Q) \land R\)
\(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\)
\(\str{T}\) \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{F}\)
\(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{T}\) \(\str{T}\)
\(\str{T}\) \(\str{F}\) \(\str{F}\) \(\str{T}\) \(\str{F}\)
\(\str{F}\) \(\str{T}\) \(\str{T}\)
\(\str{F}\) \(\str{T}\) \(\str{F}\)
  1. According to the truth table in Table 5.1.8, when \(P\) is true, \(Q\) is false, and \(R\) is true, which row are we in (do not count the “header row” with \(P\text{,}\) \(Q\text{,}\) etc.) and is the statement \((P \lor Q) \land R\) true or false?
  2. We are missing the last couple of rows of Table 5.1.8. What are the remaining true/false options? Fill in the \(P\text{,}\) \(Q\text{,}\) and \(R\) columns for the missing rows.
  3. In Table 5.1.8 we included an intermediate column for \(P \lor Q\text{.}\) Convince yourself that we correctly started that column and complete it. Notice that we ignore the \(R\) column.
  4. Convince yourself that we correctly started the final column for \((P \lor Q) \land R\) in Table 5.1.8 and complete it. Notice that we need to look at only the column for \(R\) and the intermediate column for \(P \lor Q\text{.}\)
  5. Construct a new truth table for the compound statement \((P \land R) \lor (Q \land R)\text{.}\) Include intermediate columns for \(P \land R\) and for \(Q \land R\text{.}\) What do you notice? Hint: Compare to Table 5.1.8.
  6. If we wanted to construct a truth table for a compound statement involving four components (\(P\text{,}\) \(Q\text{,}\) \(R\text{,}\) and \(S\)), how many rows would it need. Explain how you counted. Hint: Steps.
Make sure that you have completed Activity 5.1.B because we are going to reveal some of the answers.

Example 5.1.9 Distributive rule.

Use a truth table to verify the logical equivalence
\begin{equation*} (P \lor Q) \land R \equiv (P \land R) \lor (Q \land R) \end{equation*}
Solution.
The truth table is in Table 5.1.10. Notice that the columns for \((P \lor Q) \land R\) and for \((P \land R) \lor (Q \land R)\) have the same sequence of \(\str{T}\) s and \(\str{F}\) s.
Table 5.1.10. A truth table verifying the distributive equivalence \((P \lor Q) \land R \equiv (P \land R) \lor (Q \land R)\)
\(P\) \(Q\) \(R\) \(P \lor Q\) \((P \lor Q) \land R\) \(P \land R\) \(Q \land R\) \((P \land R) \lor (Q \land R)\)
\(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\)
\(\str{T}\) \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\)
\(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{F}\) \(\str{T}\)
\(\str{T}\) \(\str{F}\) \(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\)
\(\str{F}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{T}\)
\(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\)
\(\str{F}\) \(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\)
\(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\)

Subsection 5.1.C Proof Formats: And and Or Using Cases

How can we prove statements involving and and or? To prove \(P \land Q\text{,}\) we need to prove two things: \(P\) and then \(Q\text{.}\) We can summarize this idea in a proof format.
The format for a proof of \(P \lor Q\) is less direct. An option is to use a modified version of a proof by cases. Later in this textbook, we introduce two other options: proof by contradiction in Subsection 5.1.E and proof using the equivalent conditional in Subsection 5.3.B.
In Subsection 4.2.C we introduced proof by cases. In each case of the format in Subsection 4.2.C, we proved the same statement. We can modify that proof format to prove \(P \lor Q\) by proving \(P\) in one case and \(Q\) in the other case.
We present this format with two cases, since that is often all we need. This format can be modified to have more than two cases where in some cases \(P\) is true and in other cases \(Q\) is true. Officially, this is a new proof format.
Try working with these formats.

Activity 5.1.C Proving and and or using cases.

 
  1. Copy the following example of a proof of an “and” statement. Prove that 30 is even and \(5 \mid 30\text{.}\)

    Proof.
    First, \(30 = 2(15)=2k\) when \(k=15\) and so 30 is even.
    Next, \(30 = 5(6) = 5k\) when \(k=6\) and so \(5 \mid 30\text{.}\)
  2. Edit the proof in (a) to prove that 33 is odd and \(3 \mid 33\text{.}\)
  3. Copy the following example of a proof of an “or” statement using cases. Prove that \(n^2 \fn{ mod } 4 = 0\) or \(n^2 \fn{ mod } 4 = 1\) for any integer \(n\text{.}\) Yes, this proof was Exercise 19 in Section 4.2.

    Proof.
    Let \(n\) be an integer. Then \(n\) is either even or odd, by Example 4.2.11. We consider two cases.
    Case 1: Assume that \(n\) is even. By the definition of even, we can write \(n = 2k\) for some integer \(k\text{.}\) Then
    \begin{equation*} n^2=(2k)^2=4k^2=4(k^2) = 4q=4q+0 \end{equation*}
    where \(q=k^2\) is an integer. Therefore, \(n^2 \fn{ mod } 4 = 0\text{.}\)
    Case 2: Assume that \(n\) is odd. By the definition of odd, we can write \(n = 2k+1\) for some integer \(k\text{.}\) Then
    \begin{equation*} n^2=(2k+1)^2 = (2k+1)(2k+1) \end{equation*}
    \begin{equation*} =4k^2+4k+1 = 4(k^2+k) + 1 = 4q+1 \end{equation*}
    where \(q =k^2+k\) is an integer. Therefore, \(n^2 \fn{ mod } 4 = 1\text{.}\)
    In either case, we have \(n^2 \fn{ mod } 4 = 0\) or \(n^2 \fn{ mod } 4 = 1\text{.}\)
  4. Edit the proof in (c) to prove that \(n^2+2n \fn{ mod } 4 = 0\) or \(n^2+2n \fn{ mod } 4 = 3\) for any integer \(n\text{.}\)

Subsection 5.1.D Logical Equivalence and Negations

In Activity 5.1.B, we saw that the statements \((P \lor Q) \land R\) and \((P \land R) \lor (Q \land R)\) have the same final column in their truth table. That is, in each case (row of the truth table), they are both true or both false. We have a name for the situation where two logical statements have the same truth values.

Definition 5.1.15 Logical equivalence.

 
  1. Statements \(S\) and \(T\) are logically equivalent, denoted \(S \equiv T\text{,}\) if \(S\) and \(T\) always have the same truth value, either both statements are true or both statements are false. For example, we saw in Activity 5.1.B that
    \begin{equation*} (P \lor Q) \land R \equiv (P \land R) \lor (Q \land R)\text{.} \end{equation*}
  2. Statements \(S\) and \(T\) are not logically equivalent, denoted \(S \not \equiv T\) if sometimes one of the statements is true but the other is false. For example,
    \begin{equation*} (P \lor Q) \land R \not \equiv P \lor (Q \land R) \end{equation*}
    as we check in Exercise 4 because, for example, when \(P\) is true and both \(Q\) and \(R\) are false, the left-hand side \((P \lor Q) \land R\) is false but the right-hand side \(P \lor (Q \land R)\) is true.
Logically equivalent statements always have the same truth values. There is also a name for when two statements always have the opposite truth value as well as names for logical statements that are always true or always false.

Definition 5.1.16 Negation, tautology, and contradiction.

 
  1. The statements \(S\) and \(T\) are negations if \(S\) and \(T\) always have the opposite truth value. That is, \(S\) is true and \(T\) is false or \(S\) is false and \(T\) is true. The statement \(T\) is the negation of \(S\text{,}\) denoted \(\neg S\text{.}\) For example, if \(n\) is an integer and if \(S\) is the statement “\(n >2\)”, then \(\neg S\) is the statement “\(n \le 2\)”.
  2. A statement \(S\) is a tautology if it is always true. For example, the statement “either I will work on my homework Tuesday night or I will not work on my homework Tuesday night” is a tautology.
  3. A statement \(S\) is a contradiction if it is always false. For example, the statement “there is an integer \(n\) with \(n>2\) and \(n^2\lt 4\)” is a contradiction because for an integer \(n\) with \(n>2\) we know that \(n^2 > 4\text{.}\)
Here are examples of truth tables involving negations.

Example 5.1.17 Truth tables involving negations.

 
  1. Use a truth table to illustrate the meaning of the logical operation \(\neg\) (not).
    Solution.
    Table 5.1.18 shows the truth table for \(\neg P\text{.}\)
    Table 5.1.18. Truth table for the logical operation not
    \(P\) \(\neg P\)
    \(\str{T}\) \(\str{F}\)
    \(\str{F}\) \(\str{T}\)
  2. Construct a truth table for the compound statement \(P \land \neg Q\text{.}\)
    Solution.
    Table 5.1.19 shows the truth table for \(P \land \neg Q\text{,}\) using an intermediate column for \(\neg Q\text{.}\) Notice that the only time \(P \land \neg Q\) is true is when \(P\) is true and \(Q\) is false, which happens in the second row.
    Table 5.1.19. Truth table for the compound statement \(P \land \neg Q\)
    \(P\) \(Q\) \(\neg Q\) \(P \land \neg Q\)
    \(\str{T}\) \(\str{T}\) \(\str{F}\) \(\str{F}\)
    \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{F}\)
    \(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{F}\)
    \(\str{F}\) \(\str{F}\) \(\str{T}\) \(\str{F}\)
  3. Use a truth table to show that \(P \land \neg P\) is a contradiction.
    Solution.
    Table 5.1.20 shows the truth table for \(P \land \neg P\text{.}\) Since the final column is all \(\str{F}\text{,}\) it follows that \(P \land \neg P\) is a contradiction.
    Table 5.1.20. Truth table for the contradiction \(P \land \neg P\)
    \(P\) \(\neg P\) \(P \land \neg P\)
    \(\str{T}\) \(\str{F}\) \(\str{F}\)
    \(\str{F}\) \(\str{T}\) \(\str{F}\)
By the way, when the statement following the logical connective “and” is negative, we use the connective “but” instead.

Remark 5.1.21 But not.

It is common in English to pronounce \(P \land \neg Q\) as “\(P\) but not \(Q\)”. The word “but” has the same meaning logically as “and” but in English it indicates that what follows is negative in some way. For example, while we can say I like chocolate ice cream and I don’t want any now. it is more common to say I like chocolate ice cream but I don’t want any now.
Try your hand at working with negations.

Activity 5.1.D Negating and.

 
  1. In Definition 5.1.2, we noted that the statement “the integer seven is positive and odd” is true. Consider the general statement “the integer \(n\) is positive and odd.” Give examples of integers \(n\) where the statement is false, including some negative values of \(n\text{.}\)
  2. For the statement “the integer \(n\) is positive and odd” to be false, what needs to be true for \(n\text{?}\)
  3. Construct a truth table for \(\neg(P \land Q)\) and \(\neg P \land \neg Q\text{.}\)
  4. Look at your truth table from (c). Is \(\neg(P \land Q) \equiv \neg P \land \neg Q\text{?}\) Explain.
  5. Is \(\neg P \land \neg Q\) the negation of \(P \land Q\text{?}\) Explain.
  6. Make a conjecture about the negation of \(P \land Q\text{.}\) Your answer should agree with your answer to (b).
  7. Verify your conjecture from (f) using a truth table.
In Activity 5.1.D, we saw that the negation of \(P \land Q\) is not \(\neg P \land \neg Q\text{.}\) For \(P \land Q\) to be false, we need either \(P\) is false or \(Q\) is false or both are false. That is, we need \(\neg P \lor \neg Q\) to be true. Similarly, for \(P \lor Q\) to be false, we need both \(P\) is false and \(Q\) is false. That is, we need \(\neg P \land \neg Q\) to be true. We summarize these negations in a theorem.

Subsection 5.1.E Proof Format: Contradiction

One method of proving that the statement \(P\) is true is to show that the assumption that \(P\) is false leads to a contradiction, such as a statement of the form \(Q \land \neg Q\text{.}\) That is, in a proof by contradiction of a statement \(P\text{,}\) we assume that \(P\) is false and deduce that both \(Q\) and \(\neg Q\) are true for some statement \(Q\text{,}\) which is impossible. That impossibility tells us that \(P\) cannot be false, and so \(P\) must be true.
As we start writing a proof by contradiction, we usually do not know what the statement \(Q\) will be. Sometimes it helps to do a little scratch work listing the consequences of \(P\) being false to see if we find contradictory statements \(Q\) and \(\neg Q\text{.}\)
A proof by contradiction follows the following proof format.
Notice that we are proving two things (\(Q\) and \(\neg Q\)), but instead of saying “First, …. Next, ….” as we did in Theorem 5.1.11, we use the expression “First, …. On the other hand, ….” The phrase ``on the other hand`` alerts the reader that we are changing direction towards the negation of what we just proved. It is also acceptable to write ``On the one hand, …. On the other hand, …."
Try writing a proof using contradiction.

Activity 5.1.E Proof by contradiction: consecutive integers are coprime.

 
  1. Copy the following example of a proof by contradiction. Prove \(\fn{gcd}(n,n+1)=1\) for any integer \(n\text{.}\)
     1 
    We proved this result in Exercise 17 using the Euclidean Algorithm.

    Proof.
    Suppose not. Then there exists an integer \(n\) such that \(d=\fn{gcd}(n,n+1)\neq 1\text{.}\)
    First, by the definition of the greatest common divisor Definition 4.5.1, \(d \mid n\) and \(d \mid n+1\text{.}\) By the definition of divides Definition 4.1.8 we can write \(n = dk_1\) and \(n+1 = dk_2\) for some integers \(k_1\) and \(k_2\text{.}\) Observe that
    \begin{equation*} (n+1) - n = dk_2 - dk_1 = d(k_2-k_1)=dq \end{equation*}
    where \(q = k_2-k_1\) and so \(d \mid (n+1)-n\text{.}\) But, of course, \((n+1)-n=1\) so really \(d \mid 1\text{.}\) Since the only positive divisor of 1 is 1, it follows that \(d =1\text{.}\)
    On the other hand, we assumed that \(d \neq 1\text{.}\) This is a contradiction. Thus, \(\fn{gcd}(n,n+1)=1\text{.}\)
  2. Edit the proof in (a) to prove that \(\fn{gcd}(n,n-1) = 1\) for any integer \(n\text{.}\) (Yes, we are again proving that consecutive integers are coprime.)
There is a bit of controversy over the use of proof by contradiction. Some mathematicians dislike contradiction proofs because they do not actually show why a statement is true, only why it cannot be false. Other mathematicians like contradiction proofs because they settle an argument: if your reader thinks the statement is false, your proof shows them that something terrible goes wrong (a contradiction). We will let you decide which type of mathematician you are.
Because of this controversy, we often rewrite a proof by contradiction using some other format, if possible.

Example 5.1.26 Rewriting without contradiction.

Copy the proof by contradiction from Activity 5.1.E (a) and edit to to give a proof without contradiction.
Prove that \(\fn{gcd}(n,n+1)=1\) for any integer \(n\text{.}\)
Solution.
We have crossed out the statements that should be deleted, and boldfaced the statements that should be added.
Proof. Suppose not. Then there exists an integer \(\require{enclose}\enclose{horizontalstrike}{n}\) such that \(\require{enclose}\enclose{horizontalstrike}{d=\fn{gcd}(n,n+1)\neq 1}\)
Let \(n\) be an integer. Write \(d=\fn{gcd}(n,n+1)\text{.}\) Since 1 is a common divisor of any integer, \(d\) is certainly positive.
First, by the definition of greatest common divisor Definition 4.5.1, \(d \mid n\) and \(d \mid n+1\text{.}\) By the definition of divides Definition 4.1.8 we can write \(n = dk_1\) and \(n+1 = dk_2\) for some integers \(k_1\) and \(k_2\text{.}\) Observe that
\begin{equation*} (n+1) - n = dk_2 - dk_1 = d(k_2-k_1) \end{equation*}
and so \(d \mid (n+1)-n\text{.}\) But, of course, \((n+1)-n=1\) so really \(d \mid 1\text{.}\) Since the only positive divisor of 1 is 1, it follows that \(d =1\text{.}\)
On the other hand, we assumed that \(\require{enclose}\enclose{horizontalstrike}{d \neq 1}\text{.}\) This is a contradiction. Thus \(\require{enclose}\enclose{horizontalstrike}{\fn{gcd}(n,n+1)=1}\text{.}\)

Subsection 5.1.F Exercises

Subsubsection Exercises for 5.1.B And and Or

1. Practice.

Copy the standard truth tables for each expression.
  1. \(\displaystyle P \land Q\)
  2. \(\displaystyle P \lor Q\)
  3. \(\displaystyle P \oplus Q\)

2. Practice.

For this exercise, \(n\) is a specific (but unknown) integer, \(X\) is the statement “\(n\) is a multiple of 6”, and \(R\) is the statement “\(n\) is a multiple of 4”. In each part of this exercise write the statement using \(X\text{,}\) \(R\text{,}\) and logic symbols and find an example of an integer \(n\) for which the statement is true.
  1. The integer \(n\) is a multiple 6 and a multiple of 4.
  2. The integer \(n\) is a multiple of exactly one of 6 or 4.
Check.
  1. \(X \land R\) which is true when \(n=12\text{.}\) There are other correct examples.
  2. Hint: \(\oplus\)

3. Understand.

Recall that a graph is a tree if it is connected and acyclic.
  1. Give an example of a tree and explain what you have checked.
  2. Could a graph be connected but not a tree? Give an example and explain in words.
  3. Could a graph be acyclic but not a tree? Give an example and explain in words.

4. Understand.

 
  1. Construct a truth table for the compound statement \(P \lor (Q \land R)\text{.}\) Include an intermediate column for \(Q \land R\text{.}\)
  2. Compare your answer from 4.(a) with the completed truth table from Activity 5.1.B (d). Is \(P \lor (Q \land R) \equiv (P \lor Q) \land R\text{?}\) Explain.

5. Understand.

 
  1. Construct a truth table for \(P \land (Q \lor R)\text{.}\) Include an intermediate column for \(Q \lor R\text{.}\)
  2. Construct a truth table for \((P \land Q) \lor (P \land R)\text{.}\) Include intermediate columns for \(P \land Q\) and for \(P \land R\text{.}\)
  3. What do you notice?
Check.
  1. See Table 5.1.32.
    Table 5.1.32. Truth table for the compound statement \(P \land (Q \lor R)\)
    \(P\) \(Q\) \(R\) \(Q \lor R\) \(P \land (Q \lor R)\)
    \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\)
    \(\str{T}\) \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{T}\)
    \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{T}\) \(\str{T}\)
    \(\str{T}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\)
    \(\str{F}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{F}\)
    \(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{F}\)
    \(\str{F}\) \(\str{F}\) \(\str{T}\) \(\str{T}\) \(\str{F}\)
    \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{F}\)
  2. Hint: You should get the same final column as in 5.(a).
  3. They are logically equivalent.

6. Recap.

Do you know …
  1. What the symbols \(\land\text{,}\) \(\lor\text{,}\) and \(\oplus\) stand for?
  2. What the logical connectives “and”, “or”, and “xor” mean?
  3. When statements of the form \(P \land Q\) and \(P \lor Q\) are true and when they’re false?
  4. Why we might create a truth table?
  5. How to create a truth table for a compound logical statement?

Subsubsection Exercises for 5.1.C Proof Formats: And and Or Using Cases

8. Practice.

Use Theorem 5.1.12 to to prove that \(n^2+2n \fn{ mod } 4 = 0\) or \(n^2+2n \fn{ mod } 4 = 3\) for any integer \(n\text{.}\) Hint: Copy the proof in Activity 5.1.C (c) and edit as needed. Yes, this exercise repeats Activity 5.1.C (d).
Check.
Hint:
\begin{equation*} (2k)^2+2(2k) = 4k^2+4k = 4(\underline{\hspace{.5in}}) + 0 \end{equation*}
and
\begin{equation*} (2k+1)^2 + 2(2k+1) = 4k^2 + 8k + 3= 4(\underline{\hspace{.5in}}) + 3\text{.} \end{equation*}

9. Understand.

Use Theorem 5.1.11 to prove that \(3n+6\) is even and \(3 \mid (3n+6)\) for any integer \(n\text{.}\) Hint: Copy the proof in Activity 5.1.C (a) and edit as needed.
Check.
Hint: Make sure to copy all the words in the proof. During the proof, you will need to write \(3n+6 = 2(\underline{\hspace{.5in}})\) and \(3n+6 = 3(\underline{\hspace{.5in}})\text{.}\)

10. Understand.

Use Proof Format Theorem 5.1.13 to prove that for any integer \(n\) we have \(n^2 \fn{ mod } 5 = 0\text{,}\) \(n^2 \fn{ mod } 5 = 1\text{,}\) or \(n^2 \fn{ mod } 5 = 4\text{.}\) Hint: By the Division Algorithm \(n = 5q+r\) with \(0 \le r \lt 5\text{.}\) Break into five cases corresponding to \(r=0, 1, 2, 3\text{,}\) or \(4\text{.}\)
Check.
Hint: The five cases are Case 1: Assume \(n = 5q\text{;}\) Case 2: Assume \(n=5q+1\text{;}\) Case 3: Assume \(n=5q+2\text{;}\) Case 4: Assume \(n=5q+3\text{;}\) and Case 5: Assume \(n=5q+4\text{.}\) In Case 4, for example, we have
\begin{equation*} n^2=(5q+3)^2=25q^2+30q+9 \end{equation*}
\begin{equation*} =25q^2+30q+5+4=5(5q^2+6q+1)+4 \end{equation*}
and so \(n^2 \fn{ mod } 5 = 4\text{.}\) Notice how we cleverly rewrite \(9 = 5+4\text{.}\) That made it possible to factor 5 out of the 5 to show the remainder of 4.

11. Recap.

Do you know …
  1. How we prove a statement of the form \(P \land Q\text{?}\)
  2. How we prove a statement of the form \(P \lor Q\) using cases?

Subsubsection Exercises for 5.1.D Logical Equivalence and Negations

12. Practice.

Negate each statement about an integer \(k\text{.}\)
  1. \(\displaystyle k=10\)
  2. \(\displaystyle k>10\)
  3. \(k\) is odd
  4. \(\displaystyle 10 \mid k\)
Check.
  1. \(\displaystyle k \neq 10\)
  2. Hint: Make sure your answer includes the possibility that \(k=10\text{.}\)
  3. \(k\) is even.
  4. Hint: Use \(\nmid\text{.}\)

14. Understand.

For this exercise, \(n\) is a specific (but unknown) integer, \(X\) is the statement “\(n\) is a multiple of 6”, and \(R\) is the statement “\(n\) is a multiple of 4”. In each part of this exercise write the statement using \(X\text{,}\) \(R\text{,}\) and logic symbols and find an example of an integer \(n\) for which the statement is true.
  1. The integer \(n\) is not a multiple of 6.
  2. The integer \(n\) is a multiple of 6, but not a multiple of 4.
  3. The integer \(n\) is a multiple of 4, but not a multiple of 6.
  4. The integer \(n\) is not a multiple of 4 or 6.
Check.
  1. \(\neg X\) An example is \(n=10\text{.}\) There are other correct examples.
  2. Hint: See Remark 5.1.21 and use \(\nmid\text{.}\) Include an example.
  3. Hint: \(R \land \neg X\text{.}\) Include an example.
  4. Hint: You may use parentheses in your answer, but there is also a way to write it without parentheses. Include an example.

15. Practice.

 
  1. Use a truth table to show that \(P \lor \neg P\) is a tautology.
  2. Draw a truth table for \(P \lor \neg Q\text{.}\) Include an intermediate column for \(\neg Q\text{.}\)
  3. Draw a truth table for \(\neg P \land Q\text{.}\) Include an intermediate column for \(\neg P\text{.}\)
Check.
  1. Hint: The truth table only needs two rows and is similar to the table in Table 5.1.20.
  2. Hint: The truth table needs four rows and is similar to the table in Table 5.1.19. The last column should have three \(\str{T}\) and one \(\str{F}\text{.}\)
  3. Hint: The last column should have one \(\str{T}\) and three \(\str{F}\text{.}\)

16. Understand.

In Activity 5.1.D we verified the first of De Morgan’s Laws Theorem 5.1.23. Construct truth tables to verify the second equivalence
\begin{equation*} \neg(P \lor Q) \equiv \neg P \land \neg Q\text{.} \end{equation*}
Include some intermediate columns.
Check.
Hint: One way to set up the truth table is shown in Table 5.1.44. Feel free to copy the table, check the third row, and then fill in the remaining entries.
Table 5.1.44. Truth table for the compound statement \(P \land (Q \lor R)\)
\(P\) \(Q\) \(P \lor Q\) \(\neg(P \lor Q)\) \(\neg P\) \(\neg Q\) \(\neg P \land \neg Q\)
\(\str{T}\) \(\str{T}\)
\(\str{T}\) \(\str{F}\)
\(\str{F}\) \(\str{T}\) \(\str{T}\) \(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{F}\)
\(\str{F}\) \(\str{F}\)

17. Recap.

Do you know …
  1. What it means for statements to be logically equivalent and how we might use a truth table to verify an equivalence?
  2. What a tautology or contradiction is and how to verify that a statement is a tautology or contradiction using a truth table.
  3. What the negation of a statement is?
  4. What the symbols \(\neg\) and \(\equiv\) mean?
  5. How the construction \(\land \neg\) is translated into words.
  6. How to find the negation of \(P \land Q\) and \(P \lor Q\) and what those equivalences are called?

18. Explore.

 
  1. Find a statement that is logically equivalent to \(P \oplus Q\) but does not use \(\oplus\text{.}\) You may use \(\land\text{,}\) \(\lor\text{,}\) \(\neg\text{,}\) and parentheses.
  2. Use a truth table to verify that the statements are equivalent.
  3. What is the negation of the statement \(P \oplus Q\text{?}\) Describe the negation using \(\land\text{,}\) \(\lor\text{,}\) and \(\neg\text{.}\)

Subsubsection Exercises for 5.1.E Proof Format: Contradiction

19. Practice.

Use a proof by contradiction Theorem 5.1.24 to prove that there do not exist three distinct digits whose sum is equal to 25. This statement was one of the true/false questions in Activity 5.1.A (b). Hint: The negation would be that there exist three distinct digits whose sum is 25. What is the largest possible set of three distinct digits and what is their sum?
Check.
Hint: Copy this proof filling in the missing parts.
Proof.
Suppose not. Then there exist three distinct digits whose sum is equal to 25.
On the other hand, the largest possible set of three distinct digits is \(\{ \underline{\hspace{.1in}}, \underline{\hspace{.1in}}, \underline{\hspace{.1in}}\}\) and their sum is \(\underline{\hspace{.1in}} + \underline{\hspace{.1in}}+\underline{\hspace{.1in}}=\underline{\hspace{.1in}} \lt 25\text{.}\)
This is a contradiction. Therefore, there do not exist three distinct digits whose sum is equal to 25.

20. Practice.

We have nine coins and four cups. We place each coin in a cup. Use Theorem 5.1.24 to prove that some cup has three or more coins. Hint: The negation would be that each cup has two or fewer coins.

21. Practice.

Use a proof by contradiction Theorem 5.1.24 to prove that there cannot exist a 3-regular graph of order 7. Hint: By Theorem 3.2.5, the number of edges in a graph is equal to half of the sum of the degrees of the vertices. On the other hand, the number of edges must be an integer.
Check.
Hint: If there were such a graph, the sum of the degrees of the vertices would be
\begin{equation*} 3+3+3+3+3+3+3=7(3)=21\text{.} \end{equation*}
Then, use the hint.

22. Understand.

 
  1. Use a proof by contradiction Theorem 5.1.24 to prove that every bit string of length five has at least three \(\bs{0}\) s or at least three \(\bs{1}\) s. Hint: The negation would be that there exists a bit string of length five with fewer than three \(\bs{0}\)s and fewer than three \(\bs{1}\)s. What is the longest such possible bit string?
  2. Why does the negation use “and”?
Check.
  1. Hint: In the hint “fewer than three \(\bs{0}\) s” means the number of \(\bs{0}\) s is less than or equal to two.
  2. Hint: DeMorgan’s Law.

23. Understand.

Suppose \(a\) and \(b\) are coprime integers and \(p\) is a positive prime. Use a proof by contradiction Theorem 5.1.24 to prove that \(p \nmid a\) or \(p \nmid b\text{.}\) Hint: Be careful negating the “or” statement.
Check.
Hint: If \(p \mid a\) and \(p \mid b\text{,}\) then \(p\) is a positive common divisor of \(a\) and \(b\) that is greater than one. What does that tell you about \(\fn{gcd}(a,b)\text{?}\)

24. Recap.

Do you know …
  1. Why \(Q \land \neg Q\) is a contradiction?
  2. How to write a proof by contradiction?
  3. How we can begin a proof by contradiction so the reader knows that we are doing a proof by contradiction?
  4. Why the phrase “On the other hand” is used in a proof by contradiction?

25. Explore.

Use a proof by contradiction Theorem 5.1.24 to prove that an integer \(n\) cannot be even and odd. Hint: If \(n\) is even, use the definition of even to write \(n = 2k\) for some integer \(k\text{.}\) If \(n\) is odd, use the definition of odd to write \(n=2q+1\) for some integer \(q\text{.}\) Do not use \(k\) again. Put these equations together to get \(2k=2q+1\text{.}\) Next, solve for 1 to show that \(2 \mid 1\text{.}\) On the other hand, the only divisors of 1 are \(\pm1\text{.}\)

26. Explore.

Copy the following proof and fill in the blanks.
 2 
Thanks to Oscar Levin for the idea for this exercise.
Prove that \(\fn{lg}(3)\) is irrational.
Proof.
Suppose not. Then \(\fn{lg}(3)\) is . By the definition of rational numbers Definition 4.1.12, we can write
\begin{equation*} \fn{lg}(3) = \frac{s}{t} \end{equation*}
for some integers \(s\) and \(t\) with \(t \neq 0\text{.}\) Using the definition of \(\str{lg}\) Definition 2.4.17, we can write
\begin{equation*} 2^{^{\frac{s}{t}}} = \underline{\hspace{.5 in}}\text{.} \end{equation*}
Raising both sides of this equation to the power \(t\) we get
\begin{equation*} 2^s = \underline{\hspace{.5 in}} \end{equation*}
On the other hand, any power of two is even and so is even and any power of three is odd and so is odd. By Exercise 25, an integer cannot be even and odd. Thus,
\begin{equation*} 2^s \neq \underline{\hspace{.5 in}} \end{equation*}
This is a contradiction. Thus, \(\fn{lg}(3)\) is irrational.

27. Explore.

  Copy the following proof and fill in the blanks.
Prove that there are infinitely many primes.
Proof.
Suppose not. Then there would be a number of primes, so we could list all of them. Suppose that the list of all primes were \(p_1,p_2,p_3, \ldots,p_k\text{.}\) Consider the positive integer
\begin{equation*} n = p_1p_2p_3\cdots p_k \end{equation*}
First, \(n = p_1(p_2p_3\cdots p_k)\) so by the definition of \(\underline{\hspace{1in}}\) it follows that \(p_1 \mid n\text{.}\) Since \(p_1\) is prime, we know that \(p_1 > 1\text{.}\) By Exercise 17, we know that \(\fn{gcd}(n,n+1) = \underline{\hspace{1in}}\text{.}\) Since \(p_1 > 1\) and \(p_1 \mid n\text{,}\) it follows that \(p_1 \nmid (n+1)\text{.}\) For each value of \(i = 1, 2, \ldots k\text{,}\) the same argument shows that \(p_i >1\) and \(p_i \mid n\) and so \(p_i \nmid (n+1)\text{.}\) Therefore, none of the primes \(p_1,p_2,p_3, \ldots, p_k\) divides \(\underline{\hspace{1in}}\text{.}\)
On the other hand, \(p_1,p_2,p_3, \ldots,p_k\) are the only primes. It follows that \(n+1\) has no prime divisors. Since \(n\) is positive, we know \(n+1>1\text{.}\) This is a contraction of Theorem 4.4.11 which says \(\underline{\hspace{1in}}\text{.}\)
PrevTopNext