71 views

Which of the following propositional formulae is a tautology?

1. $(\neg p \vee r ) \rightarrow (p \vee \neg r)$
2. $\neg ( p \rightarrow (p \wedge q ))$
3. $r \rightarrow ( p \wedge \neg r )$
4. $( p \leftrightarrow q ) \vee (p \leftrightarrow \neg q)$
edited | 71 views
0
$(D)$ is the correct answer.

These type of questions,we can do in two ways:

 $P$ $Q$ $P \leftrightarrow Q$ $\neg Q$ $P\leftrightarrow\neg Q$ $(P \leftrightarrow Q)\vee (P\leftrightarrow\neg Q)$ $T$ $T$ $T$ $F$ $F$ $T$ $T$ $F$ $F$ $T$ $T$ $T$ $F$ $T$ $F$ $F$ $T$ $T$ $F$ $F$ $T$ $T$ $F$ $T$

$(OR)$

$P \leftrightarrow Q\equiv (P\rightarrow Q)\wedge(Q\rightarrow P)$

$P \leftrightarrow Q\equiv (\neg P \vee Q)\wedge(\neg Q\vee P)$

$P \leftrightarrow Q\equiv (\neg P \wedge \neg Q)\vee(P\wedge Q)\equiv \bar{P}\bar{Q}+PQ$ $\qquad \to(1)$

So,we can write,

$P \leftrightarrow \neg Q\equiv (\neg P \wedge \neg (\neg Q))\vee(P\wedge \neg Q)$

$P \leftrightarrow \neg Q\equiv (\neg P \wedge Q)\vee(P\wedge \neg Q)\equiv\bar{P}Q+P\bar{Q}$ $\qquad \to(2)$

Now,we can find,

$(P \leftrightarrow Q)\vee(P \leftrightarrow \neg Q)\equiv[(\neg P \wedge \neg Q)\vee(P\wedge Q)] \vee [(\neg P \wedge Q)\vee(P\wedge \neg Q)]$

$(P \leftrightarrow Q)\vee(P \leftrightarrow \neg Q)\equiv[\bar{P}\bar{Q}+PQ]+[\bar{P}Q+P\bar{Q}]$

$(P \leftrightarrow Q)\vee(P \leftrightarrow \neg Q)\equiv\bar{P}\bar{Q}+PQ+\bar{P}Q+P\bar{Q}$

$(P \leftrightarrow Q)\vee(P \leftrightarrow \neg Q)\equiv\bar{P}(\bar{Q}+Q)+P(Q+\bar{Q})$

$(P \leftrightarrow Q)\vee(P \leftrightarrow \neg Q)\equiv\bar{P}(1)+P(1)$              $[X+\bar{X}=1]$

$(P \leftrightarrow Q)\vee(P \leftrightarrow \neg Q)\equiv\bar{P}+P$

$(P \leftrightarrow Q)\vee(P \leftrightarrow \neg Q)\equiv1$  ​​​

$(P \leftrightarrow Q)\vee(P \leftrightarrow \neg Q)\equiv T$

So.this is Tautology(Valid).

$\Rightarrow$Every Tautology is Satisfiable,but every Satisfiable need not be Tautology.

Alternatively, we can try making $D$ option FALSE

$(p \leftrightarrow q) \vee (p \leftrightarrow \neg q)$

$(p \leftrightarrow q)$ is FALSE if $p \neq q$ (EXOR)
But if $p \neq q,$ $(p \leftrightarrow \neg q)$  (XNOR) becomes TRUE. So the formula, which is a disjunction (OR) of the above two, is always TRUE irrespective of the values of $p,q$

selected by

1