CODEWITHSUNDEEP
boolean-logicboolean-algebracircuit-diagram
Mary Tim
Mary Tim

Reputation: 23

Writing an expression using only NAND, OR, XNOR

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?

Upvotes: 0

Views: 1059

Answers (3)

Stanislav Kralin
Stanislav Kralin

Reputation: 11479

Simple solution

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

circuit using nand, 4 gates

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

circuit using xnor and xor, 3 gates

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.

Upvotes: 1

diginoise
diginoise

Reputation: 7620

You can build NOT from NAND:

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

NOT from NAND

Upvotes: 2

Abhay Katheria
Abhay Katheria

Reputation: 19

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

s' = nand(s,s)

Upvotes: 1

Related Questions