RankRizz
JEE MAIN 2020 · 08 JAN S1+4 / −1EASYTRANSCRIBED

JEE Main 2020 Mathematics question — Logical connectives, truth tables and tautologies

Which one of the following is a tautology?

SOLUTION

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 pp and qq. 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→q    is equivalent to    ¬p∨qp \rightarrow q \;\;\text{is equivalent to}\;\; \neg p \vee q (Because an implication is false only when pp is true and qq 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∨(p∧q)≡pp \vee (p \wedge q) \equiv p p∧(p∨q)≡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: pp already captures the whole truth of the compound.

Now we treat every option one by one.

Option A : (p∧(p→q))→q(p \wedge (p \rightarrow q)) \rightarrow q

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

So, p→q≡¬p∨q.p \rightarrow q \equiv \neg p \vee q.

Substituting this inside the main expression gives

(p∧( ¬p∨q ))→q.(p \wedge (\,\neg p \vee q\,)) \rightarrow q.

Next we simplify the bracket p∧( ¬p∨q )p \wedge (\,\neg p \vee q\,) by distributing pp over the parentheses:

p∧( ¬p∨q )≡(p∧¬p)  ∨  (p∧q).p \wedge (\,\neg p \vee q\,) \equiv (p \wedge \neg p) \;\vee\; (p \wedge q).

But p∧¬pp \wedge \neg p is always FALSE (a contradiction), hence

(p∧¬p)  ∨  (p∧q)≡FALSE  ∨  (p∧q)≡p∧q,(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∧q)→q.(p \wedge q) \rightarrow q.

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

(p∧q)→q≡¬(p∧q)  ∨  q.(p \wedge q) \rightarrow q \equiv \neg (p \wedge q) \;\vee\; q.

We apply De Morgan to the negation:

¬(p∧q)≡¬p∨¬q,\neg (p \wedge q) \equiv \neg p \vee \neg q,

so the expression becomes

(¬p∨¬q)  ∨  q.(\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 qq:

(¬p∨¬q∨q)≡(¬p∨TRUE),(\neg p \vee \neg q \vee q) \equiv (\neg p \vee \text{TRUE}),

because ¬q∨q\neg q \vee q is always TRUE. And of course ¬p∨TRUE\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 pp and qq. Therefore option A is a tautology.

Option B : q→(p∧(p→q))q \rightarrow (p \wedge (p \rightarrow q))

Again write p→qp \rightarrow q as ¬p∨q\neg p \vee q and substitute:

q→(p∧(¬p∨q)).q \rightarrow \bigl(p \wedge (\neg p \vee q)\bigr).

As in option A we know that p∧(¬p∨q)≡p∧q.p \wedge (\neg p \vee q) \equiv p \wedge q. So we obtain

q→(p∧q).q \rightarrow (p \wedge q).

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

Option C : p∧(p∨q)p \wedge (p \vee q)

Using the absorption law stated earlier, we get directly

p∧(p∨q)≡p.p \wedge (p \vee q) \equiv p.

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

Option D : p∨(p∧q)p \vee (p \wedge q)

This is the other absorption law:

p∨(p∧q)≡p.p \vee (p \wedge q) \equiv p.

Again the truth of the whole expression varies with the truth of pp, 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.

Tagged Logical connectives, truth tables and tautologies. Machine-assigned, so read it as a strong shortlist rather than a verdict.

TopicLogical connectives, truth tables and tautologies
TypeMultiple choice