Talk:Ternary logic/Draft

From Wikipedia, the free encyclopedia

A ternary, three-valued or trivalent logic is a term to describe any of several multi-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 boolean logic) which provide only for true and false.

Contents

[edit] Definitions

[edit] 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:

  • 1 for true, 2 for false, and 0 for unknown, irrelevant, or both.[1]
  • 0 for false, 1 for true, with the third value being non-integer symbol such as # or ½.[citation needed]
  • Balanced ternary uses -1 for false, 1 for true and 0 for the third value; these values may also be simplified to -, +, and 0, respectively.[2]

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

[edit] Dual-operand functions

A function that takes two values as inputs might be termed a binary function; however, to avoid confusion with the binary numeral system, functions accepting two inputs will be referred to as dual-operand functions.

[edit] Ternary truth values

The precise meaning of the truth values is essential to any system of logic. Using a ternary logic system in which unknown means "an unambiguous true or false equivalent exists, but we don't currently have access to it," then we can make deductions about compound functions.

For example, the assertion, "Jimmy hoffa is alive," may or may not be true to our current knowledge. However, we can definitively say the expression, "Either Jimmy Hoffa is alive or Jimmy Hoffa is not alive," is equivalent to true. Under such a logic system, unknown can be thought of as a sealed box that contains either one true or one false. A statement can be true, false, unknown (but secretly true), or unknown (but secretly false). In such a system, P \vee \neg P is always equivalent to true, since all possible values lead to the same result.

Under a different set of rules, the truth value unknown might mean, "some degree of truth between purely true and purely false." In this sort of ternary logic, the assertion, "Bangladesh has the same population as Russia," might be true or false, depending on perspective. The exact populations of these two countries are not known with certainty, and exacting estimates are very unlikely to coincide perfectly. The two population figures may be close enough to satisfy some needs, but not others. In such a logic system, the expression, "Either Bangladesh has the same population as Russia or it does not," might actually resolve to the third value, despite the apparent contradiction. A statement can be true, false, or both. In such a system, P \vee \neg P is sometimes equivalent to true and sometimes both, but never false, since there is no possible value of P that will lead to a false result.

[edit] Ternary functions

The functions of boolean logic can be represented as a subset of the ternary logic functions represented here. In general, the result of an operation op on the unknown value is determined by:

if op(true) = op(false)
op(unknown) = op(true) = op(false)
else
op(unknown) = unknown

Note that this rule applies only to individual operators. It does not generalize to compound boolean functions in all ternary logic systems. For example, in boolean logic, the expression P \vee \neg P resolves to true whether P is true or false. This function (known as the law of the excluded middle) is a tautology in boolean logic, since it resolves to true for all possible truth values of P. However in some ternary logics, the expression may resolve to either true or both, depending on whether P is both. In other ternary logics, the expression is the same tautology, resolving to true, whether P is true, false, or unknown, since the value unknown can be assumed to be a definite true or a definite false, which is merely unavailable at the time the expression is evaluated.

[edit] Common connectives

The examples below extend boolean logic to a ternary context, using the conventional connectives and symbols.

  • Negation ¬ (NOT)
The negation function interchanges true and false, while leaving the unknown unchanged, since the negation of an unknown statement is still unknown.
P ¬P
false true
true false
unknown unknown
  • Conjunction \wedge (AND)
The result of the conjunction function is true if both P is true and Q is true, false if either P is false or Q is false, and unknown otherwise.
  • Disjunction \vee (OR)
The result of the disjunction function is false if both P is false and Q is false, true if either P is true or Q is true, and unknown otherwise.
  • Implication \rightarrow (IF...THEN)
The implication function specifies that for the statement to be true, the operand to the right of the arrow must be true, assuming the operand on the left is true. If the operand on the left is false, then the operand on the right is irrelevant and the statement defaults to true. In some ternary logics, a false value on the left would resolve to unknown; however, the truth values in the table below show a ternary version of this function which preserves the boolean truth values.
  • Equivalence \leftrightarrow (EQUIV)
If the operands on both sides of the operator are the same, then the function resolves to true, otherwise false. If either operand is unknown, then the result is also unknown.
P Q P \wedge Q P \vee Q P \rightarrow Q P \leftrightarrow Q
false false false false true true
false true false true true false
true false false true false false
true true true true true true
unknown false false unknown unknown unknown
false unknown false unknown true unknown
unknown true unknown true true unknown
true unknown unknown true unknown unknown
unknown unknown unknown unknown unknown unknown

All other ternary logic functions can be constructed from some combination of the four basic operators NOT, AND, OR and IF...THEN.

[edit] Unary functions

Boolean logic has four possible unary functions, shown for comparison in the table below, using numerical bit representiation.

0 1
F0, "set to 0" 0 0
F1, "identity" 0 1
F2, "reverse value" 1 0
F3, "set to 1" 1 1

In the table above, we see that the unary function F2, which might be termed NOT, when applied to binary value 0 results in 1, and when applied to binary value 1 results in 0.

While bivalent logic has four possible unary functions, there are 27 unary functions available in ternary logic. That is, given the three possible initial values of a single trit, there are 27 unique sets of possible outcomes, and thus 27 possible unary functions in ternary logic.

These functions are represented in the following table, operating on numeric trits, rather than explicit truth values. The functions are numbered from F0 through F26, and some functions are given mnemonic names. The numerals given to the right of a function indicate the result of applying that function to the trit value listed in the column header. For example, F1(0) = 0, F1(1) = 0, F1(2) = 1, so these results { 0, 0, 1 } are listed beside the "shift down" function.

0 1 2 0 1 2 0 1 2
F0, "set to 0" 0 0 0 F9 1 0 0 F18 2 0 0
F1, "shift down" 0 0 1 F10 1 0 1 F19, "rotate down" 2 0 1
F2 0 0 2 F11, "swap 0/1" 1 0 2 F20 2 0 2
F3 0 1 0 F12 1 1 0 F21, "swap 0/2" 2 1 0
F4 0 1 1 F13, "set to 1" 1 1 1 F22 2 1 1
F5, "identity" 0 1 2 F14 1 1 2 F23 2 1 2
F6 0 2 0 F15, "rotate up" 1 2 0 F24 2 2 0
F7, "swap 1/2" 0 2 1 F16 1 2 1 F25 2 2 1
F8 0 2 2 F17, "shift up" 1 2 2 F26, "set to 2" 2 2 2

The number of functions for a given number of variables for ternary logic can be calculated by the equation 3^{3^v}, where v represents the number of variables. This gives us

  • 27 one-variable functions in ternary logic,
  • 19,683 two-variable functions, and
  • 7,625,597,484,987 three-variable functions.

[edit] Commutativity

As stated above, there are 19,683 dual-operand ternary functions. However, only 3^{3 \choose 2} = 729 of these are commutative. Of the four functions defined above, OR, AND, and EQUIV are commutative, while IF...THEN is not.


[edit] Draft footer

Per WP:SUBPAGE these sections are enclosed in a pair of nowiki tags. Alternatively, individual line items can be singled out for nowiki, if the mangled rendering is annoying. When this draft is promoted to the main article space, the nowiki tags should be removed.

==References== <div class="references-small"> <references/> </div> ==See also== * [[Digital circuit]] * [[Ternary]] * [[Ternary computer]] * [[Boolean algebra]] * [[Boolean function]] * [[Binary logic]] * [[Setun]] - an experimental Russian computer which was based on ternary logic ==External links== * [http://xyzzy.freeshell.org/trinary/ Trinary Computer Systems] * [http://www.progsoc.uts.edu.au/~sbg/intercal/ick5.html TriINTERCAL] - the intentionally-obfuscated INTERCAL programming language supports an implementation of ternary logic * [http://www.boost.org/doc/html/tribool.html Boost.Tribool] – an implementation of ternary logic in [[C++]] * [http://www.inria.fr/rapportsactivite/RA2004/r2d22004/uid51.html Team-R2D2] - a French institute that fabricated the first full-ternary logic chip (a 64-tert SRAM and 4-tert adder) in 2004 [[Category:Logic]] [[de:Dreiwertige Logik]] [[pl:Logika trójwartościowa]] [[ru:Троичная логика]]