Three-valued logic

Last updated

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 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.

Contents

In three unnumbered pages from his unpublished notes written before 1910, Charles Sanders Peirce developed what amounts to a semantics for three-valued logic. This is at least ten years before Emil Leon Post's dissertation, which is usually cited as the origin of three-valued logic.

Conceptual form and basic ideas were initially created 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.

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:

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

Where Boolean logic has 22 = 4 unary operators, the addition of a third value in ternary logic leads to a total of 33 = 27 distinct operators on a single input value. Similarly, where Boolean logic has 22×2 = 16 distinct binary operators (operators with 2 inputs), ternary logic has 33×3 = 19,683 such operators. Where we can easily name a significant fraction of the Boolean operators (not, and, or, nand, nor, exclusive or, equivalence, implication), it is unreasonable to attempt to name all but a small fraction of the possible ternary operators. [5]

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
FT
UU
TF
AND(A, B)
A ∧ BB
FUT
AFFFF
UFUU
TFUT
OR(A, B)
A ∨ BB
FUT
AFFUT
UUUT
TTTT
(−1, false; 0, unknown; +1, true)
NEG(A)
A¬A
−1+1
00
+1−1
MIN(A, B)
A ∧ BB
−10+1
A−1−1−1−1
0−100
+1−10+1
MAX(A, B)
A ∨ BB
−10+1
A−1−10+1
000+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 at least one unknown operand. For example, because 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, because 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:

, and its truth table is

IMPK(A, B), OR(¬A, B)
A → BB
FUT
AFTTT
UUUT
TFUT
IMPK(A, B), MAX(−A, B)
A → BB
−10+1
A−1+1+1+1
000+1
+1−10+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.) [6]

Ł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. [7]

Material implication for Łukasiewicz logic truth table is

IMPŁ(A, B)
A → BB
FUT
AFTTT
UUTT
TFUT
IMPŁ(A, B), MIN(1, 1−A+B)
A → BB
−10+1
A−1+1+1+1
00+1+1
+1−10+1

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

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

They have the following truth tables:

AMA
FF
UT
TT
ALA
FF
UF
TT
AIA
FF
UT
TF

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:

Bochvar 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: [8]

Applications

SQL

The database structural query language SQL implements ternary logic as a means of handling comparisons with NULL field content. The original intent of NULL in SQL was 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. [9] 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, [10] meaning its logical operators can express (in combination) any conceivable three-valued logical function.

See also

Related Research Articles

Logical conjunction logical connective AND

In logic, mathematics and linguistics, And (∧) is the truth-functional operator of logical conjunction; the and of a set of operands is true if and only if all of its operands are true. The logical connective that represents this operator is typically written as or .

Logical connective symbol or word used to connect sentences (of either a formal or a natural language)in a grammatically valid way, such that the value of the compound sentence produced depends only on that of the original sentences and on the meaning of the connective

In logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the value of the compound sentence produced depends only on that of the original sentences and on the meaning of the connective.

In logic, the semantic principleof bivalence states that every declarative sentence expressing a proposition has exactly one truth value, either true or false. A logic satisfying this principle is called a two-valued logic or bivalent logic.

In logic, a many-valued logic is a propositional calculus in which there are more than two truth values. Traditionally, in Aristotle's logical calculus, there were only two possible values for any proposition. Classical two-valued logic may be extended to n-valued logic for n greater than 2. Those most popular in the literature are three-valued, the finite-valued with more than three values, and the infinite-valued (infinitely-many-valued), such as fuzzy logic and probability logic.

In logic, negation, also called the logical complement, is an operation that takes a proposition to another proposition "not ", written , which is interpreted intuitively as being true when is false, and false when is true. Negation is thus a unary (single-argument) logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity and vice versa. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition is the proposition whose proofs are the refutations of .

In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth.

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

In logic, a truth function is a function that accepts truth values as input and produces a truth value as output, i.e., the input and output are all truth values. The typical example is in propositional logic, wherein a compound statement is constructed by one or two statements connected by a logical connective; if the truth value of the compound statement is determined by the truth value(s) of the constituent statement(s), the compound statement is called a truth function, and the logical connective is said to be truth functional.

In computer programming, ?: is a ternary operator that is part of the syntax for basic conditional expressions in several programming languages. It is commonly referred to as the conditional operator, inline if (iif), or ternary if. An expression a? b : c evaluates to b if the value of a is true, and otherwise to c. One can read it aloud as "if a then b otherwise c".

In computer science, the Boolean data type is a data type that has one of two possible values which is intended to represent the two truth values of logic and Boolean algebra. It is named after George Boole, who first defined an algebraic system of logic in the mid 19th century. The Boolean data type is primarily associated with conditional statements, which allow different actions by changing control flow depending on whether a programmer-specified Boolean condition evaluates to true or false. It is a special case of a more general logical data type —logic doesn't always need to be Boolean.

Null (SQL) special marker and keyword in SQL

Null 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 fulfil the requirement that all true relational database management systems (RDBMS) support a representation of "missing information and inapplicable information". Codd also introduced the use of the lowercase Greek omega (ω) symbol to represent Null in database theory. In SQL, NULL is a reserved word used to identify this marker.

In abstract algebra, a branch of pure mathematics, an MV-algebra is an algebraic structure with a binary operation , a unary operation , and the constant , satisfying certain axioms. MV-algebras are the algebraic semantics of Łukasiewicz logic; the letters MV refer to the many-valued logic of Łukasiewicz. MV-algebras coincide with the class of bounded commutative BCK algebras.

In logic, a tautology is a formula or assertion that is true in every possible interpretation. An example is "x=y or x≠y". A less abstract example is "The ball is all green, or the ball is not all green". This is true regardless of the color of the ball.

The logic alphabet, also called the X-stem Logic Alphabet (XLA), constitutes an iconic set of symbols that systematically represents the sixteen possible binary truth functions of logic. The logic alphabet was developed by Shea Zellweger. The major emphasis of his iconic "logic alphabet" is to provide a more cognitively ergonomic notation for logic. Zellweger's visually iconic system more readily reveals, to the novice and expert alike, the underlying symmetry relationships and geometric properties of the sixteen binary connectives within Boolean algebra.

T-norm fuzzy logics are a family of non-classical logics, informally delimited by having a semantics that takes the real unit interval [0, 1] for the system of truth values and functions called t-norms for permissible interpretations of conjunction. They are mainly used in applied fuzzy logic and fuzzy set theory as a theoretical basis for approximate reasoning.

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables. In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, logically valid.

An Imieliński–Lipski algebras is an extension of relational algebra onto tables with different types of null values. It is used to operate on relations with incomplete information.

The syntax of the SQL programming language is defined and maintained by ISO/IEC SC 32 as part of ISO/IEC 9075. This standard is not freely available. Despite the existence of the standard, SQL code is not completely portable among different database systems without adjustments.

In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively. Instead of elementary algebra where the values of the variables are numbers, and the prime operations are addition and multiplication, the main operations of Boolean algebra are the conjunction (and) denoted as ∧, the disjunction (or) denoted as ∨, and the negation (not) denoted as ¬. It is thus a formalism for describing logical operations in the same way that elementary algebra describes numerical operations.

In logic, a finite-valued logic is a propositional calculus in which truth values are discrete. Traditionally, in Aristotle's logic, the bivalent logic, also known as binary logic was the norm, as the law of the excluded middle precluded more than two possible values for any proposition. Modern three-valued logic allows for an additional possible truth value.

References

  1. "Stanford JavaNLP API". Stanford University. Stanford NLP Group.
  2. Knuth, Donald E. (1981). The Art of Computer Programming Vol. 2. Reading, Mass.: Addison-Wesley Publishing Company. p. 190.
  3. Hayes, Brian (November–December 2001). "Third base" (PDF). American Scientist . Sigma Xi, the Scientific Research Society. 89 (6): 490–494. doi:10.1511/2001.40.3268. Archived (PDF) from the original on 2019-10-30. Retrieved 2020-04-12.
  4. Nelson, David (2008). The Penguin Dictionary of Mathematics. Fourth Edition. London, England: Penguin Books. Entry for 'three-valued logic'. ISBN   9780141920870.
  5. Douglas W. Jones, Standard Ternary Logic, Feb. 11, 2013.
  6. http://www.uky.edu/~look/Phi520-Lecture7.pdf
  7. 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
  8. 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.
  9. 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)
  10. C. J. Date, Relational database writings, 1991–1994, Addison-Wesley, 1995, p. 371

Further reading