Key Concepts and Formulas

• Tautology: A statement that is always true, regardless of the truth values of its component propositions.
• Truth Tables: A table that lists all possible combinations of truth values for the component propositions and the resulting truth value of the compound proposition.
• Logical Equivalences:
  • $P \to Q \equiv \neg P \vee Q$
  • $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$ (De Morgan's Law)
  • $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$ (De Morgan's Law)
  • $P \vee (P \wedge Q) \equiv P$ (Absorption Law)
  • $P \wedge (P \vee Q) \equiv P$ (Absorption Law)
  • $P \vee \text{False} \equiv P$
  • $P \wedge \text{True} \equiv P$
  • $P \vee \text{True} \equiv \text{True}$
  • $P \wedge \text{False} \equiv \text{False}$
  • $P \vee \neg P \equiv \text{True}$
  • $P \wedge \neg P \equiv \text{False}$

Step-by-Step Solution

We will analyze each option to determine if it is a tautology.

Option A: $P \wedge (P \vee Q)$

Step 1: Construct the truth table for $P \wedge (P \vee Q)$.

• We need to consider all possible combinations of truth values for $P$ and $Q$.
• We calculate $P \vee Q$ first, then $P \wedge (P \vee Q)$.

Step 2: Analyze the truth table.

• The last column, representing $P \wedge (P \vee Q)$, is not always true. It is only true when P is true.
• Therefore, option A is not a tautology.
• Note that $P \wedge (P \vee Q) \equiv P$ (Absorption Law).

Option B: $P \vee (P \wedge Q)$

Step 1: Construct the truth table for $P \vee (P \wedge Q)$.

• We need to consider all possible combinations of truth values for $P$ and $Q$.
• We calculate $P \wedge Q$ first, then $P \vee (P \wedge Q)$.

Step 2: Analyze the truth table.

• The last column, representing $P \vee (P \wedge Q)$, is not always true. It is only true when P is true.
• Therefore, option B is not a tautology.
• Note that $P \vee (P \wedge Q) \equiv P$ (Absorption Law).

Option C: $Q \to (P \wedge (P \to Q))$

Step 1: Rewrite the expression using logical equivalences.

• $Q \to (P \wedge (P \to Q)) \equiv \neg Q \vee (P \wedge (\neg P \vee Q))$

Step 2: Simplify the expression.

• $\neg Q \vee (P \wedge (\neg P \vee Q)) \equiv \neg Q \vee ((P \wedge \neg P) \vee (P \wedge Q))$
• $\neg Q \vee ((P \wedge \neg P) \vee (P \wedge Q)) \equiv \neg Q \vee (False \vee (P \wedge Q))$
• $\neg Q \vee (False \vee (P \wedge Q)) \equiv \neg Q \vee (P \wedge Q)$
• $\neg Q \vee (P \wedge Q) \equiv (\neg Q \vee P) \wedge (\neg Q \vee Q)$
• $(\neg Q \vee P) \wedge (\neg Q \vee Q) \equiv (\neg Q \vee P) \wedge True$
• $(\neg Q \vee P) \wedge True \equiv \neg Q \vee P$
• $P \vee \neg Q$ is not a tautology.

Step 3: Construct the truth table for $\neg Q \vee P$.

Step 4: Analyze the truth table.

• The last column, representing $\neg Q \vee P$, is not always true.
• Therefore, option C is not a tautology.

Option D: $(P \wedge (P \to Q)) \to Q$

Step 1: Rewrite the expression using logical equivalences.

• $(P \wedge (P \to Q)) \to Q \equiv (P \wedge (\neg P \vee Q)) \to Q$
• $(P \wedge (\neg P \vee Q)) \to Q \equiv \neg (P \wedge (\neg P \vee Q)) \vee Q$

Step 2: Simplify the expression.

• $\neg (P \wedge (\neg P \vee Q)) \vee Q \equiv \neg ((P \wedge \neg P) \vee (P \wedge Q)) \vee Q$
• $\neg ((P \wedge \neg P) \vee (P \wedge Q)) \vee Q \equiv \neg (False \vee (P \wedge Q)) \vee Q$
• $\neg (False \vee (P \wedge Q)) \vee Q \equiv \neg (P \wedge Q) \vee Q$
• $\neg (P \wedge Q) \vee Q \equiv (\neg P \vee \neg Q) \vee Q$
• $(\neg P \vee \neg Q) \vee Q \equiv \neg P \vee (\neg Q \vee Q)$
• $\neg P \vee (\neg Q \vee Q) \equiv \neg P \vee True$
• $\neg P \vee True \equiv True$

Step 3: Analyze the simplified expression.

• Since the expression simplifies to True, it is a tautology.

Common Mistakes & Tips

• Be careful with the order of operations when applying logical equivalences.
• Remember De Morgan's Laws and Absorption Laws to simplify expressions.
• When using truth tables, ensure you cover all possible combinations of truth values.
• Recognizing common patterns and equivalences can greatly simplify the process.

Summary

We analyzed each option to determine if it is a tautology. Options A, B, and C were shown not to be tautologies. Option D, after simplification using logical equivalences, resulted in True, indicating that it is a tautology.

Final Answer The final answer is \boxed{(P \wedge (P \to Q)) \to Q}, which corresponds to option (D).