| a | c |
|---|---|
| – | – |
| 0 | 0 |
| + | + |
Standard Ternary Logic
Part of
http://homepage.cs.uiowa.edu/~dwjones/ternary/
Disclaimer: Nobody but the author endorses the use of the notation described here, although in general, the notations used by researchers in this field are abysmally bad and the author would like it if others accepted his proposed notation. |
Although considerable work on implementing ternary logic functions has been done, no standard notation has emerged. The notation proposed here follows from conventional Boolean logic augmented by the third value of Kleene logic, unknown. Where ternary functions are analogous to Boolean functions, parallel notations are used. New notations are introduced where there are no analogous Boolean functions, and the notation given here provides for mixing Boolean and ternary logic, where this makes sense. The presentation ends with a discussion of minimization.
Kleene logic augments the conventional true and false of Boolean logic with a third value, unknown [Fitting, 1994]. Various authors have suggested the assignment of different numerical equivalents to these values. Here, we adopt the following:
| truth value | numeric | short form |
|---|---|---|
| true | +1 | + |
| unknown | 0 | 0 |
| false | –1 | – |
The primary motivation for this choice of numeric values is that it directly supports balanced ternary encoding of numeric values, an encoding system that requires the trits (ternary digits) to have the values +1, 0 and –1. In addition, it meets the comfortable requirement that true be greater than false, and it permits an equivalence between logical negation and integer negation.
All is not perfect, however. For unsigned ternary numbers, we would prefer the values 0, 1 and 2, and users of conventional Boolean logic have a deeply ingrained desire to have false represented by zero and true by one, suggesting that, perhaps, unknown should be two. In a more abstract lattice-theoretic sense, true and false are both greater than unknown in that they convey more information. To complete the lattice (and move to 4-valued logic) we could even add an overspecified value that is greater than both true and false [Muskens, 1999]. Here, we simply ignore these alternatives while reserving the right to use alternative orderings and numeric interpretations whenever that is convenient.
Our use of the symbols +, 0 and – to abbreviate +1, 0 and -1 follows [Alexander, 1964].
In conventional Boolean logic, there are a total of four (2 squared) monadic (single argument) functions, three of which are trivial:
| input | false | identity | not | true |
|---|---|---|---|---|
| false | false | false | true | true |
| true | false | true | false | true |
The false function always returns false, ignoring its arguments. Similarly the true function always returns true, ignoring its arguments. A third trivial function, identity always returns its arguments unchanged. In electrical engineering, buffers, drivers and repeaters implement this function. The single nontrivial function is not, which inverts its input, returning false when given true and visa versa.
The move to Ternary increases the number of monadic functions from 4 to 27 (3 cubed) of which four are trivial, three constant value functions and an identity function. All of these functions are enumerated here:
| input | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | G | H | K | M | N | P | R | T | V | X | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| – | – | 0 | + | – | 0 | + | – | 0 | + | – | 0 | + | – | 0 | + | – | 0 | + | – | 0 | + | – | 0 | + | – | 0 | + |
| 0 | – | – | – | 0 | 0 | 0 | + | + | + | – | – | – | 0 | 0 | 0 | + | + | + | – | – | – | 0 | 0 | 0 | + | + | + |
| + | – | – | – | – | – | – | – | – | – | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | + | + | + | + | + | + | + | + | + |
Functions 0, D, and Z are the trivial constant valued functions false, unknown, and true. This enumeration uses the digit sequence of the standard heptavintimal notation.
In threshold logic, the input i is multiplied by a constant k and then compared to two thresholds t+ and t–. If ki ≥ t+, the output is +1. If ki ≤ t–, the otuput is -1. Otherwise, the output is 0. Only 17 of the monadic operators can be computed by threshold logic:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | G | H | K | M | N | P | R | T | V | X | Z | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| k | 0 | -1 | -1 | -1 | -1 | -1 | 1 | 1 | 0 | -1 | -1 | 1 | 1 | 1 | 1 | 1 | 0 | ||||||||||
| t+ | 1 | 2 | 1 | 2 | 1 | 0 | 2 | 2 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | ||||||||||
| t– | 0 | 0 | 0 | -1 | -1 | -1 | 0 | -1 | -1 | -2 | -2 | 0 | -1 | -2 | -1 | -2 | -1 |
Threshold implementations of the constant-valued functions are foolish but are included above for the sake of completeness. This discussion of threshold logic follows the outline given in [Merrill 1965].
The identity function, function P in the enumeration, is realized in hardware in the form of non-inverting drivers and buffers. In logic diagrams, this function is indicated by the conventional symbol for a driver or non-inverting amplifier, with an added triangle to mark it as a ternary device.
|
| c = a |
Function 5 in the enumeration above is the ternary equivalent of the Boolean not function. Here, we refer to this function as the ternary negation or neg function. This inverts its input, returning false when given true and visa versa, while leaving unknown inputs unchanged. In logic diagrams, inversion is indicated by the conventional symbol for a Boolean inverter, with an added triangle to mark it as a ternary device.
| 
| c = – a |
Note that, as with Boolean inverters, the symbol is composed of the symbol for a simple buffer or amplifier, with a bubble on the output indicating inversion. Here, we will never use the bubble to mean anything other than a fully symmetrical inversion. Numerous authors have proposed practical realizations of ternary inverters, among them [Doostaregan, Moaiyeri Navi and Hashemipour, 2010; Gorde, 2010; Lin Kim and Lombardi, 2009; Maley and Walsh, 1972; Mouftah, 1978 Wu and Prosser, 1990].
Many of these authors refer to realizations of the negation function as the standard ternary inverters or STIs because there are several other ternary functions that can be implemented as variations on the inverter.
Functions 2, and 8 in our enumeration have been referred to as the negative threshold inverter or NTIs and positive threshold inverter or PTIs because they invert the true and false values while treating the unknown input value as either true (NTI) or false (PTI). These can be considered ternary to Boolean conversion functions because they have purely two-valued outputs.
| NTI( a ) = (a = –1)
PTI( a ) = – (a = +1) |
Some approaches to building ternary logic in hardware lead to realizations of the PTI and NTI functions as trivial variations on the standard inverter, but in actual use, these functions are not used for inversion, but rather, they are used as decoders, as discussed in Section 2.4. Furthermore, their outputs are strictly two-valued and therefore, properly speaking, they can be seen as ternary to Boolean converters.
In Boolean logic, the inverter may be thought of as incrementing or decrementing its argument modulo 2. In ternary logic, the modulo 3 increment and decrement functions are quite distinct from inversion. These functions, numbers 7 and B in our enumeration, have been called rotate up and down, as well as cycle and inverse cycle, with extraordinarily obscure notations, as documented by [Connelly, 2008]. Here, we use the following notation:
| 
| c = (a + 1) |
| 
| c = (a – 1) |
The graphical notation given above borrows elements of the traditional Boolean notation for the exclusive-or gate, because of the strong relationship between that operation and modulo-2 addition.
Strictly speaking, we do not need both of these functions, since:
Note that negation plus increment can be used, in combination, to implement any of the ternary functions that deliver some permutation of their inputs as outputs; these are also known as reversable functions, since each permutation function has some other permutation as its inverse. In our enumeration, functions 7 (increment) and B (decrement) are inverses. Functions 5 (negation), F (unnamed) and M (unnamed) are all their own inverses, since each of them exchanges two values while leaving the third unchanged. Function P (identity) is also its own inverse, in a trivial sense, rounding out the 6 possible permutations functions on a 3-valued variable. The exercise of computing the unnamed functions F and M using only negation plus increment is left as an exercise for the reader.
It is worth noting that the increment and decrement functions cannot be implemented by threshold logic.
Functions 2, 6, and K in our enumeration output true when their input has a specific truth value, and false otherwise. These functions, can be used to construct decoders, and we refer to them here as decoding functions, ignoring the PTI and NTI notation and the bizarre superscript notation used by [Mouftah, 1976]. We use the following notation for these functions:
| 
| c = (a = –1) |
| 
| c = (a = 0) |
| 
| c = (a = +1) |
In the above, note the use of the triangle to indicate that these are ternary functions. The crossbar on the outputs indicates that the output is strictly two valued, or in other words, the value unknown never appears on the crossed line. Thus, the C output may be used as an input to a compatible Boolean gate, and when it is an input to a Ternary gate, the realization of that gate may be simplified because of the lack of a middle value.
Note that we use the equals sign (=) in two distinct ways: When used at the outer level, we use it to assert the identity of the expressions on the lefthand and righthand side of the symbol. When used in a parenthetic expression, we use it for Boolean comparison. In the latter context, we may also use the not-equals sign (≠) in its conventional Boolean sense.
Strictly speaking, we do not need all of these functions, since:
In many cases, we will need to decode two or three of the possible values on a ternary variable. [Kumar and Priya, 2010] gives a practical implementation of such a decoder, although using an incompatible notation. The following notation is used here:
|
Functions V, N, and 8 in our enumeration are the inverses of the decoding functions given above. As in Boolean logic, we use a bubble on the output of a function to indicate inversion, so function 8 can be given as:
| 
| c = – (a = +1) = (a ≠ +1) |
It is worth noting that the is unknown decoder function cannot be implemented by threshold logic.
There are cases where data in the range from true to false must be converted into the range true to unknown or unknown to false. Functions C and R in our enumeration do this, but we will not introduce specific notation for these. Instead, we will use diadic operators do describe these functions.
| 
| c = (a ∧ 0) |
| 
| c = (a ∨ 0) |
Note that these clamp functions can be extended to diadic and higher fan-in, and that, in implementation, they may be built by using simple logic gates with output circuitry modified to limit the output swing.
In conventional Boolean logic, a two input truth table has 4 rows, where each row of the output can take on two values, giving 16 (that is, 2 to the 4th power) possible functions of 2 variables. With only 16 functions, we could reasonably enumerate and name all of them. Of these we usually name only a few, notably the and and or functions, but also nand, nor and exclusive or.
In ternary logic, a two input truth table has 9 rows, where each row of the output can take on three values, giving 19,683 (that is, 3 to the 9th power) possible functions of 2 variables. Clearly, this is too many functions to enumerate, but as with Boolean logic, a few of these functions are worthy of naming.
In threshold logic, each input ij is multiplied by a constant kj and then the inputs are summed and then compared to two thresholds t+ and t–. If the sum is t+ or greater, the output is +1. If the sum is t–, the output is –1. According to [Merrill 1965], 471 of the 19,683 diadic ternary operators can be computed using threshold logic. Given that this is a distinct minority, we will make special note of the cases where threshold logic can be used in the functions listed below.
It is natural to extend the Boolean and function to a ternary function by declaring that the result is true only if both inputs are true, false if any input is false, and unknown otherwise. Given that the ternary values are ordered so that false is less than unknown, which is less than true, the and operator can also be thought of as returning the minimum of its two operands.
| 
| c = (a ∧ b) = min(a, b) | |||||||||||||||||||||
Here, we adopt the conventional Boolean graphical notation, adding a triangle to the symbol for an and gate as a badge to indicate the corresponding ternary function. As in Boolean logic, the min function is commutative and associative, so we may freely take the minimum of any number of terms without specifying the order of operations, and in graphical notation, we may add any number of extra inputs to the min symbol instead of drawing a tree of diadic gates.
Similarly, it is natural to extend the Boolean or function to ternary by declaring that the result is true if any input is true, false only if both inputs are false, and unknown otherwise. Given the usual ordering of ternary values where false is less than unknown, which is less than true, the or operator returns the maximum of its two operands.
| 
| c = (a ∨ b) = max(a, b) | |||||||||||||||||||||
Again, we have adopted the conventional Boolean notation, badging the or symbol with a triangle to indicate that it is a ternary function. As with Boolean logic, the max function is commutative and associative, so we need not specify the order of operations when combining multiple terms and we may add extra inputs to the max symbol when used in graphical form.
Note that, as in Boolean logic, DeMorgan's laws still hold in ternary:
As a result, we do not need both the max and min operators, since we can use either one of them, augmented with negation to make the other.
Also, as in Boolean logic, the and and or functions are distributive:
There is one significant difference between Boolean and ternary logic that these functions introduce: In Boolean logic, the and, or and not functions taken together form a basis for the entire algebra; that is, any Boolean function can be expressed solely in terms of these three functions. In fact, because of DeMorgan's laws, and plus not are sufficient, without the need for or. With ternary logic, there are many functions that cannot be expressed in terms of min plus max and negation.
Using just min, max and negation, we cannot implement the decoding functions such as is true or is false, nor can we implement decrement. It turns out, however, that adding any one of these functions to the mix provides a sufficient basis for building all of the others. The proof is a fun exercise.
Hardware implementatios of conventional Boolean logic frequently make it easier to implement the inverting versions of and and or. This leads naturally to giving these functions their own names, nand and nor, along with graphical symbols for use in logic diagrams. Several of the proposals for implementing ternary logic have the same property, leading to the natural use of inverted versions of the min and max functions, called anti min and anti max. The graphical and algebraic notations for these follow naturally from the notations introduced above.
| 
| c = – (a ∧ b) | |||||||||||||||||||||
| 
| c = – (a ∨ b) | |||||||||||||||||||||
Of course, as in Boolean logic, there is no formal need for these functions.
As with the not function, the exclusive-or function of Boolean algebra has several analogs in the Ternary realm. Perhaps the least useful of these is the one that follows directly from the conventonal assignment of values in Kleene logic. If the unknown value is excluded, this version of exclusive or behaves exactly like its Boolean prototype:
| 
| c = (a ⊕ b) = xor(a, b) | |||||||||||||||||||||
The notation used here is exactly that of Boolean logic, with a triangle brand on the logic symbol to indicate that it is ternary. Of course, as in Boolean logic, there is no formal need for this function, since it can be computed from functions we have already defined:
The exclusive-or function is associative and commutative, but unlike the min and max functions, there is no natural way to build exclusive-or gates that permits natural expansion to more than two inputs. Therefore, we will always use the exclusive-or function with just two arguments.
In Boolean logic, one use of exclusive or is to compute the modulo 2 sum of two one-bit binary values. The ternary exclusive-or function defined above does not compute this sum, but we can define a modulo-3 sum operator that does:
| 
| c = (a + b) | |||||||||||||||||||||
We adopt a graphical notation that includes elements borrowed from the Boolean exclusive-or symbol, badged with a trinagle to indicate a ternary function, but we make a point of adding details that make the symbol entirely different. In algebraic notation, we use the conventional addition operator, relying on the global constraint that all values are constrained, modulo 3, to the range from –1 to +1.
The utility of this operator was understood as far back as 1964 [Alexander, 1964]. In that early presentation, the symbol ⊕ was used, while the inverted exclusive-or operator was described as ternary multiplication and designated by the symbol ⊗.
This operator can, of course, be implemented using the operators we have already defined. It is, therefore, not strictly necessary.
|
In the above, note that the a input effectively controls a 3-input multiplexor that passes either the b input deccremented, unchanged, or incremented to the output. The sum of products cascade works in ternary logic exactly the way it works in Boolean logic. Also note that the internal control lines from the decoder to the min gates in the multiplexor have been marked with crosses at both ends to indicate that they are two-valued.
The above implementation of the modulo-3 sum from simpler gates is ad hoc. As in Boolean logic, we can implement any ternary function using a canonical sum of products (see Section 4.1).
| (a + b) | = | ( (a = –1) | ∧ (b = –1) | ∧ +1) |
| ∨ | ( (a = –1) | ∧ (b = +1) | ∧ 0) | |
| ∨ | ( (a = 0) | ∧ (b = 0) | ∧ 0) | |
| ∨ | ( (a = 0) | ∧ (b = +1) | ∧ +1) | |
| ∨ | ( (a = +1) | ∧ (b = –1) | ∧ 0) | |
| ∨ | ( (a = +1) | ∧ (b = 0) | ∧ +1) |
|
In the canonical sum of products, there could have been as many as 9 minterms, because there are two 3-valued inputs. The minterms with output values of false (-1) were eliminated, leaving only 6 minterms. In Boolean logic, each minterm would have had just two inputs, but here, we added a third input to each, a constant indicating the value of the function when that minterm is selected.
In the logic diagram, we noted which logic values were simple Boolean values by crossing each end of the corresponding line. Where all the inputs of a logic gate are Boolean, the output of that gate is also Boolean, so we noted this by omitting the triangle badge. As a result, we determined that compatible Boolean gates could be used to compute three of the minterms, those corresponding to the true (+1) outputs of the function. The gates used for the other minterms also have two-valued output, but these are clamped in the range between false and unknown. Only the final max gate that is used to combine the minterms is a fully general ternary logic gate.
The sum function is associative and commutative, but as with the exclusive-or function, there is no natural way to build sum gates with more than two inputs. Therefore, we will always use the sum function with just two arguments.
In Boolean logic, the inverse of exclusive or is true when the two inputs are the same, and false when they are different. There are several natural extensions of this idea to ternary logic. One of them is the logical consensus of a set of variables, which is true if all are true, false if all are false, and otherwise unknown:
| 
| c = (a ⊠ b) = cons(a, b) | |||||||||||||||||||||
The graphical notation given here includes elements borrowed from the symbols for the Boolean exclusive-or and and gates, badged with the ternary triangle. The similarity to and can be seen by considering the unknown and false values to be equivalent.
The circled times symbol ⊗ has been used for the consensus operator in 4-valued logic, along with the circled plus symbol ⊕ for its dual, the accept anything or gullibility operator [Fitting, 1994; Muskens, 1999; Jacobsz, 2011]. Unfiortunately, the latter symbol has long been used for the exclusive or operator in Boolean algebra, and our intent here is to build, wherever possible, on analogous Boolean operators. Therefore, we cannot use ⊕ to mean anything but the ternary analog of exclusive-or. This precludes using it for the ternary accept anything operator and suggests that we should not use ⊗ for consensus. Instead, we opt to use a squared times ⊠ and and squared plus ⊞ for consensus and accept anything.
A survey of the literature of ternary logic shows that electrical engineers and computer architects exploring this logic have not, in general, made any use of the consensus operator, yet it is extremely useful in constructing arithmetic circuits operating on balanced-ternary numbers, and there is no reason to believe that it cannot be easily implemented using typical digital electronics.
The consensus function is both commutitave and associative, and there are useful distributive laws that apply:
This operator can be expressed as a canonical sum of products as follows:
| (a ⊠ b) | = | ( (a = –1) | ∧ (b = 0) | ∧ 0) |
| ∨ | ( (a = –1) | ∧ (b = +1) | ∧ 0) | |
| ∨ | ( (a = 0) | ∧ (b = –1) | ∧ 0) | |
| ∨ | ( (a = 0) | ∧ (b = 0) | ∧ 0) | |
| ∨ | ( (a = 0) | ∧ (b = +1) | ∧ 0) | |
| ∨ | ( (a = +1) | ∧ (b = –1) | ∧ 0) | |
| ∨ | ( (a = +1) | ∧ (b = 0) | ∧ 0) | |
| ∨ | ( (a = +1) | ∧ (b = +1) | ∧ +1) |
In Section 4, we will discuss how to systematically minimise this extraordinarily long-winded description of the function, giving the following result:
|
Unlike exclusive or and sum, there are natural implementations of the ternary consensus function that are as simple as those that have been widely tested for the max and min functions. Therefore, there is little reason to implement consensus using the canonical sum of products. Furthermore, these implementations extend naturally to more than two inputs, so it is reasonable to take advantage of the fact that consensus is both commutative and associative and use consensus functions with more than two inputs. Here is a schematic for a resistor-MOSFET inverting consensus gate using the notation of Wu and Prosser, 1990:
| c = –(a ⊠ b) |
In this gate, if the a and b inputs are both below the lower threshold voltage, the upper transistors turn on and the c output is pulled high. Similarly, if the a and b inputs are both above the upper threshold voltage, the lower transistors turn on and the c output is pulled low. In all other circumstances, the resistor pulls the c output toward the middle voltage between the two thresholds. The fan-in of this gate design is limited by the number of MOSFETs that may be connected in series; it appears safe to assume that fan-in values exceeding 4 are achievable.
Threshold logic can be used to compute the consensus function using multipliers of +1 on each input and thresholds of +2 and –2, although practical hardware realizations using multipliers of 0.5 and thresholds of +1 and –1 are more likely.
In four-valued logic, the dual of consensus is an operator usually known as gullibility or accept anything. Where consensus requires that both inputs agree before it asserts anything but unknown, the accept anything operator declares an unknown conclusion only if both inputs are unknown or actively disagree. Otherwise, it jumps to a conclusion from any non-unknown input available to it. While the dual nature of consensus and accept anything is not evident when we conflate the top and bottom values of four-valued logic into a single unknown value, a somewhat useful accept anything operator can be defined in ternary logic:
| 
| c = (a ⊞ b) = any(a, b) | |||||||||||||||||||||
The schematic symbol for accept anything reflects the fact that this operator is to or as consensus is to and. The similarity to exclusive or is deliberate, but with sufficient differences that confusion with that operator should be unlikely.
The accept anything operator participates in two useful distributive rules:
However, this ternary accept anything operator is not associative, and it does not participate in other distributive rules:
Threshold logic can be used to compute the accept-anything function using multipliers of +1 on each input and thresholds of +1 and –1, although practical hardware realizations using multipliers of 0.5 and thresholds of +0.5 and –0.5 are more likely.
The monadic decoding functions have a natural diadic counterpart, simple comparison for equality. As with its monadic counterpart, this function of two ternary values has a Boolean value. It is true only if the two arguments are identical:
| 
| c = (a = b) | |||||||||||||||||||||
The notation given here follows naturally from the notation used for the monadic decoding functions. Expressing this as an canonical sum of products and minimization are left as exercises for the reader.
Note that the equality operator in Boolean logic is the inverse of the exclusive-or operator. This is not the case here! In Kleene logic the inverse exclusive-or operator answers the question "are the two operands equal, to the best of your knowledge?" To this question we can only give a definitive answer if all the inputs are either true or false. In contrast, the equality operator defined here considers two unknown inputs to be equal.
Minimization of ternary logic can be done by generalizing on the conventional minimization algorithm for Boolean logic. Given an arbitrary function, we begin by expressing it as a truth table, from which we derive the canonical sum of products. We then merge minterms in order to find a minimal cover for the function. Unfortunately, the visual shortcut represented by Karnaugh maps does not work for ternary functions of more than 2 variables, and as with Boolean algebra, the basic optimization problem has exponential complexity in the number of variables.
Consider the consensus function described in Section 3.6. Here is the truth table given previously for that function, with the cells numbered so we can refer to them in what follows:
|
| |||||||||||||||||||||||||||||||||||||||||||||
Each cell in the truth table can be represented by one minterm in a sum-of-products expression of the function, as follows:
| (a ⊠ b) | = | ( (a = –1) | ∧ (b = –1) | ∧ –1) | — 0 |
| ∨ | ( (a = –1) | ∧ (b = 0) | ∧ 0) | — 1 | |
| ∨ | ( (a = –1) | ∧ (b = +1) | ∧ 0) | — 2 | |
| ∨ | ( (a = 0) | ∧ (b = –1) | ∧ 0) | — 3 | |
| ∨ | ( (a = 0) | ∧ (b = 0) | ∧ 0) | — 4 | |
| ∨ | ( (a = 0) | ∧ (b = +1) | ∧ 0) | — 5 | |
| ∨ | ( (a = +1) | ∧ (b = –1) | ∧ 0) | — 6 | |
| ∨ | ( (a = +1) | ∧ (b = 0) | ∧ 0) | — 7 | |
| ∨ | ( (a = +1) | ∧ (b = +1) | ∧ +1) | — 8 |
Each row in the above sum-of products is called a minterm because it is the min of several subsidiary terms. For a 2-input ternary function, the minterms will all have 3 subsidiary terms. Two of these decode the values of the two input variables, while the third is the value taken from the output cell of the truth table corresponding to those input values.
For clarity, we have included all 9 minterms for the two-input function we are working with. Note, however, that one of those minterms will always be false (–1), term number 0. We never need to write out this term, since it never contributes anything to the value of the function. Omitting this term gives us the canonical sum of products representation of our function:
| (a ⊠ b) | = | ( (a = –1) | ∧ (b = 0) | ∧ 0) | — 1 |
| ∨ | ( (a = –1) | ∧ (b = +1) | ∧ 0) | — 2 | |
| ∨ | ( (a = 0) | ∧ (b = –1) | ∧ 0) | — 3 | |
| ∨ | ( (a = 0) | ∧ (b = 0) | ∧ 0) | — 4 | |
| ∨ | ( (a = 0) | ∧ (b = +1) | ∧ 0) | — 5 | |
| ∨ | ( (a = +1) | ∧ (b = –1) | ∧ 0) | — 6 | |
| ∨ | ( (a = +1) | ∧ (b = 0) | ∧ 0) | — 7 | |
| ∨ | ( (a = +1) | ∧ (b = +1) | ∧ +1) | — 8 |
|
It is interesting to note that all of the signals from the input decoders to the column of min gates in any circuit organized as a sum of products are all two-valued. This leads to straightforward implementations of any terny-to-Boolean and Boolean-to-ternary logic function:
It is also fair to speculate that the use of Boolean signals between the input decoders and the min gates is likely less than optimal. There ought to be a systematic methodology for developing minimal implementations of ternary functions that takes full advantage of ternary logic throughout instead of descending to an intermediate Boolean layer.
Simplification of the function begins by searching the table of minterms, examining every triplet of 3 terms that differ in exactly one of the inputs to the function and have the same output. For a 2-input function, the triplets we are interested in are: Minterms {0,3,6} {1,4,7} and {2,5,8}, since these differ in only the value of the first variable, and minterms {0,1,2}, {3,4,5} and {6,7,8}, since they differ only in the value of the second variable. In the event that there are minterms for which the function's output is irrelevant, these can be taken to be equal to every other value where such equality would allow terms to be combined.
For each of these triplets where the output is the same, do the following: Introduce a new minterm omitting the variable that differs, and with the constant representing the function's output set to the minimum value of the outputs of the minterms being combined, and also mark all of the combined minterms that have that same output value. The marking is to indicate that those combined minterms are covered by the new one. For our example, as we begin work, we get the following result after two such reductions:
| (a ⊠ b) | = | ( (a = –1) | ∧ (b = 0) | ∧ 0) | — 1 * |
| ∨ | ( (a = –1) | ∧ (b = +1) | ∧ 0) | — 2 | |
| ∨ | ( (a = 0) | ∧ (b = –1) | ∧ 0) | — 3 * | |
| ∨ | ( (a = 0) | ∧ (b = 0) | ∧ 0) | — 4 ** | |
| ∨ | ( (a = 0) | ∧ (b = +1) | ∧ 0) | — 5 * | |
| ∨ | ( (a = +1) | ∧ (b = –1) | ∧ 0) | — 6 | |
| ∨ | ( (a = +1) | ∧ (b = 0) | ∧ 0) | — 7 * | |
| ∨ | ( (a = +1) | ∧ (b = +1) | ∧ +1) | — 8 | |
| ∨ | ( (b = 0) | ∧ 0) | — 1, 4, 7 | ||
| ∨ | ( (a = 0) | ∧ 0) | — 3, 4, 5 |
In the above, we have reduced one column (minterms {1,4,7}) and one row (minterms {3,4,5}) of our original truth table. As a result, minterm 4 has been covered twice. The minterms covered by the two reductions we made had all of their outputs the same, so all of the covered minterms have been marked with a star. All of these reductions would have been permitted in conventional Boolean logic minimization.
We can make two more reductions that do not have identical outputs and would not, therefore, have been permitted in Boolean logic. In these cases, we only star the minterms that have outputs identical to the output of the reduced term:
| (a ⊠ b) | = | ( (a = –1) | ∧ (b = 0) | ∧ 0) | — 1 * |
| ∨ | ( (a = –1) | ∧ (b = +1) | ∧ 0) | — 2 * | |
| ∨ | ( (a = 0) | ∧ (b = –1) | ∧ 0) | — 3 * | |
| ∨ | ( (a = 0) | ∧ (b = 0) | ∧ 0) | — 4 ** | |
| ∨ | ( (a = 0) | ∧ (b = +1) | ∧ 0) | — 5 ** | |
| ∨ | ( (a = +1) | ∧ (b = –1) | ∧ 0) | — 6 * | |
| ∨ | ( (a = +1) | ∧ (b = 0) | ∧ 0) | — 7 ** | |
| ∨ | ( (a = +1) | ∧ (b = +1) | ∧ +1) | — 8 | |
| ∨ | ( (b = 0) | ∧ 0) | — 1, 4, 7 | ||
| ∨ | ( (b = +1) | ∧ 0) | — 2, 5, 8 | ||
| ∨ | ( (a = 0) | ∧ 0) | — 3, 4, 5 | ||
| ∨ | ( (a = +1) | ∧ 0) | — 6, 7, 8 |
If our function had more input variables, we would repeat the above steps comparing our reduced minterms with each other in order to see if any of them could be combined. When we make such combinations, we follow the exact same rules, starring the terms that were combined.
Once all minterms that can be combined are combined, we eliminate all of the starred terms, since each of them is covered by one of the reduced minterms. This gives us the following result:
| (a ⊠ b) | = | ( (a = +1) | ∧ (b = +1) | ∧ +1) | — 8 |
| ∨ | ( (b = 0) | ∧ 0) | — 1, 4, 7 | ||
| ∨ | ( (b = +1) | ∧ 0) | — 2, 5, 8 | ||
| ∨ | ( (a = 0) | ∧ 0) | — 3, 4, 5 | ||
| ∨ | ( (a = +1) | ∧ 0) | — 6, 7, 8 |
|
When there are more inputs to the function, it is possible that one or more of the combined minterms may be entirely covered by other combined minterms. In such cases, these redundant minterms may be eliminated, although eliminating these redundant minterms may lead to glitches in the output of a function when one of its inputs changes, leading to potentially undesirable behavior in sequential circuits.
We can perform one more reduction. If two of our combined minterms have the same output and differ in just one input variable, we can replace them with a single minterm that replaces two comparisons for equality with one comparison for inequality. This gives us the following:
| (a ⊠ b) | = | ( (a = +1) ∧ (b = +1) ∧ +1) | — 8 |
| ∨ | ( (b ≠ –1) ∧ 0) | — 1, 4, 7, 2, 5, 8 | |
| ∨ | ( (a ≠ –1) ∧ 0) | — 3, 4, 5, 6, 7, 8 |
This optimization is not guaranteed to pay off. For example, if we end up needing both (a=+1) and (a≠+1), the need for an extra decoding function could offset the elimination of a minterm.
There are some final optimizations: Wherever we included the literal true in a minterm, we can eliminate it. In addition, in rare cases such as this example, we can replace ((a=+1)∧(b=+1)) with (a∧b). This is only possible when the truth table for the entire function covers the truth table for the min function -- that is, all of the minterms of the function in question have output values greater than or equal to the corresponding terms of the min function. The net result of applying these two optimizations is:
| (a ⊠ b) | = | ( a ∧ b) | — 8 | |
| ∨ | ( (b ≠ –1) ∧ 0) | — 1, 4, 7, 2, 5, 8 | ||
| ∨ | ( (a ≠ –1) ∧ 0) | — 3, 4, 5, 6, 7, 8 |
Drawing this in circuit diagram form, we get the following optimized result:
|
|
The minimization rules given here are comparable to the rules given in [Yoeli and Rosenfeld, 1965]. That work presents both 2 and 3 variable analogs of Karnaugh maps as well as tabular methods. [Kumar and Priya, 2010] also attempted to apply Karnaugh maps to ternary functions, but then focused on a completely different approach to minimization, attempting to minimize the number of multiplexors needed in a multiplexor tree implementation of a ternary function. This may be useful on occasion, but in general, the pure sum of products solutions produced by the tabular methods given here will produce faster logic because the number of gate delays is always three, a delay for decoding followed by one delay for the minterms and then the final max operation used to combine the minterms.
The exercise above was done using algebraic notation, but it is easier to do this with truth tables. We start with a conventional truth table for the function, with the rows numbered:
| |||||||||||||||||||||||||||||||||||||||||||||
Now, we begin to identify triples of rows in the truth table that have the same output for all three values of one of the input variables. When we find such a triplet of rows, we star those rows and add a new row at the bottom, keeping a record, with each added rows, of what rows it covers. After two such steps, we have the following:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
The reason we put a star on each of the new rows is to keep track of which rows above were combined to make that row. We also added a horizontal line separating the original truth table from the new rows.
The next step is less obvious. Here, identify triples of rows in the truth table that have outputs of either 0 or +1 for all three values of one of the input variables. In these cases, we mark the rows with an asterisk where the output is 0 and with an x where the output is +1, and we add a new row at the bottom, again, eliminating the input variable that allowed the combination and giving it an output of 0. We can do this twice:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
There are no more input eliminations possible in our example, so we can now re-write the table, dropping all of the rows that have outputs of –1 and also dropping all of the starred rows. The rows marked with x marks must be retained in order to force an output of +1 where one of the new rows would otherwise output a zero. We also eliminate all of our bookkeeping comments at this point, giving the following simplified table:
| |||||||||||||||||||||||
If we had more variables, we might be able to repeat the same basic process on the new rows of the table, combining some of them to eliminate additional input variables. If we did that, we would add an additional horizontal line dividing the results of the second elimination round from the first.
At this point, we have the optimal sum-of-products form, identical to the version with 5 minterms that we already derived using algebraic notation. We could also have applied a more graphical approach, analogous to the Karnaugh maps used with Boolean logic, but this would not generalized to functions of more than 2 variables (just as Karnaugh maps generalize poorly to functions of more than 4 variables). The payback for using 2-variable Karnaugh is so small that we ignore the possibility.
When ternary functions are expressed in sum-of-products form, it is important to note that all of the min gates used to decode the minterms are actually simple Boolean and gates. The variable inputs to these gates are all Boolean, either true or false, with the unknown value excluded. Where the constant input is +1, the output is also Boolean. Where the constant input is 0, this does not require the use of a ternary min, rather, the constant input serves to clamp the output between false (-1) and unknown (0). As such, an and gate with its output limited to this range is all that is required.
From this, we conclude that our sum-of-products methodology only requires a single ternary max gate for each output, plus ternary to Boolean decoders for each input. As a result, when comparing the Boolean logic realization of some higher-level function with its ternary realization, the number of minterms in the Boolean version can be directly compared with the number of minterms in the Ternary version.