🚀 go-pugleaf

On Tue, 06 May 1997 15:47:08 +0800, felixmeister
<gaynos@icenet.com.au> wrote:

>Can anyone please help with a problem.
>
>How can you show that any minimal AND/OR circuit can be replaced by an
>equivalent circuit that uses the same number of NAND gates as in the
>AND/OR circuit and no logic gates of any other kind.
>
>regards
>
>Andrew Poli

Just use the DeMorgan theorem: to get the complement of an expression,
complement all the terms in it, and change AND for OR and OR for AND.

I don't know if this is clear enough. For example:

Let's say we have the AND/OR expression: (A*B)+(C*D)

If we complement it twice, we get the same result: ((A*B)+(C*D))''

Now, using the inner negation and DeMorgan theorem, we get the
expression:

((A*B)' * (C*D)')' 

And this expression simply states: (A NAND B) NAND (C NAND D)

And there it is. We have three NAND gates were we had 2 AND and 1 OR

I think that was your question. If you want anything moe, just ask.



Alberto Rodriguez Prieto
alberto_rp@iponet.es
Madrid. Spain