recategorized by
2,112 views
13 votes
13 votes

A Boolean formula is said to be a $tautology$ if it evaluates to TRUE for all assignments to its variables. Which one of the following is NOT a tautology?

  1. $(( p \vee q) \wedge (r \vee s)) \Rightarrow (( p \wedge r) \vee q \vee s)$
  2. $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow (q \vee s)$
  3. $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( r \vee q \vee s)$
  4. $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( p \vee q \vee s)$
  5. $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( p \vee q)$
recategorized by

5 Answers

8 votes
8 votes

ANSWER: B) option as it does not evaluate to true 

A) evaluate to TRUE
C) evaluate to TRUE
D) evaluate to TRUE
E) evaluate to TRUE

edited by
4 votes
4 votes
in such type of questions set all 'premises' TRUE and then see if conclusion also becomes TRUE then given 'implication' is a valid formula.

a)    $P$ $\vee$ $Q$          ------->>>premise 1

       $ R\vee S$           ------->>>premise 2

-------------------------------

$(P\wedge R)\vee Q\vee S$   ---->>>Conclusion

-------------------------------

key concept is try to make conclusion false , and see if some of values for which our conclusion became FALSE , can make all premises TRUE?

we can observe to make conclusion $(P\wedge R)\vee Q\vee S$ FALSE , both $S$ and $R$ must have to be false and atleast one of $P$ and $R$ must be FALSE.so in that way our premises will become , $P\vee F and R\vee F$ which are nothing but $P$ and $R$ , so eventually formula will become $P\wedge R\Rightarrow P\wedge R$ , which is always TRUE , so this formula is a tautology.

b)   $P\vee Q$     ------->>>Premise 1

      $R\vee S$    -------->>>Premise 2

---------------------------

     $Q\vee S$       ------->>>Conclusion

---------------------------

Make how can our conclusion be FALSE. It can be FALSE when both $Q$  and $S$ are FALSE. and in that way premises will become  $P$ and $R$ , Now overall our formula reduced to $P\wedge R\Rightarrow F$. Here we can easily see , it can produce $T \Rightarrow F$ , when both  $P$ and $R$ are TRUE.So this is clearly not a Tautology.

C) Here make $R\vee Q \vee S$ FALSE , which can only possible when all $R$,$Q$ and $S$ are FALSE and in that case our premises will become $P$ and FALSE , which will trivially make our formula tautology because $F\Rightarrow Anything$ is Tautology.

Same reasoning for other  options.
1 votes
1 votes
A⇒B is false iff T⇒F

A) ((p∨q)∧(r∨s))⇒((p∧r)∨q∨s), RHS will be false iff q=F and a=F and  (p∧r)=F

      (p∧r) will be not be false only if p=T and r=T

     now in RHS substitute values of variables ((p∨F)∧(r∨F))

      ((p∨F)∧(r∨F))  will be true only if p=T and r=T but this is not true by LHS assumption sp this is tautology.

C) ((p∨q)∧(r∨s))⇒(r∨q∨s), RHS will be false iff r=F ans q=F and s=F

       so (r∨s)=F then (p∨q)∧(r∨s)=F

        so F⇒F i.e. this is tautology

D) ((p∨q)∧(r∨s))⇒(p∨q∨s) will be false iff p=F ans q=F and s=F

      so (p∨q)=F then (p∨q)∧(r∨s)=F

     so F⇒F is tautology

E)((p∨q)∧(r∨s))⇒(p∨q)

      RHS will be False iff p=F and q=F

     so (p∨q)=F then ((p∨q)∧(r∨s)) = F

      so this is tautology

 

B) ((p∨q)∧(r∨s))⇒(q∨s)

 RHS will be false if q=F and s=F

 SO LHS will be ((p∨F)∧(r∨F))

((p∨F)∧(r∨F)) will be true iff p=T and r=T

so for p=r=T this will not be tautology.
1 votes
1 votes

$\mathbf{{\underline{Answer: B}}}$

$\mathbf{\underline{Explanation:}}$

I am taking $\mathbf B$ directly and proving that why its not the tautology.

The rest of the options can be proved int he similar manner.

Given: $\mathbf{((p\lor q)\land(r\lor s)) \Rightarrow (q\lor s)}$

Now, we need to prove that its a Tautology but let me try to prove its not because its easier this way.

For not being tautology: The implication should be in the form.

$\color{blue}{\mathbf{\Large T \rightarrow \Large F}}$

Now, take $\mathbf{q\lor S}$ as $\mathbf{False}$ and the left side as $\mathbf{True}$.

For $\mathbf{q\lor s}$ $3$cases would be possible:

  1. q = F, s = F
  2. q = T, s = F
  3. q = F, s = T

Substitute accordingly and get the result.

PS: ping me if anyone needs full detailed explanation.

Answer:

Related questions

23 votes
23 votes
4 answers
1