3 ms·
I'm unsure if it counts as elegant. It's so large. But maybe our minds are too small to see the elegance! Ternary logic is an enormous space, mathematically.
by retrac 6y ago
I'm unsure if it counts as elegant. It's so large. But maybe our minds are too small to see the elegance!
Ternary logic is an enormous space, mathematically. In two value Boolean, there are 16 distinct binary operators, many of which are useless values (such as identity). We're basically left with the family of NAND/NOR/XOR and their complements. NAND/NOR, or their complement and NOT, are universal and can construct the rest. In some 3VL like Kleene, there's 3^9 (about 20,000) possible operators, many of which are logically universal.
Boolean NAND and AND-OR-INVERT are universal and map very nicely to CMOS. But it's likely many (as in dozens or hundreds) of different universal gates in 3VL map nicely into electronic structures. (Assuming the existence of circuits for 3VL.) It's such a large space to explore that we've only begun to scrape the surface.
- petschge 6y agoOne thing that really cuts down on the number of operators that you need to consider is the requirement of symmetry. If two inputs are swapped you still want the same output. In binary this requirement removes 8 of the 16 operators. The fact that we don't want the output stuck at true of false removes another two and we are left with the six common, useful operations. If you impose this symmetry condition on ternary operators, the huge number of 19683 operators is cut down to 729. Three of those are stuck to one of the three output states and can be ignored as well. If you additionally require that changing an input from 0 to 1 (or to -1) can not make a definite (non-zero) output to 0 (less certain) nor flip it, you cut the total list of operators down to just 64 operators. Of course 64 operators is much more than 6, it is not as bad as going from 16 to 20k.
- neolog 6y ago> If you additionally require that changing an input from 0 to 1 (or to -1) can not make a definite (non-zero) output to 0 (less certain) nor flip it Why does it make sense to require those conditions?
- petschge 6y agoIt ONLY makes sense if you view trinary as (false, uncertain, true or -1,0,+1). That is NOT the only view of trinary, but it is useful for e.g. soft-decision decoders.
- sdenton4 6y agoFWIW, in ternary the x->-x is a new 'uninteresting' symmetry, so for any non-constant-zero operation F(x, y) you've got a paired -F(x, y). If these pairs are uninteresting (eg, you can run the operation -F for free, given F), you can cut the number of operators by another factor of 2. More generally, if you allow composition of a permutation of the trit values 'for free', (eg, F(x,y) + 1 is 'free' given F) you get to reduce the 'atomic' operations by a factor of 6. This is the same as collapsing 'G' and 'not G' among binary operators. But I guess you've got to implement these in circuits at some point, so the symmetries aren't necessarily helpful (eg, NAND is a thing, rather than AND composed with a symmetry?). (caveat: i am, obviously, more a mathematician than a circuit designer. :P )
- petschge 6y agoSo far I have imposed mainly F(x,y) = F(y,x). You could also enforce F(-x,-y) = -F(x,y), but I have not done that. The second reduction that I mention is actually to require every F to satisfy either F(-1,y) <= F(0,y) <= F(1,y) OR F(-1, y) >= F(0,y) >= F(1,y). And no the symmetries are not that useful to implement the circuitry, but are nice to select operators that compose nicely and allow many simplifications (think De Morgan's laws)