Converting boolean expression into disjunctive normal form

dee93 · 2013-08-12 04:07:07

Hi,everyone I am struggling with some homework on discrete mathematics can anyone help me with the following question?

Last edited by dee93 (2013-08-18 03:35:46)

Bob · 2013-08-12 05:16:23

hi dee93

Welcome to the forum.

I thought (pq + r) meant (p AND q OR r) so now I'm confused as all these expressions appear to be in DNF already. Have I got this wrong?

Please take a look at

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

and

http://homepages.math.uic.edu/~kauffman/BooleanAlg.pdf

and then post again. I'm fairly confident I can do the manipulations but what am I trying to achieve?

Bob

dee93 · 2013-08-12 05:56:52

bob bundy wrote:

hi dee93
Welcome to the forum.
I thought (pq + r) meant (p AND q OR r) so now I'm confused as all these expressions appear to be in DNF already. Have I got this wrong?

and then post again. I'm fairly confident I can do the manipulations but what am I trying to achieve?
Bob

thanks for the welcome.
I have no idea,this is a homework question and i've been asked to put these into dnf but you think they already are thats very strange.
i have also been asked to simplify them using a kavanaugh map?

bobbym · 2013-08-12 05:58:29

I think you mean a Karnaugh map.

Bob · 2013-08-12 06:46:09

I can simplify one:

eg

p'q' + q = (p' + q)(q' + q) = p' + q ( as q' OR q is always true)

Here are the truth tables: (apologies if the alignment goes wrong; it's quite hard to do a neat table like this)

p ' AND q ' + q
1 0 0 1 0 1 1
1 0 0 0 1 0 0
0 1 0 1 0 1 1
0 1 1 0 1 1 0

p ' + q
1 0 1 1
1 0 0 0
0 1 1 1
0 1 1 0

So both versions give
1
0
1
1

How is DNF defined on your course?

Bob

dee93 · 2013-08-12 06:50:33

bob bundy wrote:

I can simplify one:
eg
p'q' + q = (p' + q)(q' + q) = p' + q ( as q' OR q is always true) note: this is now FULL DNF
Here are the truth tables: (apologies if the alignment goes wrong; it's quite hard to do a neat table like this)
p ' AND q ' + q
1 0 0 1 0 1 1
1 0 0 0 1 0 0
0 1 0 1 0 1 1
0 1 1 0 1 1 0

p ' + q
1 0 1 1
1 0 0 0
0 1 1 1
0 1 1 0
So both versions give
1
0
1
1
How is DNF defined on your course?
Bob

they have called it disjunctive normal function but i assumed its just another word for disjunctive normal form.thanks for that is not possible to convert the others?

Bob · 2013-08-12 07:22:08

But what have you been told it is? You must have been given a rule for it. Or an example.

I'll come clean about this topic.

I did some Boolean algebra and propositional logic back in 1969ish. DNF was not part of it.

So when I saw your question I thought I'd better leave it for someone who knew what it was.

A while later I looked it up on Wiki. It seemed straight forward enough for me to blunder in with a reply.

Wiki says DNF is " it is an OR of ANDs " and all their examples look like this:

(a AND b) OR (c AND d) etc.

If that definition is correct then all your questions have that form already:

(not p AND not q) OR (q)

(p AND q) OR (NOT p AND NOT q AND r)

(a AND b AND c) OR (a AND c)

So I wondered if the questioner wanted FULL DNF or maybe NOT is dis-allowed. But Wiki's examples include NOTs and anyway, some expressions could not be rendered in DNF if NOT was dis-allowed.

If you are able to give the definition according to your course, maybe we can get somewhere.

Bob

dee93 · 2013-08-12 07:50:18

bob bundy wrote:

But what have you been told it is? You must have been given a rule for it. Or an example.
I'll come clean about this topic.
I did some Boolean algebra and propositional logic back in 1969ish. DNF was not part of it.
So when I saw your question I thought I'd better leave it for someone who knew what it was.
A while later I looked it up on Wiki. It seemed straight forward enough for me to blunder in with a reply.
Wiki says DNF is " it is an OR of ANDs " and all their examples look like this:
(a AND b) OR (c AND d) etc.
If that definition is correct then all your questions have that form already:
(not p AND not q) OR (q)
(p AND q) OR (NOT p AND NOT q AND r)
(a AND b AND c) OR (a AND b)
So I wondered if the questioner wanted FULL DNF or maybe NOT is dis-allowed. But Wiki's examples include NOTs and anyway, some expressions could not be rendered in DNF if NOT was dis-allowed.
If you are able to give the definition according to your course, maybe we can get somewhere.
Bob

This is the definiton I found on a lecture note

Disjunctive Normal Form for a Boolean Expression which means

Last edited by dee93 (2013-08-18 03:37:11)

dee93 · 2013-08-12 07:54:41

double post

Last edited by dee93 (2013-08-18 03:37:33)

Bob · 2013-08-12 08:07:39

OK. That's brilliant. Stay on-line and I'll do them all/

Bob

Bob · 2013-08-12 08:19:41

I think that is what Wiki calls Full DNF

(a) pq + q

Second term needs some p bits

p + p' is always true so you can add it.

p'q' + q = p'q' + q(p + p')

clear bracket

p'q' + qp + qp'

tidy up

p'q' + pq + p'q

check with truth table

p ' AND q ' + p AND q + p ' AND q combination of three ORs
1 0 0 1 0 1 1 1 1 0 0 1 1
1 0 0 0 1 1 0 0 1 0 0 0 0
0 1 0 1 0 0 0 1 0 1 1 1 1
0 1 1 0 1 0 0 0 0 1 0 0 1

That took a while to layout so I'll post now and then just do the DNF of the other two without the tables.

Bob

Bob · 2013-08-12 08:25:04

(b) pq + p'q'r

add r bits to first term

= pq(r + r') + p'q'r = pqr + pqr' + p'q'r

(c) abc + ac

add b bits to second term

= abc + a(b + b')c = abc + abc + ab'c

remove repeated term

= abc + ab'c

There's a tie up with set theory so I'll make a diagram that should make it a lot clearer (and show why it is useful)

Next post coming up

Bob

dee93 · 2013-08-12 08:33:02

would you know how to simplify these new dnf expression with a karnaugh map?

Last edited by dee93 (2013-08-12 08:42:30)

Bob · 2013-08-12 08:42:43

Not sure. I'll do some research.

Meanwhile here's a venn diagram version of (b) in three stages. The last diagram shows the DNF version with each section having its own border.

Bob

Bob · 2013-08-12 08:58:01

OK. This is what I can do with a two variable karnaugh map.

(a) p'q' + q

Diagram shows the p'q' box in a yucky yellow colour (if p' and q' are both 1s then p and q are zeros) and all the boxes for q in green.

then I've identified in the second part the three boxes in DNF form.

Now to sort out three variables.

Bob

Bob · 2013-08-12 09:00:29

Corrected diagram

Bob · 2013-08-12 09:17:55

3 variable case:

(b) pq + p'q'r

You have to squeeze up the pq bits to one line.

in the first part of the diagram pq is the green region (two boxes) and p'q'r is the red box.

The DNF version is shown on the right.

Hope that sorts it our for you. I'll leave you to do the third one yourself. Good luck.

Bob

dee93 · 2013-08-12 09:24:20

bob bundy wrote:

3 variable case:
(b) pq + p'q'r
You have to squeeze up the pq bits to one line.
in the first part of the diagram pq is the green region (two boxes) and p'q'r is the red box.
The DNF version is shown on the right.
Hope that sorts it our for you. I'll leave you to do the third one yourself. Good luck.
Bob

brilliant if you could do the same for the other 2 dnf expressions that would be great

Bob · 2013-08-13 05:39:41

?? Did you look at all my recent posts?

Bob

dee93 · 2013-08-13 06:24:04

bob bundy wrote:

?? Did you look at all my recent posts?
Bob

yes but i think you missed one out. abc + ac if you could also simplify that in its dnf form using the map like you have done the others?

Last edited by dee93 (2013-08-13 06:29:15)

Bob · 2013-08-13 06:36:09

Try it yourself and I'll help out if you get stuck. (after all, I need to know that I've successfully taught you something )

Step 1: Make a set of boxes for three variables. What goes across the top and what down the side?

Bob

dee93 · 2013-08-13 08:56:26

bob bundy wrote:

Try it yourself and I'll help out if you get stuck. (after all, I need to know that I've successfully taught you something )
Step 1: Make a set of boxes for three variables. What goes across the top and what down the side?
Bob

a on top b on side?

Bob · 2013-08-13 10:12:26

and where will you put c ?

Look at post 17

Bob

dee93 · 2013-08-13 10:50:46

bob bundy wrote:

and where will you put c ?
Look at post 17
Bob

some where in the boxes?

Bob · 2013-08-13 18:33:00

see diagram

Then decide which boxes to shade

Bob

Math Is Fun Forum

#1 2013-08-12 04:07:07

Converting boolean expression into disjunctive normal form

#2 2013-08-12 05:16:23

Re: Converting boolean expression into disjunctive normal form

#3 2013-08-12 05:56:52

Re: Converting boolean expression into disjunctive normal form

#4 2013-08-12 05:58:29

Re: Converting boolean expression into disjunctive normal form

#5 2013-08-12 06:46:09

Re: Converting boolean expression into disjunctive normal form

#6 2013-08-12 06:50:33

Re: Converting boolean expression into disjunctive normal form

#7 2013-08-12 07:22:08

Re: Converting boolean expression into disjunctive normal form

#8 2013-08-12 07:50:18

Re: Converting boolean expression into disjunctive normal form

#9 2013-08-12 07:54:41

Re: Converting boolean expression into disjunctive normal form

#10 2013-08-12 08:07:39

Re: Converting boolean expression into disjunctive normal form

#11 2013-08-12 08:19:41

Re: Converting boolean expression into disjunctive normal form

#12 2013-08-12 08:25:04

Re: Converting boolean expression into disjunctive normal form

#13 2013-08-12 08:33:02

Re: Converting boolean expression into disjunctive normal form

#14 2013-08-12 08:42:43

Re: Converting boolean expression into disjunctive normal form

#15 2013-08-12 08:58:01

Re: Converting boolean expression into disjunctive normal form

#16 2013-08-12 09:00:29

Re: Converting boolean expression into disjunctive normal form

#17 2013-08-12 09:17:55

Re: Converting boolean expression into disjunctive normal form

#18 2013-08-12 09:24:20

Re: Converting boolean expression into disjunctive normal form

#19 2013-08-13 05:39:41

Re: Converting boolean expression into disjunctive normal form

#20 2013-08-13 06:24:04

Re: Converting boolean expression into disjunctive normal form

#21 2013-08-13 06:36:09

Re: Converting boolean expression into disjunctive normal form

#22 2013-08-13 08:56:26

Re: Converting boolean expression into disjunctive normal form

#23 2013-08-13 10:12:26

Re: Converting boolean expression into disjunctive normal form

#24 2013-08-13 10:50:46

Re: Converting boolean expression into disjunctive normal form

#25 2013-08-13 18:33:00

Re: Converting boolean expression into disjunctive normal form

Board footer