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

You are not logged in.

• Index
•  » Exercises
•  » Converting boolean expression into disjunctive normal form

## #1 2013-08-13 02:07:07

dee93
Member

Offline

### 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-19 01:35:46)

## #2 2013-08-13 03:16:23

bob bundy
Moderator

Offline

### 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

## #3 2013-08-13 03:56:52

dee93
Member

Offline

### 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?

## #4 2013-08-13 03:58:29

bobbym
Administrator

Online

### 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.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

## #5 2013-08-13 04:46:09

bob bundy
Moderator

Offline

### 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

## #6 2013-08-13 04:50:33

dee93
Member

Offline

### 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?

## #7 2013-08-13 05:22:08

bob bundy
Moderator

Offline

### 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

## #8 2013-08-13 05:50:18

dee93
Member

Offline

### 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-19 01:37:11)

## #9 2013-08-13 05:54:41

dee93
Member

Offline

### Re: Converting boolean expression into disjunctive normal form

double post

Last edited by dee93 (2013-08-19 01:37:33)

## #10 2013-08-13 06:07:39

bob bundy
Moderator

Offline

### 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

## #11 2013-08-13 06:19:41

bob bundy
Moderator

Offline

### 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

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

bob bundy
Moderator

Offline

### 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

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

dee93
Member

Offline

### 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-13 06:42:30)

## #14 2013-08-13 06:42:43

bob bundy
Moderator

Offline

### 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

Uploaded Images

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

## #15 2013-08-13 06:58:01

bob bundy
Moderator

Offline

### 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

Uploaded Images

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

## #16 2013-08-13 07:00:29

bob bundy
Moderator

Offline

### Re: Converting boolean expression into disjunctive normal form

Corrected diagram

Uploaded Images

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

## #17 2013-08-13 07:17:55

bob bundy
Moderator

Offline

### 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.

Bob

Uploaded Images

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

## #18 2013-08-13 07:24:20

dee93
Member

Offline

### 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.

Bob

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

## #19 2013-08-14 03:39:41

bob bundy
Moderator

Offline

### 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

## #20 2013-08-14 04:24:04

dee93
Member

Offline

### 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-14 04:29:15)

## #21 2013-08-14 04:36:09

bob bundy
Moderator

Offline

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

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

## #22 2013-08-14 06:56:26

dee93
Member

Offline

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

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?

## #23 2013-08-14 08:12:26

bob bundy
Moderator

Offline

### 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

## #24 2013-08-14 08:50:46

dee93
Member

Offline

### 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?

## #25 2013-08-14 16:33:00

bob bundy
Moderator

Offline

### Re: Converting boolean expression into disjunctive normal form

see diagram

Then decide which boxes to shade

Bob

Uploaded Images

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

• Index
•  » Exercises
•  » Converting boolean expression into disjunctive normal form

## Board footer

Powered by FluxBB