News for hackers. Stuff that matters.
Re:Universal Logic Gates (2015) by cperciva on Sunday June 16, 2019 @08:37PM (#20198872)
Of the 16 possible 2-input/1-output gates:

* 8 of them are linear, in that the output is A xor (B and X) xor (C and Y). Any combination of these can only ever generate linear combinations of their inputs, thus they cannot be universal.

* 6 of them are monotonic, in that X op Y <= X' op Y' if X <= X' and Y <= Y'. Any combination of these can only ever generate monotonic functions of their inputs, thus they cannot be universal.

* 4 gates (0, X, Y, 1) are both linear and monotonic.

* The 6 gates which are neither linear nor monotonic are universal.

There are no comments on this comment yet.