GATE CSE 2021 Set 1 | Question: 7

Question

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?

• A. Both $S_1$ and $S_2$ are tautologies.
• B. $S_1$ is a tautology but $S_2$ is not a tautology
• C. $S_1$ is not a tautology but $S_2$ is a tautology
• D. Neither $S_1$ nor $S_2$ is a tautology

Comments

B is the correct answer.

---

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

Works for most GATE questions.

Here, it gives Ans (B.)

Answer 1

We can Use By Case Method .

Case 1 : P = True

S1 : ( ~T ∧ ( T V q ) ) → q = (F ∧ (q) ) → q = F → q = T

S2  : q → (~T∧(T∨q)) = q → F = ~q . S2 can be True / False

 

Case 2 : P = False

S1 :  ( ~F ∧ ( F V q ) ) → q = q→ q  = T .

S2 : q → (~F∧(F∨q)) = q → q = T

 

We can clearly see for any value of P :

S1 is Tautology

S2 is not Tautology

Hence , Option (B) is correct .

Answer 2

S1 : (p’ $\wedge$ (p V q)) → q  $\equiv$ (p’ $\wedge$ q) → q
Approach 1 (Intuition based) :- Given p is false and q is true, from this info we can infer that q is true. So, S1 is valid argument.
Approach 2 (Formula based) :- (p’ $\wedge$ q) → q $\equiv$ (p’ $\wedge$ q)’ V q $\equiv$ p V q’ V q $\equiv$ True. So, tautology.

S2 : q → (p’ $\wedge$ (p V q)) $\equiv$ q → (p’ $\wedge$ q)
Approach 1 (Intuition based) :- Given q is true, from this info we can not infer that p is false and q is true. So, S1 is invalid argument.
Approach 2 (Formula based) :- q → (p’ $\wedge$ q) $\equiv$ q’ V (p’ $\wedge$ q) $\equiv$ (q’ V p’) $\wedge$ (q’ V q) $\equiv$ (q’ V p’). So, not tautology.

Answer 3

S1 is direct definition of disjunctive syllogism, so it is a tautology.

But S2 is converse of disjunctive syllogism, and the converse of disjunctive syllogism is not true, so it is not a tautology. 

Hence, answer: B

Answer 4

Hope it helps!! By the help of case method it is solved