Three Valued Logic

An extension of BooleanLogic (TwoValuedLogic) or BooleanAlgebra, where there are three values: 'True', 'False' and 'Unknown'. Unknown might also mean 'undefined', or 'neither'.

Three-valued logic is used quite a lot in FormalMethods.

Truth tables for ThreeValuedLogic ( | = or, & = and, ^ = xor, ! = not)

 T & T = T  T & U = U  T & F = F
 U & T = U  U & U = U  U & F = F
 F & T = F  F & U = F  F & F = F

 T | T = T  T | U = T  T | F = T
 U | T = T  U | U = U  U | F = U
 F | T = T  F | U = U  F | F = F

 T ^ T = F  T ^ U = U  T ^ F = TU ^ T = U  U ^ U = U  U ^ F = U
 F ^ T = T  F ^ U = U  F ^ F = F

 !T = F     !U = U     !F = T

In addition, an operator isUnknown (?) is often defined; this has the following truth table

 ?T = F     ?U = T     ?F = F

Although technically "three-valued logic" does not depend on the particular operator definitions given above, these are by far the most commonly used definitions (they are used in ViennaDevelopmentMethod, for example).

Note that unknowns are not held to be equivalent. The exclusive OR of unknown and unknown is unknown (not false); as it is not necessary that the two unknowns are the same thing. Likewise, comparing two unknowns for equality returns unknown, not true. This can cause "holes" in reasoning; as such operations can be well-defined if two instances of unknown can be shown to be equivalent.

For example, the proposition ((P==NP) ^ (P==NP)), one could argue, is false. P==NP is a well-known unknown proposition; however one could argue that if it is true on one side of the ^, it's true on the other (and likewise for false); thus the exclusive-OR ought to be well-defined, not unknown.

Likewise, the proposition ((P==NP) ^ (P!=NP)), one could argue, is true.

On the other hand, the proposition ((P==NP) ^ (IsFactoringHardAsDiscreteLogarithm?)) ought to be unknown; as the two OpenProblemsInComputerScience might not have the same solution.

Many authors and computer scientists, for this (and other) reasons, prefer to avoid ThreeValuedLogic. Part of the problem, of course, is that by reducing an unknown predicate from it's explicit formulation to the singular value "unknown", one loses information in the process.

ChrisDate argues at length against ThreeValuedLogic in the context of database systems in the book AnIntroductionToDatabaseSystems (and in many of his other writings). This section has been moved to NullsAndRelationalModel.

This page, so far, appears to miss several major implications of ThreeValuedLogic. Most importantly, the operators considered (| = or, & = and, ^ = xor, ! = not) are only four of 19,683 possible ternary logic functions. Instead of discussing values of (T F U), it might be more helpful to consider the tuple (0 1 2). The truth table for an arbitrary ternary function is then:

 F|0 1 2 
 -+------
 0|a b c
 1|d e f
 2|g h i

For example, here's one:

 F|0 1 2 
 -+------
 0|1 0 2 
 1|0 2 1 
 2|2 1 0

There are 19,683 (3^9) unique permutations of the truth table, leading to the same number of values for F. In general, for nary logic, there are n^(n^2) possible single-argument functions. The number of such functions for 4-ary is 4^(4^2), or 4^16, or 2^32.

How many of them are useful? :)

That's a good question. :)
We can manage Boolean logic with one unary and one binary operator (of a possible sixteen) plus two propositions (NOT, AND, 1, 0). One way to answer this question is to find an intuitive but minimal sets of operations for performing all the ternary logic one might ever wish to do. Then add any desired for semantic convenience and syntactic clarity for common constructs (OR, XOR, IMPLICATION). In searching for good, intuitive, binary ops, some reasonable targets are Commutivity ((a OP b) == (b OP a)) and Associativity (((a OP b) OP c) == (a OP (b OP c))). Identity ops can be dropped, since they don't really calculate anything useful. Any binary ops independent of one input should also be eliminated or considered for unary. Reflexive ops ((a OP a) == a) such as AND and OR seem a bit easier to grasp (than, e.g. XOR), but that shouldn't be a ruling factor if something can be gained from them (e.g. with XOR).
How much does that eliminate? From the basic set, there are 3^(3^2) possible binary ops.

  F|0 1 2
  -+-----
  0|a b c
  1|d e f
  2|g h i

Well, in support of commutivity, we can eliminate three of the items. That cuts us down immediately to 729 binary functions for potentially 'useful' and intuitive ternary logic.

  FC|0 1 2
  --+-----
   0|a b c
   1|b e f
   2|c f i

For Reflexive binary ops, we can also eliminate questions on the diagonal, reducing us to 27 functions that are reflexive. If only reflexive ops are chosen for binary, then at least one unary op is needed.

  FCR|0 1 2
  ---+-----
    0|0 b c
    1|b 1 f
    2|c f 2

The requirement of dependence on both inputs eliminates as useless all functions where either each row contains only one value, or each column contains only one value. As you might expect, there aren't many of these. For F, it eliminates 51 functions (27 for pick-column value + 27 for pick-row-values - 3 shared (all values equal)). For FC, it eliminates only 3 functions (all values equal). For FCR, it eliminates none at all.
For associative operations, the constraint is that ((x OP y) OP z) == (x OP (y OP z))... which is nice for folding operations across collections and such. Counting these is a brain teaser that I haven't figured out yet, and I'm not sure how much more it restricts things than commutivity already did.
For Unary operators, however, the qualities of value are more questionable. Only one operator is needed for all possible unary operations (\x -> (x+1) mod N for N-ary logic), but what is intuitive and meaningful would depend on the interpretation of the logic. For true/false/unknown, I'd propose the Boolean 'not' (which is identity on the unknown value) and the 'unknown?' operator, which returns true if the value is unknown, and false otherwise.

We should also consider the question of state inversion in ternary systems (as well as 4-state systems and so on). In a binary system, inversion is trivial - not 0 is 1, not 1 is 0. In three-value logic, inversion (!) is not necessarily as simple as claimed above. The inversion of 0 can be either 1 or 2. Inversions are often most useful when they are reversible, so that if !0 = 2, then !2 = 0. This leaves 1 to invert to itself. Another approach, however, has !0=1, !1=2, and !2=0 - this is invertible but not reversible, as !(!0) = 2, not 0. There are 6 reversible ternary inverters (including the identity).

This material is excerpted from http://www.multivaluelogic.com. Another good site is http://www.ternarylogic.com.

Ternary systems (and ThreeValuedLogic) is of interest in biology because it may be helpful in analysing and modeling "pathways", the chains of various reactions that promote or inhibit the production of a particular protein. Such a pathway can be modeled as a network of nodes, where each node is promoted, inhibited, or not affected by others. Some researchers have speculated that ThreeValuedLogic may be as natural to a biological computing system as binary logic is to an electronic system.

-- TomStambaugh

Only one operator is needed for all possible unary operations. (\x -> (x+1) mod N)

How so? Consider unary operation not, mentioned already. not(0)=1, not(1)=0, not(2)=2. It can't be defined in terms of x+1 mod N.
To express 'not', you'd combine the unary operator with a binary operator on the same operand.

I'd propose the Boolean 'not' (which is identity on the unknown value) and the 'unknown?' operator, which returns true if the value is unknown, and false otherwise. With these two functions it's impossible to get undefended value from true or false value. Only by combining all three (not, unknown? x+1 mod n) it's possible to cover all unary functions. -- AnonymousDonor

Do you have a URL on that?

There's some relevant material at http://www.stats.gla.ac.uk/~microarray/talks/eddougherty_25jun02.htm. This whole field is fairly new and moving pretty rapidly, so material is fleeting and hard to find. You may find yourself doing a LOT of reading. -- TomStambaugh

These things don't show the same sorts of structure as normal binary logic. What makes them logics, as opposed to just operations on sets? I couldn't find an answer in the quoted pages.

I don't understand the distinction you're drawing between "logics" and "operations on sets". Each particular truth table corresponds to a function mapping the value of two ternary variables to a third outcome. Boolean logic has 16 such mappings. Ternary logic has 19,683. The association between the chosen values (0 and 1 or 0, 1 and 2, or -1, 0, 1, etc) and concepts such as "true", "false", "on", "off", "undefined", and so on is arbitrary.

 A ------+
         |
         v
      +--+--+
      |     |
      |  F  +---> Out
      |     | 
      +--+--+
         ʌ
         |
 B ------+

In the above diagram, "A", "B" and "Out" are ternary variables. The box represents an operation, F, which can be associated with one of the 19,683 possible ternary logic functions. Given values for A, B, and F, the truth table specifies the resulting value of "Out". Any semantic value associated with a value of F (such as "and", "or", "plus", "minus", etc.) is arbitrary. -- TomStambaugh

I understand all that. I'm asking you what makes a particular collection of set operations a "logic", or why the word is overloaded to include them. Normally, in mathematics, categories of objects are defined by axioms, and I have seen some versions of "logics" defined that way. But those normally at least include some rule about negation being self-inverse, and apparently these don't. Hence my question.

[The subject is complicated by the development of so many new kinds of logic in the 20th century (multi-valued, FuzzyLogic, relevance, etc), however it probably remains true that any system of "logic" contains at minimum the primitive values "true" and "false", as well as some kind of inference system for deriving truth or falsehood.]

[From that point of view, a set theory must at minimum have values isomorphic to true and false, as well as morphisms between sets which is in some sense equivalent to inference. Given that, such a set theory could be regarded as a logic, whereas without that, it wouldn't seem profitable to call it such.]

[This seems more to the point than the well-known fact that traditional logic can be modelled in set theory and vice-versa. -- DougMerritt]

The association of semantics with ternary logic, such as the assignment of "true" and "false" to values and the identification of "interesting" functions, is one of the more interesting areas of study at the moment. My cursory read of the literature is that this is being approached statistically, through simulation and computation, rather than through more classic approaches. Researchers are assembling networks of ternary operators, using brute-force relaxations from initial conditions, and comparing the results to observed gene expression data. The theme is to discover, empirically, "interesting" functions that increase the correlation between the computed and measured results. -- TomStambaugh

How does the "unknown" value compare with "top" and "bottom" elements of LatticeTheory? ?

Example:

Unknown probably doesn't correspond to either; however the database NULLs that give rise to unknowns in a relational context are very similar to the BottomType.

http://plato.stanford.edu/entries/logic-manyvalued/ (from where the diagram above is from) seems to be saying that BottomType corresponds to "unknown" and top should represent "conflict" or in their words: "conflicting information saying that the state of affairs obtains as well as fails." In which case you are then dealing with a FourValuedLogic? but is the construct valid for ThreeValuedLogic if you omit TopType?

In my personal opinion - BottomType should be used for exactly one thing - divergence. Anything else (nulls, exceptions, unknowns, etc.) should be handled with separate types, and whenever you need one of these you should construct a type-union of the "normal" datatype and whichever of the aforementioned SingularityType?s you like.

Why? Because BottomType is like a wildcard in the type system - any expression or variable, no matter the type, can also be BottomType - as BottomType is the universal subtype of anything. There is no way to exclude the possibility of any expression being _|_. Many OO languages - CommonLisp, JavaLanguage (to some extent), EiffelLanguage - treat nulls in this fashion; thus there is no way to say in any of these that a given reference cannot be null; because the type system says null is valid in any context. (I qualified Java because it doesn't explicitly equate null with BottomType; Eiffel and CommonLisp do, OTOH; however Java doesn't provide mandatory references).

"Any expression or variable, no matter the type, can also be BottomType" -- this is incorrect. Any expression or variable, no matter the type, is also of TopType. If some particular value managed to instantiate the BottomType of some particular TypeLattice?, then you could say that this value was an element of every other type in the lattice. This does happen to be the case when dealing with the TypeLattice? constructed under the Maybe monad where Just T | Nothing is considered, which is structurally equivalent to references for which NULL values are allowed. One should not say that Nothing/Null/etc. is a type of Integer (since it lacks the properties of an Integer), but rather that it is a value that instantiates the type: Maybe Integer/Reference Integer/etc.
In many languages, BottomType isn't occupied by anything at all. Thus, while BottomType is a subtype of all types, it doesn't have any values, because any value in BottomType would need all the properties of all the different types of values in the language... which are often mutually exclusive.

Having BottomType represent divergence does make sense, because any computation can potentially diverge - and unlike the other cases, divergence doesn't mean the returning of in invalid result; it's the failure to return a result at all.

To make good use of this in the general case, of course, you'd need to solve the halting problem.

-- ScottJohnson

IT DEPENDS ON THE APPLICATION!

There is no single "right" answer that applies to every situation. An obvious contradiction to your expressed preference is in divergence-free systems, such as SQL. All SQL queries terminate.

That doesn't necessary contradict my preference - in such a system, one could dispense with BottomType altogether. Of course, SQL doesn't use BottomType (and SQL nulls are very much like bot, in that any attribute, regardless of its type, can be set to NULL) for divergence, it uses it for "unknown". Whether that usage is appropriate is the subject of much heated debate in the relational community. -- sj

Are you playing Devil's Advocate? Surely you should take into account WhatIsNull, BottomType, NullsAndRelationalModel, and NullConsideredHarmful, rather than just say the above here in isolation. I don't feel like repeating here what I said there literally yesterday, and between all these pages, I feel like everything you're saying is addressed. (I must be getting mixed up, I thought you posted on some of those pages.) -- dm
- Not intending to, though perhaps I'm confused. It's been known to happen before. :) My general feelings on the subject of nulls (in the context of general purpose programming languages, and SQL at least has its toes in that particular pond) is that use of BottomType to implement null is questionable practice, for the reasons outlined on the aforementioned pages. That said, many languages do it, and there are far worse sins committed than null=bot. There seems to be some confusion (not in your mind) between "null" and "unknown"; these ought to be different concepts (and "unknown", one of the three values in ThreeValuedLogic) definitely ought to not be the BottomType. (You shouldn't be able to assign "unknown" to an arbitrary int; any more than you can assign "true" to one; C/C++ type coercions nonwithstanding). Costin pointed out some flaws in ChrisDate's proposed solution (and I have a few of my own doubts). Some of the above commentary on logic(s) is interesting; however it tends to consider logic in isolation. Null in general, I have no problems with, as they are damn useful, even if it gives the academic types fits - I've several books on CategoryTheory and TypeInference (relatively advanced material), and the authors of all of 'em (KimBruce?, BenjaminPierce) tend to sidestep nulls. Part of the disconnect between theory and practice, I suspect, springs from the fact that proving that a particular expression isn't null (at compile time) is a hard thing for a TypeInference system to do - but it's so quick and easy for programmers to do the check. At any rate, I don't mind null; I just prefer systems that allow me to exclude it from the set of values for any particular variable/attribute/etc. I hope this explains my position a bit more on the issue. -- sj
- Yes, and that's not unreasonable. But consider the functional language feature of first class type unions. You should be able to say in some program, ok, I'm going to define a NAME type, and today I want it to be the union of the types STRING and UNKNOWN. Tomorrow, though I want to add BOTTOM to that union. The biggest problem I see with SQL and other languages that have various multi-valued-logic types predefined is precisely that they are trying to pick a single solution, rather than allowing the programmer to specify the multi-valued-logic types that are appropriate for the application domain. -- dm
  - I think type unions are an excellent solution to the problem. Date doesn't like them, but he and I part company there. However, it should be pointed out that adding BottomType to the union is an operation with no effect. As BottomType is the universal subtype, it already is a valid value for any domain you create.. Even if your type system allows a class/domain to be declared "final" (using the Java terminology), it still has at least one subtype if BottomType is present. Which is why I argue against using BottomType for nulls - if null is of type BottomType, it can never be excluded from the set of values for any given variable. I think we mostly agree here, and again are picking at the nits. :) -- sj
  - "As BottomType is the universal subtype, it already is a valid value for any domain you create." -- in favor of picking a few more nits, it's wrong to assume that BottomType actually has any occupying values. However, your claim is certainly true for every value that is allowed to occupy BottomType (including NULLs, as you mention).
  - I almost said "ERROR" rather than "BOTTOM". I guess I should have. I have seen a fairly bewildering variety of systems, and I thought that, in some of them, BOTTOM wasn't always universally valid, but maybe I'm just misremembering, so skip that. One thing, though, NULL is already a type union in SQL, so shouldn't you say that it is "null being used for BottomType", not "BottomType being used for null"? Anyway Date has a favored approach, whereas I favor a multitude of paradigms with the choice in the hands of the programmer. -- dm
  - BottomType comes from CategoryTheory, and I've never seen it used for anything other than the universal subtype. Some languages, like Haskell, import the concept directly; others have Bottom-like things but call it something else. Null (however spelled or capitalized), AFAIK, doesn't have a well-defined meaning in CategoryTheory - it's very much an application-specific thing. Date has a point that (in the context of relational) NULL can cause problems - especially if any attribute can be NULL, which is the current state of affairs. However, he seems to want to exclude NULL (or other singularities) from domains/attributes completely, because it "breaks the model" (or at least complicates things greatly). However, databases are intended to model reality; if relational-without-singularities cannot model reality (including dealing with unknowns) then that's a problem with relational-without-singularities, not a problem with reality. In many cases, "unknown" or "N/A" and the like are valid values for a domain--and when that's true, they should be available. They just shouldn't be forced into domains where they aren't valid. -- sj
  - NitPick: I'm 99% sure that BottomType did not originate in CategoryTheory, because I first ran into it in the 1970s in some theoretical CS books (the Anatomy of Lisp, 1979, and another one on something like DenotationalSemantics from circa 1973-1975), and CategoryTheory was very new at that time; I don't remember noticing the existence of CategoryTheory until I read SaundersMacLane?'s "Form and Function in Mathematics" in the 1980s, which had a section on it (of course). -- dm
  - You're probably right, then... 'course in 1973 I was still in diapers. :) -- sj

In terms of the diagram referred to above, the discussion on that Stanford page explains that the topmost symbol is True, the bottommost is False, the leftmost is Unknown, and the rightmost is Contradictory.

But there are other possibilities; there is no single 3-value nor 4-value logic, and any mathematician or architect is free to choose whatever system they like (and then get flamed by the people who disagree with his choice :-)

-- DougMerritt

I know of no biology researchers who are even remotely interested in the application of ternary logic to the mathematics of relational database theory. -- TomStambaugh

Exactly. It depends on the application which theory to use. -- dm

In CommonLisp, t (true) is TopType and nil (false/empty list/unknown/whatever/etc.) is BottomType. Of course, CommonLisp is a dynamically typed language, so much of the debate over the structure of the typing lattice just doesn't matter. For statically typed languages with advanced typing systems (Haskell, ML, Eiffel, even C++/Java to some extent), this sort of thing does matter.

You are right, there is no "one correct" answer. But some answers are more correct than others...

In a particular application area, yes, but even there, still not just a single clear way to go. This should be unsurprising, considering that the mathematical issues are very far from settled. We don't have an overarching formal theory yet.

A clear example of this is in how the frame problem arises in theorem proving. You would think that this could be fixed by doing a TheoremProvingSystem based on relevance logic, but as far as I can see, that's still beyond the state of the art. (If anyone knows differently, please let me know.) -- dm

In the electronics world such logical devices, known as "tri-state", have three output values: high, low, and high impedance, meaning they are essentially disconnected from the rest of the world. It is possible to have an array of devices that all talk to the same data line but only have one device driving the line at a time. It is possible to have no devices driving the data line at all, of course - although its logical value would then be undefined.

Does this analog help in the discussion somehow?

I thought about tri-states as well when I first started thinking about gene regulation pathways (long ago in a distant universe I was trained as a hardware engineer), but it's really a different concept I think. For genes, the states are "promotes" (meaning increases production of a protein), "inhibits" (meaning decreases production of a protein), and "no effect". In a typical lab setting, you have many samples of many genes. The analysis problem is to explore the space of all possible ternary networks, searching for those whose behavior matches the observed data. -- TomStambaugh

Electronics does provide another application domain where examples demonstrate that, once again, it depends on what you want. Tristate is a ternary logic with T, F, and a third truth value which typically is not indicative of error or divergence.

In a truth table for a PLA or for test vectors, inputs are T, F, or don't care.

How the third truth value is intended is different on input vs output, and there's actually a lot of things it might mean. -- dm

Um, actually, it means, "not connected," which can't have a lot of different interpretations to it. A high impedance input has no effect on fanout of a driving device, contributes very little to overall capacitive effects, and affects no logic anywhere. A high impedance output acts exactly the same way to the outputs of other devices. The third state has a pretty specific meaning under these conditions. I see no reason why tri-state logic can't act the same way.

An oversimplication, of course. The behavior of tri-state logic is entirely predictable and defined, from the various voltages and impedances of the various devices in questions (output nodes driving a bus, input nodes being driven, and any external pullups which may be present). At DC of course; at high frequency things get difficult to model as solid state devices have decidedly non-linear responses. At any rate, the above discussion should be convincing that tri-state (or any) logic has (or doesn't have) value, depending on the application. The suitability of tri-state logic in electronics has nothing to do with its suitability in a relational database.

Despite the messiness, three-value logic often models the real world better than two-value. For example, a common source of debate in this wiki is "X is better than Y". Before any evidence is applied, the "default" value of this statement should generally be considered "null". In other words, "The difference in value between X and Y is unknown".

I think until you define "better", the "default" and "actual" value of this statement should generally be considered "undefined".

See: LogicalAnd, TetralemmicLogic, NullsAndRelationalModel, MultiValuedLogic, CantHideFromNulls, NullVersusNone.

CategoryLogic