Which one of the following is a tautology?

We want to know which of the given compound statements is a tautology, that is, which statement is always true no matter which truth-values (T or F) we assign to the simple propositions $$p$$ and $$q$$. The straightforward way is to construct truth-tables for every option, but often we can save time by using well-known logical equivalences. Nevertheless, for absolute clarity we shall give every algebraic step and also exhibit at least one counter-example for all the non-tautological options.

First recall some standard logical facts that we shall need:

1. Implication equivalence $$p \rightarrow q \;\;\text{is equivalent to}\;\; \neg p \vee q$$ (Because an implication is false only when $$p$$ is true and $$q$$ is false.)

2. Distributive, associative, commutative and absorption laws for $$\vee$$ (OR) and $$\wedge$$ (AND) behave exactly like their algebraic counterparts, but with the understanding that TRUE behaves like 1 and FALSE like 0.

3. The absorption laws that we shall use twice are $$p \vee (p \wedge q) \equiv p$$ $$p \wedge (p \vee q) \equiv p.$$ These tell us that mixing a statement with itself inside an OR or an AND does not add any new logical content: $$p$$ already captures the whole truth of the compound.

Now we treat every option one by one.

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

We start by rewriting the implication inside the antecedent ($$p \rightarrow q$$) using fact 1.

So, $$p \rightarrow q \equiv \neg p \vee q.$$

Substituting this inside the main expression gives

$$ (p \wedge (\,\neg p \vee q\,)) \rightarrow q. $$

Next we simplify the bracket $$p \wedge (\,\neg p \vee q\,)$$ by distributing $$p$$ over the parentheses:

$$ p \wedge (\,\neg p \vee q\,) \equiv (p \wedge \neg p) \;\vee\; (p \wedge q). $$

But $$p \wedge \neg p$$ is always FALSE (a contradiction), hence

$$ (p \wedge \neg p) \;\vee\; (p \wedge q) \equiv \text{FALSE} \;\vee\; (p \wedge q) \equiv p \wedge q, $$

because OR with FALSE leaves the other term unchanged.

So up to now we have reduced the whole statement to

$$ (p \wedge q) \rightarrow q. $$

Once again we use fact 1 on the outer implication, i.e.

$$ (p \wedge q) \rightarrow q \equiv \neg (p \wedge q) \;\vee\; q. $$

We apply De Morgan to the negation:

$$ \neg (p \wedge q) \equiv \neg p \vee \neg q, $$

so the expression becomes

$$ (\neg p \vee \neg q) \;\vee\; q. $$

OR is associative and commutative, therefore we can rearrange freely. We now gather the two clauses that contain $$q$$:

$$ (\neg p \vee \neg q \vee q) \equiv (\neg p \vee \text{TRUE}), $$

because $$\neg q \vee q$$ is always TRUE. And of course $$\neg p \vee \text{TRUE}$$ simplifies to TRUE (OR with TRUE is TRUE).

Thus the entire compound statement has simplified to the constant truth-value TRUE for every truth assignment to $$p$$ and $$q$$. Therefore option A is a tautology.

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

Again write $$p \rightarrow q$$ as $$\neg p \vee q$$ and substitute:

$$ q \rightarrow \bigl(p \wedge (\neg p \vee q)\bigr). $$

As in option A we know that $$p \wedge (\neg p \vee q) \equiv p \wedge q.$$ So we obtain

$$ q \rightarrow (p \wedge q). $$

This implication is equivalent to $$\neg q \vee (p \wedge q).$$ Now choose a valuation with $$q = \text{T}$$ and $$p = \text{F}.$$ Then $$\neg q = \text{F}$$ and $$p \wedge q = \text{F}$$, so the whole expression evaluates to FALSE. Hence option B is not a tautology.

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

Using the absorption law stated earlier, we get directly

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

The value of $$p$$ obviously depends on our choice of truth-values; it is TRUE for $$p = \text{T}$$ and FALSE for $$p = \text{F}$$. Therefore this compound statement sometimes becomes FALSE, so it is not a tautology.

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

This is the other absorption law:

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

Again the truth of the whole expression varies with the truth of $$p$$, so option D is not a tautology.

After examining every choice we see that only option A is always TRUE, i.e. is a tautology.

Hence, the correct answer is Option A.