Hacker News Reader

Comment by _0ffh | Hacker News Reader

I would guess that NAND and NOR might better lend themselves to practical physical implementation.

Also: If you don't limit yourself to 2-input/1-output gates, there's loads more universal gates. Many 3-in/3-out reversible gates are universal [1]. I really have a soft spot for the Fredkin, it just seems so elegant.

[1] http://www.thefullwiki.org/Three-input_universal_logic_gate

View on HN

The monotone, linear, etc. functions are called clones and the clones form a lattice called Post's Lattice

https://en.wikipedia.org/wiki/Post%27s_lattice

Given several logic gates, if their most recent common ancestor in the lattice is the clone of all boolean functions, then that set is universal. This provides a convenient prescription for deciding universality for a new k-input gate.

It really is about physical implementation. In TTL "single input NAND" and invertor is the same physical structure and extending it to multiple inputs involves just adding additional emitters to one BJT structure. For CMOS logic, NOR is the smallest two-input "true" gate, because PMOS transistors have to be larger than NMOS and two series connected MOS transistors can be collapsed into one structure with multiple gates that is significantly smaller than two connected transistors.

> I really have a soft spot for the Fredkin, it just seems so elegant.

I agree. It’s so simple, yet it easily leads to other seeminly-more-complicated gates, simply by ignoring some of the inputs or outputs.

Plus it has the feature that the # of on inputs always equals the # of on outputs. And the feature that it’s reversible. Really a cool gate all around.

Reply on news.ycombinator.com