The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
63 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)$
asked in Mathematical Logic by Boss (13.8k points)
edited by | 63 views
0
$(D)$ is the correct answer.

1 Answer

+2 votes
Best 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$

answered by Boss (26.8k points)
selected by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,080 questions
51,333 answers
177,707 comments
66,675 users