3 ms·
One 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 th
by petschge 6y ago
One 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)