Using deMorgans theorem

Thread Starter

ann

Joined Feb 15, 2008
14
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
3. P3=/AD+/AC+A/B/C/D+/AB
4. P4= AB+AD+AC

some guidance will be appreciated.
 

Dave

Joined Nov 17, 2003
6,970
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
 

Thread Starter

ann

Joined Feb 15, 2008
14
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.
 

Thread Starter

ann

Joined Feb 15, 2008
14
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

P4= AB+AD+AC
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.
 

Dave

Joined Nov 17, 2003
6,970
Ok, lets deal with them one by one.

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