-3
$\begingroup$

Can someone explain for me how to build a XOR gate using 5 NOR gates? The thing I'm looking for is a proof similar to this:

$A^B\ =\ (!A)B\ +\ A(!B)$

$=\ !!((!A)B)\ +\ !!(A(!B))$

$=\ !(!!A\ +\ !B)\ +\ !(!A\ +\ !!B)$

$=\ !(A\ +\ !B)\ +\ !(!A\ +\ B)$

$=\ !((A\ +\ !B)(!A\ +\ B))$

$=\ !(A(!A)\ +\ AB\ +\ (!A)(!B)\ +\ B(!B))$

$=\ !(AB\ +\ (!A)(!B))$

$=\ !(AB)(!(!A)(!B))$

$=\ !(AB)(!!A\ +\ !!B)$

$=\ !(AB)(A+B)$

$=\ !(AB)A\ +\ !(AB)B$

$=\ !!(!(AB)A\ +\ !(AB)B)$

$=\ !((!(!(AB)A))(!(!(AB)B)))$

$\endgroup$
3
  • 2
    $\begingroup$ This can be answered by a very simple Google query $\endgroup$
    – Pål GD
    Mar 29 at 20:19
  • $\begingroup$ geeksforgeeks.org/implementation-of-xor-gate-from-nor-gate this link provides solution. and I got result by simply typing in google search: "XOR gate with 5 nor gates" $\endgroup$
    – math boy
    Mar 29 at 21:34
  • $\begingroup$ @mathboy this was not what I was looking for, I already did that type of search before asking this question. In the website you linked they only explain it starting from the circuit implementation. What I woul like to know is how you can prove it starting from an expression and then using only formulas step by step. Maybe I wasn't clear enough. Sorry and thank you for the answer. $\endgroup$ Mar 30 at 11:31

2 Answers 2

3
$\begingroup$

The brute force approach: There are 16 functions with two arguments, and 65,536 sets of such functions. Initially with 0 gates you have two functions: A and B.

Calculate all sets that you can build with one nor gate. You can implement a nor a = not a with one gate, or not b, or a nor b. So you create three sets by adding one of these three functions to your existing set.

Calculate all sets that you can build with two nor gates, by adding x nor y with x, y being any of the three existing set members. Then all sets needing three, four or five gates. And hope the last gate contains your expression.

This approach also lets you solve questions like “how do I implement these three functions simultaneously with the minimum number of nor gates”.

$\endgroup$
3
$\begingroup$

a xor b = x nor y. We need x, y so that x or y = not (a xor b) = (a and b) or (!a and !b). So we try to represent x = (a and b) using nor, and y = (!a and !b), then a xor b = x nor y.

y is easy: !a and !b = ! (a and b) = a nor b.

!a = a nor a, !b = b nor b, so x = ((a nor a) nor (b nor b)), and that’s it.

a xor b = ((a nor a) nor (b nor b)) nor (a nor b).

$\endgroup$
1
  • $\begingroup$ Interesting. Wikipedia gives two "implementations" of XOR using NOR gates. This is the second one. The other implementation is not in tree format, meaning that one gate-output is reused as input in two different gates. I now realize that the non-tree implementation cannot be obtained by straightforward algebraic manipulation, as logical formulas are in itself tree-like. $\endgroup$ Apr 1 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.