Fuzzy knowledge and fuzzy logic connectives

Tweet

2017.02.21

Interesting things are going on in the world of many-valued logic as recent approaches to combine first-order logic rules with deep learning tend to involve fuzzying the logic predicates. Whereas fuzzy logic is fairly simple to understand intuitively, it has more connectives, or to be exact, alternative ways to define them.

In this post I'll explain a bit why fuzzy logic is interesting in the context of knowledge representation. Then, I'll introduce various fuzzy logic connectives and explain how they're connected. Fuzzy logic connectives are based on triangular norms (T-norms), and the more formal treatments of the subject tend to care only about conjunction (for good reason, we'll see why). Here, my goal is to be very explicit and get derive the formulas to compute the truth values. The maths are really simple, but hopefully the discussion will still be interesting.

From expert systems to scientific knowledge

Fuzzy logic is a radical departure from normal logic. Everything you've done in mathematics, computer science, and even probability theory, was bivalent. True or false, and nothing else. Sure, you can say the probability to pick a queen from a deck of cards is 1/13, but in the end, you'll either have a queen or not. Again: true or false. Fuzzy logic breaks the mold, considering truth be be a gradient from 0 (false) to 1 (true). There are various many-valued ("fuzzy") logics, but here we'll always consider the truth values to be real numbers in the [0, 1] closed range. An important thing to remember is that fuzzy logic is a strict superset of bivalent logic, it's more general, and thus the connectives should behave exactly like bivalent logic connectives when the truth values are restricted to 0s and 1s.

There's a long tradition in A.I. of building expert systems, arguably the most famous being MYCIN, which was used for infections, but what if we wanted a system flexible enough to include complex scientific theories. Turns out that's tricky. We've made a lot of progress on this front, with frameworks like Markov logic allowing first-order logic rules to be associated with a weight, which in turn allows probabilistic queries. Yet you're still limited to true/false values for predicates. Take for example this seemingly simple idea: when a population is small and has plenty of preys (or is an autotroph, in which case it has no preys), it will experience exponential growth. With \(s\) for a species, \(l\) for a location, and \(t\) for time, we could express the rule in predicate logic as:

\[SmallPop(s, l) \land (HasPreys(s, l) \lor Autotroph(s)) \Rightarrow N(s, l, t + 1) = R(s) \times N(s, l, t).\]

Where \(SmallPop\) establishes whether the population is small, \(HasPreys\) whether it has preys, \(Autotroph\) whether it needs preys, and the right-side of the implication is the traditional formula for exponential growth in discrete time (\(R\) is the rate of growth).

Even a probability of being true is just not enough, because we never expect this rule to be exactly true. If you predict 102 rabbits and get 101, it's "false". Furthermore, predicates like \(SmallPop\) and \(HasPreys\) are better represented with nuances. With fuzzy logic, we could give a truth value for \(SmallPop\) based on the current population size compared to a normal-sized population, we could also quantify \(HasPreys\) on the population densities of the preys, and perhaps more importantly, we could have an \(ExponentialGrowth\) predicate and establish its truth value by comparing the predicted population size to the real population size. In this framework, predicting 102 rabbits when there are 101 would yield a truth value of 0.99 instead of 0. Note that it's still possible to assign weights to fuzzy rules, in fact, it's exactly what probabilistic soft logic is about.

But enough exposition, let's explore how the connectives work.

Normal logic is fuzzy logic with boring values

With False = 0 and True = 1, you get the following connectives and truth tables for standard logic:

Connective Informal name Symbol 1 x 11 x 00 x 10 x 0
Conjunction and \(\land\) 1000
Disjunction or \(\lor\) 1110
Implication implies \(\Rightarrow\) 1011
Equivalence iff \(\leftrightarrow\) 1001
Exclusive disjunction xor \(\veebar\) 0110

Plus, we have one unary connective, negation, represented by \(\neg\). In practice all the connectives can be defined with only negation and conjunction:

\[x \land y.\] \[x \lor y = \neg(\neg x \land \neg y).\] \[x \Rightarrow y = \neg x \lor y = \neg (x \land \neg y).\] \[x \leftrightarrow y = (x \Rightarrow y) \land (y \Rightarrow x) = \neg (x \land \neg y) \land \neg (y \land \neg x).\] \[x \veebar y = \neg (x \leftrightarrow y) = \neg (\neg (x \land \neg y) \land \neg (y \land \neg x)).\]

The definition of disjunction using only negation and conjunction leads us to the famous De Morgan laws:

\[\neg(x \land y) = \neg x \lor \neg y\] \[\neg(x \lor y) = \neg x \land \neg y\]

We won't talk about qualifiers (forall \(\forall\) and exists \(\exists\)), let's just say that, even in this case, for a formula \(x\), the qualified formula \(\exists x\) could be written \(\neg \forall \neg x\). I say this because, while we explore all the connectives here, formal texts will often define the smallest possible set of symbols. The larger set of connectives and qualifiers are mostly there for us, to make things easier to read and understand. Typical pandering to humans :P. As a quick side note, there's intriguing work being done on soft qualifiers for fuzzy logic. But back to the connectives...

A first bite of fuzzy connectives

With False = 0 and True = 1, and given that we expect the fuzzy connectives to behave the same as bivalent connectives, we can have:

\[\neg x = 1 - x.\] \[x \land y = min(x, y).\] \[x \lor y = max(x, y).\]

So \(\neg 1 = 0\), \(1 \land 0 = 0\), \(0 \land 1 = 1\), you can check, these connectives behave like normal bivalent connectives when they need to but they're also defined for other values: with \(x = 0.1\) and \(y = 0.7\) we get \(x \land y = 0.1\) and \(x \lor y = 0.7\). Let's try to see if our definition of disjunction using only conjunction and negation works too:

\[x \lor y = \neg(\neg x \land \neg y).\] \[x \lor y = \neg min(\neg x, \neg y).\] \[x \lor y = 1 - min(1 - x, 1 - y).\]

Turns out, \(max(x, y)\) is indeed the same as \(1 - min(1 - x, 1 - y)\). To see why it's helpful to use a more geometric formula for the minimum and maximum:

\[max(a, b) = \frac{a + b + |a - b|}{2}.\] \[min(a, b) = \frac{a + b - |a - b|}{2}.\]

The intuition behind the formulas above is that the maximum is the mid-point \((a + b)/2\) plus half the distance between \(a\) and \(b\) (i.e.: \(|a - b|\)), while the minimum is the mid-point minus half the distance. Back to our definition of disjunction:

\[max(x, y) = 1 - min(1 - x, 1 - y),\] \[max(x, y) = 1 - 0.5(1 - x + 1 - y - |1 - x - 1 + y|),\] \[max(x, y) = 0.5(x + y + |y - x|).\]

...and that's our definition of maximum (remember that \(|a| = |-a|\).

Alright! We have our simple, happy definitions for conjunction and disjunction with continuous values. These definition are awesome: they are both simpler and more general than the truth tables we normally get for logic connectives... but there's a catch: there are other ways to define the fuzzy connectives. For example

\[x \land y = max(0, x + y - 1).\] \[x \lor y = min(1, x + y).\]

Our first definitions for fuzzy connectives were based on the Gödel T-norm, while these are based on the Lukasiewicz T-norm. Again, is our definition of disjunction from conjunction valid?

\[x \lor y = \neg(\neg x \land \neg y),\] \[min(1, x + y) = \neg max(0, \neg x + \neg y - 1),\] \[min(1, x + y) = 1 - max(0, 1 - x + 1 - y - 1),\] \[min(1, x + y) = 1 - max(0, 1 - x - y),\] \[0.5(1 + x + y - |1 - x - y|) = 1 - 0.5(0 + (1 - x - y) + |0 - (1 - x - y)|),\] \[0.5(1 + x + y - |1 - x - y|) = 1 - 0.5(1 - x - y + |x + y - 1|),\] \[0.5(1 + x + y - |1 - x - y|) = 0.5(1 + x + y - |x + y - 1|),\]

Works fine! These definitions might look needlessly complicated compared to the simple \(min(x, y)\) for conjunction, but they often make more sense since they combine the truth values instead of just discarding one like the minimum.

Defining implication in Lukasiewicz logic is straightforward:

\[x \Rightarrow y = \neg x \lor y,\] \[x \Rightarrow y = min(1, 1 - x + y).\]

As for equivalence:

\[x \leftrightarrow y = (x \Rightarrow y) \land (y \Rightarrow x),\] \[x \leftrightarrow y = min(1, 1 - x + y) \land min(1, 1 - y + x),\] \[x \leftrightarrow y = max(0, min(1, 1 - x + y) + min(1, 1 - y + x) - 1),\] \[x \leftrightarrow y = max(0, 0.5(4 - x + y - y + x - | x - y| - |y - x|) - 1),\] \[x \leftrightarrow y = max(0, 1 - |x - y|).\]

Technically, this is the definition of equivalence, but in practice since \(x - y\) can never be greater than 1 with the truth values restricted to the [0, 1] range, we can simplify to

\[x \leftrightarrow y = 1 - |x - y|.\]

And we'll define exclusive disjunction from there:

\[x \veebar y = \neg (x \leftrightarrow y),\] \[x \veebar y = 1 - (1 - |x - y|),\] \[x \veebar y = |x - y|.\]

We have all our connectives, plus two versions of disjunction and conjunction. We'll now explore T-norm. Yes, there are more possible connectives.

Triangular norm (T-norm)

So we have two ways to define conjunction, are there others? Yes! A T-norm is a function from \([0, 1]^2 \rightarrow [0, 1]\) that satisfies the following properties given \(x, y, z, z', y' \in [0, 1]\):

  1. \(t(x, 0) = 0\).
  2. \(t(x, 1) = x\).
  3. Commutativity: \(t(x, y) = t(y, x)\).
  4. Associativity: \(t(x, t(y, z)) = t(t(x, y), z)\).
  5. Monotonicity: If \(x \leq x', y \leq y'\), then \(t(x, y) \leq t(x', y')\).

We also have the T-conorm, which has the same properties as the T-norm except the the first two properties are changed to \(t(x, 0) = x\) and \(t(x, 1) = 1\).

So what is a T-norm? Multiplication, yes, simple plain multiplication, is a valid T-norm:

\[x \land y = x \times y.\] \[x \lor y = 1 - ((1 - x) \times (1 - y)).\] \[x \lor y = y + x - xy.\]

At this point we have three ways to define conjunction: \(min(x, y)\), which is called Gödel's T-norm (or Gödel-Dummett), \(max(0, x + y - 1)\) which is Lukasiewicz' T-norm, and finally we have simple multiplication, often called the product T-norm.

In practice I mostly saw the Lukasiewicz connectives, but it's interesting to see how many variants are possible while still being consistent with standard bivalent logic.

Appendix: Connectives for the three T-norms

Equations for all connectives for the three most common T-norms used in many-valued logic.

Connective Gödel-Dummett
Conjunction \(min(x, y)\)
Disjunction \(max(x, y)\)
Implication \(max(1 - x, y)\)
Equivalence \(min(max(1 - x, y), max(1 - y, x))\)
Exclusive disjunction \(max(min(1 - x, y), min(1 - y, x))\)
Connective Łukasiewicz
Conjunction \(max(0, x + y - 1)\)
Disjunction \(min(1, x + y)\)
Implication \(min(1, 1 - x + y)\)
Equivalence \(1 - |x - y|\)
Exclusive disjunction \(|x - y|\)
Connective Product
Conjunction \(xy\)
Disjunction \(x + y - xy\)
Implication \(1 - x + xy\)
Equivalence \((1 - x + xy)(1 - y + xy)\)
Exclusive disjunction \(1 - (1 - x + xy)(1 - y + xy)\)
let world = "世界" in print $ "Hello " ++ world ++ "!"