Log In
10 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)$
in Mathematical Logic 4.1k views

9 Answers

9 votes
Best answer
$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

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





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

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

$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 )$
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.

2 votes
Option B


(a <-> c) -> (~b -> (a˄c))

For the expression to be Tautology, T -> F should not arise. So taking a = False, c= False and ~b = True,

(~b -> (a˄c)) = False

and (a <-> c)  = True

So, True -> False, scenario is arising. So option B is the correct answer.

For all other expressions, True-> False scenario will not arise.
1 vote
Answer B??
I also got B :)
Solution steps please
Option A is a Tautology by Hypothetical Syllogism.Just refer Rosen.

Option C can be proven by simplification. If a,b,c are true then defenitely c or a will be true.

In the case of Option D , just expand it you will get a ,b and negation a. with OR gate inbetween them. 'a' and 'negation a' will give True. Anything 'OR'ed with True will be true. Hence that will also become a Tautology.

Option B

1 vote

Option B is right choice it can be calculated from several methods:-like table method ,T->F method(The only condition which is false in implies so we focus to get T->F in this method),and may be others

0 votes
(A)    (a → b) ^ (b → c)) →  (a → c)

         (a'+b)(b'+c) →(a'+c)





          1+a'+c      (becoz (b+b')=1

          1(true)......    so tautology

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



            1+b'           (becoz (a+a')=1 and c+c' =1

             1(true)          so tautology

(D)         a→(b→a)



              1(true)           so tautology

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







                  (a'c+ac)+(ac'+ac)+b           (becoz a+a+a+a+....+a =a)


                  a+b+c       so not a tautology

edited by

Related questions

9 votes
8 answers
Which of the following data structure is useful in traversing a given graph by breadth first search? Stack Queue List None of the above
asked May 10, 2017 in Algorithms Arjun 7.9k views
7 votes
4 answers
What is the minimum number of two-input $\text{NAND}$ gates used to perform the function of two-input $\text{OR}$ gate? One Two Three Four
asked May 10, 2017 in Digital Logic Arjun 5.7k views
13 votes
4 answers
The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be a. $O(n\log n)$ b. $O\left( n^{3/2}\right)$ c. $O( n^3 )$ d. $O(n)$
asked May 7, 2017 in Algorithms sh!va 3.3k views
4 votes
2 answers
If $L$ and $P$ are two recursively enumerable languages then they are not closed under Kleene star $L^*$ of $L$ Intersection $L \cap P$ Union $L \cup P$ Set difference
asked May 7, 2017 in Theory of Computation sh!va 4.5k views