🚀 go-pugleaf

In article <336EE1FC.76A5@icenet.com.au>, felixmeister
<gaynos@icenet.com.au> writes:

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

I don't know about the number of gates, but NAND gates are "functionally
complete."
That is, they can be used to create any other logic circuit all by
themselves.  The And /OR pair is NOT complete.  Other gates and
combinations of other gates are also functionally complete.  I'd start by
looking up that phrase on your own to start.

Standard Boolean minimization methods(maximal cubes, simultaneous
minimizations,cyclic tables, etc, etc), can be used to greatly reduce the
required number of gates in a circuit, but that is irrespective of the
gates used.   It is only  dependent on the number of inputs, and the input
truth table. 

Of course minimizations based upon particular gates (ie NAND or NOR, etc)
would hopefully reduce the gate count even further.  

An old book, the one I used in school,is:

"Mathematical Theory of Switching Circuits and Automata"  by  Sze-tsen Hu

Univ. of Cal. Press,  1968

I hope that is of some help.
                                           H Higgins