Logic gates

Topic: Neural units · more questions on this topic
‹ Derivative of the sigmoid A decision boundary ›

Find weights and a bias for a single threshold unit that computes (a) AND, (b) OR, (c) NAND, of two binary inputs. Why can a single unit not compute XNOR, the complement of XOR?

Worked answer (click to show)

AND: w=(1,1)^\top, w_0=-1.5. The net input x_1+x_2-1.5 is nonnegative only for (1,1).
OR: w=(1,1)^\top, w_0=-0.5. Then x_1+x_2\ge 0.5 unless both inputs are 0.
NAND: negate AND, so w=(-1,-1)^\top, w_0=1.5. The net input 1.5-x_1-x_2 is nonnegative unless both inputs are 1.

XNOR has the pattern (0,0)\to 1, (0,1)\to 0, (1,0)\to 0, (1,1)\to 1. It is the complement of XOR. The four inequalities of the XOR argument reverse in sense:

w_0\ge 0,\qquad w_0+w_1<0,\qquad w_0+w_2<0,\qquad w_0+w_1+w_2\ge 0.

Adding the middle two gives 2w_0+w_1+w_2<0, while the first and the last give 2w_0+w_1+w_2\ge 0. No single threshold unit computes XNOR.