Electrical – Creating a logic circuit with only NAND gates

In positive true logic, an AND can be described by "all ones make a one".

The same circuit, in negative true logic, can be described by "any zero makes a zero.", which is an OR.

So, a positive true AND is exactly equivalent to a negative true OR.

In the same vein, a positive true NAND (all ones make a zero) becomes "any zero makes a one", a positive true OR (any one makes a one) becomes "all zeroes make a zero" and a positive true NOR (any one makes a zero) becomes "all zeroes make a one"

UPDATE:

The difference between positive true and negative true logic is in their different symbologies and in the way logic circuits are thought about, used, and presented.

The following graphic shows the four basic logic gates: the AND, the NAND, the OR, and the NOR in both their conventional and negative true garb, along with the truth table for each gate. It's important to note that the truth table is the same for the positive and negative true symbols, and that both symbols represent the same thing in hardware. For example, the AND pair could be for an HC08, the NAND pair for an HC00, the OR pair for an HC32, and the NOR pair for an HC02.

Now for the cool part... :)

Take a look at the positive true AND symbol and you'll notice that its inputs, A and B terminate into a straight line and that its output, Y, comes out of a semicircle. The semicircle doesn't mean much of anything, but the straight line means that the output will only go true when both inputs (since neither is a bubble) are ones, which is when A \$ \style{color:red;font-size:100%}{AND}\$ B are both ones.

But what about when A and B aren't both ones,?

Then we have a situation where if one, or the other, or both of the inputs are low, the output will also be low, which is a logical OR when looked at from the point of view of lows on the inputs.

Voila! negative true logic is born!.

The symbol to the right of the positive true AND has a curvy input, which indicates "any", so if any of its inputs is low its output will be low as well.

The bubbles indicate logical zeroes.

So why should we muck about with this when its just as easy to use positive true logic symbology?

Strangely enough, to reduce confusion.

My favorite example is an RS NAND latch where the gates are depicted as positive true and yet need low-going signals to switch.

Befuddling to many a cadet, I think.

The 4-gate implementation of the XOR function requires the output of one of the gates to be used twice. As far as I know, there's no direct algorithmic way to come up with such solutions; they must be "discovered".

In a sense, you have to "de-optimize" the solution before optimizing it, and knowing what deoptimization step makes sense is a matter of intuition. In this case, it requires the observation* that

$$A\cdot\overline{B} = A\cdot\overline{(A\cdot B)}$$

and

$$\overline{A}\cdot B = \overline{(A\cdot B)}\cdot B$$

and then realizing that the \$\overline{(A\cdot B)}\$ term for both right-hand expressions can be generated by the same gate.

*The details:

Since \$A\cdot\overline{A} = 0\$, you can add this term to any expression without changing it:

$$A\cdot\overline{B} = A\cdot\overline{A} + A\cdot\overline{B}$$

Now, factor out the A

$$\ldots = A\cdot(\overline{A} + \overline{B})$$

and apply DeMorgan's:

$$\ldots = A\cdot\overline{(A\cdot B)}$$