in Mathematical Logic recategorized by
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)$
in Mathematical Logic recategorized by

1 comment

Why not E . suppose p=q=1 and r=s=0 then p or q =1 and r or s =0 . 1 and 0 =0 but p or q =1 LHS = 0 and RHS = 1.

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


can anyone explain this solution

We have 4 possibilities to have the LHS true.

  1. p=r=1
  2. p=s=1
  3. q=r=1
  4. q=s=1

In each of these 4 possibilities LHS is true. So in each of the options the RHS cannot be false for all the above 4 possibilities. Just checking this, we will be able to see RHS of all options except Option B turns out to be true. In Option B, LHS = true when p=r=1 but RHS is false. Hence Option B is not a valid implication.

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 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 vote
1 vote
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


      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 vote
1 vote

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


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.


Related questions