The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+15 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.

+22 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.

+18 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.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,756 questions

52,850 answers

183,548 comments

68,742 users