Use equivalence rules to show that the following compound propositions are tautologies. Do not use truth tables. (a) (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r)

Steps to Solve

1. Identify the implications in the expression

The given expression is $(p \lor q) \land (\neg p \lor r) \rightarrow (q \lor r)$. We can rewrite the implication in terms of disjunction:

$A \rightarrow B \equiv \neg A \lor B$

Thus, we rewrite:

$$(\neg ((p \lor q) \land (\neg p \lor r))) \lor (q \lor r)$$

2. Apply De Morgan's Laws

Now, we apply De Morgan's laws to the negation:

$$\neg (X \land Y) \equiv \neg X \lor \neg Y$$

Setting $X = p \lor q$ and $Y = \neg p \lor r$, we have:

$$(\neg (p \lor q) \lor \neg (\neg p \lor r)) \lor (q \lor r)$$

Which simplifies to:

$$(\neg (p \lor q) \lor (p \land \neg r)) \lor (q \lor r)$$

3. Further simplify the expression

Recall that $\neg (p \lor q) \equiv \neg p \land \neg q$. Thus:

$$((\neg p \land \neg q) \lor (p \land \neg r)) \lor (q \lor r)$$

4. Rearranging terms

Now we'll rearrange the expression:

$$(\neg p \land \neg q) \lor (p \land \neg r) \lor q \lor r$$

This can be reorganized to show that it covers all cases:

$$(\neg p \land \neg q) \lor q \lor r \lor (p \land \neg r)$$

5. Analyze possible cases

In this case, we see that regardless of the truth values of $p$, $q$, or $r$, we can simplify and see that:

• If $q$ is true, the whole expression is true.
• If $r$ is true, it remains true.
• If $q$ and $r$ are both false, $\neg p$ must be true (which means $p$ is false).

Thus, regardless of the truth values assigned to $p$, $q$, and $r$, the overall expression is satisfied.