A
ternary,
three-valued or
trivalent logic (sometimes abbreviated
3VL) is any of several
multi-valued logicMulti-valued logics are 'logical calculi' in which there are more than two truth values. Traditionally, in Aristotle's logical calculus, there were only two possible values for any proposition. An obvious extension to classical two-valued logic is an n-valued logic for n > 2...
systems in which there are three truth values indicating
true,
false and some third value. This is contrasted with the more commonly known
bivalentIn logic, the semantic principle of bivalence states that every proposition is either true or false. The dual semantic principle, the principle of contravalence, states that no proposition is both true and false. The principle of bivalence is related to the excluded middle though the latter is a...
logics (such as
boolean logicBoolean logic is a complete system for logical operations, used in many systems. It was named after George Boole, who first defined an algebraic system of logic in the mid 19th century. Boolean logic has many applications in electronics, computer hardware and software, and is the base of all...
) which provide only for
true and
false. Conceptual form and basic ideas were initially created by Łukasiewicz, Lewis and Sulski. These were then re-formulated by
Grigore MoisilGrigore Constantin Moisil was a Romanian mathematician, computer pioneer, and member of the Romanian Academy. His research was mainly in the fields of mathematical logic, , Algebraic logic, MV-algebra, algebra and differential equations...
in an axiomatic algebraic form, and also extended to
n-valued logics in 1945.
Definitions
Concerning
fuzzinessFuzzy logic is a form of multi-valued logic derived from fuzzy set theory to deal with reasoning that is approximate rather than precise. In contrast with "crisp logic", where binary sets have binary logic, the fuzzy logic variables may have a membership value of not only 0 or 1 – that is, the...
, ternary logic might be seen formally as a fuzzy type of logic as membership values may be different from just 0 and 1 as with
binary logic, however, ternary logic is defined as a
crisp logic.
Representation of values
As with bivalent logic, truth values in ternary logic may be represented numerically using various representations of the
ternary numeral systemTernary or trinary is the base- numeral system. Analogous to a "bit", a ternary digit is known as a trit . One trit contains bits of information...
. A few of the more common examples are:
- 1 for true, 2 for false, and 0 for unknown, irrelevant, or both.
- 0 for false, 1 for true, and a third non-integer symbol such as # or ½ for the final value.
- Balanced ternary
Balanced ternary is a non-standard positional numeral system , useful for comparison logic. It is a ternary system, but unlike the standard ternary system, the digits have the values −1, 0, and 1...
uses −1 for false, +1 for true and 0 for the third value; these values may also be simplified to −, +, and 0, respectively.
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 logicIn mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulas contain variables which can be quantified. Two common...
s exist as well; 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 tableA truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
showing the logic operations for
KleeneStephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...
's logic.
!
A !!
B !!
A OR
B !!
A AND
B !! NOT
A
|-
| True >
True |
True |
True |
|
>-
| True
Unknown |
True |
Unknown |
|
>-
| True
False |
True |
False |
|
>-
| Unknown
True |
True |
Unknown |
|
>-
| Unknown
Unknown |
Unknown |
Unknown |
|
>-
| Unknown
False |
Unknown |
False |
|
>-
| False
True |
True |
False |
|
>-
| False
Unknown |
Unknown |
False |
|
>-
| False
False |
False |
False |
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.
In database applications
The database structural query language
SQLSQL is a database computer language designed for managing data in relational database management systems , and originally based upon Relational Algebra. Its scope includes data query and update, schema creation and modification, and data access control. SQL was one of the first languages for...
implements ternary logic as a means of handling
NULLNull is a special marker used in Structured Query Language to indicate that a data value does not exist in the database. Introduced by the creator of the relational database model, E. F. Codd, SQL Null serves to fulfill the requirement that all true relational database management systems support...
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 LanguageData Manipulation Language is a family of computer languages used by computer programs and/or database users to insert, delete and update data in a database. Read-only querying, i.e...
, 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. In this way, ternary logic is implemented in SQL, while behaving as binary logic to the SQL user.
SQL
Check ConstraintA check constraint is a condition that defines valid data when adding or updating an entry in a table of a relational database. A check constraint is applied to each row in the table. The constraint must be a predicate. It can refer to a single or multiple columns of the table...
s 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.
An in-depth discussion of the SQL implementation of ternary logic is available in the article on
NullNull is a special marker used in Structured Query Language to indicate that a data value does not exist in the database. Introduced by the creator of the relational database model, E. F. Codd, SQL Null serves to fulfill the requirement that all true relational database management systems support...
.
Electronics
Digital electronics theory supports
four distinct logic values (as defined in VHDL's
std_logic):
- 1 or High, also H, usually representing TRUE.
- 0 or Low, also L, usually representing FALSE.
- X representing a "Conflict".
- U representing "Unassigned" or "Unknown".
- - representing "Don't Care
In digital logic, a don't-care term is an input-sequence to a function that the designer does not care about, usually because that input would never happen, or because differences in that input would not result in any changes to the output...
".
- Z representing "high impedance
In electronics, high impedance is the state of an output terminal which is not currently driven by the circuit. In digital circuits, it means that the signal is neither driven to a logical high nor low level - hence "tri-stated"...
", undriven line.
- H, L and W are other high-impedance values, the weak pull to "High", "Low" and "Don't Know" correspondingly.
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 languageIn electronics, a hardware description language or HDL is any language from a class of computer languages and/or programming languages for formal description of electronic circuits, and more specifically, digital logic...
(HDL) simulation tools, such as
VerilogIn the semiconductor and electronic design industry, Verilog is a hardware description language used to model electronic systems. Verilog HDL, not to be confused with VHDL, is most commonly used in the design, verification, and implementation of digital logic chips at the Register transfer level ...
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 CareIn digital logic, a don't-care term is an input-sequence to a function that the designer does not care about, usually because that input would never happen, or because differences in that input would not result in any changes to the output...
" when building truth tables. This is especially common in state machine design and
Karnaugh mapThe Karnaugh map, also known as a Veitch diagram , is a method to simplify Boolean algebra expressions...
simplification. The "X" values provide additional
degrees of freedomDegrees of freedom can mean:* Degrees of freedom * Degrees of freedom * Degrees of freedom...
to the final circuit design, generally resulting in a simplified and smaller circuit.
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 logicIn digital electronics three-state, tri-state, or 3-state logic allows output ports to assume a high impedance state in addition to the fundamental 0- and 1-levels, effectively "removing" the output from the circuit...
on their outputs only. The three states are "0", "1", and "Z".
Commonly referred to as
tristate logic (a trademark of
National SemiconductorNational Semiconductor is a semiconductor manufacturer, specializing in analog devices and subsystems,headquartered in Santa Clara, California, USA. The products of National Semiconductor include power management circuits, display drivers, audio and operational amplifiers, communication interface...
), it comprises the usual true and false states, with a third
transparent high impedanceIn electronics, high impedance is the state of an output terminal which is not currently driven by the circuit. In digital circuits, it means that the signal is neither driven to a logical high nor low level - hence "tri-stated"...
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, 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
CMOSComplementary metal–oxide–semiconductor is a technology for making integrated circuits. CMOS technology is used in microprocessors, microcontrollers, static RAM, and other digital logic circuits. CMOS technology is also used for a wide variety of analog circuits such as image sensors, data...
technology will temporarily hold the previous state seen on that input (due to the
capacitanceIn electromagnetism and electronics, capacitance is the ability of a body to hold an electrical charge.Capacitance is also a measure of the amount of electric charge stored for a given electric potential. A common form of charge storage device is a parallel-plate capacitor...
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
noiseElectronic noise is a random signal characteristic of all electronic circuits. Depending on the circuit, the noise generated by electronic devices can vary greatly. Noise can be produced by several different effects. Thermal noise and shot noise are inherent to all devices...
, they can cause
oscillationOscillation is the repetitive variation, typically in time, of some measure about a central value or between two or more different states. Familiar examples include a swinging pendulum and AC power...
, 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 logicFuzzy logic is a form of multi-valued logic derived from fuzzy set theory to deal with reasoning that is approximate rather than precise. In contrast with "crisp logic", where binary sets have binary logic, the fuzzy logic variables may have a membership value of not only 0 or 1 – that is, the...
and error correction, and several true ternary logic devices have been manufactured (see external links).
See also
- Digital circuit
Digital electronics are systems that represent signals as discrete levels, rather than as a continuous range. In most cases the number of states is two, and these states are represented by two voltage levels: one near to zero volts and one at a higher level depending on the supply voltage in use...
- Ternary numeral system
Ternary or trinary is the base- numeral system. Analogous to a "bit", a ternary digit is known as a trit . One trit contains bits of information...
(and Balanced ternaryBalanced ternary is a non-standard positional numeral system , useful for comparison logic. It is a ternary system, but unlike the standard ternary system, the digits have the values −1, 0, and 1...
)
- Ternary computer
A ternary computer is a computer that uses ternary logic instead of the more common binary logic in its calculations.-History:...
- Boolean algebra (structure)
- Boolean function
In mathematics, a Boolean function is a function of the form f : Bk → B, where B = {0, 1} is a Boolean domain and k is a nonnegative integer called the arity of the function...
- Binary logic
- Setun
Setun was a balanced ternary computer developed in 1958 at Moscow State University. The device was built under the lead of Sergei Sobolev and Nikolay Brusentsov. It was the only modern ternary computer, using three-valued ternary logic instead of two-valued binary logic prevalent in computers...
- an experimental Russian computer which was based on ternary logic
- Aymara language
Aymara is an Aymaran language spoken by the Aymara people of the Andes. It is one of only a handful of Native American languages with over a million speakers. Aymara, along with Quechua and Spanish, is an official language of Peru and Bolivia...
- a Bolivian language famous for using ternary rather than binary logic
- Four value logic
External links