3,834 views

Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic.

• $S_1: (\neg p\wedge(p\vee q))\rightarrow q$
• $S_2: q\rightarrow(\neg p\wedge(p\vee q))$

Which one of the following choices is correct?

1. Both $S_1$ and $S_2$ are tautologies.
2. $S_1$ is a tautology but $S_2$ is not a tautology
3. $S_1$ is not a tautology but $S_2$ is a tautology
4. Neither $S_1$ nor $S_2$ is a tautology

Fastest way is to try out $(p,q) = \{(0,1), (1,0)\}$ combinations.

Works for most GATE questions.

Here, it gives Ans (B.)

$S_1 : \neg p \wedge ( p \vee q ) \to q$

If consequence is false and hypothesis is true, then we will get False in the truth table.

Lets assume $q$ is false. So consequence is FALSE.

Can it make Hypothesis TRUE?

Hypothesis: $\neg p \wedge ( p \vee q ) \equiv \neg p \wedge ( p \vee \text{FALSE} ) \equiv \neg p \wedge ( p ) \equiv \text{FALSE}.$

Hypothesis can’t be true, So we can’t get False in the Truth Table.

∴ $S_1$ is Tautology.

$S_2: q \to \neg p \wedge ( p \vee q )$

If hypothesis is true and consequence is false, then we will get False in the truth table.

Lets assume $q$ is True, So Hypothesis is TRUE.

Can it make Consequence FALSE ?

Consequence: $\neg p \wedge ( p \vee q ) \equiv \neg p \wedge ( p \vee \text{TRUE} ) \equiv \neg p \wedge ( \text{TRUE} ) \equiv \neg p$

Consequence can be false and so we can get False in the Truth Table.

∴ $S_2$ is not Tautology.

Correct Option: B

“Consequence can be true and so we can get False in the Truth Table.”

In S2 (from last 3rd line) seems wrong.

correct:

“Consequence can be false and so we can get False in the Truth Table.”

corrected 👍
S1 can be written as : (P’(P+Q))’+Q

Simplifying S1: (P + (P+Q)’)+Q

(P + (P’Q’))+Q

(P+P’) (P+Q’)+Q

P+Q’+Q

1

Hence S1 is tautology.

S2 can be written as: Q’+ (P’(P+Q))

Simplifying S2: Q’+(PP’+P’Q)

Q’+(P’Q)

Q’+P’

Which is not always 1.Hence S2 is not tautology.

A tautology is a proposition that is always true for every value of its propositional variables.

$S_1: (\neg p \land(p\lor q)) \rightarrow q$

 $p$ $q$ $\neg p$ $p\lor q$ $(\neg p \land(p\lor q))$ $(\neg p \land(p\lor q))\rightarrow q$ $T$ $T$ $F$ $T$ $F$ $T$ $T$ $F$ $F$ $T$ $F$ $T$ $F$ $T$ $T$ $T$ $T$ $T$ $F$ $F$ $T$ $F$ $F$ $T$

$\therefore S_1$ is tautology.

$S_2: q\rightarrow (\neg p \land(p\lor q))$

 $p$ $q$ $\neg p$ $p\lor q$ $\neg p \land(p \lor q)$ $q \rightarrow (\neg p \land(p \lor q))$ $T$ $T$ $F$ $T$ $F$ $F$ $T$ $F$ $F$ $T$ $F$ $T$ $F$ $T$ $T$ $T$ $T$ $T$ $F$ $F$ $T$ $F$ $F$ $T$

$\therefore S_2$ is not tautology.

Option $B$ is correct.

ANS IS B, S1 IS A TAUTOLOGY BUT S2 IS NOT A TAUTOLOGY

by