ISRO2017-22

Question

Which one of the following Boolean expressions is NOT a tautology?

• A. $((a \rightarrow b) \wedge (b \rightarrow c)) \rightarrow  (a \rightarrow c)$
• B. $(a \leftrightarrow c) \rightarrow (\sim b\rightarrow (a\wedge c))$
• C. $(a\wedge b \wedge c)\rightarrow (c \vee a)$
• D. $a\rightarrow (b\rightarrow a)$

Answer 1

$A.\ \ ((a \rightarrow b) \wedge (b \rightarrow c)) \rightarrow (a \rightarrow c)$

$\equiv (( \sim a \vee b) \wedge (\sim b \vee c)) \rightarrow (\sim a \vee c)$

$\equiv \sim (( \sim a \vee b) \wedge (\sim b \vee c)) \vee (\sim a \vee c)$

$\equiv (( a \ \wedge \sim b) \vee ( b \wedge \sim c)) \vee (\sim a \vee c)$

$\equiv (\sim a \vee ( a \ \wedge \sim b) )\vee( ( b \wedge \sim c) \vee c)$

$\equiv( (\sim a \vee a )\wedge(\sim a \vee \sim b) )\vee( ( b \vee c) \wedge( \sim c\vee c))$

$\equiv(T\wedge(\sim a \vee \sim b) )\vee( ( b \vee c) \wedge T)$

$\equiv\sim a \vee (\sim b \vee b) \vee c$

$\equiv\sim a \vee T \vee c$

$\equiv T$

 

$B.\ \ (a \leftrightarrow c)\rightarrow (\sim b \rightarrow(a \wedge c))$

$\equiv ((a \rightarrow c)\wedge(c \rightarrow a))\rightarrow ((\sim b \rightarrow(a \wedge c))$

$\equiv \sim((\sim a \vee c)\wedge(\sim c \vee a))\vee (( b \vee (a \wedge c))$

$\equiv\sim (( a \wedge c)(\sim a \wedge \sim c) )\vee (( b \vee (a \wedge c))$

$\equiv (( a \wedge \sim c)\vee(\sim a \wedge c) )\vee (( b \vee (a \wedge c))$

$\equiv (( a \wedge \sim c)\vee c (\sim a \wedge a) )\vee b$

$\equiv (( a \wedge \sim c)\vee c\vee b$

$\equiv a \vee b \vee c $

 

$C. \ \ (a\wedge b \wedge c) \rightarrow(c \vee a)$

$\equiv \sim(a\wedge b \wedge c) \vee (c \vee a)$

$\equiv \sim a \sim b \sim c \vee c \vee a$

$\equiv (a\vee\sim a )\vee \sim b \vee(\sim c \vee c)$

$\equiv T\vee \sim b \vee T$

$\equiv T$

 

$D.\ \ a\rightarrow (b\rightarrow a)$

$\equiv\sim a \vee (\sim b \vee a)$

$\equiv(\sim a\vee a)\vee \sim b$

$\equiv T \vee \sim b$

$\equiv T$

 

Hence, Option(B) $(a \leftrightarrow c)\rightarrow (\sim b \rightarrow(a \wedge c))$ is the correct choice.

Answer 2

for A → B condition to be invalid we have to show that B is false when A is true.

So we assume that A ( left side of  → ) is true,  then we note the value of B (right side of → )  if it is false then A → B is not a tautology . 

a)     ((a → b) ^ (b → c)) →  (a → c)

left side of   '→'   is ((a → b) ^ (b → c)) which we assume to be true . for this to be true     both (a → b)  and (b → c) must be true. now if 'a' is false then right side (a → c)  is true so there is need to check bcoz we have to show right side as false in case of fallacy

 let 'a' is true then 'b' and  'c' must be true for left side ((a → b) ^ (b → c)) to be true .now as 'a' and 'c' is true (a → c) is true.

 so it is a tautology.

c )    (a^b^c)→(c v a))

 for left side (a^b^c) to be true 'a' ,'b' and 'c' must be true so right side (c v a) is also true.so it is a tautology.

d)     a→(b→a)

for left side to be true 'a'  must be true then (b→a) is also true bcoz we assume 'a' to be true.  so it is a tautology.

 b)     (a ↔ c) →(~b→(a^c))

 for left side to be true both ' a' and ' c' either be true or  false.

In case when both are 0 then (a^c) is 0.so for  b=0, a=0 and c=0 right side is false even if left side is true.As there is a case  when 1→0  so it is not a tautology 

Answer 3

Option B is not tautology.

$(a \Leftrightarrow c) \rightarrow (b{}'\rightarrow (a\wedge c))$

$((a{}'\vee c)(a\vee c{}')) \rightarrow (b{}'\rightarrow (a\wedge c))$

$(ac+a{}'c{}')) \rightarrow (b{}'\rightarrow (a\wedge c))$

$(ac+a{}'c{}')){}' + (b{}'\rightarrow (a\wedge c))$

$((a{}'+c{}')(a+c)) + (b{}'\rightarrow (a\wedge c))$

$(ac{}'+a{}'c) + (b{}'\rightarrow (a\wedge c))$

$(ac{}'+a{}'c) + (b+ (a\wedge c))$

$(ac{}'+a{}'c) + (b+ a c)$

$(ac{}'+(a{}'+ a )c)+b$

$ac{}'+c+b$

$(ac{}'+c)+b$

$(a+c)+b$

$a+b+c$

Comments

HI
Can you please explain me how you are deducing these below steps . specificly on LHS side.

(a⇔c)→(b ′ →(a∧c))
((a ′ ∨c)(a∨c ′ ))→(b ′ →(a∧c)) 
(ac+a ′ c ′ ))→(b ′ →(a∧c)) 

---

$a \Leftrightarrow c=\left ( \left ( a\rightarrow c \right )\left ( c\rightarrow a \right ) \right )$
                              =$\left ( \left ( a{}'+ c \right )\left ( c{}' +a \right ) \right )$
                              =$\left ( a{}'c{}'+a c \right )$

Answer 4

A:   ((a→b)∧(b→c))→(a→c)

approach - find an assignment for which above statement becomes false.

The above statement becomes false only when  ((a→b)∧(b→c)) = T and (a→c) = F

to make (a→c) false .  put c=F and a=T.

so T→F = F

(a→b) will be true only when b=T.

by putting b = T

(b→c) becomes false which makes (a→b)∧(b→c) false 

so F→F = T

so there is no such assignment which makes ((a→b)∧(b→c))→(a→c) false . So its a tautology

C. (a∧b∧c)→(c∨a)

for the assignment a=F and c=F

(c∨a) becomes False.

but (a∧b∧c) also becomes false.

F→F = T 

so  there is no such assignment which makes ((a→b)∧(b→c))→(a→c) false . So it is also tautology.

D.  a→(b→a)

= ∼av(∼bva)

= ∼a v a v∼b

=T v ∼b

= T

it is also tautology. 

B. (a↔c)→(∼b→(a∧c))

for the assignment a=F b=F c=F the above statement becomes false so it is not a tautology.

So B is the correct option.