Fuzzy Logic

[lpetrich]

Fuzzy logic is the logic of partial set membership, and it has gotten a lot of use in control systems. Here is the most accessible introduction that I've found for it: Fuzzy Logic course notes (PDF)

I'll describe a very simple example: a thermostat. It turns on a room heater if its room is too cold, and turns it off if the room is too hot. That is crisp-logic operation. If the heater can be throttled, then one can do fuzzy-logic operation, throttling it down with greater temperature. One can define two categories: "too hot" and "too cold". For instance, "too hot" can have membership 1 above 25 C, membership 0 below 15 C, and linear in between. "Too cold" can be a mirror image of that, 0 for above 25 C, 1 for below 15 C and linear in between. Both categories have membership 0.5 at 20 C.

So to decide how much to run one's heater, one does (full)*(too-cold membership) + (off)*(too-hot membership), and one has a nice linear decline from 15 C to 25 C.


But fuzzy logic has interesting mathematical properties, and I will be discussing them.

 

[lpetrich]

Crisp logic, as it may be called, is defined by these axioms.

Variable values: true (1), false (0), possibly others
Operators: not (negation), and (conjunction), or (disjunction)

Commutativity: a and b = b and a ... a or b = b or a
Associativity: (a and b) and c = a and (b and c) ... (a or b) or c = a or (b or c)
Idempotence: a and a = a ... a or a = a
Identity: a and true = a ... a or false = a
Zero (annihilation): a and false = false ... a or true = a

Distributivity: a and (b or c) = (a and b) or (a and c) ... a or (b and c) = (a or b) and (a or c)
Absorption: a and (a or b) = a ... a or (a and b) = a

Complementation: a and (not a) = false ... a or (not a) = true
Double Negation: not (not a) = a
Inversion (De Morgan): not (a and b) = (not a) or (not b) ... not (a or b) = (not a) and (not b)

Complementation is more traditionally stated as non-contradiction and excluded middle.

Operation tables:
not ... false: true ... true: false
and ... false false, false true, true false: false ... true true: true
or ... false false: false ... false true, true false, true true: true

These axioms are all true only for 2-valued logic and for powers of 2-valued logic: elements a = (a1, a2, a3, ..., an) where each of the a's is either true or false. Overall true is (all true), and overall false (all false).


So other sorts of logics will violate some of the axioms, though one usually tries to keep those violations to a minimum.

Let us consider a three-valued logic, with maybe added to true and false. Its operation tables are:

false, maybe, true
not:
true, maybe, false
and:
false, false, false
false, maybe, maybe
false, maybe, true
or:
false, maybe, true
maybe, maybe, true
true, true, true

The only axioms violated are the complementation ones, because not maybe = maybe, and
maybe and maybe = maybe, violating non-contradiction
maybe or maybe = maybe, violating excluded middle

Violations of these axioms is typical of fuzzy logic.

 

[lpetrich]

Now we go beyond "maybe" to a continuous value, from 0 (false) to 1 (true).

Let us see what happens for various values of "and" and "or".

Lotfi Zadeh proposed
and = min
or = max

This set violates the complementation axioms, but no others. The true-maybe-false logic is a subset of this logic with maybe = 1/2.

Jan Łukasiewicz proposed
a and b = max(a+b-1,0)
a or b = min(a+b,1)

This set satisfies the complementation axioms, but violates idempotence, absorption, and distributivity.

There is a multiplicative set
a and b = a*b
a or b = a + b - a*b

It violates complementation, idempotence, absorption, and distributivity, thus sharing the axiom violations of the Zadeh and Łukasiewicz versions.

Horst Hamacher proposed
a and b = (a*b)/(a + b - a*b)
a or b = (a + b - 2*a*b)/(1 - a*b)
with
0 and 0 = 0
1 or 1 = 1

It also violates these four.

I've found
a or b = (a + b)/(1 + a*b)
with (a and b) found using De Morgan inversion. It also violates those four.

 

[lpetrich]

More generally, I've found  T-norm,  Construction of t-norms: construction of fuzzy "and" operators that satisfy commutativity, associativity, identity, zero, and monotonicity. T-norm is short for "triangular norm".

Being monotonic (uniformly increasing with increasing parameter values):
For (c >= a) and (d >= b), (c and d) >= (a and b)

Commutativity and associativity lead to this construction:
(a and b) = finv(f(a) + f(b)) -- additive
or else
(a and b) = finv(f(a)*f(b)) -- multiplicative
for some function f and its inverse finv. Using De Morgan inversion: a or b = not ( (not a) and (not b) ) gives the "or" functions parallel definitions.

For the min-max "and" and "or", (a or b) has additive generator f(x) = x^p, where p -> +infinity.

For the multiplicative "and" and "or", (a and b) has multiplicative generator f(x) = x.


I've tested all the continuous ones in those Wikipedia articles on the Boolean axioms, and they all violate those four sets of axioms violated earlier: complementation, idempotence, absorption, and distributivity.

There are two non-continuous ones listed there:
Drastic: a and b = b if a = 1, a if b = 1, 0 otherwise
Nilpotent Minimum: a and b = min(a,b) if a+b>1, 0 otherwise


I've also found some super-absorption axioms:
a and ((not a) or b) = a and b
a or ((not a) and b) = a or b

These are also violated by the true-maybe-false logic and also by all the continuous-valued logics that I've discussed here.

 

[lpetrich]

Let's consider possible "and" and "or" functions that are commutative and associative, and that have identities and zeros.

First, consider a function f with commutative, associative, and identity properties. I will set its identity to 0 for convenience.

By the first two properties,
f(f(x,y),z) = f(x,f(y,z)) = f(x,f(z,y))

Take d/dy:
f₍₂₎(x,y) * f₍₁₎(f(x,y),z) = f₍₂₎(z,y) * f₍₂₎(x,f(z,y))

Set y = 0:
f₍₂₎(x,0) * f₍₁₎(x,z) = f₍₂₎(z,0) * f₍₂₎(x,z)

Let X = integral of 1/f₍₂₎(x,0) over x and Z for z. With these results, change variables from x to X and z to Z. This gives us
f₍₁₎(X,Z) = f₍₂₎(X,Z)

Change variables in f to give f(X+Z,X-Z). Then
f₍₁₎ + f₍₂₎ = f₍₁₎ - f₍₂₎

This means that f is only a function of X + Z. Setting X = h(x) for some function h, we get
f(x,y) = f(h(x) + h)

We can set h(0) = 0 without loss of generality, and we get
f(x,y) = hinv(h(x) + h)
where hinv is the inverse function for h. Now consider a zero of the function, 1: f(x,1) = 1. Then,
1 = hinv(h(x) + h(1))
giving us
h(1) = h(x) + h(1)

This means that h(1) must be infinite.

So, (a and b) = hainv(ha(a) + ha(b)) and (a or b) = hoinv(ho(a) + ho(b))
where ha(a) = ho(1-a) and vice versa.

 

[lpetrich]

Let's consider how various Boolean axioms / identities work out. I will assume that ha(a) is finite for a > 0 and that ho(a) is finite for a < 1.

Idempotence ... a and a = a ... a or a = a
For h = ha or ho, 2h(a) = h(a)
For finite h, not possible.

Complementation ... a and (not a) = 0 ... a or (not a) = 1
ha(a) + ha(1-a) = ha(0)
ho(a) + ho(1-a) = ho(1)
The left side is finite and the right side is infinite. Not possible.

Absorption ... a and (a or b) = a ... a or (a and b) = a
ha(a) + ha(a or b) = ha(a) .... ho(a) + ho(a and b) = ho(a)
a or b = 1 ... a and b = 0
ha(a) + ha(b) is infinite ... ho(a) + ho(b) is infinite
For a and b between 0 and 1, not possible.

Super absorption ... a and ((not a) or b) = a and b ... a or ((not a) and b) = a or b
ha(a) + ha((not a) or b) = ha(a) + ha(b) ... ho(a) + ho((not a) and b) = ho(a) + ho(b)
(not a) or b = b ... (not a) and b = b
ho(not a) = 0 ... ha(not a) = 0
a = 1 ... a = 0
Not possible.

I'm stumped on distributivity.


The Zadeh and Lukasiewicz definitions of "and" and "or" both violate the finiteness condition for functions ha and ho. Thus, these arguments do not apply to them.

 

[lpetrich]

 Fuzzy set operations has some interesting details. Here are the axioms that it lists:

Fuzzy complement, negation: "not"

1. Boundary condition: not 0 = 1, not 1 = 0
2. Monotonicity: if a < b, then (not a) > (not b)
3. Continuity
4. Being an involution: done twice gives the original value: not (not a) = a

Fuzzy intersection, conjunction (t-norm): "and"

1. Boundary condition: a and 1 = a
2. Monotonicity: if a <= b, then (a and c) <= (b and c)
3. Commutativity
4. Associativity
5. Continuity
6. Sub-idempotency: (a and a) <= a
7. Strict monotonicity: if a1 <= a2 and b1 <= b2, then (a1 and b1) <= (a2 and b2)

Fuzzy union, disjunction (t-conorm): "or"

1. Boundary condition: a or 0 = a
2. Monotonicity: if a <= b, then (a or c) <= (b or c)
3. Commutativity
4. Associativity
5. Continuity
6. Super-idempotency: (a or a) >= a
7. Strict monotonicity: if a1 <= a2 and b1 <= b2, then (a1 or b1) <= (a2 or b2)

It's t-norm and t-conorm, because "and" and "or" are related by DeMorgan's laws: a or b = not( (not a) and (not b) ) and vice versa.


That article states that the only forms of fuzzy "and" and "or" that are idempotent are the Zadeh minmax forms:
a and b = min(a,b)
a or b = max(a,b)

Likewise, the only ones that satisfy complementation -- non-contradiction and excluded middle -- are the Lukasiewicz clamped-sum forms:
a and b = max(a+b-1,0)
a or b = min(a+b,1)

 

[lpetrich]

I've found Theory of T-Norms and fuzzy inference methods by M.M. Gupta and J. Qi

It has a table of what properties are satisfied by different sets of fuzzy operators (Table 2 in it). The fuzzy operators are "T-norms", and they satisfy the commutative, associative, identity, zero, double-negative, and De-Morgan properties.

The Goedel-Zadeh minmax one is the one with and = min, or = max, and it is the only one with distributivity, absorption, and idempotence. Some of the other ones satisfy non-contradiction/excluded-middle, though none of the three that the minmax one satisfies.

Complementation = non-contradiction and excluded middle

Double-negative property = involution

All of them use the standard "not" operator: not a = 1 - a

Goedel-Zadeh minmax:
a and b = min(a,b)
a or b = max(a,b)
(Distributive, absorption, idempotence)

Multiplicative:
a and b = a*b
a or b = a + b - a*b
Generator (additive) gadd(a) = - log(a), (multiplicative) gmult(a) = a

Lukasiewicz:
a and b = max(a+b-1,0)
a or b = min(a+b,1)
(Non-contradiction/excluded-middle)
Generator inverse: gaddinv(a) = min(a,1)

Drastic:
a and b = b if a = 1, a if b = 1, 0 otherwise
a or b = b if a = 0, a if b = 0, 1 otherwise
(Non-contradiction/excluded-middle)

 

[steve_bank]

FYI fuzzy microcomputers exist. Thery can learn a process without quantified input and output bounds. The best articles are behind an IEEE pay wall.

http://what-when-how.com/microcontrollers/fuzzy-logic-microcontrollers/

 

[lpetrich]

Here is a big collection of T-norm functions, functions for getting the value of "and" in fuzzy-logic systems. For "or", the function is called a T-conorm.

Hamacher family (parameter p):
a and b = (x*y)/(p + (1-p)*(x+y-x*y))
a or b = (x+y -(2-p)*x*y)/(1 - (1-p)*x*y))
Generator: gadd(a) = log((p + (1-p)*x)/x)

Schweizer-Sklar family (parameter p):
a and b = ( max(0, a^p + b^p - 1) )^(1/p)
a or b = (De Morgan of above)
Generator: gadd(a) = (1 - a^p)/p

Frank family (parameter p):
a and b = log(p, 1 + (p^a - 1)*(p^b - 1)/(p - 1) )
a or b = (De Morgan of above)
Generator: gadd(a) = log( (p-1)/(p^a-1) )

Yager family (parameter p):
a and b = max(0, 1 - ( (1-a)^p + (1-b)^p )^(1/p) )
a or b = min(1, ( a^p + b^p )^(1/p) )
Generator: gadd(a) = (1 - a)^p

Aczel-Alsina family (parameter p):
a and b = exp( - ( (-log a)^p + (-log b)^p )^(1/p) ) )
a or b = (De Morgan of above)
Generator: gadd(a) = (- log a)^p

Dombi family (parameter p):
a and b = 1 / (1 + ((1-a)/a)^p + ((1-b)/b)^p )^(1/p) )
a or b = 1 / (1 + ((1-a)/a)^(-p) + ((1-b)/b)^(-p) )^(-1/p) )
Generator: gadd(a) = ((1-a)/a)^p

Sugeno-Weber family (parameter p):
a and b = max(0, (a + b - 1 + p*a*b)/(1 + p) )
a or b = min(1, (a + b + p*(a + b - a*b))/(1 + p) )
Generator: gadd(a) = 1 - log(1+p, 1+p*a)

Dubois-Prade family (parameter p):
a and b = a*b/max(a,b,p)
a or b = (De Morgan of above)

Yandong family (parameter p):
a and b = max( (1+p)*(a+b-1) - p*a*b, 0)
a or b = min( a + b + p*a*b, 1)
(Non-contradiction/excluded-middle)

Weber family with asymmetric negation (parameter p):
not a = (1 - a)/(1 + p*a) -- still a double-negative involution
a and b = max( (a + b - 1 + p*a*b)/(1 + p), 0)
(Non-contradiction/excluded-middle)
a or b = min( a + b * p*a*b, 1)

 

[lpetrich]

In Fundamentals of Fuzzy Logics (Metcalfe) (rather arcane), there is a nice proof that the minmax and-or functions are the only ones possible if the and-or functions are idempotent (operator x x = x).

Consider a <= b <= 1. By monotonicity, (a and a) <= (a and b) <= (a and 1). By monotonicity and identity,
a <= (a and b) <= a
Thus yielding
a and b = a = min(a,b)

Thus, the Goedel-Zadeh minmax and-or function.

-

Now absorption.
a and (a or b) = a

Set b = 0. Then
a and (a or 0) = a
a and a = a
(Absorption) -> (Idempotence)
or
(Not Idempotence) -> (Not Absorption)
Since a non-minmax and-or function is not idempotent, it therefore violates absorption.

We must check the remaining case, the minmax function. It has two subcases:
a <= b:
a and (a or b) = a and a = a
a >= b
a and (a or b) = a and b = a

Thus, only the minmax function has absorption.

-

Now distributivity.
a or (b and c) = (a or b) and (a or c)

Set b = c = 0. Then
a or (0 and 0) = (a or 0) and (a or 0)
a or 0 = a and a
a = a and a
(Distributivity) -> (Idempotence)
(Not Idempotence) -> (Not Distributivity)
Since a non-minmax and-or function is not idempotent, it therefore violates distributivity.

We must check the remaining case, the minmax function. It has three subcases:
a <= b <= c
a or (b and c) = (a or b) and (a or c)
a or b = b and c
b = b
.
b <= a <= c
a or (b and c) = (a or b) and (a or c)
a or b = a and c
a = a
.
b <= c <= a
a or (b and c) = (a or b) and (a or c)
a or c = a and a
a = a

Thus, only the minmax function has distributivity.

-

Let us now check non-contradiction (a and (not a) can't be true at the same time) and excluded middle (at least one of a and (not a) is true).

I'll do the half-true case: a = 1/2. That means not a = 1/2 also.
Non-contradiction: 1/2 and 1/2 = 1/2 != 0
Excluded middle: 1/2 or 1/2 = 1/2 != 1

Of the properties of crisp logic that I'd listed in my second post, these are the only ones that the minmax-and-or function lacks.

 

[lpetrich]

About the three-valued logic that I'd mentioned in my second post, it is a subset of the minmax-function logic, with maybe = 1/2.

Setting (maybe and maybe) = false and (maybe or maybe) = true gives a subset of the Lukasiewicz logic, also with maybe = 1/2. It satisfies non-contradiction and excluded middle, but breaks distributivity, absorption, and idempotence.

 

[lpetrich]

Here is a simple example of fuzzy logic for device control. Let's imagine that one has a fan in one's room that one wants to run whenever the air is hot or humid or both, but not when the air is cold and dry. We also want the fan to run faster with greater heat and humidity. So it should run like this:

	Dry	Medium	Wet
Cold	Off	Slow	Medium
Medium	Slow	Medium	Fast
Hot	Medium	Fast	Fast

"Medium", "Cold", "Hot", "Dry", "Wet", "Off", "Slow", and "Fast" are all "linguistic variables", variables that must be translated into numerical quantities.

For instance, "cold" could be less than 15 C (59 F), "hot" could be greater than 25 C (77 F), and "medium temperature" anywhere in between.

Using a crisp-logic approach, the fan would jump in speed as the temperature and the humidity change. But for many applications, one wants continuous variation. Fuzzy logic is a convenient way to specify such variation.

The first step is fuzzification. Continuing with temperature, "cold" could have membership 1 for temperatures less than 15 C, and then linearly declining to 0 at 20 C. Likewise, "hot" could have membership 1 for greater than 25 C, and then linearly declining to 0 at 20 C. Medium would rise from 0 at 15 C to 1 at 20 C then fall to 0 at 25 C. Thus, 23 C has "cold" = 0, "medium" = 0.4, and "hot" = 0.6.

One then finds the values of all the combined variables, "cold"-"dry", "cold"-"medium", etc. In this case, one uses the "and" operator, and one usually uses the Goedel-Zadeh one, the minimum.

Once one gets that table of temperature-humidity combined-variable memberships, one gets a fan speed by defuzzification. The usual method is a weighted average:

(fan speed) = (sum of (combined-variable membership) * (fan speed for that variable combination) ) / (sum of (combine-variable membership))

 

[lpetrich]

On a simpler level, when driving a car, one usually doesn't do all-or-nothing with the gas and brake pedals. One usually pushes them only part of the way in, and in variable amount. Slamming on those pedals isn't usually very good to do.

So one does a sort of fuzzy-logic control of one's car.

 

[steve_bank]

On a simpler level, when driving a car, one usually doesn't do all-or-nothing with the gas and brake pedals. One usually pushes them only part of the way in, and in variable amount. Slamming on those pedals isn't usually very good to do.

So one does a sort of fuzzy-logic control of one's car.

The human sped control example is an example of PID proportional-integral-derivative traditional feed back control. A second order system.

Proportional is a linear response to the difference, error, between the set point desired and the current state.

Integral is a running average of the error

Derivative is the rate of change of response.

A dominant integral term slows down response, a dominate derivative term speeds up response.

The instantaneous gas pedal response, amount of gas, is the linear sum of each term. Alow sytem creeps up on the set point, speed, with no overshoot. A fast system will accelerate faster with overshoot of the set point.


The best graphical image I saw of fuzzy control is a balance beam weighted with overlapping distributions achieving a balance on each side of the beam.

 

[lpetrich]

Returning to absorption, I have found a chain of distributive property -> absorption -> idempotence, using only the identities and zeros of the "and" and "or" operators.

a and (b or c) = (a and b) or (a and c)
c = 1
a = (a or b) and a
b = 0
a = a and a

a or (b and c) = (a or b) and (a or c)
c = 0
a = (a and b) or a
b = 1
a = a or a

So (dist) -> (abs) -> (idem)
leading to
(not idem) -> (not abs) -> (not dist)

 

[lpetrich]

Wikipedia has an article on  Boolean algebra, an article that lists all the properties of crisp logic that I'd mentioned earlier.

I've found some additional properties somewhere:
Super Absorption
a and ((not a) or b) = a and b
a or ((not a) and b) = a or b

First one, b = 0:
a and (not a) = 0

Second one, b = 1:
a or (not a) = 1

Thus, (super absorption) -> (complementation), meaning that (not comp) -> (not super abs).
Complementation = non-contradiction and excluded middle

Both of them with b = a:
a and ((not a) or a) = a and a
a or ((not a) and a) = a or a

With complementation,
a = a and a
a = a or a

That is, idempotence. The only idempotent fuzzy logic, the Goedel-Zadeh minimax one, violates complementation. Thus, no fuzzy logic satisfies super absorption.

BTW, one can get super absorption from the distributive property by setting one of the variables to be distributed over to "not" the distribution variable, and then using complementation:
a or (b and c) = (a or b) and (a or c)
a and (b and c) = (a and b) or (a and c)

a or (b and (not a)) = (a or b) and (a or (not a))
a and (b and (not a)) = (a and b) or (a and (not a))

 

[lpetrich]

One can define an equivalence relation for crisp logic with this truth table:

eqv:
true false
false true

It has properties
a eqv a = 1
a eqv (not a) = 0
(not a) eqv (not b) = a eqv b
a eqv b = (a and b) or ((not a) and (not b)) = (a or (not b)) and ((not a) or b)

Here is one fuzzy-logic definition:
a eqv b = 1 - |a - b|

Let us see what properties equivalence can have in fuzzy logic more generally. The first one is necessary. Everything must equal itself. The second one violates the first one, because in fuzzy logic, (not a) = a is possible. For the usual definition of negation, a = 1/2. The third one we can add in for convenience. The fourth one is more difficult.

a eqv a = 1 = (a and a) or ((not a) and (not a)) = (a or (not a)) and (a or (not a))

If we also assume monotonicity, we can prove some theorems about equal arguments to "and" and "or"

a and 0 <= a and a <= a and 1
0 <= a and a <= a

a or 0 <= a or a <= a or 1
a <= a or a <= 1

So (a or (not a) and (a or (not a)) must be <= (a or (not a)) and only equal for idempotence.
For non-idempotence, that quantity must be less than (a or (not a)), and in turn, less than 1. It is thus not possible.
For idempotence, 1 = a or (not a), only possible if excluded middle holds. Both properties together hold only for crisp logic.

So the second and fourth properties only hold for crisp logic, while the third one can be extended to fuzzy logic without contradiction.

 

[steve_bank]

Any logic function can be implemented by AND-OR or NAND-NOR. logic.

 

[lpetrich]

Any logic function can be implemented by AND-OR or NAND-NOR. logic.

Crisp logic, at least.

However, one needs a NOT function to do so. I will prove that by finding out what happens when one only has AND and OR.

Each of those two operators is both commutative and associative, so that one can easily define multiple-argument versions of them. Also, both operators are idempotent, meaning that one can collapse repetitions of an argument to a single copy of it.

They are also monotone, meaning that (x <= y) <-> (AND(x,z) <= AND(y,z)) and (OR(x,z) <= OR(y,z)). This has the consequence that every combination is monotone, and also that every combination is bounded from below by AND(all its args) and from above by OR(all its args).

Thus, every combination of AND's and OR's returns 0 for all-0 args and 1 for all-1 args. So to get 0 for all-1's and 1 for all-0's, one needs a NOT operator. That is also true for violations of monotonicity, like X(0,others) = 1 while X(1,others) = 0.


But if one has a NAND or a NOR operator, one can get a NOT out of it with NOT(x) = NAND(x,x) = NOR(x,x), using the idempotence of AND and OR. NOT with NAND gives AND, and with DeMorgan's rules, OR, and with further negation, NOR. Likewise, one can get OR, AND, and NAND from NOR.

In fact, one can get any truth table with combinations of NOT, AND, and OR.