Close

Ternary Logic

A project log for Ternary Computing Menagerie

A place for documenting the many algorithms, data types, logic diagrams, etc. that would be necessary for the design of a ternary processor.

mechanical-advantageMechanical Advantage 04/19/2019 at 07:210 Comments

In earlier posts I made some comments about using Kleene logic in ternary computer systems and that it was "more appropriate" for balanced ternary math. These statements could be misleading and this is a good place in the sequence of documentation to take up the subject of logic and logical operations in a balanced ternary computer.

Boolean logic has it's roots going back to the classical era, but was initially formalized by George Boole in the 1850's as a mathematical approach to human thought. Boole proposed that statements or concepts could be either true or false and that, using some logical conclusions based on truth or falsity, you could perform mathematical operations on non-mathematical subjects. The key here is that this was originally intended to be a philosophic tool, not an engineering one. That's why the terminology may seem a bit unfamiliar.

What we now call "boolean algebra" is actually a well defined set of extensions to Boole's work. The 16 possible binary gates come from this algebra. In the field of formal logic these gates are called "connectives". Let's take a look at these logic gates again, but this time in the context of formal logic. Note that the inputs in logic texts are traditionally denoted as P and Q instead of A and B.

As gone over in my post on 2-input gates, most of these gates are either logically useless, or are redundant. The redundant ones can be built using one or more of the other gates in combination with the 1-input inverter.

When we are trying to extend this system to include a third value, what we want is a logic system where the equivalent ternary connectives are "most-like" the most commonly used binary connectives. From my research, the ternary logic system most closely approximating binary algebra is Kleene logic.

Kleene's thee-valued logic originally only included connectives that corresponded to Conjunction (AND gate), Disjunction (OR gate), Biconditional (XNOR gate) and Implication (no common gate for this, but it is equivalent to "B OR Not A"). The rest of the 16 connectives can be deduced from these four. Let's compare them to their binary equivalents:

As you can see, there is a close similarity between the two. Anything with a false input results in a false output and only where both inputs are true is the output true. An uncertain input denies a true output but does not overide a false one. Thus the definition of conjunction (a joining or union) is required to achieve a true output. Also, both connectives have the effect of outputting the lowest input. This is why the ternary version is referred to as the Minimum gate, or Min gate.

In this case, the similarity is still there but the effects are reversed. Anything with a true input results in a true output and only where both inputs are false is the output false. An uncertain input denies falsity, but does not override a truth. Thus the definition of disjunction (a separation or lack of union) is maintained by allowing a true output even in the face of disagreement. Both have the effect of outputting the highest input. There ternary version is referred to as the Maximum gate, or Max gate.

Here again, we have a strong similarity. Where the inputs agree unambiguously the output is True and where they disagree unambiguously the output is false. Where an uncertain input is present, the agreement or disagreement cannot be determined and the output is uncertain. I don't know of anyone having coined a really appropriate name for this gate so I am currently just referring to it as the XNOR gate, the same way I would the binary version.

As expected, there is similarity here as well. The entire concept of logical implication can be summed up as "if P is true, then Q cannot be false". As we can see, the binary version expresses this as the output always being true except in the one case where P is true, but Q is false. The Kleene logic interpretation is predictably extended to three values where the basic law remains the same but we get an uncertain output if it cannot be determined with certainty that both conditions of the law have been met. With this gate, there isn't even a binary gate name to steal, so I'm just borrowing the Boolean algebra name and calling it the Implication gate, or Imp gate.

When you get down to practical application, the "choice" of ternary logic systems turns out to be mostly a matter of labeling. Remember, all 19,683 possible two-input gates could be produced and used. That means that *any* ternary connective from any three-valued logic system can be produced with ternary circuits. Therefore any ternary logic system can be implemented if desired. Maybe an alternative system will turn out to be extremely useful in some niche application. In that case it can be implemented without great difficulty. We aren't really limiting ourselves by using Kleene logic, we're just picking Kleene's terminology for which truth table corresponds to which binary gate.

A later post will enumerate all of the ternary equivalents to the 16 binary connectives, two more connectives proposed by Kleene at a later date, and some additional gates that follow logically from the others.

Discussions