News for hackers. Stuff that matters.
Re:Universal Logic Gates (2015) by adrian_b on Monday June 17, 2019 @01:19AM (#20200126)
See my answer above. Even if a single universal gate is enough if you disregard speed and cost (area and power consumption) when you implement physical logic circuits speed and cost are essential so you cannot use a single type of universal gate but you must use a small number of basic gates, because each of them has a better implementation from diodes and transistors than an implementation made as a cascade of a single type of universal gates.
Re:Universal Logic Gates (2015) by analognoise on Monday June 17, 2019 @02:03AM (#20200297)
Boolean logic says nothing about implementation.

They're entirely different levels of abstraction.

https://en.wikipedia.org/wiki/Functional_completeness This line in particular: "In digital electronics terminology, the binary NAND gate and the binary NOR gate are the only binary universal logic gates."

Saying that insight isn't useful (that you can reduce any Boolean equation to a single universal gate) - when it is a cornerstone in modern equivalence checking, Boolean SAT solving, and minimization of combinatorial equations) is really, really missing some very key things...

It is the kind of fundamental cornerstone that allows modern digital computers to even exist.

Re:Universal Logic Gates (2015) by kragen on Monday June 17, 2019 @04:15AM (#20200901)
Doesn't equivalence checking normally use BDDs, and SAT solving normally use separate AND, OR, and NOT? I mean the algorithm to reduce an expression to CNF is a pretty simple set of local rewrite rules with AND, OR, and NOT; I could be wrong but I feel like the NAND-based equivalent of CNF is quite a bit hairier.

As for minimizing combinational logic, don't you want to use the full set of gates available to you in that case, taking into account their cost, and maybe trying to minimize or at least limit circuit depth? It seems like just using NAND would be kind of a step backwards in that case. Karnaugh maps give you DNF; PALs/GALs want DNF; the fact that your DNF PAL circuit might just be two layers of NAND (equivalent to a layer of AND feeding into an OR layer) is kind of an implementation detail, isn't it? I mean you would configure the circuit in the exact same way if it were made out of physical AND and OR gates.

Re:Universal Logic Gates (2015) by analognoise on Monday June 17, 2019 @02:05PM (#20205734)
Of course after you do the minimization, you move to a technology mapping step that takes these things into account.

"the fact that your DNF PAL circuit might just be two layers of NAND (equivalent to a layer of AND feeding into an OR layer) is kind of an implementation detail, isn't it?"

No. That's absolutely, 100% fundamental.

It's called "Canonical Form" https://en.wikipedia.org/wiki/Canonical_normal_form

It's canonical for a reason.

Re:Universal Logic Gates (2015) by kragen on Thursday June 20, 2019 @06:20PM (#20237979)
It seems that you didn't understand my comment well enough to respond to it, maybe due to a lack of domain knowledge.
Re:Universal Logic Gates (2015) by analognoise on Saturday June 22, 2019 @04:17PM (#20251518)
Sure, what's a good reference?