{"id":1286,"date":"2011-01-31T21:23:17","date_gmt":"2011-02-01T02:23:17","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=1286"},"modified":"2011-01-31T21:23:17","modified_gmt":"2011-02-01T02:23:17","slug":"more-3-valued-logic-lukasiewicz-and-bochvar","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2011\/01\/31\/more-3-valued-logic-lukasiewicz-and-bochvar\/","title":{"rendered":"More 3-valued logic: Lukasiewicz and Bochvar"},"content":{"rendered":"

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<\/em> (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.<\/p>\n

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<\/em>” 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<\/em> Jane are happy. It works nicely. It’s a rather vague<\/em> way of handling vagueness, (that is, it lets you say you’re not sure, but it doesn’t let you say how<\/em> not sure you are) but in so far as it goes, it works nicely.<\/p>\n

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<\/em> fundamental, canonical three-valued logic in the same way that, say, first order predicatelogic defines the fundamental two-valued predicate logic.<\/p>\n

It isn’t.<\/p>\n

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.<\/p>\n

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.<\/p>\n

<\/p>\n

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. <\/p>\n

The change has one big benefit. In L_3, there are real tautologies.<\/p>\n

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<\/em> 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<\/em> true. If A is N, N rightarrow N is not<\/em> true. So it’s not a tautology. In fact, every<\/em> tautology in classical logic will have that problem: it won’t be true for truth-bindings involving N.<\/p\n\n\n\n

But L_3 does<\/em> have tautologies – and, in fact, they’re the same tautologies as two-valued logic!<\/p>\n

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<\/em> 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.<\/p>\n

With N having the meaning that something is nonsense, the proper behavior of the logical connectives is quite different. Nonsense iscontagious<\/em>: 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.<\/p>\n

In terms of vagueness, this seems somewhat less useful. We can<\/em> 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<\/em> smiling? No. We don’t know enough to conclude either way. So that makes sense, in its way.<\/p>\n

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<\/em> 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.<\/p>\n

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.<\/p>\n

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<\/em>, written a. aP is the assertion operator applied to the proposition P. What the a operator means<\/em> 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.<\/p>\n

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).<\/p>\n

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.<\/p>\n

There are a couple of properties of three-valued logic that we can use to categorize the logics.<\/p>\n

The most important property is normality<\/em>. We really wouldn’t want to use a logic that’s not normal. A three-valued logic is normal<\/em> if, for any logical statement that only involves the values true and false, it will have the same<\/em> 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.<\/p>\n

Next, we’ve got uniformity<\/em>. 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<\/em>.<\/p>\n

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?<\/p>\n

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.<\/p>\n

In Bochvar’s internal logic, we also can’t have tautologies – for exactly the same reason.<\/p>\n

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.<\/p>\n

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.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 , Kleene’s strong 3-valued logic. In , we extended a standard logic so that for any statement, you can say that it’s true (T), false […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[87],"tags":[165,193],"class_list":["post-1286","post","type-post","status-publish","format-standard","hentry","category-fuzzy-logic","tag-fuzzy","tag-logic-2"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-kK","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1286","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=1286"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/1286\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=1286"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=1286"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=1286"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}