 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

Three-valued logic

Article Id: WHEBN0000249904
Reproduction Date:

 Title: Three-valued logic Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

Three-valued logic

In logic, a three-valued logic (also trivalent, ternary, trinary logic, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating true, false and some indeterminate third value. This is contrasted with the more commonly known bivalent logics (such as classical sentential or Boolean logic) which provide only for true and false. Conceptual form and basic ideas were initially created by Jan Łukasiewicz and C. I. Lewis. These were then re-formulated by Grigore Moisil in an axiomatic algebraic form, and also extended to n-valued logics in 1945.

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:

• in Balanced ternary, each digit has one of 3 values: −1, 0, or +1; these values may also be simplified to −, 0, +, respectively.
• in the Redundant binary representation, each digit can have a value of -1, 0, 0, or 1 (the value 0 has two different representations)
• in the Ternary numeral system, each digit is a trit (trinary digit) having a value of: 0, 1, or 2
• in the Skew binary number system, only most-significant non-zero digit has a value 2, and the remaining digits have a value of 0 or 1
• 1 for true, 2 for false, and 0 for unknown, unknowable/undecidable, irrelevant, or both.
• 0 for false, 1 for true, and a third non-integer symbol such as # or ½ for the final value, also known as "maybe".

Inside a ternary computer, ternary values are represented by ternary signals.

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 well; these may have readings of the quantifier different from classical (binary) predicate logic, and may include alternative quantifiers as well.

Logics

Kleene logic

Below is a set of truth tables showing the logic operations for Kleene's logic.
(F: FALSE, U: UNKNOWN, T: TRUE)
NOT(A)
A ¬ A
F T
U U
T F
AND(A, B)
AB B
F U T
A F F F F
U F U U
T F U T
OR(A, B)
AB B
F U T
A F F U T
U U U T
T T T T
(−1: FALSE, 0: UNKNOWN, +1: TRUE)
NEG(A)
A ¬ A
−1 +1
0 0
+1 −1
MIN(A, B)
AB B
−1 0 +1
A −1 −1 −1 −1
0 −1 0 0
+1 −1 0 +1
MAX(A, B)
AB B
−1 0 +1
A −1 −1 0 +1
0 0 0 +1
+1 +1 +1 +1

In these truth tables, 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.

If numeric values, e.g. balanced ternary values, are assigned to FALSE, UNKNOWN and TRUE such that FALSE is less than UNKNOWN and UNKNOWN is less than TRUE, then A AND B AND C... = MIN(A, B, C ...) and A OR B OR C ... = MAX(A, B, C...).

Material implication for Kleene logic can be defined as:

A \rightarrow B \ \overset{\underset{\mathrm{def}}{}}{=} \ \mbox{NOT}(A) \ \mbox{OR} \ B , and its truth table is

IMPK(A, B), OR(¬A, B)
A B B
T U F
A T T U F
U T U U
F T T T
IMPK(A, B), MAX(−A, B)
A B B
+1 0 −1
A +1 +1 0 −1
0 +1 0 0
−1 +1 +1 +1

which differs from that for Łukasiewicz logic (described below).

Kleene logic has no tautologies (valid formulas) because whenever all of the atomic components of a well-formed formula are assigned the value Unknown, the formula itself must also have the value Unknown. (And the only designated truth value for Kleene logic is True.) However, the lack of valid formulas does not mean that it lacks valid arguments and/or inference rules. An argument is semantically valid in Kleene logic if, whenever (for any interpretation/model) all of its premises are True, the conclusion must also be True. (Note that the Logic of Paradox (LP) has the same truth tables as Kleene logic, but it has two designated truth values instead of one; these are: True and Both (the analogue of Unknown), so that LP does have tautologies but it has fewer valid inference rules.)

Łukasiewicz logic

The Łukasiewicz Ł3 has the same tables for AND, OR, and NOT as the Kleene logic given above, but differs in its definition of implication. This section follows the presentation from Malinowski's chapter of the Handbook of the History of Logic, vol 8.

IMPŁ(A, B)
A B B
T U F
A T T U F
U T T U
F T T T
IMPŁ(A, B)
A B B
+1 0 −1
A +1 +1 0 −1
0 +1 +1 0
−1 +1 +1 +1

In fact, using Łukasiewicz's implication and negation, the other usual connectives may be derived as:

• AB = (AB) → B
• AB = ¬(¬A ∨ ¬ B)
• AB = (AB) ∧ (BA)

It's also possible to derive a few other useful unary operators (first derived by Tarski in 1921):

• MA = ¬AA
• LA = ¬M¬A
• IA = MA ∧ ¬LA

They have the following truth tables:

A MA
F F
U T
T T
A LA
F F
U F
T T
A IA
F F
U T
T F

M is read as "it is not false that..." or in the (unsuccessful) Tarski–Łukasiewicz attempt to axiomatize modal logic using a three-valued logic, "it is possible that..." L is read "it is true that..." or "it is necessary that..." Finally I is read "it is unknown that..." or "it is contingent that..."

In Łukasiewicz's Ł3 the designated value is True, meaning that only a proposition having this value everywhere is considered a tautology. For example AA and AA are tautologies in Ł3 and also in classical logic. Not all tautologies of classical logic lift to Ł3 "as is". For example, the law of excluded middle, A ∨ ¬A, and the law of non-contradiction, ¬(A ∧ ¬A) are not tautologies in Ł3. However, using the operator I defined above, it is possible to state tautologies that are their analogues:

• AIA ∨ ¬A [law of excluded fourth]
• ¬(A ∧ ¬IA ∧ ¬A) [extended contradiction principle].

Modular algebras

Some 3VL modular algebras have been introduced more recently, motivated by circuit problems rather than philosophical issues:

• Cohn algebra