Key Concepts and Formulas

• Tautology: A statement that is always true, regardless of the truth values of its components.
• Conditional Statement: $p \rightarrow q \equiv \sim p \vee q$ (If p, then q is equivalent to not p or q).
• De Morgan's Laws:
  • $\sim(p \wedge q) \equiv \sim p \vee \sim q$
  • $\sim(p \vee q) \equiv \sim p \wedge \sim q$
• Commutative Laws: $p \vee q \equiv q \vee p$ and $p \wedge q \equiv q \wedge p$
• Associative Laws: $(p \vee q) \vee r \equiv p \vee (q \vee r)$ and $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$
• Identity Laws: $p \vee T \equiv T$ and $p \wedge F \equiv F$, where T represents True and F represents False.
• Absorption Law: $p \vee (p \wedge q) \equiv p$ and $p \wedge (p \vee q) \equiv p$

Step-by-Step Solution

We will evaluate each option to determine which is a tautology.

Option (A): $p \vee (p \wedge q)$

• Step 1: Simplify the expression using the absorption law.
  • We are applying the absorption law: $p \vee (p \wedge q) \equiv p$.
  • $p \vee (p \wedge q) \equiv p$
• Step 2: Analyze if the simplified expression is a tautology.
  • The expression simplifies to $p$. This is not a tautology because its truth value depends on the truth value of $p$. If $p$ is false, the expression is false.

Therefore, option (A) is not a tautology.

Option (B): $(p \wedge (p \rightarrow q)) \rightarrow \sim q$

• Step 1: Replace $p \rightarrow q$ with its equivalent form $\sim p \vee q$.
  • We are using the conditional statement equivalence: $p \rightarrow q \equiv \sim p \vee q$.
  • $(p \wedge (\sim p \vee q)) \rightarrow \sim q$
• Step 2: Distribute $p$ over $(\sim p \vee q)$.
  • We are applying the distributive law: $p \wedge (\sim p \vee q) \equiv (p \wedge \sim p) \vee (p \wedge q)$.
  • $((p \wedge \sim p) \vee (p \wedge q)) \rightarrow \sim q$
• Step 3: Simplify $p \wedge \sim p$ to $F$ (False).
  • $((F) \vee (p \wedge q)) \rightarrow \sim q$
• Step 4: Simplify $F \vee (p \wedge q)$ to $(p \wedge q)$.
  • $(p \wedge q) \rightarrow \sim q$
• Step 5: Replace the conditional with its equivalent form.
  • We are using the conditional statement equivalence: $p \rightarrow q \equiv \sim p \vee q$.
  • $\sim (p \wedge q) \vee \sim q$
• Step 6: Apply De Morgan's Law.
  • $\sim p \vee \sim q \vee \sim q$
• Step 7: Simplify $\sim q \vee \sim q$ to $\sim q$.
  • $\sim p \vee \sim q$
• Step 8: Analyze if the simplified expression is a tautology.
  • The expression simplifies to $\sim p \vee \sim q$, which is not a tautology because its truth value depends on the truth values of $p$ and $q$. For example, if $p$ and $q$ are both true, the expression is false.

Therefore, option (B) is not a tautology.

Option (C): $p \rightarrow (p \wedge (p \rightarrow q))$

• Step 1: Replace $p \rightarrow q$ with its equivalent form $\sim p \vee q$.
  • We are using the conditional statement equivalence: $p \rightarrow q \equiv \sim p \vee q$.
  • $p \rightarrow (p \wedge (\sim p \vee q))$
• Step 2: Replace the conditional with its equivalent form.
  • We are using the conditional statement equivalence: $p \rightarrow q \equiv \sim p \vee q$.
  • $\sim p \vee (p \wedge (\sim p \vee q))$
• Step 3: Distribute $p$ over $(\sim p \vee q)$.
  • $\sim p \vee ((p \wedge \sim p) \vee (p \wedge q))$
• Step 4: Simplify $p \wedge \sim p$ to $F$ (False).
  • $\sim p \vee (F \vee (p \wedge q))$
• Step 5: Simplify $F \vee (p \wedge q)$ to $(p \wedge q)$.
  • $\sim p \vee (p \wedge q)$
• Step 6: This can be rewritten as $(\sim p \vee p) \wedge (\sim p \vee q)$.
• Step 7: Since $\sim p \vee p$ is always true, we can replace it with $T$.
  • $T \wedge (\sim p \vee q)$
• Step 8: Simplify $T \wedge (\sim p \vee q)$ to $(\sim p \vee q)$
  • $(\sim p \vee q)$
• Step 9: Analyze if the simplified expression is a tautology.
  • The expression simplifies to $\sim p \vee q$, which is not a tautology because its truth value depends on the truth values of $p$ and $q$. For example, if $p$ is true and $q$ is false, the expression is false.

Therefore, option (C) is not a tautology.

Option (D): $(p \wedge q) \rightarrow (\sim p \rightarrow q)$

• Step 1: Replace $\sim p \rightarrow q$ with its equivalent form $\sim (\sim p) \vee q$, which simplifies to $p \vee q$.
  • We are using the conditional statement equivalence: $p \rightarrow q \equiv \sim p \vee q$.
  • $(p \wedge q) \rightarrow (p \vee q)$
• Step 2: Replace the conditional with its equivalent form.
  • $\sim (p \wedge q) \vee (p \vee q)$
• Step 3: Apply De Morgan's Law.
  • $(\sim p \vee \sim q) \vee (p \vee q)$
• Step 4: Rearrange the terms using the commutative and associative laws.
  • $(\sim p \vee p) \vee (\sim q \vee q)$
• Step 5: Simplify $\sim p \vee p$ and $\sim q \vee q$ to $T$ (True).
  • $T \vee T$
• Step 6: Simplify $T \vee T$ to $T$.
  • $T$
• Step 7: Analyze if the simplified expression is a tautology.
  • The expression simplifies to $T$, which is a tautology.

Therefore, option (D) is a tautology.

Common Mistakes & Tips

• Remember to use the correct logical equivalences when simplifying expressions.
• Pay attention to the order of operations (parentheses, negation, conjunction/disjunction, implication).
• When in doubt, create a truth table to verify your results.

Summary

We analyzed each of the given options and determined that option (D), $(p \wedge q) \rightarrow (\sim p \rightarrow q)$, simplifies to T (True), and therefore is a tautology.

Final Answer

The final answer is \boxed{D}, which corresponds to option (D).