Writing an expression using only NAND, OR, XNOR

Question

I have a 2-1 mux and I'm trying to write z = s'd0 + sd1 using only NAND, XNOR, and OR gates (not necessarily all of them).

I tried simplifying it and what I ended up with is z = NAND(NAND(s', d0), NAND(s, d1)), but I can't use NOT ('), so is there a way to write NAND(s', d0) without the NOT?

Answer 1

You can build NOT from NAND:

NAND(X,X) == NOT(X)

Answer 2

NAND gate is an universal gate; you can use it to make any other gate.

s' = nand(s,s)

Answer 3

Simple solution

Full version of the solution proposed by others is (A NAND S) NAND (B NAND (S NAND S)) .

By the way, NOT X could also be expressed as X NAND 1, not only as X NAND X.

Advanced solution

(S OR (A XNOR B)) XNOR A

The latter solution is definitely more interesting:

• It uses a fewer number of gates (though of two different types).
• It uses not functionally complete set of gates (thereby is less trivial).

How to find the latter solution?

1. Construct the Zhegalkin polynomial of 2:1 mux and simplify it slightly: (S AND (A XOR B)) XOR B.
2. Note that the boolean function dual to 2:1 mux is also 2:1 mux, but for swapped input signals.
3. Now "dualize" the polynomial (replace AND and XOR with OR and XNOR respectively) and swap A with B.