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

You are not logged in.

- Topics: Active | Unanswered

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

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

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

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

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

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

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

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

Offline

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

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**1011**

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

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

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 011

1 0 0 0 100

0 1 0 1 011

0 1 1 0 110p '

+q

1 011

1 000

0 111

0 110So both versions give

1

0

1

1How 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

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

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

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

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

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

double post

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

Offline

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

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

Bob

Offline

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

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

Offline

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

(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

Offline

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

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

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

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

Offline

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

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

Offline

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

Corrected diagram

Offline

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

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

Offline

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

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

Offline

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

?? Did you look at all my recent posts?

Bob

Offline

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

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

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

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

Offline

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

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?

Offline

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

and where will you put c ?

Look at post 17

Bob

Offline

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

bob bundy wrote:

and where will you put c ?

Look at post 17

Bob

some where in the boxes?

Offline

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

see diagram

Then decide which boxes to shade

Bob

Offline