More 3-valued logic: Lukasiewicz and Bochvar

13 Replies

Last time I wrote about fuzzy logic, we were looking at 3-valued logics, and I mentioned that there’s more than one version of 3-valued logic. We looked at one, called K^S_3, Kleene’s strong 3-valued logic. In K^S_3, we extended a standard logic so that for any statement, you can say that it’s true (T), false (F), or that you don’t know (N). In this kind of logic, you can see some of the effect of uncertainty. In many ways, it’s a very natural logic for dealing with uncertainty: “don’t know” behaves in a very reasonable way.

For example, suppose I know that Joe is happy, but I don’t know if Jane is happy. So the truth value of “Happy(Joe)” is T; the truth value of “Happy(Jane)” is N. In Kleene, the truth value of “Happy(Joe) ∨ Happy(Jane)” is T; since “Happy(Joe)” is true, then “Happy(Joe) ∨ anything” is true. And “Happy(Joe) ∧ Happy(Jane)” is N; since we know that Joe is happy, but we don’t know whether or not Jane is happy, we can’t know whether both Joe and Jane are happy. It works nicely. It’s a rather vague way of handling vagueness, (that is, it lets you say you’re not sure, but it doesn’t let you say how not sure you are) but in so far as it goes, it works nicely.

A lot of people, when they first see Kleene’s three-valued logic think that it makes so much sense that it somehow defines the fundamental, canonical three-valued logic in the same way that, say, first order predicatelogic defines the fundamental two-valued predicate logic.

It isn’t.

There are a bunch of different ways of doing three-valued logic. The difference between them is related to the meaning of the third value – which, in turn, defines how the various connectives work.

There are other 3-valued logics. We’ll talk about two others. There’s Bochvar’s logic, and there’s Lukasiewicz’s. In fact, we’ll end up building our fuzzy logic on Lukasiewicz’s. But Bochvar is interesting in its own right. So we’ll take a look at both.

Lukasiewicz’s, which we’ll call L_3, is very similar to K^S_3. N means the same thing in L_3 as in K^S_3. The difference is in the implication operator. In Kleene, N rightarrow N is N. But in Lukasiewicz’s, it’s T. So where K^S_3 says, roughly, that “If I don’t know, I can’t infer anything”; and L_3 says “If I I don’t know, I can infer that I don’t know”. They’re both reasonable interpretations. But you can see the difference: even though both K^S_3 and L_3 both define N as “I don’t know”, L_3‘s version of N has a slightly different meaning, because you can use statements involving N to infer truth. In K^S_3, the only way you can infer a truth from a statement containing something with the truth-value N is by eliminating the N. For example, in Kleene, we can infer that if B is N in A lor B. But in L_3, we can actually use N statements: if A and B are both N, then A leftrightarrow B == T.

The change has one big benefit. In L_3, there are real tautologies.

If you recall classical two-valued logic, a tautology is a statement which, by virtue of its structure, is always true. No matter what truth values you assign to the elements of a tautology, the tautology itself will always be true. For example, in classical propositional logic, A rightarrow A is always true. If A is true, then A rightarrow A is true; if A is false, then A rightarrow A is still true. In K^S_3, it’s not true. If A is N, N rightarrow N is not true. So it’s not a tautology. In fact, every tautology in classical logic will have that problem: it won’t be true for truth-bindings involving N.

But L_3 does have tautologies – and, in fact, they’re the same tautologies as two-valued logic!

Another example of a three-valued logic is Bochvar’s internal three-valued logic, commonly written as B^I_3. Bochvar was interested in logic where you’ve got statements that aren’t true or false – not because we don’t know whether they’re true or false, but rather they aren’t true or false because they’re nonsensical, like the classical liars paradox: “This sentence is false.”. Is it true, or is it false? It makes no sense. It can’t be true, and it can’t be false. Most logics try to cope with that by saying is’s not a valid statement at all – that it’s not something you can say in the logic. Bochvar lets you say it, but gives it a truth value of “N”, meaning either nonsense or meaningless.

With N having the meaning that something is nonsense, the proper behavior of the logical connectives is quite different. Nonsense iscontagious: N &land; Anything = N; N ∨ Anything = N. N → Anything = N. And so on. Any logical statement that includes an N value will always have a combined truth value of N. What this is supposed to mean is pretty simple: if any step in a logical is nonsense, then the entire argument is nonsense. You can’t reason from garbage to meaningful.

In terms of vagueness, this seems somewhat less useful. We can use it, and in some ways, it makes sense. If you’ve got a vague statement, and you can’t quantify vagueness, then the only thing you can conclude from vagueness is vagueness. I’m a little bit happy. If I’m happy, then I must be smiling. If I’m not happy, then I’m not smiling. Can we conclude from that that I’m smiling? No. Can we conclude that I’m not smiling? No. We don’t know enough to conclude either way. So that makes sense, in its way.

If you’re the kind of person who reads this blog, you’ve probably been wondering: Why is the logic named B^I_3 instead of just B_3? The reason is that there’s more to Bochvar than this. What I’ve been describing to you so far is Bochvar’s internal three-valued logic. Bochvar described another 3-value logic, called the external logic, and he defined a way of combining the two, which makes things much more interesting.

The second Bochvar logic, also known as B^E_3 or Bochvar’s external three-valued logic, treats “N” as being equivalent to “F”. We’ll write Bochvar’s external connectives as land_E and lor_E, etc. Bochvar’s external logic is, sort of like taking the internal logic, and asking “What can we prove to be true if we discard everything nonsensical?”. So, for example, T land_E N = F: if part of a logical and statement isn’t true, then the conjunction can’t be true.

The connection between the two is the use of a sort-of forcing operator: something which takes the truth value from the three-valued logic, and converts it into a valid truth value in standard two-value logic. It’s called the assertion operator, written a. aP is the assertion operator applied to the proposition P. What the a operator means is “I assert that this statement can be proven to be true”. So aN = F; N isn’t true, and it isn’t false: it’s N. Since it’s not true, aN is false.

So if land_I is the and operator from the internal logic, and land_E is the and operator from the external logic, then A land_E B is equivalent to a(A land_I B).

The way that the two can be combined is through the use of asassertion operation, a, where aS is the assertion that S is true. So the connectives in the Bochvar’s external are really just the result of applying a to the internal connectives. In the internal logic, T land N = N. So in the external, a(T land N) = a(N) = F.

There are a couple of properties of three-valued logic that we can use to categorize the logics.

The most important property is normality. We really wouldn’t want to use a logic that’s not normal. A three-valued logic is normal if, for any logical statement that only involves the values true and false, it will have the same truth value as standard FOPL. All of the logics we’ve seen: Kleene, Lukasiewicz’s, Bochvar’s internal, Bochvar’s external, and Bochvar’s combined, are all normal.

Next, we’ve got uniformity. This is a bit harder to explain. In conventional two-valued logic, some binary operators have results that are determinable by a single particular truth value. For example, land is determinable by F: if either side of a logical and is false, then it doesn’t matter what the other side is: we know the result. An operator in a three-valued logic is uniform if it’s truth values are determinable by a single truth value, just like the conventional two-valued logic. Kleene’s three-valued logic is uniform; Lukasiewicz’s three-valued logic is uniform; Bochvar’s internal and combined logics are not; Bochvar’s external is.

Now we can get to a really interesting one: tautologies. A tautology is a statement that is always true, by virtue of its structure. No matter what truth value you assign to its elements, the statement will always be true. For example, A lor lnot A. Whether A is true or false, that’s going to be true. A implies A is always true in a two-valued logic. So, can we have tautologies in three-valued logics?

In Kleene, the answer is no. Take that simple example, above: A lor lnot A. Suppose A is N. Then we’ll end up with N lor lnot N, which is not true. So the tautology doesn’t work. In fact, in Kleene, we can’t have any tautologies: they’ll all fail this way.

In Bochvar’s internal logic, we also can’t have tautologies – for exactly the same reason.

Bochvar’s external, because of the way that the assertion operator forces things into a two-valued frame, does allow tautologies. Likewise, obviously, the combined form of Bochvar’s allows tautologies.

So – if we’re looking for a candidate for talking about vagueness, we’d like something which is normal, uniform, and contains tautologies. That eliminates everything except Lukasiewicz’s. And so we’ll use a Lukasiewicz based logic as the foundation of our fuzzy logic.

13 thoughts on “More 3-valued logic: Lukasiewicz and Bochvar”

  2. Andrew Turner

    “That eliminates everything Lukasiewicz’s.”

    I’m sure you meant to put an “except” in there.

    Reply ↓
  3. Richard D. Morey

    Given that probability theory can be thought of as a generalization of propositional logic, why do we need to reinvent the wheel with fuzzy logic and three-valued logic?

    Reply ↓
  5. Emlyn

    “That eliminates everything Lukasiewicz’s”

    I think that should be: “everything but Lukasiewicz’s”

    Reply ↓
  7. guest

    “But L_3 does have tautologies – and, in fact, they’re the same tautologies as two-valued logic!”

    I am afraid this is not true. Let us consider the formula
    “negation ( A biconditional negationA)”
    This formula is classically valid, but it is not the case in L_3 (just consider the interpretation where A has value 0.5)

    Reply ↓
  9. Chris Cogan

    I, too, was going to make the point that probability theory is, in effect, a generalization of two-valued logic to a multi-valued logic. But, I wasn’t going to suggest, as Richard Morey does, that we don’t need three-valued or “fuzzy” logics. One reason we still need these is that not all of them are equivalent to all or part of probability theory. Part of what Mark is pointing out is that not all three-valued logics are the same. The two Bochvar systems Mark discusses are not even equivalent to each other, and one of them does not even allow tautologies (so it’s not even a superset of ordinary two-valued logic but something else entirely). Another logic that’s not equivalent to any of the one’s Mark discusses is G. Spencer Brown’s system, which allows us to use “imaginary” values, which are fundamentally (not merely incidentally) analogous to imaginary numbers in mathematics.

    Further, the fact that we have probability theory as a generalization of two-valued logic does not mean that we no longer need three-valued (and other-valued) logics. Try using the apparatus of probability theory to write a theorem prover, or to do something like proving a Godelian incompleteness theorem, if you think probability theory is simply an extended system of logic. Probability theory includes logic as an implicit structure, but, even if you limited it to two values, 0 and 1, you’d still have a lot of work to do before you could use it in in practice for the kinds of things we use systems of logic for (much of ordinary inference, for example). And, the situation would not be hugely better if we allowed three (and only three) values (0, .5, and 1), because, again, you’d have to greatly re-work the system to and re-build it for use in cases where the corresponding system of logic can be applied directly.

    Reply ↓
  10. Yiab

    I’m confused: how is B^I_3 not uniform?
    Every operator in B^I_3, when any input is N, gives a result of N . This seems to me to be the definition of uniformity, unless the term “truth value” refers only to those truth values also present in 2-valued logic.

    Reply ↓
  12. PBL

    Penelope Maddy arrives at the Lukasiewicz and Kleene connectives as the most appropriate way of construing the logic of the world for her “Second Philosopher” (p229, Second Philosophy, Oxford U.P., 2007). Maddy’s Second Philosopher is trying to make the very best sense of the world that she can, and deriving methods to do so.

    This is an ambitious – and traditional – project. It is “Second Philosophy” in contrast with Descartes’ “First Philosophy”, which may be said to founder on its radical scepticism (which the Second Philosopher does not find rational, but, rather, extreme). The book is superb, narrated in Maddy’s usual fluid style, which enables her to guide the reader through a series of deep insights with a facility akin to Tamino and Pamina in the trial-caverns at the end of the Magic Flute.

    I came to it because I have been concerned for a while with deriving a metaphysics and accompanying formalism sufficient for construing the “outside world” in order to describe the intended function of engineering artifacts (an “ideal requirements language/logic” if one will). I asked Professor Maddy, without knowing that she had already thoroughly dealt with the question, if not in those terms. I think her answer is brilliant.

    Reply ↓

Leave a Reply