Three-valued logic

Short description: System including an indeterminate value

In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean,^[1] sometimes abbreviated 3VL) is any of several many-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 classical sentential or Boolean logic) which provide only for true and false.

Emil Leon Post is credited with first introducing additional logical truth degrees in his 1921 theory of elementary propositions.^[2] The conceptual form and basic ideas of three-valued logic were initially published by Jan Łukasiewicz and Clarence Irving Lewis. These were then re-formulated by Grigore Constantin Moisil in an axiomatic algebraic form, and also extended to n-valued logics in 1945.

Pre-discovery

Around 1910, Charles Sanders Peirce defined a many-valued logic system. He never published it. In fact, he did not even number the three pages of notes where he defined his three-valued operators.^[3] Peirce soundly rejected the idea all propositions must be either true or false; boundary-propositions, he writes, are "at the limit between P and not P."^[4] However, as confident as he was that "Triadic Logic is universally true,"^[5] he also jotted down that "All this is mighty close to nonsense."^[6] Only in 1966, when Max Fisch and Atwell Turquette began publishing what they rediscovered in his unpublished manuscripts, did Peirce's triadic ideas become widely known.^[7]

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;^[8]
in the redundant binary representation, each digit can have a value of −1, 0, 0/1 (the value 0/1 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 the least-significant non-zero digit can have a value of 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;^[9]
0 for false, 1 for true, and a third non-integer "maybe" symbol such as ?, #, ½,^[10] or xy.

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, true}, and extends conventional Boolean connectives to a trivalent context. Ternary predicate logics exist as well;^{[citation needed]} these may have readings of the quantifier different from classical (binary) predicate logic and may include alternative quantifiers as well.

Logics

Boolean logic allows 2² = 4 unary operators; the addition of a third value in ternary logic leads to a total of 3³ = 27 distinct operators on a single input value. (This may be made clear by considering all possible truth tables for an arbitrary unary operator. Given 2 possible values TF of the single Boolean input, there are four different patterns of output TT, TF, FT, FF resulting from the following unary operators acting on each value: always T, Identity, NOT, always F. Given three possible values of a ternary variable, each times three possible results of a unary operation, there are 27 different output patterns:TTT,TTU,TTF, TUT,TUU,TUF, TFT,TFU,TFF, UTT,UTU,UTF, UUT,UUU,UUF, UFT,UFU,UFF, FTT,FTU,FTF, FUT,FUU,FUF, FFT,FFU, and FFF.) Similarly, where Boolean logic has 2^2×2 = 16 distinct binary operators (operators with 2 inputs) possible, ternary logic has 3^3×3 = 19,683 such operators. Where the nontrival Boolean operators can be named (AND, NAND, OR, NOR, XOR, XNOR (equivalence), and 4 variants of implication or inequality), with six trivial operators considering 0 or 1 inputs only, it is unreasonable to attempt to name all but a small fraction of the possible ternary operators.^[11] Just as in bivalent logic, where not all operators are given names and subsets of functionally complete operators are used, there may be functionally complete sets of ternary-valued operators.

Kleene and Priest logics

Below is a set of truth tables showing the logic operations for Stephen Cole Kleene's "strong logic of indeterminacy" and Graham Priest's "logic of paradox".

(F, false; U, unknown; T, true)

NOT(A)
A	¬A
F	T
U	U
T	F

AND(A, B)
A ∧ B		B
A ∧ B		F	U	T
A	F	F	F	F
	U	F	U	U
	T	F	U	T

OR(A, B)
A ∨ B		B
A ∨ 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)
A ∧ B		B
A ∧ B		−1	0	+1
A	−1	−1	−1	−1
	0	−1	0	0
	+1	−1	0	+1

MAX(A, B)
A ∨ B		B
A ∨ 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 thought of as neither true nor false in Kleene logic, or thought of as both true and false in Priest logic. The difference lies in the definition of tautologies. Where Kleene logic's only designated truth value is T, Priest logic's designated truth values are both T and U. In Kleene logic, 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 an unknown operand. For example, because true OR true equals true, and true OR false also equals true, then true OR unknown equals true as well. In this example, because either bivalent state could be underlying the unknown state, and either state also yields the same result, 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:

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

IMP_K(A, B), OR(¬A, B)
A → B		B
A → B		F	U	T
A	F	T	T	T
	U	U	U	T
	T	F	U	T

IMP_K(A, B), MAX(−A, B)
A → B		B
A → B		−1	0	+1
A	−1	+1	+1	+1
	0	0	0	+1
	+1	−1	0	+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. (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).^[12]

Ł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 in that "unknown implies unknown" is true. This section follows the presentation from Malinowski's chapter of the Handbook of the History of Logic, vol 8.^[13]

Material implication for Łukasiewicz logic truth table is

IMP_Ł(A, B)
A → B		B
A → B		F	U	T
A	F	T	T	T
	U	U	T	T
	T	F	U	T

IMP_Ł(A, B), MIN(1, 1−A+B)
A → B		B
A → B		−1	0	+1
A	−1	+1	+1	+1
	0	0	+1	+1
	+1	−1	0	+1

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

$A \lor B = (A \to B) \to B$
$A \land B = \neg(\neg A \lor \neg B)$
$A \Leftrightarrow B = (A \to B) \land (B \to A)$

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

$M A = \neg A \to A$
$L A = \neg M \neg A$
$I A = M A \land \neg L A$

They have the following truth tables:

$A$	$M A$
F	F
U	T
T	T

$A$	$L A$
F	F
U	F
T	T

$A$	$I A$
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, $A \to A$ and $A \leftrightarrow A$ 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 \lor \neg A$ , and the law of non-contradiction, $\neg(A \land \neg A)$ are not tautologies in Ł3. However, using the operator $I$ defined above, it is possible to state tautologies that are their analogues:

$A \lor I A \lor \neg A$ (law of excluded fourth)
$\neg(A \land \neg I A \land \neg A)$ (extended contradiction principle).

RM3 logic

The truth table for the material implication of R-mingle 3 (RM3) is

IMP_RM3(A, B)
A → B		B
A → B		F	U	T
A	F	T	T	T
	U	F	U	T
	T	F	F	T

A defining characteristic of RM3 is the lack of the axiom of Weakening:

$(A \to (B \to A))$

which, by adjointness, is equivalent to the projection from the product:

$(A \otimes B) \to A$

RM3 is a non-cartesian symmetric monoidal closed category; the product, which is left-adjoint to the implication, lacks valid projections, and has $U$ as the monoid identity. This logic is equivalent to an "ideal" paraconsistent logic which also obeys the contrapositive.

HT logic

The logic of here and there (HT, also referred as Smetanov logic SmT or as Gödel G3 logic), introduced by Heyting in 1930^[14] as a model for studying intuitionistic logic, is a three-valued intermediate logic where the third truth value NF (not false) has the semantics of a proposition that can be intuitionistically proven to not be false, but does not have an intuitionistic proof of correctness.

(F, false; NF, not false; T, true)

NOT_HT(A)
A	¬A
F	T
NF	F
T	F

IMP_HT(A, B)
A → B		B
A → B		F	NF	T
A	F	T	T	T
	NF	F	T	T
	T	F	NF	T

It may be defined either by appending one of the two equivalent axioms (¬q → p) → (((p → q) → p) → p) or equivalently p∨(¬q)∨(p → q) to the axioms of intuitionistic logic, or by explicit truth tables for its operations. In particular, conjunction and disjunction are the same as for Kleene's and Łukasiewicz's logic, while the negation is different.

HT logic is the unique coatom in the lattice of intermediate logics. In this sense it may be viewed as the "second strongest" intermediate logic after classical logic.

Bochvar logic

This logic is also known as a weak form of Kleene's three-valued logic.

Ternary Post logic

not(a) = (a + 1) mod 3, or

not(a) = (a + 1) mod (n), where (n) is the value of a logic

Modular algebras

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

Cohn algebra
Pradhan algebra
Dubrova^[16] and Muzio algebra

Applications

SQL

The database structural query language SQL implements ternary logic as a means of handling comparisons with NULL field content. NULL was originally intended to be used as a sentinel value in SQL to represent missing data in a database, i.e. the assumption that an actual value exists, but that the value is not currently recorded in the database. SQL uses a common fragment of the Kleene K3 logic, restricted to AND, OR, and NOT tables.

In SQL, the intermediate value is intended to be interpreted as UNKNOWN. Explicit comparisons with NULL, including that of another NULL yields UNKNOWN. However this choice of semantics is abandoned for some set operations, e.g. UNION or INTERSECT, where NULLs are treated as equal with each other. Critics assert that this inconsistency deprives SQL of intuitive semantics in its treatment of NULLs.^[17] The SQL standard defines an optional feature called F571, which adds some unary operators, among which is IS UNKNOWN corresponding to the Łukasiewicz I in this article. The addition of IS UNKNOWN to the other operators of SQL's three-valued logic makes the SQL three-valued logic functionally complete,^[18] meaning its logical operators can express (in combination) any conceivable three-valued logical function.

References

↑ "Stanford JavaNLP API". Stanford NLP Group. https://nlp.stanford.edu/nlp/javadoc/javanlp/edu/stanford/nlp/util/Trilean.html.
↑ Post, Emil L. (1921). "Introduction to a General Theory of Elementary Propositions". American Journal of Mathematics 43 (3): 163–185. doi:10.2307/2370324. ISSN 0002-9327. https://www.jstor.org/stable/2370324.
↑ "Peirce's Deductive Logic > Peirce's Three-Valued Logic (Stanford Encyclopedia of Philosophy)". https://plato.stanford.edu/entries/peirce-logic/three-valued-logic.html.
↑ Lane, R. (2001). "Triadic Logic". http://www.commens.org/encyclopedia/article/lane-robert-triadic-logic.
↑ Peirce, Charles S. (1839–1914). "Logic : autograph manuscript notebook, November 12, 1865-November 1, 1909". Houghton Library, Harvard University. https://iiif.lib.harvard.edu/manifests/view/drs:15255301$645i. "Triadic Logic is universally true. But Dyadic Logic is not aboslutely false"
↑ Peirce, Charles S. (1839–1914). "Logic : autograph manuscript notebook, November 12, 1865-November 1, 1909". Houghton Library, Harvard University. https://iiif.lib.harvard.edu/manifests/view/drs:15255301$638i.
↑ Lane, Robert. "Triadic Logic". http://www.digitalpeirce.fee.unicamp.br/lane/p-trilan.htm.
↑ Knuth, Donald E. (1981). The Art of Computer Programming Vol. 2. Reading, Mass.: Addison-Wesley Publishing Company. pp. 190.
↑ "Third base". American Scientist (Sigma Xi, the Scientific Research Society) 89 (6): 490–494. November–December 2001. doi:10.1511/2001.40.3268. http://bit-player.org/wp-content/extras/bph-publications/AmSci-2001-11-Hayes-ternary.pdf. Retrieved 2020-04-12.
↑ Nelson, David (2008). The Penguin Dictionary of Mathematics. Fourth Edition.. London, England: Penguin Books. Entry for 'three-valued logic'. ISBN 9780141920870. https://books.google.com/books?id=ud3sEeVdTIwC&pg=PT1113.
↑ Douglas W. Jones, Standard Ternary Logic, Feb. 11, 2013.
↑ "Beyond Propositional Logic"
↑ Grzegorz Malinowski, "Many-valued Logic and its Philosophy" in Dov M. Gabbay, John Woods (eds.) Handbook of the History of Logic Volume 8. The Many Valued and Nonmonotonic Turn in Logic, Elsevier, 2009
↑ Heyting (1930). "Die formalen Regeln der intuitionistischen Logik.". Sitz. Berlin 42–56.
↑ Miller, D. Michael; Thornton, Mitchell A. (2008). Multiple valued logic: concepts and representations. Synthesis lectures on digital circuits and systems. 12. Morgan & Claypool Publishers. pp. 41–42. ISBN 978-1-59829-190-2.
↑ Dubrova, Elena (2002). Multiple-Valued Logic Synthesis and Optimization, in Hassoun S. and Sasao T., editors, Logic Synthesis and Verification, Kluwer Academic Publishers, pp. 89-114
↑ Ron van der Meyden, "Logical approaches to incomplete information: a survey" in Chomicki, Jan; Saake, Gunter (Eds.) Logics for Databases and Information Systems, Kluwer Academic Publishers ISBN:978-0-7923-8129-7, p. 344; PS preprint (note: page numbering differs in preprint from the published version)
↑ C. J. Date, Relational database writings, 1991–1994, Addison-Wesley, 1995, p. 371

v t e Non-classical logic
Modal	Alethic Axiologic Deontic Doxastic Epistemic Temporal Normal Regular Classical
Intuitionistic	Intuitionistic logic Constructive analysis Heyting arithmetic Intuitionistic type theory Constructive set theory
Fuzzy	Degree of truth Fuzzy rule Fuzzy set Fuzzy finite element Fuzzy set operations
Substructural	Structural rule Relevance logic Linear logic
Paraconsistent	Dialetheism
Description	Ontology Ontology language
Many-valued	Three-valued Four-valued Łukasiewicz
Digital logic	Three-state logic Tri-state buffer Four-valued Verilog IEEE 1164 VHDL

v t e Mathematical logic
General	Formal language Formation rule Formal proof Formal semantics Well-formed formula Set Element Class Classical logic Axiom Rule of inference Relation Theorem Logical consequence Type theory Symbol Syntax Theory
Systems	Formal system Deductive system Axiomatic system Hilbert style systems Natural deduction Sequent calculus
Traditional logic	Proposition Inference Argument Validity Cogency Syllogism Square of opposition Venn diagram
Propositional calculus and Boolean logic	Boolean functions Propositional calculus Propositional formula Logical connectives Truth tables Many-valued logic
Predicate logic	First-order Quantifiers Predicate Second-order Monadic predicate calculus
Naive set theory	Set Empty set Element Enumeration Extensionality Finite set Infinite set Subset Power set Countable set Uncountable set Recursive set Domain Codomain Image Map Function Relation Ordered pair
Set theory	Foundations of mathematics Zermelo–Fraenkel set theory Axiom of choice General set theory Kripke–Platek set theory Von Neumann–Bernays–Gödel set theory Morse–Kelley set theory Tarski–Grothendieck set theory
Model theory	Model Interpretation Non-standard model Finite model theory Truth value Validity
Proof theory	Formal proof Deductive system Formal system Theorem Logical consequence Rule of inference Syntax
Computability theory	Recursion Recursive set Recursively enumerable set Decision problem Church–Turing thesis Computable function Primitive recursive function

Anonymous

Search

Three-valued logic

Namespaces

More

Page actions

Contents

Pre-discovery

Representation of values

Logics

Kleene and Priest logics

Łukasiewicz logic

RM3 logic

HT logic

Bochvar logic

Ternary Post logic

Modular algebras

Applications

SQL

See also

References

Further reading

Navigation

Navigation

Help

Translate

Wiki tools

Wiki tools

Anonymous

Search

Three-valued logic

Pre-discovery

Representation of values

Logics

Kleene and Priest logics

Łukasiewicz logic

RM3 logic

HT logic

Bochvar logic

Ternary Post logic

Modular algebras

Applications

SQL

See also

References

Further reading

Navigation

Wiki tools

Page tools

Other projects

Categories