Archive for the 'Fuzzy Logic' category

3-Valued Semantics

Mar 23 2011 Published by under Fuzzy Logic

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 extend the basic semantic structure. This isn't exactly one of the more exciting topics I've ever written about - but it is important, and going through it now will set the groundwork for the interesting stuff - the semantics of a true fuzzy logic.

What we've looked at so far has been propositional 3-valued logics. Propositional logics aren't particularly interesting. You can't do or say much with them. What we really care about is predicate logics. But all we need to do is take the three-valued logics we've seen, and allow statements to be predicate(object).

In a conventional first-order predicate logic, we define the semantics in terms of a model or interpretation of the logic. (Technically, a logic and an interpretation aren't quite the same thing, but for our purposes here, we don't need to get into the difference.)

An interpretation basically takes a domain consisting of a set of objects or values, and does two things:

  1. For each atomic symbol in the logic, it assigns an object from the domain. That value is called the interpretation of the symbol.
  2. For each predicate in the logic, it assigns a set, called the extension of the predicate. The extension contains the tuples for which the predicate is true.

For example, we could use logic to talk about Scientopia. The domain would be the set of bloggers, and the set of blogs. Then we could have predicates like "Writes", which takes two parameters - A, and B - and which is true is A is the author of the blog B.

Then the extension of "Writes" would be a set of pairs: { (MarkCC, Good Math/Bad Math), (Scicurious, Neurotic Physiology), ... }.

We can also define the counterextension, which is the set of pairs for whiche the predicate is not true. So the counterextension of "writes" would contain values like { (MarkCC, Neurotic Physiology), ...}.

Given a domain of objects, and the extension of each predicate, we know the meaning of statements in the logic. We know what objects we're reasoning about, and we know the truth or falsehood of every statement. Importantly, we don't need to know the counterextension of a predicate: if we know the extension, then the counterextension is simple the complement of the extension.

In three-valued Lukasiewicz logic, that's not true, for reasons that should be obvious: if \(I(A)\) is the interpretation of the predicate \(A\), then the complement of \(I(A)\) is not the same thing as \(I(lnot A)\). \(L_3\) requires three sets for a predicate: the extension, the counterextension, and the fringe. The fringe of a predicate \(P\) is the set of values \(x\) for which \(P(x)\) is \(N\).

To be more precise, an interpretation \(I\) for first order \(L_3\) consists of:

  1. A set of values, \(D\), called the domain of the logic. This is the set of objects that the logic can be used to reason about.
  2. For each predicate \(P\) of arity \(n\) (that is, taking \(n\) arguments), three sets \(ext(P)\), \(cext(P)\), and \(fringe(P)\), such that:
    • the values of the members of all three sets are members of \(D^n\).
    • the sets are mutually exclusive - that is, there is no value that is in more than one of the sets.
    • the sets are exhaustive: \(ext(P) cup cext(P) cup fringe(P) = D^n\).
  3. For each constant symbol \(a\) in the logic, an assignment of \(a\) to some member of \(D\): \(I(a) in D\)

With the interpretation, we can look at statements in the logic, and determine their truth or falsehood. But when we go through a proof, we'll often have statements that don't operate on specific values - they use variables inside of them. In order to make a statement have a truth value, all of the variables in that statement have to be bound by a quantifier, or assigned to a specific value by a variable assignment. So given a statement, we can frequently only talk about its meaning in terms of variable assignments for it.

So, for example, consider a simple statement: P(x,y,z). In the interpretation I, P(x, y, z) is satisfied if \((I(x), I(y), I(z)) in ext(P)\); it's dissatisfied if \((I(x), I(y), I(z)) in cext(P)\). Otherwise, \((I(x), I(y), I(z))\) must be in \(fringe(P)\), and then the statement is undetermined.

The basic connectives - and, or, not, implies, etc., all have defining rules like the above - they're obvious and easy to derive given the truth tables for the connectives, so I'm not going to go into detail. But it does get at least a little bit interesting when we get to quantified statements. But to talk about we need to first define a construction called a variant. Given a statement with variable assignment v, which maps all of the variables in the statement to values, an x-variant \(v'\) of \(v\) is a variable assignment where for every variable \(y\) except \(x\), \(v'(y) == v(y)\). In other words, it's an assignment where all of the variables except x have the same value as in \(v\).

Now we can finally get to the interpretation of quantified statements. Given a statement \(forall x P\), \(P\) is satisfied by a variable assignment \(v\) if \(P\) is satisfied by every x-variant of \(v\); it's dissatisfied if \(P\) is dissatisfied by at least one x-variant of \(v\). Otherwise, it's undetermined.

Similarly, an existentially quantified statement \(exists x P\) is satisfied by \(v\) if \(P\) is satisfied by at least one x-variant of \(v\); it's dissatisfied if \(P\) is dissatisfied by every x-variant of v. Otherwise, it's undetermined.

Finally, now, we can get to the most important bit: what it means for a statement to be true or false in \(L_3\). A statement \(S\) is \(T\) (true) if it is satisfied by every variable assignment on \(I\); it's \(F\) (false) if it's dissatisfied by every variable assignment on \(I\), and it's \(N\) otherwise.

9 responses so far

Fuzzy Logic vs Probability

Feb 02 2011 Published by under Fuzzy Logic

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 very closely related. As we'll see when we start looking at fuzzy logic, the basic connectives in fuzzy logic are defined in almost the same way as the corresponding operations in probability theory.

The key difference is meaning.

There are two major schools of thought in probability theory, and they each assign a very different meaning to probability. I'm going to vastly oversimplify, but the two schools are the frequentists and the Bayesians

First, there are the frequentists. To the frequentists, probability is defined by experiment. If you say that an event E has a probability of, say, 60%, what that means to the frequentists is that if you could repeat an experiment observing the occurrence or non-occurrence of E an infinite number of times, then 60% of the time, E would have occurred. That, in turn, is taken to mean that the event E has an intrinsic probability of 60%.

The other alternative are the Bayesians. To a Bayesian, the idea of an event having an intrinsic probability is ridiculous. You're interested in a specific occurrence of the event - and it will either occur, or it will not. So there's a flu going around; either I'll catch it, or I won't. Ultimately, there's no probability about it: it's either yes or no - I'll catch it or I won't. Bayesians say that probability is an assessment of our state of knowledge. To say that I have a 60% chance of catching the flu is just a way of saying that given the current state of our knowledge, I can say with 60% certainty that I will catch it.

In either case, we're ultimately talking about events, not facts. And those events will either occur, or not occur. There is nothing fuzzy about it. We can talk about the probability of my catching the flu, and depending on whether we pick a frequentist or Bayesian interpretation, that means something different - but in either case, the ultimate truth is not fuzzy.

In fuzzy logic, we're trying to capture the essential property of vagueness. If I say that a person whose height is 2.5 meters is tall, that's a true statement. If I say that another person whose height is only 2 meters is tall, that's still true - but it's not as true as it was for the person 2.5 meters tall. I'm not saying that in a repeatable experiment, the first person would be tall more often than the second. And I'm not saying that given the current state of my knowledge, it's more likely than the first person is tall than the second. I'm saying that both people possess the property tall - but in different degrees.

Fuzzy logic is using pretty much the same tools as probability theory. But it's using them to trying to capture a very different idea. Fuzzy logic is all about degrees of truth - about fuzziness and partial or relative truths. Probability theory is interested in trying to make predictions about events from a state of partial knowledge. (In frequentist terms, it's about saying that I know that if I repeated this 100 times, E would happen in 60; in Bayesian, it's precisely a statement of partial knowledge: I'm 60% certain that E will happen.) But probability theory says nothing about how to reason about things that aren't entirely true or false.

And, in the other direction: fuzzy logic isn't particularly useful for talking about partial knowledge. If you allowed second-order logic, you could have fuzzy meta-predicates that described your certainty about crisp first-order predicates. But with first order logic (which is really where we want to focus our attention), fuzzy logic isn't useful for the tasks where we use probability theory.

So probability theory doesn't capture the essential property of meaning (partial truth) which is the goal of fuzzy logic - and fuzzy logic doesn't capture the essential property of meaning (partial knowledge) which is the goal of probability theory.

30 responses so far

More 3-valued logic: Lukasiewicz and Bochvar

Jan 31 2011 Published by under Fuzzy Logic

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.

Continue Reading »

13 responses so far

Introducing Three-Valued Logic

Aug 24 2010 Published by under Fuzzy Logic, Logic

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 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.

Continue Reading »

52 responses so far

Leading in to Fuzzy Logic

Aug 05 2010 Published by under Fuzzy Logic

So, as I said in the intro to the new Scientopical Good Math/Bad Math, I'm
going to writing some articles about fuzzy logic.

Before diving into the fuzzy stuff, let's start at the beginning. What
is fuzzy logic? More fundamentally, what is logic? And what problem does fuzziness solve?

So, first, what's logic?

Logic isn't really a single thing. There are many different logics, for different purposes. But at the core, all logics have the same basic underlying concept: a logic is a symbolic reasoning system. A logic is a system for expressing statements in a form where you reason about them in a completely mechanical way, without even knowing what they mean. If you know that some collection of statements is true, using the logic, you can infer - meaning derive from a sequence of purely mechanical steps - whether or not other statements are true. If the logic is formulated properly, and you started with an initial set of true statements, then any conclusions drawn using the inference process from those statements will also be true.

When we say logic, we tend to automatically think of a particular logic: the first order predicate logic, which is the most common, fundamental logic used in both mathematics, and in rhetoric and debate. But there are an astonishing number of different logics for different purposes. Fuzzy logic is one particular
variation, which tries to provide a way of reasoning about vagueness.

Continue Reading »

94 responses so far