Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Universal Logic Gates (2015)

allaboutcircuits.com

Post reply on HN
Print view View original

31–38 of 38 posts

Re: Universal Logic Gates (2015)

#31

Post by abdullahkhalids »

fallingfrog wrote: post #29

You can almost make a continuous variable version of all the logic gates, for variables A and B which are between 0 and 1, but I couldn't quite get it to work. I tried: (I'm using => to mean "maps to") !A => 1 - A A && B => AB A || B => A + B - AB If you do this, some of the rules of logic work fine: !(!A && !B) => 1 - ((1 - A)(1 - B)) = A + B - AB, which is the same as the expression for A || B. But A && A obviously…

The generalization of continuous variable version of boolean logic can be achieved in various ways as far as I know. One way is Cox's theorem [1], which forms the basis of Bayesian probability theory, and will give you consistent logic and reduces to the standard rules of boolean logic in the limit of 0/1.

[1] https://en.wikipedia.org/wiki/Cox%27s_theorem

Re: Universal Logic Gates (2015)

#32

Post by fallingfrog »

abdullahkhalids wrote: post #31
fallingfrog wrote: post #29

You can almost make a continuous variable version of all the logic gates, for variables A and B which are between 0 and 1, but I couldn't quite get it to work. I tried: (I'm using => to mean "maps to") !A => 1 - A A && B => AB A || B => A + B - AB If you do this, some of the rules of logic work fine: !(!A && !B) => 1 - ((1 - A)(1 - B)) = A + B - AB, which is the same as the expression for A || B. But A && A obviously…

The generalization of continuous variable version of boolean logic can be achieved in various ways as far as I know. One way is Cox's theorem [1], which forms the basis of Bayesian probability theory, and will give you consistent logic and reduces to the standard rules of boolean logic in the limit of 0/1. [1] https://en.wikipedia.org/wiki/Cox%27s_theorem

The way I came up with my attempt was just to notice that when you are looking at the probability of two independent events happening together, you multiply them; and if you want the probability of A or B or both, you add them and then subtract the probability of (A and B). I guess the reason the multiplication rule doesn’t work for (A && A) is that those two variables are clearly not independent, since they’re the same variable.

Re: Universal Logic Gates (2015)

#33

Post by analognoise »

kragen wrote: post #27
analognoise wrote: post #20

Earlier quoted context omitted.

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…

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 th…

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)

#34

Post by analognoise »

adrian_b wrote: post #28
analognoise wrote: post #21

Earlier quoted context omitted.

If you make a NOT from an XOR, and already have AND, you've made... NAND! Which is why it isn't a minimal set - because you're using AND and XOR to get NAND, which (by itself) is universal!

The question about a minimal set of primitives arises in many domains, not only in Boolean functions, for example in structured programming or in a minimal computer instruction set. In all such domains it is possible to find a set composed of only one primitive and some people think that that is the minimal set because it has a minimum number of primitives. Nevertheless, other people do not agree that the minimum num…

"In my opinion, it is nice to know this nice trick about reducing a set of independent primitives to only one, but this almost never has any practical application."

Also, NAND/NOR aren't "complex primitive", they're literally just primitives.

You've never used any modern computer? I consider modern computers pretty useful; considering this "trick" backs everything we do with modern computers, I consider it pretty fundamental...

Re: Universal Logic Gates (2015)

#35

Post by [deleted] »

kragen wrote: post #24
adrian_b wrote: post #19

Earlier quoted context omitted.

Also, I forgot to mention in my first answer above that it is false that "XOR and AND is not a minimal construction". The following 4 sets of logic operations (and many others) are minimal: 1. AND, NOT 2. AND, XOR 3. NAND 4. NOR So AND + XOR is a minimal set, because you can make NOT from a XOR where one input is true.

XOR and AND is a falsehood-preserving set of gates. Whatever acyclic circuit you make out of them will always produce 0 as its output if all its inputs are 0. It's a minimal universal set if you have access to constants (specifically, constant 1), but the other sets you mention do not require access to constants for universality. AND-NOT (BIC, set subtraction, logical abjunction, &^ in Golang) is a single binary gate…

[deleted]

Re: Universal Logic Gates (2015)

#36

Post by OJFord »

kragen wrote: post #25
OJFord wrote: post #22

Earlier quoted context omitted.

That makes the set {AND, XOR} a cover, yes, but since it is larger than {NAND} (or {NOR}) it is not a minimum cover.

In the set-containment lattice, neither {AND, XOR} nor {NAND} is "larger than" the other, so they are both minimum covers.

Agh, yes, you're absolutely right. Been too long :(

Re: Universal Logic Gates (2015)

#37

Post by kragen »

analognoise wrote: post #33
kragen wrote: post #27

Earlier quoted context omitted.

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 th…

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 can…

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)

#38

Post by analognoise »

kragen wrote: post #37
analognoise wrote: post #33

Earlier quoted context omitted.

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 can…

It seems that you didn't understand my comment well enough to respond to it, maybe due to a lack of domain knowledge.

Sure, what's a good reference?
Post reply on HN