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