Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Converting boolean expression into disjunctive normal form

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)

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

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


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

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?

Offline

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

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,744

Re: Converting boolean expression into disjunctive normal form

I think you mean a Karnaugh map.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Online

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

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


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

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?

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

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


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

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)

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

double post

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

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

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

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

I think that is what Wiki calls Full DNF

(a)    p’q’ + 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


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

(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


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

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

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

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

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

View Image: dee93.gif View Image: dee93b.gif View Image: dee93c.gif

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

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

View Image: dee93d.gif

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

Corrected diagram

View Image: dee93d.gif

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

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.

smile

Bob

View Image: dee93e.gif

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

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.

smile

Bob

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

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

?? Did you look at all my recent posts?

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

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)

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

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

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

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

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

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?

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

and where will you put c ?

Look at post 17

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

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

dee93
Member
Registered: 2013-08-12
Posts: 19

Re: Converting boolean expression into disjunctive normal form

bob bundy wrote:

and where will you put c ?

Look at post 17

Bob

some where in the boxes?dunno

Offline

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

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,395

Re: Converting boolean expression into disjunctive normal form

see diagram

Then decide which boxes to shade

Bob

View Image: dee93e.gif

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

Board footer

Powered by FluxBB