Key Concepts and Formulas

• Tautology: A statement that is always true, regardless of the truth values of its components.
• Logical connectives:
  • $p \wedge q$ (p and q) is true if and only if both p and q are true.
  • $p \vee q$ (p or q) is true if at least one of p or q is true.
  • $p \to q$ (p implies q) is false if and only if p is true and q is false. It is equivalent to $\neg p \vee q$.

Step-by-Step Solution

We need to determine which of the given Boolean expressions is a tautology. A tautology is a statement that is always true, regardless of the truth values of its components. We will use truth tables to evaluate each option.

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

Step 1: Construct a truth table for $(p \wedge q) \vee (p \to q)$. We need columns for p, q, $p \wedge q$, $p \to q$, and $(p \wedge q) \vee (p \to q)$.

Step 2: Fill in the truth values for p and q.

Step 3: Calculate the truth values for $p \wedge q$. $p \wedge q$ is true only when both p and q are true.

Step 4: Calculate the truth values for $p \to q$. $p \to q$ is false only when p is true and q is false.

Step 5: Calculate the truth values for $(p \wedge q) \vee (p \to q)$. $(p \wedge q) \vee (p \to q)$ is true if either $p \wedge q$ is true or $p \to q$ is true (or both).

The truth table is:

$\begin{array}{|c|c|c|c|c|} \hline p & q & p \wedge q & p \to q & (p \wedge q) \vee (p \to q) \\ \hline T & T & T & T & T \\ \hline T & F & F & F & F \\ \hline F & T & F & T & T \\ \hline F & F & F & T & T \\ \hline \end{array}$

Since the last column is not all true, option (A) is not a tautology.

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

Step 1: Construct a truth table for $(p \wedge q) \vee (p \vee q)$.

Step 2: Fill in the truth values for p and q.

Step 3: Calculate the truth values for $p \wedge q$.

Step 4: Calculate the truth values for $p \vee q$. $p \vee q$ is true if either p is true or q is true (or both).

Step 5: Calculate the truth values for $(p \wedge q) \vee (p \vee q)$.

The truth table is:

$\begin{array}{|c|c|c|c|c|} \hline p & q & p \wedge q & p \vee q & (p \wedge q) \vee (p \vee q) \\ \hline T & T & T & T & T \\ \hline T & F & F & T & T \\ \hline F & T & F & T & T \\ \hline F & F & F & F & F \\ \hline \end{array}$

Since the last column is not all true, option (B) is not a tautology.

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

Step 1: Construct a truth table for $(p \wedge q) \to (p \to q)$.

Step 2: Fill in the truth values for p and q.

Step 3: Calculate the truth values for $p \wedge q$.

Step 4: Calculate the truth values for $p \to q$.

Step 5: Calculate the truth values for $(p \wedge q) \to (p \to q)$. $(p \wedge q) \to (p \to q)$ is false only when $p \wedge q$ is true and $p \to q$ is false.

The truth table is:

$\begin{array}{|c|c|c|c|c|} \hline p & q & p \wedge q & p \to q & (p \wedge q) \to (p \to q) \\ \hline T & T & T & T & T \\ \hline T & F & F & F & T \\ \hline F & T & F & T & T \\ \hline F & F & F & T & T \\ \hline \end{array}$

Since the last column is all true, option (C) is a tautology.

Option (D): $(p \wedge q) \wedge (p \to q)$

Step 1: Construct a truth table for $(p \wedge q) \wedge (p \to q)$.

Step 2: Fill in the truth values for p and q.

Step 3: Calculate the truth values for $p \wedge q$.

Step 4: Calculate the truth values for $p \to q$.

Step 5: Calculate the truth values for $(p \wedge q) \wedge (p \to q)$. $(p \wedge q) \wedge (p \to q)$ is true only when both $p \wedge q$ and $p \to q$ are true.

The truth table is:

$\begin{array}{|c|c|c|c|c|} \hline p & q & p \wedge q & p \to q & (p \wedge q) \wedge (p \to q) \\ \hline T & T & T & T & T \\ \hline T & F & F & F & F \\ \hline F & T & F & T & F \\ \hline F & F & F & T & F \\ \hline \end{array}$

Since the last column is not all true, option (D) is not a tautology.

Common Mistakes & Tips

• Carefully evaluate $p \to q$. Remember that it is only false when p is true and q is false.
• Double-check your truth tables to avoid errors.
• If you are having trouble, rewrite $p \to q$ as $\neg p \vee q$.

Summary

We examined each option using truth tables to determine which Boolean expression is a tautology (always true). By constructing the truth tables for each option, we found that the expression $(p \wedge q) \to (p \to q)$ in option (C) is a tautology.

Final Answer

The final answer is \boxed{(p \wedge q) \to (p \to q)}, which corresponds to option (C).