The Gateway to Computer Science Excellence

+20 votes

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?

- Every Boolean expression is equivalent to an expression in sum of product form.
- Every Boolean expression is equivalent to an expression in product of sum form.
- Every Boolean expression is equivalent to an expression without $\vee$ operator.
- Every Boolean expression is equivalent to an expression without $\wedge$ operator.
- Every Boolean expression is equivalent to an expression without $\neg$ operator.

+27 votes

Best answer

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.

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.

+23 votes

Answer will be (E)

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,312 answers

198,347 comments

105,046 users