Key Concepts and Formulas

• Implication: $p \to q \equiv \sim p \vee q$
• De Morgan's Laws: $\sim (p \wedge q) \equiv \sim p \vee \sim q$ and $\sim (p \vee q) \equiv \sim p \wedge \sim q$
• Tautology: A statement that is always true, regardless of the truth values of its components. We denote a tautology by $t$.
• Contradiction: A statement that is always false, regardless of the truth values of its components.
• Law of Excluded Middle: $p \vee \sim p \equiv t$
• Identity Laws: $p \vee t \equiv t$ and $p \wedge t \equiv p$

Step-by-Step Solution

Step 1: Analyze option (A): $(p \wedge q) \to (\sim p) \vee q$

We want to determine if $(p \wedge q) \to (\sim p) \vee q$ is a tautology. We will use the implication rule to rewrite the expression.

$(p \wedge q) \to (\sim p) \vee q \equiv \sim (p \wedge q) \vee (\sim p \vee q)$

Using De Morgan's Law, we can rewrite $\sim(p \wedge q)$ as $\sim p \vee \sim q$.

$\sim (p \wedge q) \vee (\sim p \vee q) \equiv (\sim p \vee \sim q) \vee (\sim p \vee q)$

Using the associative property of $\vee$, we can rearrange the terms.

$(\sim p \vee \sim q) \vee (\sim p \vee q) \equiv \sim p \vee (\sim q \vee q)$

By the Law of Excluded Middle, $\sim q \vee q \equiv t$.

$\sim p \vee (\sim q \vee q) \equiv \sim p \vee t$

Since $\sim p \vee t$ is always true, the expression is a tautology.

$\sim p \vee t \equiv t$

Step 2: Analyze option (B): $(p \wedge q) \to p$

We want to determine if $(p \wedge q) \to p$ is a tautology. We use the implication rule.

$(p \wedge q) \to p \equiv \sim (p \wedge q) \vee p$

Using De Morgan's Law, we rewrite $\sim(p \wedge q)$ as $\sim p \vee \sim q$.

$\sim (p \wedge q) \vee p \equiv (\sim p \vee \sim q) \vee p$

Using the associative property of $\vee$, we can rearrange the terms.

$(\sim p \vee \sim q) \vee p \equiv (\sim p \vee p) \vee \sim q$

By the Law of Excluded Middle, $\sim p \vee p \equiv t$.

$(\sim p \vee p) \vee \sim q \equiv t \vee \sim q$

Since $t \vee \sim q$ is always true, the expression is a tautology.

$t \vee \sim q \equiv t$

Step 3: Analyze option (C): $(p \vee q) \to (p \vee (\sim q))$

We want to determine if $(p \vee q) \to (p \vee (\sim q))$ is a tautology. We use the implication rule.

$(p \vee q) \to (p \vee (\sim q)) \equiv \sim (p \vee q) \vee (p \vee (\sim q))$

Using De Morgan's Law, we rewrite $\sim (p \vee q)$ as $\sim p \wedge \sim q$.

$\sim (p \vee q) \vee (p \vee (\sim q)) \equiv (\sim p \wedge \sim q) \vee (p \vee \sim q)$

Using the associative property of $\vee$, we can rewrite the expression as

$(\sim p \wedge \sim q) \vee (p \vee \sim q) \equiv (\sim p \wedge \sim q) \vee (p \vee \sim q) \equiv (\sim q \wedge \sim p) \vee (\sim q \vee p)$

Using the distributive property: $a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$ and $a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$

We have $\sim q \wedge \sim p$ and $\sim q \vee p$.

$(\sim q \wedge \sim p) \vee (\sim q \vee p) \equiv \sim q \wedge \sim p \vee p \vee \sim q \equiv \sim q \vee p \wedge \sim p \vee \sim q$

Rearranging terms using the commutative property of $\vee$ and $\wedge$: $(\sim p \wedge \sim q) \vee (p \vee \sim q) \equiv \sim q \wedge \sim p \vee p \vee \sim q$ $(\sim q \wedge \sim p) \vee (p \vee \sim q) \equiv \sim q \vee (\sim p \wedge p) \vee p \equiv \sim q \vee (\sim p \wedge p) \vee p$ Rearranging terms: $(\sim p \wedge \sim q) \vee (p \vee \sim q) \equiv (\sim p \wedge \sim q) \vee (p \vee \sim q) \equiv \sim q \vee (\sim p \wedge p)$ This simplifies to $\sim q$ since $(\sim p \wedge p)$ is a contradiction. $\sim q \vee (\sim p \wedge p) \equiv \sim q \vee f \equiv \sim q$ Since $\sim q$ is not always true, the expression is not a tautology.

Step 4: Analyze option (D): $p \to (p \vee q)$

We want to determine if $p \to (p \vee q)$ is a tautology. We use the implication rule.

$p \to (p \vee q) \equiv \sim p \vee (p \vee q)$

Using the associative property of $\vee$, we can rearrange the terms.

$\sim p \vee (p \vee q) \equiv (\sim p \vee p) \vee q$

By the Law of Excluded Middle, $\sim p \vee p \equiv t$.

$(\sim p \vee p) \vee q \equiv t \vee q$

Since $t \vee q$ is always true, the expression is a tautology.

$t \vee q \equiv t$

Common Mistakes & Tips

• Remember to apply De Morgan's Laws correctly. A common mistake is forgetting to negate both terms and change the operator.
• When simplifying expressions, use the associative and commutative properties to group terms that can be simplified using the Law of Excluded Middle.
• Don't assume an expression is a tautology without fully simplifying it.

Summary

We analyzed each option to determine if it is a tautology. Options (A), (B), and (D) simplified to $t$, indicating they are tautologies. Option (C) simplified to $\sim q$, which is not always true, meaning it is not a tautology. Therefore, the statement that is not a tautology is option (C).

Final Answer The final answer is \boxed{( p \vee q) \to ( p \vee (~q))}, which corresponds to option (C).