Ternary logic

A ternary, three-valued or trivalent logic (sometimes abbreviated 3VL) is a term to describe any of several multi-valued logic systems in which there are three truth values indicating "true", "false" and some third value. This is contrasted with the more commonly known bivalent logics (such as boolean logic) which provide only for "true" and "false".

Definitions

Representation of values

As with bivalent logic, truth values in ternary logic may be represented numerically using various representations of the ternary numeral system. A few of the more common examples are:
* 1 for "true", 2 for "false", and 0 for "unknown", "irrelevant", or "both". [cite journal | last = Hayes | first = Brian | title = Third Base | journal = American Scientist | volume = 89 | issue = 6 | pages = 490–494 | publisher = Sigma Xi, the Scientific Research Society | date = November-December, 2001 | url = http://www.americanscientist.org/content/AMSCI/AMSCI/ArticleAltFormat/20035214317_146.pdf | accessdate = 2006-12-25 | doi = 10.1511/2001.6.490 ]
* 0 for "false", 1 for "true", with the third value being a non-integer symbol such as # or ½. [cite book|title = The Penguin Dictionary of Mathematics. 2nd Edition| pages = 417| publisher = Penguin Books | date = 1998 |location = London, England]
* Balanced ternary uses −1 for "false", +1 for "true" and 0 for the third value; these values may also be simplified to −, +, and 0, respectively. [cite book | last = Knuth | first = Donald E. | authorlink = Donald Knuth | title = The Art of Computer Programming Vol. 2 | publisher = Addison-Wesley Publishing Company | date = 1981 | location = Reading, Mass. | pages = 190 ]

This article mainly illustrates a system of ternary propositional logic using the truth values {"false, unknown," and "true"}, and extends conventional boolean connectives to a trivalent context. Ternary predicate logics exist as wellFact|date=February 2007; these may have readings of the quantifier different from classical (binary) predicate logic, and may include alternative quantifiers as well.

Basic truth table

Below is a truth table showing the logic operations for Kleene's logic.

In this truth table, the UNKNOWN state can be metaphorically thought of as a sealed box containing either an unambiguously TRUE or unambiguously FALSE value. The knowledge of whether any particular UNKNOWN state secretly represents TRUE or FALSE at any moment in time is not available. However, certain logical operations can yield an unambiguous result, even if they involve at least one UNKNOWN operand. For example, since TRUE OR TRUE equals TRUE, and TRUE OR FALSE also equals TRUE, one can infer that TRUE OR UNKNOWN equals TRUE, as well. In this example, since either bivalent state could be underlying the UNKNOWN state, but either state also yields the same result, a definitive TRUE results in all three cases.

Ternary logic in database applications

The database structural query language SQL implements ternary logic as a means of handling NULL field content. SQL uses NULL to represent missing data in a database. If a field contains no defined value, SQL assumes this means that an actual value exists, but that value is not currently recorded in the database. Note that a missing value is not the same as either a numeric value of zero, or a string value of zero length. Comparing anything to NULL—even another NULL—results in an UNKNOWN truth state. For example, the SQL expression "City = 'Paris'" resolves to FALSE for a record with "Chicago" in the City field, but it resolves to UNKNOWN for a record with a NULL City field. In other words, to SQL, an undefined field represents potentially any possible value: a missing city "might or might not" represent Paris.

Using ternary logic, SQL can then account for the UNKNOWN truth state in evaluating boolean expressions. Consider the expression "City = 'Paris' OR Balance < 0.0". This expression resolves to TRUE for any record whose Balance field contains a negative number. Likewise, this expression is TRUE for any record with 'Paris' in its City field. The expression resolves to FALSE only for a record whose City field explicitly contains a string other than 'Paris', "and" whose Balance field explicitly contains a non-negative number. In any other case, the expression resolves to UNKNOWN. This is because a missing City value "might be" missing the string 'Paris', and a missing Balance "might be" missing a negative number. However, regardless of missing data, a boolean OR operation is FALSE only when "both" of its operands are also FALSE, so not all missing data leads to an UNKNOWN resolution.

In SQL Data Manipulation Language, a truth state of TRUE for an expression (e.g. in a WHERE clause) initiates an action on a row (e.g. return the row), while a truth state of UNKNOWN or FALSE does not. [cite journal | last = Lex de Haan and Gennick, Jonathan | title = Nulls: Nothing to Worry About | journal = Oracle Magazine | publisher = Oracle | date = July-August, 2005 | url = http://www.oracle.com/technology/oramag/oracle/05-jul/o45sql.html ] In this way, ternary logic is implemented in SQL, while behaving as binary logic to the SQL user.

SQL Check Constraints behave differently, however. Only a truth state of FALSE results in a violation of a check constraint. A truth state of TRUE or UNKNOWN indicates a row has been successfully validated against the check constraint [cite journal | last = Coles, Michael | title = Null Versus Null? | journal = SQL Server Central | publisher = Red Gate Software | date = February 26, 2007 | url = http://www.sqlservercentral.com/columnists/mcoles/2829.asp] .

An in-depth discussion of the SQL implementation of ternary logic is available in the article on Null.

Electronics

Digital electronics theory supports four distinct logic values:
* 1 or High, also H, usually representing TRUE.
* 0 or Low, also L, usually representing FALSE.
* X representing "Unknown", "Don't Know", or "Don't Care".
* Z representing "high impedance", or a disconnected input.

The "X" value does not exist in real-world circuits, it is merely a placeholder used in simulators and for design purposes. Some simulators support representation of the "Z" value, others do not. The "Z" value does exist in real-world circuits but only as an output state.

Use of "X" value in simulation

Many hardware description language (HDL) simulation tools, such as Verilog and VHDL, support an unknown value like that shown above during simulation of digital electronics. The unknown value may be the result of a design error, which the designer can correct before synthesis into an actual circuit. The unknown also represents uninitialised memory values and circuit inputs before the simulation has asserted what the real input value should be.

HDL synthesis tools usually produce circuits that operate only on binary logic.

Use of "X" value in digital design

When designing a digital circuit, some conditions may be outside the scope of the purpose that the circuit will perform. Thus, the designer does not care what happens under those conditions. In addition, the situation occurs that inputs to a circuit are masked by other signals so the value of that input has no effect on circuit behaviour.

In these situations, it is traditional to use "X" as a placeholder to indicate "Don't Care" when building truth tables. This is especially common in state machine design and Karnaugh map simplification. The "X" values provide additional degrees of freedom to the final circuit design, generally resulting in a simplified and smaller circuit. [cite book
first=John F
last=Wakerly
title=Digital Design Principles & Practices
year=2001
isbn=0-13-090772-3
publisher=Prentice Hall]

Once the circuit design is complete and a real circuit is constructed, the "X" values will no longer exist. They will become some tangible "0" or "1" value but could be either depending on the final design optimisation.

Use of "Z" value for high impedance

Some digital devices support a form of three-state logic on their outputs only. The three states are "0", "1", and "Z".

Commonly referred to as tristate [cite | author = National Semiconductor | title = LS TTL Data Book | date = 1993 | publisher = National Semiconductor Corporation | url = http://www.national.com ] logic (a trademark of National Semiconductor), it comprises the usual true and false states, with a third "transparent" high impedance state (or 'off-state') which effectively disconnects the logic output. This provides an effective way to connect several logic outputs to a single input, where all but one are put into the high impedance state, allowing the remaining output to operate in the normal binary sense. This is commonly used to connect banks of computer memory and other similar devices to a common data bus; a large number of devices can communicate over the same channel simply by ensuring only one is enabled at a time.

It is important to note that while outputs can have one of three states, yet inputs can only recognise two. Hence the kind of relations shown in the table above do not occur. Although it could be argued that the high-impedance state is effectively an "unknown", there is absolutely no provision in the vast majority of normal electronics to interpret a high-impedance state as a state in itself. Inputs can only detect "0" and "1".

When a digital input is left disconnected (i.e. when it is given a high impedance signal), the digital value interpreted by the input depends on the type of technology used. TTL technology will reliably default to a "1" state. On the other hand CMOS technology will temporarily hold the previous state seen on that input (due to the capacitance of the gate input). Over time, leakage current causes the CMOS input to drift in a random direction, possibly causing the input state to flip. Disconnected inputs on CMOS devices can pick up noise, they can cause oscillation, the supply current may dramatically increase (crowbar power) or the device may completely destroy itself.

Exotic ternary-logic devices

True ternary logic "can" be implemented in electronics, although the complexity of design has thus far made it uneconomical to pursue commercially and interest has been primarily confined to research, since 'normal' binary logic is much cheaper to implement and in most cases can easily be configured to emulate ternary systems. However, there are useful applications in fuzzy logic and error correction, and several true ternary logic devices have been manufactured (see external links).

References

ee also

* Digital circuit
* Ternary numeral system (and Balanced ternary)
* Ternary computer
* Boolean algebra (structure)
* Boolean function
* Binary logic
* Setun - an experimental Russian computer which was based on ternary logic

External links

* [http://jeff.tk/wiki/Trinary Jeff's Trinary Wiki]
* [http://www.trinary.cc/ Steve Grubb's Trinary Website]
* [http://www.boost.org/doc/html/tribool.html Boost.Tribool] – an implementation of ternary logic in C++
* [http://www.inria.fr/rapportsactivite/RA2004/r2d22004/uid51.html Team-R2D2] - a French institute that fabricated the first full-ternary logic chip (a 64-tert SRAM and 4-tert adder) in 2004