Finally, we're at the end of our walkthrough of Gödel great incompleteness proof. As a refresher, the basic proof sketch is:</p. Take a simple logic. We've been using a variant…
The Meta of Gödel
As you may be figuring out, there's a reason why I resisted walking through Gödel's proof of incompleteness for so long. Incompeteness isn't a simple proof! To refresh your memory,…
Defining Properties Arithmetically (part 1): Gödel and Primitive Recursion
When I left off, we'd seen how to take statements written in the logic of the Principia Mathematica, and convert them into numerical form. What we need to see now…
G&oum;del Numbering: Encoding Logic as Numbers
The first step in Gödel's incompleteness proof was finding a way of taking logical statements and encoding them numerically. Looking at this today, it seems sort-of obvious. I mean, I'm…
Gödel's Incompleteness
I've mentioned Gödel's incompleteness theorems many times on this blog, but I've never actually written about them in detail. I was asking, on twitter, for topics that readers would be…
Programs As Proofs: Models and Types in the Lambda Calculus
Lambda calculus started off with the simple, untyped lambda calculus that we've been talking about so far. But one of the great open questions about lambda calculus was: was it…
Models and Why They Matter
As I said in the last post, Church came up with λ-calculus, which looks like it's a great formal model of computation. But - there was a problem. Church struggled…
3-Valued Semantics
Before we can move from three-valued logic to fuzzy logic, we need to take a look at semantics - both how conventional two-valued logic handle semantics, and how three-valued logics…
Fuzzy Logic vs Probability
In the comments on my last post, a few people asked me to explain the difference between fuzzy logic and probability theory. It's a very good question. The two are…
More 3-valued logic: Lukasiewicz and Bochvar
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.