RankRizz
JEE MAIN 2021 · 31 AUG S1+4 / −1MEDIUMTRANSCRIBED

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

Let ∗,□∈{∧,∨}*, \square \in \{\wedge, \vee\} be such that the Boolean expression (p∗∼q)⇒(p□q)(p * \sim q) \Rightarrow (p \square q) is a tautology. Then:

SOLUTION

We have to select the two connectives ∗* and □\square from the set {∧,∨}\{\wedge ,\vee\} in such a way that the statement

( p∗∼q )  ⇒  (p  □  q)(\,p * \sim q\,)\;\Rightarrow\;(p \;\square\; q)

is a tautology, that is, it must be true for every possible truth-value assignment of the propositional variables pp and qq.

First recall the standard equivalence that rewrites an implication:

a⇒b  ≡  ¬a  ∨  b.a \Rightarrow b \;\equiv\; \lnot a \;\vee\; b.

Applying this formula to our expression we obtain

( p∗∼q )  ⇒  (p□q)  ≡  ¬ (p∗∼q)  ∨  (p□q).(\,p * \sim q\,)\;\Rightarrow\;(p \square q) \;\equiv\; \lnot\,(p * \sim q) \;\vee\; (p \square q).

Because ∗* and □\square may each be either ∧\wedge (AND) or ∨\vee (OR), four distinct combinations are possible. We test them one by one, showing every algebraic step.

Case 1: ∗=∧,  □=∨*=\wedge,\;\square=\vee

Substituting these symbols gives

¬ (p∧∼q)  ∨  (p∨q).\lnot\,(p \wedge \sim q) \;\vee\; (p \vee q).

We now push the negation inside the parenthesis with De Morgan’s law:

¬(p∧∼q)  ≡  (¬p)  ∨  (¬ ⁣∼q)  =  (¬p)  ∨  q.\lnot (p \wedge \sim q) \;\equiv\; (\lnot p) \;\vee\; (\lnot\!\sim q) \;=\; (\lnot p) \;\vee\; q.

Therefore the whole expression becomes

((¬p)  ∨  q)  ∨  (p  ∨  q).\big((\lnot p) \;\vee\; q\big) \;\vee\; (p \;\vee\; q).

Using associativity and commutativity of ∨\vee we group the disjuncts that involve pp:

((¬p)  ∨  p)  ∨  q.\big((\lnot p) \;\vee\; p\big) \;\vee\; q.

Since a proposition OR its negation is always true, we have

(¬p)  ∨  p  =  T(a tautology).(\lnot p) \;\vee\; p \;=\; \text{T} \quad\text{(a tautology).}

Thus the entire expression simplifies to

T  ∨  q  =  T.\text{T} \;\vee\; q \;=\; \text{T}.

So for ∗=∧,  □=∨*=\wedge,\;\square=\vee the implication is always true; hence this choice makes the given statement a tautology.

Case 2: ∗=∧,  □=∧*=\wedge,\;\square=\wedge

The expression now is

¬ (p∧∼q)  ∨  (p∧q)  =  (¬p  ∨  q)  ∨  (p∧q).\lnot\,(p \wedge \sim q) \;\vee\; (p \wedge q) \;=\; (\lnot p \;\vee\; q) \;\vee\; (p \wedge q).

To check whether this is a tautology, take the assignment p=T,  q=Fp=\text{T},\;q=\text{F} (i.e. p=1,q=0p=1,q=0).

Then we get

¬p=0,q=0,p∧q=1∧0=0.\lnot p = 0,\quad q = 0,\quad p \wedge q = 1\wedge 0 = 0.

So the whole disjunction becomes 0  ∨  0=00\;\vee\;0=0, which is false. Hence this case fails to be a tautology.

Case 3: ∗=∨,  □=∨*=\vee,\;\square=\vee

We have

¬ (p∨∼q)  ∨  (p∨q).\lnot\,(p \vee \sim q) \;\vee\; (p \vee q).

Again by De Morgan,

¬ (p∨∼q)  =  (¬p)∧q.\lnot\,(p \vee \sim q) \;=\; (\lnot p) \wedge q.

Hence the whole statement is

((¬p)∧q)  ∨  (p∨q).\big((\lnot p) \wedge q\big) \;\vee\; (p \vee q).

Choose p=F,  q=Fp=\text{F},\;q=\text{F}. Then

(¬p)∧q=1∧0=0,p∨q=0∨0=0,(\lnot p)\wedge q = 1\wedge 0 = 0,\quad p\vee q = 0\vee 0 = 0,

so the overall value is 0∨0=00\vee 0 = 0—not a tautology.

Case 4: ∗=∨,  □=∧*=\vee,\;\square=\wedge

The expression becomes

¬ (p∨∼q)  ∨  (p∧q)  =  ((¬p)∧q)  ∨  (p∧q).\lnot\,(p \vee \sim q) \;\vee\; (p \wedge q) \;=\; ((\lnot p) \wedge q) \;\vee\; (p \wedge q).

With the assignment p=F,  q=Fp=\text{F},\;q=\text{F} we get

(¬p)∧q=1∧0=0,p∧q=0∧0=0,(\lnot p)\wedge q = 1\wedge 0 = 0,\quad p\wedge q = 0\wedge 0 = 0,

so the disjunction is again 0∨0=00\vee 0 = 0. Hence this case also fails to be a tautology.

Among all four possibilities, only Case 1—namely ∗=∧*=\wedge and □=∨\square=\vee—produces a statement that is true under every possible truth assignment. All other choices admit at least one counter-example, so they are not tautologies.

Hence, the correct answer is Option C.

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