Ternary logic

From Free net encyclopedia

Template:References A ternary, three-valued or trivalent logic is a multi-valued logic in which there are three truth values indicating true, false and some third value, often called possible, unknown, uncertain, neither true nor false (see fuzzy logic), or paraconsistent.

This is contrasted with traditional Aristotlean logic which only provides for True and False.

1 Formal definitions
- 1.1 Representation of values
- 1.2 Ternary operators
  - 1.2.1 Common connectives
  - 1.2.2 Other operators
2 Dyadic (two-argument) functions
- 2.1 Commutativity
3 Implementation
4 History
5 See also
6 External links

[edit]

Formal definitions

[edit]

Representation of values

In ternary logics, the number symbols 0, 1, and 2 are often used to denote the following truth values (or some permutation thereof):

0 means unknown
1 means true
2 means false

Other logics may use 0 and 1 as truth and falsity, just like classical (boolean) logic, denoting the third value by # or 1/2. Balanced ternary uses -1 for false, 1 for true and 0 for the third value.

The rest of this article discusses a system of ternary propositional logic using the above representations of truth values. Other systems assign different truth tables to the various connectives, and may even include other connectives.

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.

[edit]

Ternary operators

The operations from boolean logic can be extended to work with ternary logic. In general, the result of an operation op on the unknown value is determined by:

if op(1) ≠ op(2)

op(0) = 0

else

op(0) = op(1) = op(2)

Note that this rule does not generalize from operators to arbitrary boolean functions. For example, the formula <math> A \vee \neg A</math>, commonly called the law of the excluded middle, has the value 'true' (i.e. 1) when A is true or false (i.e. 1 or 2), and is therefore a tautology in the standard two-valued Boolean logic. However, in the usual ternary logic, its value is 0 (unknown).

[edit]

Common connectives

negation (NOT) ¬
- The negation operator should interchange true and false, while leaving the unknown value unchanged, since the negation of an unknown statement is still unknown.

conjunction (AND) <math>\wedge</math>
- The result of the conjunction operator is true if both P and Q are true, false if P or Q is false, and unknown otherwise.

disjunction (OR) <math>\vee</math>
- The result of the disjunction operator is false if both P and Q are false, true if P or Q is true, and unknown otherwise.

implication (IF...THEN) <math>\rightarrow</math>

equivalence (EQUALS) <math>\leftrightarrow</math>
- Note that any two statements with the same truth value are equivalent, even if the truth value is unknown.

P	Q	¬P	P <math>\wedge</math> Q	P <math>\vee</math> Q	P <math>\rightarrow</math> Q	P <math>\leftrightarrow</math> Q
0	0	0	0	0	1	1
0	1	0	0	1	1	0
0	2	0	2	0	0	0
1	0	2	0	1	0	0
1	1	2	1	1	1	1
1	2	2	2	1	2	2
2	0	1	2	0	1	0
2	1	1	2	1	1	2
2	2	1	2	2	1	1

[edit]

Other operators

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

The 27 unary operators in ternary logic are represented in the following table. Some of them are given names:

	1	2		0	1	2		0	1	2
f0, "clear to 0"	0	0	f9	1	0	0	f18	2	0	0
f1, "shift down"	0	1	f10	1	0	1	f19, "rotate down"	2	0	1
f2	0	2	f11, "swap 0/1"	1	0	2	f20	2	0	2
f3	1	0	f12	1	1	0	f21, "swap 0/2"	2	1	0
f4	1	1	f13, "clear to 1"	1	1	1	f22	2	1	1
f5, "identity"	1	2	f14	1	1	2	f23	2	1	2
f6	2	0	f15, "rotate up"	1	2	0	f24	2	2	0
f7. "NOT"	2	1	f16	1	2	1	f25	2	2	1
f8	2	2	f17, "shift up"	1	2	2	f26, "clear to 2"	2	2	2

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

27 one-variable functions in ternary logic (as compared to only 4 one-variable Boolean functions).
19,683 two-variable functions in trinary logic (compared with 16 for binary), and
7,625,597,484,987 three-variable functions.

[edit]

Dyadic (two-argument) functions

In order to avoid confusion with the binary numeral system, functions accepting two inputs will be referred to as dyadic functions, following the convention introduced in The Art of Assembly Language by Randall Hyde.

[edit]

Commutativity

As stated above, there are 19,683 dyadic ternary functions. However, only <math>3^{3 \choose 2} = 729</math> of these are commutative. Of the four functions defined above, OR, AND, and EQUIV are commutative, while IF/THEN is not. For comparison, there are 8 commutative two-argument binary functions.

[edit]