in Mathematical Logic recategorized by
3,834 views
6 votes
6 votes

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
in Mathematical Logic recategorized by
by
3.8k views

2 Comments

B is the correct answer.
1
1

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

Works for most GATE questions.

Here, it gives Ans (B.)

0
0

5 Answers

7 votes
7 votes
Best answer
$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
edited by

2 Comments

“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.”

2
2
corrected 👍
0
0
4 votes
4 votes
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.

Answer is: (B)
4 votes
4 votes

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.

2 votes
2 votes

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

Answer:

Related questions