{"id":994,"date":"2010-08-24T20:20:15","date_gmt":"2010-08-25T00:20:15","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=994"},"modified":"2010-08-24T20:20:15","modified_gmt":"2010-08-25T00:20:15","slug":"introducing-three-valued-logic","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2010\/08\/24\/introducing-three-valued-logic\/","title":{"rendered":"Introducing Three-Valued Logic"},"content":{"rendered":"

So, finally, I’m getting around to three-valued logic!<\/p>\n

To start, why are we even looking at three-valued logic? We want to get to fuzzy reasoning, and three valued logic really doesn’t do the job. But it’s a useful starting point, because in general, most of us have only worked with standard logics where statements are either true or false. In Fuzzy logic, we’re don’t have that – and that can lead to a lot of complexity. So looking at something simple that shows us how something either than “true” or “false” can actually make sense in logic.<\/p>\n

<\/p>\n

The idea of three-valued logic is, quite simply, to add an alternative to true or false: neither. We usually abbreviate the truth values to T, F, and N. What does N mean? It depends on exactly which<\/em> three-valued logic you choose. And already, we can start to see where some of the complexity is going to come from.<\/p>\n

In traditional propositional or predicate logic, we can take statements, and assign them a truth value: either they’re true, or they’re false. Once we know whether they’re true or false, we can use that knowledge to infer whether other statements are true or false. In general, in classical logic, the inference rules seem obvious. If you know that A is true, then you know A lor B is true. It doesn’t matter what B is; if B is false, then A lor B is true; if B is true, then A lor B is true. No matter what, if you know that A is true, then A lor B must<\/em> be true.<\/p>\n

In a three valued logic, that isn’t necessarily the case. It all depends on what N means. For example, you can define a three-valued logic where N means “I don’t know”. In that case, you’d have inference rules like Gamma :- A={bf T} Rightarrow Gamma :- (A lor B)={bf T} – meaning that if I know that A is true, then I can infer that A lor B is also true. If N means “I don’t know”, then A lor N is still true.<\/p>\n

But N doesn’t have to mean “I don’t know”. It could mean “maybe”. It could mean “neither” (in the sense of vagueness; Ann isn’t really tall, but she isn’t really not tall<\/em> either). Or it could mean “nonsense”, as in an invalid statement that can’t be assigned a truth value. If it means “nonsense”, then (A lor {bf N}) = {bf N} – that is, A or meaningless nonsense is meaningless nonsense.<\/p>\n

So there are many three-valued logics, depending on exactly what you want N to mean, and how you want it to behave. Let’s look at one particular three-valued logic, just to see how it works. We’ll start with Kleene’s strong three valued logic – generally written K^S_3. K^S_3 is a three valued logic where N means “unknown” or “uncertain”. The basic logical operators in K^S_3 behave according to the truth table below:<\/p>\n

begin{array}{|c|c|c|c|c|} hline{bf A} \\ hlineT & T & T & T & F\\ hlineT & N & T & N & F\\ hlineT & F & T & F & F \\ hlineN & T & T & N & N \\ hlineN & N & N & N & N \\ hlineN & F & N & F & N \\ hlineF & T & T & F & T \\ hlineF & N & N & F & T \\ hlineF & F & F & F & T \\ hlineend{array}<\/center><\/p>\n

So N behaves pretty much as you’d expect unknown to behave. If you know something is true, then true or unknown is true, because the unknown could be true or it could be false – and in either case, it makes sense that the result of a logical or should result in true.<\/p>\n

Setting things up this way has some interesting effects. In K^S_3, there are no tautologies. (A tautology is a statement that is always true.) Take a look at one of the classic ones: A lor lnot A. If A is true, then it’s true. If A is false, then it’s true. But if $A$ is N, then it’s N. Similarly, there are no contradictions: A land not A isn’t false when A is N.<\/p>\n

So just by adding this simple N value, some of the most basic things that we’ve come to expect from logical reasoning, some of our most basic logical intuitions no longer work<\/em>. We’re going to have to get used to that as we get fuzzier.<\/p>\n

So there are some unexpected things in our three-valued logic. But some things continue to work as we expect. One of the nice properties of K^S_3 is that its connectives are normal<\/em> – which just means that if we limit ourselves to true and false, they’ll behave the same way as they do in two-valued logic.<\/p>\n

But normality doesn’t give us as much as it might seem. We can take some pretty innocuous looking proofs from two-valued logic, and they’ll fall apart in K^S_3, even though they’re built on normal connectives.<\/p>\n

Consider one simple argument from propositional argument. Suppose that we know lnot (A leftrightarrow B). In two-valued propositional logic, from that, we can infer that for any proposition P, either P leftrightarrow A, or P leftrightarrow B. That’s not true in K^S_3: suppose that A is N, and B is T. P could then be F.<\/p>\n

This is, obviously, just a quick taste. But K^S_3 is pretty simple – you can figure out most of its properties just from this little bit here. But there are several other ways of defining three-valued logics. In the next post, we’ll take a quick look at two others: L_3, which is similar to K^S_3 but modifies the definition of implication so that N leftrightarrow N is true; and B_3, which is built on the idea that N means something like undefined<\/em>. B_3 also builds up some more interesting structure around the three-valued logic.<\/p>\n","protected":false},"excerpt":{"rendered":"

So, finally, I’m getting around to three-valued logic! To start, why are we even looking at three-valued logic? We want to get to fuzzy reasoning, and three valued logic really doesn’t do the job. But it’s a useful starting point, because in general, most of us have only worked with standard logics where statements are […]<\/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,33],"tags":[164,195],"class_list":["post-994","post","type-post","status-publish","format-standard","hentry","category-fuzzy-logic","category-logic","tag-fuzziness","tag-logic-4"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-g2","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/994","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=994"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/994\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=994"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=994"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=994"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}