search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
20 votes
3.5k views

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

  1. $((\,a\,\to\,b\,)\,\wedge\,(\,b\,\to\,c))\,\to\,(\,a\,\to\,c)$
  2. $(\,a\,\to\,c\,)\,\to\,(\,\sim b\,\to\,(a\,\wedge\,c))$
  3. $(\,a\,\wedge\,b\,\wedge\,c)\,\to\,(\,c\vee\,a)$
  4. $a\,\to\,(b\,\to\,a)$
in Mathematical Logic
edited by
3.5k views

5 Answers

31 votes
 
Best answer
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$ AND $c$ is false if both $a$ and $c$ are false or one of them is true and other is false.

Now, if $a$ and $c$ both are false then $a\to c$ is true. Now ,LHS is $\text{true}$ and RHS is $\text{false}.$

So option b is not tautology..

edited by
0
In option C if a and b are false and c is true then the proposition should be F --> T. Then, the proposition should be false and hence it must not be tautology. Am I correct ?
0

No,you are not correct.Conditional statement P->q is false only when p is true and q is false and true otherwise.

You can also check in this way-

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

≡~(a∧b∧c)∨ (c∨a)

(~a∨~b∨~c)∨ (c∨a)

(~a∨a)∨(~b∨b)∨ c

≡T∨T∨c

≡T∨c

≡T

Hence,(a∧b∧c)→(c∨a) is tautology.

0
i am not able to get it for option a)
a) can be reduced like this:
((a`+b)(b`+c))`+a`+c
:= ab` + bc` + a` + c

now how this is a tautology?
1
now for quick check put any combination of 0 and 1 you will get 1 always.
1
thanks :)
0
welcome :)
3

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

0

LeenSharma  putting 0/1 can be time consuming because we may have to check all the combination and that can be frustrating in exam.

1
Solving by boolean algebra rules is quite easy :)
13 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.
0
All doubts are cleared.Nice explanation.
11 votes

option B reduces to A+B rest all reduces to 1

Hence, B is not a tautology.

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.
0 votes
we can also solve it by satisfying the T(try to make LHS true) and F(try to make RHS False) condition of ->(implication), if it satisfied then it is NOT tautology. if it is not then it is Tautology. Answer is B
Answer:

Related questions

29 votes
10 answers
1
4.5k views
Which one of the following propositional logic formulas is TRUE when exactly two of $p,q$ and $r$ are TRUE? $(( p \leftrightarrow q) \wedge r) \vee (p \wedge q \wedge \sim r)$ $( \sim (p \leftrightarrow q) \wedge r)\vee (p \wedge q \wedge \sim r)$ $( (p \to q) \wedge r) \vee (p \wedge q \wedge \sim r)$ $(\sim (p \leftrightarrow q) \wedge r) \wedge (p \wedge q \wedge \sim r) $
asked Sep 28, 2014 in Mathematical Logic jothee 4.5k views
2 votes
2 answers
2
53 votes
3 answers
3
9.4k views
Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, ... be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________
asked Sep 28, 2014 in Operating System jothee 9.4k views
53 votes
5 answers
4
7.5k views
SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below: select * from R where a in (select S.a from S) select R.* from R, S where R.a ... R,(select distinct a from S) as S1 where R.a=S1.a select R.* from R,S where R.a=S.a and is unique R
asked Sep 28, 2014 in Databases jothee 7.5k views
...