Skip to main content

Section 5.5 Excursion: Equivalence and Inference

Logical equivalences such as Demorgan’s laws Theorem 5.1.23 and the broken promise Theorem 5.3.17 help us negate statements, which is useful for constructing counterexamples to false statements, for writing proofs by contradiction, and for stating the contrapositive. The contrapositive equivalence Theorem 5.4.14 and implication equivalence Theorem 5.3.11 gave us new proof formats for proving conditionals and “or” statements, respectively. Logical equivalences can also help simplify complicated compound statements, which has applications to computer science. In this section, we return to discuss logical equivalences in more detail and also introduce logical inference.

Subsection 5.5.A Logical Equivalence

In this section, we look at a long list of logical equivalences and see how to derive new logical equivalences from this list. We begin by introducing some new logical equivalences involving negations, tautologies, and contradictions.
These logical equivalences can be confirmed using a truth table, but they should also make sense. Let’s look closely at a couple of these equivalences.

Example 5.5.2 Understanding logical equivalences: negation, tautology, and contradiction.

For each equivalence from Theorem 5.5.1, explain words why it is true. Recall that by Definition 5.1.15 that two statements are logical equivalent if they have the same truth values and so we can check if one statement is true, then so is the other and if one statement is false, then so is the other.
  1. \(P \lor P \equiv P\)
    Solution.
    If \(P \lor P\) is true, then either \(P\) is true or \(P\) is true. In either case, \(P\) is true. If \(P \lor P\) is false, then \(P\) is false and \(P\) is false. (We used Demorgan’s laws, Theorem 5.1.23 to negate the “or”.) In either case \(P\) is false. Thus, \(P \lor P \equiv P\text{.}\)
  2. \(\neg (\neg P) \equiv P\)
    Solution.
    If \(\neg (\neg P)\) is true, then by definition of negation Definition 5.1.16 \(\neg P\) is false and so \(P\) is true. If \(\neg (\neg P)\) is false, then by definition of negation Definition 5.1.16 \(\neg P\) is true and so \(P\) is false. Thus, \(\neg (\neg P) \equiv P\)
  3. \(P \land \str{F} \equiv \str{F}\)
    Solution.
    For the statement \(P \land \str{F}\) to be true, we would need both \(P\) and \(\str{F}\) to be true. But \(\str{F}\) is a contradiction so it is always false. Therefore \(P \land \str{F}\) is also always false. That is, \(P \land \str{F} \equiv \str{F}\text{.}\)
The equivalence in Definition 5.1.15 (a), for example, is one of several equivalences that have names that may be familiar since we used the same names in integer algebra Definition 2.1.20.
Each of the statements in Theorem 5.5.3 can be confirmed using a truth table.
For reference, we repeat the implication and contraposition logical equivalences here.
We also repeat the equivalences that help us negate compound statements.
We can use this long list of equivalences to prove new equivalences.

Activity 5.5.A Proofs of Logical Equivalences.

 
  1. Many lists of equivalences omit contraposition because it can be proved from the other equivalences. Fill in the missing equivalences to prove contraposition.

    Proof.
    \(P \to Q\) \(\equiv \neg P \lor Q\) using
    \(\equiv Q \lor \neg P\) using
    \(\equiv \neg (\neg Q) \lor \neg P\) using
    \(\equiv \neg Q \to \neg P\) using
  2. Fill in the missing steps of the proof using the given equivalences. What new equivalence did we just prove?

    Proof.
    \(P \to (Q \land R) \) \(\equiv\) using implication
    \(\equiv \) using the distributive property
    \(\equiv \) using implication (twice)
  3. Fill in the missing equivalences to prove
    \begin{equation*} ((P \land (P \to Q)) \to Q) \equiv \str{T}\text{.} \end{equation*}
    This tautology shows that modus ponens (which we will see in Theorem 5.5.11 (d)) is valid.

    Proof.
    \((P \land (P \to Q)) \to Q\) \(\equiv(P \land (\neg P \lor Q)) \to Q\)
    \(\) using
    \(\equiv ((P \land \neg P) \lor (P \land Q)) \to Q\)
    \(\) using \(\underline{\hspace{1in}} \)
    \(\equiv(\str{F} \lor (P \land Q)) \to Q\)
    \(\) using \(\underline{\hspace{1in}} \)
    \(\equiv (P \land Q) \to Q\)
    \(\) using \(\underline{\hspace{1in}} \)
    \(\equiv \neg(P \land Q) \lor Q\)
    \(\) using \(\underline{\hspace{1in}} \)
    \(\equiv(\neg P \lor \neg Q) \lor Q\)
    \(\) using \(\underline{\hspace{1in}} \)
    \(\equiv \neg P \lor (\neg Q \lor Q)\)
    \(\) using \(\underline{\hspace{1in}} \)
    \(\equiv \neg P \lor \str{T}\)
    \(\) using \(\underline{\hspace{1in}} \)
    \(\equiv \str{T}\)
    \(\) using \(\underline{\hspace{1in}} \)
Make sure to complete Activity 5.5.A because we are about to reveal some of the answers.

Example 5.5.7 Proofs of Logical Equivalences.

 
  1. Many lists of equivalences omit contraposition because it can be proved from the other equivalences. Prove contraposition using other equivalences This was Activity 5.5.A (a).
    Solution.
    Proof:
    \(P \to Q\) \(\equiv \neg P \lor Q\) using implication
    \(\equiv Q \lor \neg P\) using the commutative property
    \(\equiv \neg (\neg Q) \lor \neg P\) using double negation
    \(\equiv \neg Q \to \neg P\) using implication
  2. Fill in the missing steps of the proof using the given equivalences to prove
    \begin{equation*} P \to (Q \land R) \equiv (P \to Q) \land (P \to R) \end{equation*}
    This was Activity 5.5.A (b).
    Solution.
    Proof.
    \(P \to (Q \land R)\) \(\equiv \neg P \lor (Q \land R)\) using implication
    \(\equiv (\neg P \lor Q) \land (\neg P \lor R)\) using the distributive property
    \(\equiv (P \to Q) \land (P \to R)\) using implication (twice)

Subsection 5.5.B Simplifying Negations

We can use logical equivalences to simplify the negation of a statement.

Example 5.5.8 Negating a complicated statement.

Negate the statement
\begin{equation*} (P \lor R) \land (Q \lor\neg R) \end{equation*}
and simplify your negation so that there are no negation signs in front of parentheses. State which equivalences you use.
Solution.
\(\neg ((P \lor R) \land (Q \lor \neg R))\) \(\equiv \neg (P \lor R) \lor \neg (Q \lor \neg R)\)
using De Morgan’s laws
\(\equiv (\neg P \land \neg R) \lor (\neg Q \land \neg (\neg R))\)
using De Morgan’s laws (twice)
\(\equiv (\neg P \lor \neg R) \land (\neg Q \lor R)\)
using double negation.

Activity 5.5.B Simplifying complicated statements.

Negate each statement and use logical equivalences to simplify your negation so that there are no negation signs in front of parentheses. State which equivalences you use.
  1. \(\displaystyle P \lor \neg Q\)
  2. \(\displaystyle \neg P \to Q\)
  3. \(\displaystyle P \land (Q \to R)\)

Subsection 5.5.C Logical Inference

The primary tool that drives our explanations in proofs are logical inferences.

Definition 5.5.10 Logical Inferences.

 
  1. For statements \(S\) and statement \(C\text{,}\) a logical inference, denoted
    \begin{equation*} S \implies C\text{,} \end{equation*}
    is a rule saying if we know that statement \(S\) is true, then we can conclude that statement \(C\) is also true. For example, in Example 5.3.7 (d) we proved that \((P \land Q) \to P\) is a tautology. Therefore, if we know that \(S=P \land Q\) is true, we can conclude that \(C=P\) is true. We write
    \begin{equation*} P \land Q \implies P\text{.} \end{equation*}
    (This inference is Theorem 5.5.11 (a).)
  2. An logical inference can also involve multiple statements. That is, for statements \(S_1\text{,}\) \(S_2\text{,}\) …, \(S_k\text{,}\) and \(C\text{.}\) The logical inference
    \begin{equation*} \left. \begin{array}{c} S_1 \\ S_2 \\ \vdots \\ S_k \end{array} \right\} \implies C \end{equation*}
    means that if we know that statements \(S_1\text{,}\) \(S_2\text{,}\) …, \(S_k\) are true, then we can conclude that statement \(C\) is also true. For example, if we know that \(P\) is true and \(Q\) is true, then we can conclude that \(P \land Q\) is true. We write
    \begin{equation*} \left. \begin{array}{cc} P \\ Q \end{array} \right\} \implies P \land Q\text{.} \end{equation*}
    (This inference is Theorem 5.5.11 (c).)
  3. A logical inference \(S \implies C\) is valid if the corresponding conditional statement \(S \to C\) is a tautology or, equivalently, if \((S \to C) \equiv \str{T}\text{.}\) For example, \((P \land Q) \implies P\) is a valid inference because \((P \land Q) \to P\) is a tautology.
There are five key logical inferences.
We explained why simplification and conjunction are valid in Definition 5.5.10. Let’s look at why modus ponens is valid.

Example 5.5.12 Why modus ponens is valid.

We proved modus ponens in Activity 5.5.A (c) using equivalences. In this example, we look at two different ways to show that modus ponens is a valid inference.
  1. Explain in words why modus ponens makes sense.
    Solution.
    Suppose we know that \(P\) is true and that \(P \to Q\) is true. The statement \(P \to Q\) promises that if \(P\) is true, then \(Q\) is guaranteed to be true. Since \(P\) is indeed true, it follows that \(Q\) is true.
  2. Prove modus ponens is valid using a truth table.
    Solution.
    To prove modus ponens is valid, we need to prove that \((P \land (P \to Q)) \to Q\) is a tautology. The truth table is shown in Table 5.5.13. Notice that the last column is all \(\str{T}\text{,}\) so \((P \land (P \to Q)) \to Q\) is a tautology. Therefore, modus ponens is valid.
    Table 5.5.13. Truth table showing modus ponens is valid for Example 5.5.12 (b)
    \(P\) \(Q\) \(P \to Q\) \(P \land (P \to Q)\) \((P \land (P \to Q)) \to Q\)
    \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\) \(\str{T}\)
    \(\str{T}\) \(\str{F}\) \(\str{F}\) \(\str{F}\) \(\str{T}\)
    \(\str{F}\) \(\str{T}\) \(\str{T}\) \(\str{F}\) \(\str{T}\)
    \(\str{F}\) \(\str{F}\) \(\str{T}\) \(\str{F}\) \(\str{T}\)
Let’s look at how to use logical inferences to write proofs.

Example 5.5.14 Validity of modus tollens.

Prove modus tollens is valid using equivalences and the other inferences.
Solution.
We want to prove that if \(P \to Q\) and \(\neg Q\) are each true, then \(\neg P\) is true. As we work through the proof, let’s number each statement for future reference.
Proof. Assume ① \(P \to Q\) and ② \(\neg Q\text{.}\)
By ① and contraposition Theorem 5.4.14, it follows that ③ \(\neg Q \to \neg P\text{.}\)
By ② , ③ , and modus ponens, it follows that \(\neg P\text{.}\)    \(\Box\)
Your turn to work with logical inferences.

Activity 5.5.C Proofs with equivalences and inferences.

 
  1. Fill in the missing inferences to prove \(P \land Q \implies P \lor Q\text{.}\)

    Proof.
    Assume ① \(P \land Q\text{.}\)
    By ① and it follows that ② \(P\text{.}\)
    By ② and ,
    it follows that \(P \lor Q\text{.}\)   \(\Box\)
  2. Fill in the missing conclusions to prove the transitivity inference
    \begin{equation*} \left. \begin{array}{cc} P \to Q \\ Q \to R \end{array} \right\} \implies P \to R\text{.} \end{equation*}

    Proof.
    Assume ① \(P \to Q\) and ② \(Q \to R\text{.}\)
    We will use a direct proof Theorem 5.3.13 to prove \(P \to R\text{.}\)
    Assume ③ \(P\text{.}\)
    By ③ , ① , and modus ponens, it follows that ④ .
    By ④ , ② , and modus ponens, it follows that .
    Thus, \(P \to R\text{.}\)   \(\Box\)
  3. Fill in the missing equivalences, inferences, or conclusions to prove
    \begin{equation*} \left. \begin{array}{cc} \neg(Q \lor R) \\ P \to Q \end{array} \right\} \implies \neg (P \lor R)\text{.} \end{equation*}

    Proof.
    Assume ① \(\neg(Q \lor R)\) and ② \(P \to Q\text{.}\)
    By ① and DeMorgan’s Law it follows that ③ .
    By ③ and , it follows that ③ \(\neg Q\text{.}\)
    By ③ , ② , and modus tollens, it follows that ④ .
    By ③ and , it follows that ⑤ \(\neg R \land \neg Q\text{.}\)
    By ⑤ and simplification, it follows that ⑥ .
    By ④ , ⑥ , and conjunction, it follows that ⑦ .
    By ⑦ and , it follows that \(\neg(P \lor R)\)
Let’s look at the proof from Activity 5.5.C (c).

Example 5.5.16 Proof using equivalences and inferences.

Fill in the missing equivalences, inferences, or conclusions to prove
\begin{equation*} \left. \begin{array}{cc} \neg(Q \lor R) \\ P \to Q \end{array} \right\} \implies \neg (P \lor R) \end{equation*}
Solution.
Proof. Assume ① \(\neg(Q \lor R)\) and ② \(P \to Q\text{.}\)
By ① and DeMorgan’s Law it follows that ③ \(\neg Q \land \neg R\text{.}\)
By ③ and simplification, it follows that ③ \(\neg Q\text{.}\)
By ③ , ② , and modus tollens, it follows that ④ \(\neg P\text{.}\)
By ③ and the commutative property, it follows that ⑤ \(\neg R \land \neg Q\text{.}\)
By ⑤ and simplification, it follows that ⑥ \(\neg R\text{.}\)
By ④ , ⑥ , and conjunction, it follows that ⑦ \(\neg P \land \neg R\text{.}\)
By ⑦ and Demorgan’s laws, it follows that \(\neg(P \lor R)\text{.}\)

Subsection 5.5.D Exercises

Subsubsection Exercises for 5.5.A Logical Equivalence

1. Practice.

For each equivalence, explain words why it is true. Recall that by Definition 5.1.15 that two statements are logical equivalent if they have the same truth values and so we can check if one statement is true, then so is the other and if one statement is false, then so is the other.
  1. \(\displaystyle P \land P \equiv P\)
  2. \(\displaystyle P \land \str{T} \equiv P\)
  3. \(\displaystyle P \lor \str{T} \equiv \str{T}\)
Check.
  1. If \(P \land P\) is true, then \(P\) is true and \(P\) is true. That is, \(P\) is true. On the other hand, if \(P \land P\) is false, then \(P\) is false or \(P\) is false. That is, \(P\) is false.
  2. Hint: Follow the format from (a).
  3. Hint: Begin with “for the statement \(P \lor \str{T}\) to be false, we would need both …” It should never be false.

2. Practice.

Use a truth table to verify the associative property for \(\land\text{:}\)
\begin{equation*} P \land (Q \land R) \equiv (P \land Q) \land R\text{.} \end{equation*}
Include intermediate columns for \(Q \land R\) and \(P \land Q\text{.}\)
Check.
Hint: Your truth table should have seven columns: \(P\text{,}\) \(Q\text{,}\) \(R\text{,}\) \(Q \land R\text{,}\) \(P \land (Q \land R)\text{,}\) \(P \land Q\text{,}\) and \((P \land Q) \land R\text{.}\) Your truth table should have eight rows. The fifth column and the seventh column should match.

3. Understand.

 
  1. Explain in words why \(P \oplus Q \equiv (P \lor Q) \land \neg (P \land Q)\text{.}\)
  2. Use a truth table to verify that \(P \oplus Q \equiv (P \lor Q) \land \neg (P \land Q)\text{.}\)
Check.
  1. Hint: If \(P \oplus Q\) is true, then \(P\) is true or \(Q\) is true, but not both. Since at least one of \(P\) or \(Q\) is true, it follows that \(P \lor Q\) is true. Since not both are true, it follows that \(P \land Q\) is false. That is, \(\neg(P \land Q)\) is true. Thus, \((P \lor Q) \land \neg(P \land Q)\) is true. Now explain what happens if \(P \oplus Q\) is false.
  2. Hint: Your truth table should have seven columns \(P\text{,}\) \(Q\text{,}\) \(P \oplus Q\text{,}\) \(P \lor Q\text{,}\) \(P \land Q\text{,}\) \(\neg(P \land Q)\text{,}\) and \((P \lor Q) \land \neg (P \land Q)\text{.}\) Your truth table should have four rows. The third and seventh columns should match.

4. Understand.

Many lists of equivalences omit broken promise because it can be proved from the other equivalences. Fill in the missing equivalences to prove broken promise.
Proof.
\(\neg(P \to Q)\) \(\equiv \neg(\neg P \lor Q)\) using
\(\equiv \neg(\neg P) \land \neg Q\) using
\(\equiv P \land \neg Q\) using
Check.
Hint: The three reasons, in some order, are DeMorgan’s laws, double negation, and implication.

5. Understand.

Fill in the missing equivalences to prove \(P \to (Q \to R)\equiv (P \land Q) \to R\text{.}\)
Proof.
\(P \to (Q \to R)\) \(\equiv \neg P \lor (Q \to R)\) using
\(\equiv \neg P \lor (\neg Q \lor R)\) using
\(\equiv (\neg P \lor \neg Q) \lor R\) using
\(\equiv \neg(P \land Q) \lor R\) using
\(\equiv (P \land Q) \to R\) using
Check.
Hint: The proof uses the associative property, DeMorgan’s laws, and implication.

6. Understand.

This exercise repeats Activity 5.5.A (c). Fill in the missing equivalences to prove \(((P \land (P \to Q)) \to Q) \equiv \str{T}\text{.}\)
Proof.
\((P \land (P \to Q)) \to Q\) \(\equiv(P \land (\neg P \lor Q)) \to Q\)
\(\) using
\(\equiv ((P \land \neg P) \lor (P \land Q)) \to Q\)
\(\) using \(\underline{\hspace{1in}} \)
\(\equiv(\str{F} \lor (P \land Q)) \to Q\)
\(\) using \(\underline{\hspace{1in}} \)
\(\equiv (P \land Q) \to Q\)
\(\) using \(\underline{\hspace{1in}} \)
\(\equiv \neg(P \land Q) \lor Q\)
\(\) using \(\underline{\hspace{1in}} \)
\(\equiv(\neg P \lor \neg Q) \lor Q\)
\(\) using \(\underline{\hspace{1in}} \)
\(\equiv \neg P \lor (\neg Q \lor Q)\)
\(\) using \(\underline{\hspace{1in}} \)
\(\equiv \neg P \lor \str{T}\)
\(\) using \(\underline{\hspace{1in}} \)
\(\equiv \str{T}\)
\(\) using \(\underline{\hspace{1in}} \)
Check.
Hint: The first three reasons are, in some order, the distributive property, implication, and negation. Other reasons used include DeMorgan’s laws and identity.

7. Understand.

Use equivalences to simplify \((P \land Q) \lor (P \land \neg Q)\text{.}\)
Check.
Hint: Start with the distributive property to get
\begin{equation*} (P \land Q) \lor (P \land \neg Q) \equiv P \land (Q \lor \neg Q)\text{.} \end{equation*}
Next, use negation.

8. Understand.

Use equivalences to prove \(\neg(\neg Q \land P) \equiv P \to Q\text{.}\)

9. Recap.

Do you know …
  1. What it means for two statements to be logically equivalent?
  2. How to use a truth table to verify that a logical equivalence is valid?
  3. What the commutative, associative, and distributive properties tell us?
  4. What the double negation equivalence says?
  5. How to use logical equivalences to prove new logical equivalences?

10. Explore.

Use a truth table to verify the following equivalences involving xor.
  1. Commutative property \(P \oplus Q \equiv Q \oplus P\)
  2. Associative property \(P \oplus (Q \oplus R) \equiv (P \oplus Q) \oplus R\)

11. Explore.

For statements \(P\) and \(Q\text{,}\) the Sheffer stroke (nand), denoted \(P \mid Q\text{,}\) is defined by
\begin{equation*} P \mid Q \equiv \neg (P \land Q) \end{equation*}
  1. Construct a truth table for \(P \mid Q\text{.}\)
  2. Use equivalences to simplify \(P \mid \str{T}\) and \(P \mid \str{F}\text{.}\)
  3. Use equivalences to simplify \(Q \mid Q\text{.}\)
  4. Use equivalences to simplify \(P \mid (Q \mid Q)\text{.}\)

Subsubsection Exercises for 5.5.B Simplifying Negations

12. Practice.

Negate each statement and use logical equivalences to simplify your negation so that there are no negation signs in front of parentheses. State which equivalences you use.
  1. \(\displaystyle P \land \neg Q\)
  2. \(\displaystyle \neg P \lor \neg Q\)
  3. \(\displaystyle \neg P \to \neg Q\)
Check.
  1. The answer is \(\neg P \lor Q\) Show the steps of your work and state which equivalences you use.
  2. Hint: The answer has no negations.
  3. Hint: Use broken promise.

13. Understand.

Negate each statement and use logical equivalences to simplify your negation so that there are no negation signs in front of parentheses. State which equivalences you use.
  1. \(\displaystyle P \lor (Q \land R)\)
  2. \(\displaystyle (P \land R) \lor (Q \land \neg R)\)

14. Understand.

Negate each statement and use logical equivalences to simplify your negation so that there are no negation signs in front of parentheses. State which equivalences you use.
  1. \(\displaystyle P \to (Q \lor \neg R)\)
  2. \(\displaystyle (P \to Q) \land (R \to \neg Q)\)
Check.
  1. The answer is \(P \land (\neg Q \land R)\text{.}\) Show the steps of your work and state which equivalences you use.
  2. Hint: The answer includes \(\lor\text{.}\)

15. Recap.

Do you know …
  1. What DeMorgan’s laws say?
  2. What the broken promise equivalence says?
  3. How to simplify negations using equivalences?

16. Explore.

 
  1. Recall that \(P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)\text{.}\) Negate \(P \leftrightarrow Q\) and use logical equivalences to simplify your negation so that there are no negation signs in front of parentheses. State which equivalences you use.
  2. Recall that \(P \oplus Q \equiv (P \lor Q) \land \neg (P \land Q)\text{.}\) Negate \(P \oplus Q\) and use logical equivalences to simplify your negation so that there are no negation signs in front of parentheses. State which equivalences you use.
  3. What do you notice?

Subsubsection Exercises for 5.5.C Logical Inference

17. Practice.

Fill in the missing conclusions to prove \(P \land Q \implies Q\text{.}\)
Proof.
Assume ① \(P \land Q\text{.}\)
By ① and the commutative property it follows that ② .
By ② and simplification, it follows that .   \(\Box\)
Check.
\(Q \land P\text{,}\) \(Q\)

18. Practice.

Fill in the missing inferences to prove the inference
\begin{equation*} \left. \begin{array}{cc} P \\ P \to Q \\ P \to R \end{array} \right\} \implies Q \land R \end{equation*}
Proof.
Assume ① \(P\text{,}\) ② \(P \to Q\) and ③ \(P \to R\text{.}\)
By ① , ② , and , it follows that ④ \(Q\text{.}\)
By ① , ③ , and , it follows that ⑤ \(R\text{.}\)
By ④ , ⑤ , and , it follows that \(Q \land R\text{.}\)   \(\Box\)
Check.
Hint: The proof uses conjunction and modus ponens.

19. Practice.

 
  1. Use equivalences and inferences to prove
    \begin{equation*} \left. \begin{array}{c} P \\ P \to Q \\ Q \to R \end{array} \right\} \implies R\text{.} \end{equation*}
  2. Use equivalences and inferences from our lists to prove
    \begin{equation*} \left. \begin{array}{cc} P \land Q \\ P \to R \\ Q \to S \end{array} \right\} \implies R \land S\text{.} \end{equation*}
Check.
  1. Hint: The proof uses modus ponens twice.
  2. Hint: Use simplification, but be careful. It says \(P \land Q \implies P\text{.}\) If you later want to conclude \(Q\) instead, you need to use the commutative property first.

20. Understand.

 
  1. Explain in your own words why \(\left. \begin{array}{cc} P \lor Q \\ \neg P \end{array} \right\} \implies Q\text{.}\)
  2. Fill in the missing equivalences and inferences to prove
    \begin{equation*} \left. \begin{array}{cc} P \lor Q \\ \neg P \end{array} \right\} \implies Q \end{equation*}
    Proof.
    Assume ① \(P\lor Q\) and ② \(\neg P\text{.}\)
    By it follows from ① that \(\neg (\neg P) \lor Q\text{.}\)
    By , it follows that \(\neg P \to Q\text{.}\)
    We know \(\neg P\) from ② , so by it follows that \(Q\)

21. Understand.

Fill in the missing equivalences, inferences, or conclusions, to prove the inference that justifies proof by cases Theorem 4.2.12.
\begin{equation*} \left. \begin{array}{c} P \lor Q \\ P \to R \\ Q \to R \end{array} \right \} \implies R \end{equation*}
Proof.
Assume ① \(P \lor Q\text{,}\) ② \(P \to R\text{,}\) and ③ \(Q \to R\text{.}\)
By ② , ③ , and conjunction it follows that ④ .
By ④ and implication (twice), it follows that ⑤ .
By ⑤ and the commutative property (twice), it follows that ⑥ .
By ⑥ and the distributive property, it follows that ⑦ .
By ⑦ and the commutative property, it follows that ⑧ .
By ⑧ and Demorgan’s law, it follows that ⑨ .
By ⑧ and implication, it follows that ⑩ .
By ⑩ , ① , and it follows that \(R\text{.}\)
Check.
Hint: The first blank should say \((P \to R) \land (Q \to R)\text{.}\)

22. Understand.

Fill in the missing equivalences and inferences to prove
\begin{equation*} \left. \begin{array}{cc} P \land Q \\ \neg(\neg R \land P) \end{array} \right\} \implies P \land R \end{equation*}
Proof.
Assume ① \(P\land Q\) and ② \(\neg(\neg R \land P)\text{.}\)
By it follows from ② that \(\neg (\neg R) \lor \neg P\text{.}\)
By , it follows that \(R \lor \neg P\text{.}\)
By , it follows that \(\neg P \lor R\text{.}\)
By , it follows that \(P \to R\text{.}\)
By , it follows from ① that \(P\text{.}\)
By , it follows that \(R\text{.}\)

23. Understand.

Consider the inference
\begin{equation*} \left. \begin{array}{cc} P \to \neg Q \\ R \to (P \land Q) \end{array} \right\} \implies \neg R\text{.} \end{equation*}
Fill in the missing steps to prove it, using the equivalences and inferences given.
Proof.
Assume ① \(P \to \neg Q\) and ② \(R \to (P \land Q)\text{.}\)
By ① and implication, it follows that ③ .
By ② and DeMorgan’s laws, it follows that ④ .
By ② , ④ , modus tollens, it follows that .
Check.
Hint: The second blank is \(\neg(P \land Q)\text{.}\)

24. Understand.

  Use equivalences and inferences to prove
\begin{equation*} \left. \begin{array}{cc} \neg P \to Q \\ \neg P \to \neg Q \end{array} \right\} \implies P \end{equation*}
which is the inference that justifies proof by contradiction Theorem 5.1.24. Hint: Start with conjunction.
Check.
Hint: Use conjunction to get \((\neg P \to Q) \land (\neg P \to \neg Q)\text{.}\) Next, use implication (twice), double negation (twice), the distributive property, negation, and then identity.

25. Recap.

Do you know …
  1. What a logical inference is?
  2. How to use a truth table to verify a logical inference?
  3. What modus ponens and modus ponens say and how to use them in a proof?
  4. Why the simplification, conjunction, and addition inferences are valid?
  5. How to use logical equivalences and logical inferences to prove new logical inferences?
PrevTopNext