# Using deMorgans theorem

Discussion in 'Homework Help' started by ann, Mar 1, 2008.

1. ### ann Thread Starter Member

Feb 15, 2008
14
0
I have tried to reduce these three equations using demorgan's but I don't even know where to start from. In my result I need to have not more than 4 nand gates,6 not gates,4 and gates and 4 or gates.

1. P1=/C/D+CD
2. P2=/B/C/D+BD+BC

some guidance will be appreciated.

2. ### Dave Retired Moderator

Nov 17, 2003
6,960
146
The trick is the same as all your previous questions:

1) Take out common factors to simplify expression.

2) Double NOT the function - this doesn't change the function.

3) Then apply DeMorgan's theorems.

4) After applying DeMorgan's theorems simplify, and reapply DeMorgan's if necessary.

I gave you a lengthy response in a previous thread. Have a look there, and have a go. Post up your attempts I will be happy to give you some guidance.

Dave

3. ### MilK Member

Mar 1, 2008
25
0
Anyway 1 nand gates = 1 not gate
2 nand gates = 1 and gate
3 nand gates = 1 or gate

Nov 9, 2007
5,005
515
5. ### ann Thread Starter Member

Feb 15, 2008
14
0
Dave,

I think my problem is I am not seeing the reduction form of the equation even after using demorgan's. Please explain to me in the example below. I think once I understand it, I will be able to solve any other problem. As an example I did
P=B'C'D'+BD+BC
= '(B+C+D) (B+D) (B+C)

If I not again, then I am getting to the first step again. I really want to understand how to use demorgan's.

6. ### ann Thread Starter Member

Feb 15, 2008
14
0
Dave,

Here is what I have as my work outs.

1. P1= C'D'+CD

(CD)'+CD AND SINCE A'+A=1

(CD)'+CD=1

2. P2=B'C'D'+BD+BC
B(D+C)+B'C'D'
B(D'+C')'+B'C'D'
BDC+B'C'D'
BDC+(BDC)' =1 BECAUSE A+A'=1

3. P3=A'D+A'C+AB'C'D'+A'B
A'(D+C)+AB'C'D'+A'B
NOT DC and AB'C'D'
A'DC+A+B'+C'+D'+A'B
A'(DCB)+A+B'+C'+D'
NOTA+B'+C'+D'
A'(DCB)+AB+CD
NOT A'(DCB)
A'+B+C+D+AB+CD
NOT A'+B and C+D
A'B+CD+AB+CD
B(A'+A)+CD+CD
B+CD+CD FROM A+A=A
= B+A

A(B+D+C)
NOT ABCD
A+B+C+D
NOT (A+B) and (C+D)
AB+CD

I have done my best, please correct me where am wrong.

7. ### Dave Retired Moderator

Nov 17, 2003
6,960
146
Ok, lets deal with them one by one.

It's not clear how you have come to this answer. Perhaps you could show the working out for this.

So we're clear, you are happy with the notion of DeMorgans:

(A + B)' = A'.B'

(A.B)' = A' + B'

This can be extrapolated for an arbitrary number of inputs.

Now for P=B'C'D'+BD+BC

This one is a bit of a misnomer. You can get stuck in a circle of applying DeMorgan's and end up at the starting equation. As for what constitutes simplified, I have gone for the number of transistors in a CMOS implementation as the benchmark.

Let me know if you are unfamiliar with the CMOS implementation of logic gates and I will explain, it is a very useful metric for deducing the minimum footprint of an expression.

The starting equation can be implemented using the following gates (CMOS transistors in brackets):

1 x 3 I/P AND (1 x 6 = 6)
2 x 2 I/P AND (2 x 4 = 8)
1 x 3 I/P OR (1 x 6 = 6)
3 x INV (3 x 2 = 6)

Total number of transistors = 26

Just taking out B as a common factor reduces the number of transistors:

P=B'C'D'+B(D+C)

1 x 3 I/P AND (1 x 6 = 6)
1 x 2 I/P AND (1 x 4 = 4)
2 x 2 I/P OR (2 x 4 = 8)
3 x INV (3 x 2 = 6)

Total number of transistors = 24

The simplification can get it down to 20 transistors:

P = B'C'D'+BD+BC

Double NOT the function:

P = (B'C'D'+BD+BC))''

Take DeMorgans, (A + B)' = A'B'

P = ((B'C'D')'(BD)'(BC)')'

Take DeMorgans on (B'C'D')' and remember B'' = B etc

P = ((B + C + D)(BD)'(BC)')'

Take DeMorgans on (BD)'

P = ((B + C + D)(B' + D')(BC)')'

Take DeMorgans on (BC)'

P = ((B + C + D)(B' + D')(B' + C'))'

Note the identity (B' + D')(B' + C') = (B' + D'C') - proof

P = ((B + C + D)(B' + D'C'))'

Take DeMorgans again on the whole expression

P = (B + C + D)' + (B' + D'C')'

Take DeMorgans on (B' + D'C')', remember B'' = B

P = (B + C + D)' + (B(D'C')')

Take DeMorgans on (D'C')', remember D'' = D and C'' = C, this gives the simplified expression

P = (B + C + D)' + (B(D + C))

In transistors:

1 x 2 I/P AND (1 x 4 = 4)
2 x 2 I/P OR (2 x 4 = 8)
1 x 3 I/P OR (1 x 6 = 6)
1 x INV (1 x 2 = 2)

Total number of transistors = 20

Can you see how I have used DeMorgans here to simplify the expression? If you are unsure about any of the steps or how the transistor implementation work let me know.

Once you happy with this, we can move onto the others. When you understand the basics its just a case of application and a bit of patience.

Dave