28 votes 28 votes Which one of the following Boolean expressions is NOT a tautology? $((\,a\,\to\,b\,)\,\wedge\,(\,b\,\to\,c))\,\to\,(\,a\,\to\,c)$ $(\,a\,\to\,c\,)\,\to\,(\,\sim b\,\to\,(a\,\wedge\,c))$ $(\,a\,\wedge\,b\,\wedge\,c)\,\to\,(\,c\vee\,a)$ $a\,\to\,(b\,\to\,a)$ Mathematical Logic gatecse-2014-set2 mathematical-logic propositional-logic normal + – go_editor asked Sep 28, 2014 • edited Jun 25, 2017 by Silpa go_editor 9.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 39 votes 39 votes Another way to solve it... Implication $A\to B$ is not tautology if $B$ is false and $A$ is true. For b option Let RHS ie. $b\to (a\wedge c)$ be false ie $b$ is false and $(a\wedge c)$ is false. Now, $a \wedge c$ is false if either one of them is false. Now, if $a$ and $c$ both are false then $a\to c$ is true. LHS is $\text{true}$ and RHS is $\text{false}.$ So option b is not tautology. Pooja Palod answered Nov 3, 2015 • edited Jan 11, 2023 by shadymademe Pooja Palod comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments amolagrawal commented Jan 12, 2017 reply Follow Share @ Aayushi , := ab` + bc` + a` + c continuing ... = a'+ab' + c+c'b = a'+b' + c+b for details see this http://cs.stackexchange.com/questions/24587/which-law-is-this-expression-x-x-y-xy = a'+c + b+b' = a'+c + 1 = 1 (Tautology) 3 votes 3 votes Aakash_ commented Aug 19, 2018 reply Follow Share LeenSharma putting 0/1 can be time consuming because we may have to check all the combination and that can be frustrating in exam. 0 votes 0 votes Verma Ashish commented Jan 12, 2019 reply Follow Share Solving by boolean algebra rules is quite easy :) 1 votes 1 votes Please log in or register to add a comment.
25 votes 25 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 \rightarrow c)\rightarrow (\sim b \rightarrow(a \wedge c))$ $\equiv \sim(\sim a \vee c)\vee (( b \vee (a \wedge c))$ $\equiv ( a \wedge \sim c)\vee (( b \vee (a \wedge c))$ $\equiv (( a \wedge \sim c)\vee ( a \wedge c) )\vee b$ $\equiv (a \wedge(c \vee \sim c))\vee b$ $\equiv a \vee b $ $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 \rightarrow c)\rightarrow (\sim b \rightarrow(a \wedge c))$ is the correct choice. LeenSharma answered May 15, 2017 LeenSharma comment Share Follow See 1 comment See all 1 1 comment reply Sona Barman commented Nov 11, 2017 reply Follow Share All doubts are cleared.Nice explanation. 0 votes 0 votes Please log in or register to add a comment.
12 votes 12 votes option B reduces to A+B rest all reduces to 1 Hence, B is not a tautology. amarVashishth answered Oct 8, 2015 amarVashishth comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes here, option a,c,d are only give T value by evaluating each parts... And option b does not give any Truth value. hence, b is the answer. pps121 answered Jan 3, 2015 pps121 comment Share Follow See all 0 reply Please log in or register to add a comment.