2
$\begingroup$

There are some not-very-commonly considered forms of trinary logic using 3 truth values. Even entire (unusual/rare) ternary computers have been built from it.

Is there some knowledge or reference of how to convert some trinary logic systems into functionally complete boolean circuits/logic?

"Functionally complete" means all boolean functions can be computed. I am asking the more general question above in case the following more specific question does not have an answer. The motivation is more this specific following case. Consider the following "trinary truth table" for a single trinary operator.

   a b c

a  a c a
b  c b b
c  a b c

Is it possible to somehow create functionally complete boolean circuits out of the single above trinary truth table operator? Or, maybe it can be definitively proven it's not possible?

I am also looking for any reference to that or something similar.

Improve this question
$\endgroup$
4
  • $\begingroup$ The ternary logic can't have a Boolean algebra structure. See Arpasi, J. P. (2009). Fundamentals of Ternary Logic. Far East Journal of Mathematical Sciences (FJMS), 34(3), 289-302. $\endgroup$ – Juho Jan 27 '13 at 19:10
  • $\begingroup$ @juho thx for ref, prob good enough as answer, can you sketch out the proof? but its prob not exactly what Im asking. clearly one can use some versions of ternary logic to implement boolean logic (as the existence of full trinary computers reveals), it just depends on the operators/structure available. $\endgroup$ – vzn Jan 27 '13 at 19:13
  • $\begingroup$ Funny, $f_{13} = f_{19}$ in Table 8 is the same function, though the author claims them all to be distinct. Probably just a typo, but this paper is maybe not peer-reviewed properly. Also, Jan Łukasiewicz is mis-spelled. :) $\endgroup$ – Pål GD Jan 27 '13 at 19:19
  • $\begingroup$ didnt realize paper was online, not merely ref. looked at it. the paper has some interesting ideas on the subj but its not really a proof that binary logic cannot be reduced to trinary logic or for the particular trinary operator given above... $\endgroup$ – vzn Jan 27 '13 at 19:21
3
$\begingroup$

It is not possible to "invert" a value. Here is a list (computed in Python) of all unary functions achievable using your gate (the order of inputs is abc):

aaa
aba
abb
abc
aca
acc
bbb
cbb
cbc
ccc

An inverter would have one of the patterns ba?, c?a, ?cb (depending on which two values you choose to encode True and False), which none of these functions have.

On the other hand, it is possible to compute all monotone functions. Use a for True and c for False. The Or gate is realized as $x \lor y = (xy)$. The And gate is realized as $x \land y = ((((xb)y)b)a)$. (Note that your gate is symmetric but not associative.) There might be other solutions, e.g. using b and c.

Edit: Here is how to extend this to a complete simulation using double wires, according to vzn's suggestion. We represent True by (a,c) and False by (c,a). Negation is accomplished by swapping the two wires. The Or gate is formed by applying the Or gate described above for the first wire, and the And gate for the second wire. The And gate is defined analogously.

Further edit for the curious: here is how to compute all unary functions. We start with the list abc,aaa,bbb,ccc corresponding to the identity function and all constants. We now repeatedly choose two members and compose them, i.e. given functions $f,g$, we compute the function $(fg)$. Eventually the process stabilizes, that is generates no new functions, and we get the ten functions listed above.

Improve this answer
$\endgroup$
6
  • $\begingroup$ thx, not totally following yet, this is fine/interesting but does it assume that any of the 'a,b,c' correspond to binary values, ie map onto them? (however maybe a reasonable proof for that case). for example consider the case where multiple trinary values in tuples could represent binary truth values and single boolean gates are constructed out of arrays of the above trinary operator linking input tuples to output tuples... impossible? $\endgroup$ – vzn Jan 27 '13 at 19:23
  • $\begingroup$ Now that I've explained how to rule this out (or find a construction) for 1-tuples, you can use the same method for 2-tuples and 3-tuples, and so on. Either one of them works, or (when you've reached 27-tuples, 27 being the number of mappings from {a,b,c} to itself) it is impossible. Let us know what you get! $\endgroup$ – Yuval Filmus Jan 27 '13 at 19:28
  • $\begingroup$ still thinking about your proof (its phrased a little too briefly) but does it rule out possibility of negation for larger than 1-tuples? you seem to be saying you dont know? $\endgroup$ – vzn Jan 27 '13 at 19:55
  • $\begingroup$ I don't know, and my proof doesn't rule out the possibility. You can find out algorithmically, at least for 2-tuples. $\endgroup$ – Yuval Filmus Jan 27 '13 at 20:42
  • $\begingroup$ On second thought, it is actually trivial to extend the monotone gates into full-blown binary logic using double wires. See my edit. $\endgroup$ – Yuval Filmus Jan 27 '13 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.