From: ikastan@uranus.uucp (Ilias Kastanas)
Subject: Re: Ternary logic
Date: 30 Oct 1999 04:32:56 GMT
Newsgroups: sci.logic,sci.math,alt.math,comp.theory
Keywords: 3-valued logics of Kleene, Post
In article ,
Fred Galvin wrote:
@On 28 Oct 1999, David Kinny wrote:
@
@> Fred Galvin writes:
@>
@> >On 28 Oct 1999, David Kinny wrote:
@>
@> >> There's more than one way to do 3-valued logics based on T/F/U,
@> >> but if I recall the most obvious one is that due to Kleene, where:
@> >>
@> >> not U = U
@> >> T and U = U
@> >> F and U = F
@> >> T or U = T
@> >> F or U = U
@> >>
@> >> Everything else is either derived from this or as in Boolean logic.
@>
@> >If you have 3 truth values, then shouldn't you have more operators,
@> >besides the ones definable from AND, OR, and NOT? For instance, a unary
@> >operator h such that h(T) = U, h(U) = U, h(F) = F? Is there a standard set
@> >of basic operators for 3-valued logic?
@>
@> You've got a choice about which operators you use, and which you consider
@> basic: in boolean logic there're 4 distinct unary operators, 16 binary,
@> 256 ternary, etc. (some of which are constant or rather idiosynchratic).
@> In 3-valued logic its 9 unary, 19683 binary, and 7625597484987 ternary!
@
@I know how many functions there are; I was wondering if there are any
@standard generating sets for 3-valued logic.
@
@> Some extra ones are often used. For example, h(T) = T, h(F) = T, h(U) = F
@> gives the "isknown" unary function.
And then no more are needed; 0-ary F, T, U, unary h, ~ and
binary &, v (or just one of the two) are a functionally complete system:
It's easy to see that all (ahem) 27 unary functions can be realized. For
an m+1-ary g(P, P1, ..., Pm) consider the m-ary g_1 = g(F, ...), g_2 =
g(T, ...), g_3 = g(U, ...); g is realized by (~h(P) v P v g_1) &
& (~h(P) v ~P v g_2) & (h(P) v g_3).
By the way, this 3-valued logic of Kleene differs from the m = 3
case of the "m-valued logic" studied by L/ukasiewicz, Post, Tarski et al.
In the 3-element Post algebra ( F = e_0 <= e_1 <= e_2 = T ) ~e_1 is F,
rather than e_1; and e_1 -> e_1 is T. No 3-valued Post algebra (or
m-valued, for that matter) can have an element c with ~c = c... because
in any pseudo-Boolean algebra x & ~x = F.
No surprise, of course. The truth-value e_1 is "between" F and
T... quite unlike Kleene's U, which was motivated by the logic of partial
recursive predicates. U behaves "like" the set {F,T}... its ~ being
{T, F}, and so on.
Ilias