Dark Mode

1,476 views

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?

- $(( p \vee q) \wedge (r \vee s)) \Rightarrow (( p \wedge r) \vee q \vee s)$
- $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow (q \vee s)$
- $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( r \vee q \vee s)$
- $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( p \vee q \vee s)$
- $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( p \vee q)$

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

We have 4 possibilities to have the LHS true.

- p=r=1
- p=s=1
- q=r=1
- 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.

0

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.

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

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.

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 vote

$\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:

- q = F, s = F
- q = T, s = F
- q = F, s = T

Substitute accordingly and get the result.

PS: ping me if anyone needs full detailed explanation.