retagged by
7,214 views
12 votes
12 votes

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

  1. $((a \rightarrow b) \wedge (b \rightarrow c)) \rightarrow  (a \rightarrow c)$
  2. $(a \leftrightarrow c) \rightarrow (\sim b\rightarrow (a\wedge c))$
  3. $(a\wedge b \wedge c)\rightarrow (c \vee a)$
  4. $a\rightarrow (b\rightarrow a)$
retagged by

9 Answers

Best answer
10 votes
10 votes
$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.
selected by
9 votes
9 votes

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 

edited by
5 votes
5 votes
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$
3 votes
3 votes

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 =

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.

Answer:

Related questions

0 votes
0 votes
0 answers
2
Pooja Khatri asked Apr 4, 2019
256 views
Show that if you pick three socks from a drawer containing just blue socks and black socks, you must get either a pair of blue socks or a pair of black socks.
1 votes
1 votes
3 answers
4