# TIFR2015-B-9

917 views

A Boolean expression is an expression made out of propositional letters (such as $p, q, r$) and operators $\wedge$, $\vee$ and $\neg$; e.g. $p\wedge \neg (q \vee \neg r)$. An expression is said to be in sum of product form (also called disjunctive normal form) if all $\neg$ occur just before letters and no $\vee$ occurs in scope of $\wedge$; e.g. $(p\wedge \neg q) \vee (\neg p \wedge q)$. The expression is said to be in product of sum form (also called conjunctive normal form) if all negations occur just before letters and no $\wedge$ occurs in the scope of $\vee$; e.g. $(p\vee \neg q) \wedge (\neg p \vee q)$. Which of the following is not correct?

1. Every Boolean expression is equivalent to an expression in sum of product form.
2. Every Boolean expression is equivalent to an expression in product of sum form.
3. Every Boolean expression is equivalent to an expression without $\vee$ operator.
4. Every Boolean expression is equivalent to an expression without $\wedge$ operator.
5. Every Boolean expression is equivalent to an expression without $\neg$ operator.

edited
0
They have mentioned wrong in question. Sum of product is conjunctive normal form and not disjunctive normal form. And product of sum is disjunctive normal form and not conjunctive normal form.
1

No, In question, they have mentioned correctly.

https://en.wikipedia.org/wiki/Disjunctive_normal_form

Basically they are saying all the same thing as what we have see. for ex just simplify this. use  and operator ( . ) for ^ . so sop will become $(p.q') + (p'.q)$

So, no meaning have been changed and we can move further with all the boolean logic we have read.

We know every expression can be expressed in pos or sop form so, $1$ and $2$ are true.

We know that AND and NOT are functionally complete. so any expression can be expressed using these two only. so all the expression can be expresed in a form which does not contain OR but contain and and not,
with the same logic point $4$ will be true because we know not and OR are also functionally complete.

But without NOT we can't get a functionally complete gate. so E is wrong.

edited
0

Though this is a good answer but definitely needs some edits.

@Arjun Sir.

a) True. Every expression can be written in SOP form

b) True. Every expression can be written in POS form

c)True. We can write OR in the form of AND. e.g.(A+B)=not(not(A) . not(B))

d)True.We can write AND in the form of OR e.g. (A .B)=not(not(A) + not(B))

(e)False. We cannot convert NOT gate to any other gate. We cannot also get NAND , NOR such universal gate without NOT gate. So, without NOT gate we cannot get every boolean expression

0
perfect!
0
Great Explaination ....
0
0

## Related questions

1
363 views
Consider a square of side length $2$. We throw five points into the square. Consider the following statements: There will always be three points that lie on a straight line. There will always be a line connecting a pair of points such that two points lie on one side of the line and one point on the ... the above is true: $(i)$ only. $(ii)$ only. $(iii)$ only. $(ii)$ and $(iii)$. None of the above.
Consider the following grammar (the start symbol is $E$) for generating expressions. $E \rightarrow T - E \mid T + E \mid T$ $T \rightarrow T * F \mid F$ $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$ With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?
Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently). x:=1 cobegin x:= x + 1 || x:= x + 1 || x:= x + 1 coend Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values of $x$ ... $\left \{2, 4 \right \}$ $\left \{ 2, 3 \right \}$ $\left \{2 \right \}$
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ if and only $( \pi (u), \pi (v)) \in E_{2}$. Consider the ... (ii) $L$ is $NP$- hard. (iii) $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$