Undergrad What Are the Axioms of Fuzzy Logic and How Do They Extend Boolean Algebra?

[lpetrich]

TL;DR

Extensions of axioms of Boolean algebra, but what extensions are possible?

Boolean algebra, or crisp logic, involves functions of two truth values: true (T) and false (F). These functions satisfy various interrelationships: Boolean algebra (structure) - Wikipedia Some of these functions:

Negation: not ¬ -- conjunction: and ∧ -- disjunction: or ∨ -- exclusive or: xor ⊕ (exclusive disjunction, symmetric difference) -- (symbols from List of logic symbols - Wikipedia)

They satisfy several properties, which can be treated as axioms:

• Involution (self-inversion): ¬ (¬ x) = x
• Commutation, association: ∧, ∨, ⊕ -- ∧, ∨ distributive over each other
• Absorption: x ∨ (x ∧ y) = x -- x ∧ (x ∨ y) = x
• Idempotence: x ∧ x = x ∨ x = x
• Identity: ∧ T, ∨ F, ⊕ F -- Zero: ∧ F, ∨ T
• DeMorgan inversion: ¬ (x ∧ y) = (¬ x) ∨ (¬ y) -- ¬ (x ∨ y) = (¬ x) ∧ (¬ y)
• XOR Inversion: ¬ (x ⊕ y) = (¬ x) ⊕ y -- x ⊕ y = (¬ x) ⊕ (¬ y)
• Complementation: non-contradiction: x ∧ (¬ x) = F -- excluded middle: x ∨ (¬ x) = T

In fuzzy logic, we generalize the variables' domain from {T,F} to real numbers [0,1] where 0 ~ F and 1 ~ T. We attempt to carry over as much of these axioms as we can, and we introduce a new one: monotonicity: for operator "op", if x <= u and y <= v, then (x op y) <= (u op v). We make and ∧, or ∨, xor ⊕ commutative, associative, and monotonic, with the same identities and zeros as in crisp logic. For more, T-norm - Wikipedia. These functions can be expressed as changes of variables applied to other commutative, associative, and monotonic functions. For op -> op' with function f and its inverse fi:

x op' y = fi( f(x) op f(y) )

Common choices for op are addition and multiplication, themselves related with the exp and log functions.

Negation we can carry over by making it satisfy involution, making it a bijection, and if it is continuous, then it is monotonic: x < y implies (¬ x) > (¬ y). A non-monotonic discontinuous negation function that is an involution is, for argument x, (x rational: 1 - x), (x irrational: x). One with piecewise continuity is (x < 1/3 and x > 2/3: 1 - x), (1/3 <= x <= 2/3: x). It may also be carried over by imposing monotonic decrease with increasing argument, however.

With negation, we can relate conjunction (and ∧) and disjunction (or ∧) with DeMorgan inversion.

Let us consider idempotence and complementation with a continuous negation function. If negation is continuous, then there is some self-negating "middle" value m between 0 and 1 such that m = ¬ m. If ∧ and ∨ satisfy idempotence, then x ∧ (¬ x) = x ∨ (¬ x) = m, equaling neither 0 nor 1. Thus, self-negation, idempotence and complementation cannot coexist.

 

[lpetrich]

Continuing further, let us consider the consequences of fuzzy logic having the distributive property.

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) and likewise for ∧ and ∨ interchanged.

Set z = 1 (interchanged: z = 0). This reduces distributiveness to absorption:

x = (x ∧ y) ∨ x = (x ∨ y) ∧ x

Set y = 0 (interchanged: y = 1). This reduces absorption to idempotence:

x = x ∨ x = x ∧ x

So distributiveness -> absorption -> idempotence. This is equvalent to: not idempotence -> not absorption -> not distributiveness.

Let us go further with monotonicity. For y < z, x ∧ y <= x ∧ z.

Consider x <= y <= 1. Then,

x ∧ x <= x ∧ y <= x ∧ 1 (= x)

If ∧ is idempotent, then

x <= x ∧ y <= x

and we find the Gödel-Zadeh norm: x ∧ y = min(x,y) with conorm x ∨ y = max(x,y). This can be shown to satisfy distributiveness and absorption, though not complementation.

Negation is only constrained to be monotonically decreasing, however.

 

[lpetrich]

Having found exactly one conjunction-disjunction set that is distributive, let us see what one can find of complementation.

Here, however, there is more than one conjunction-disjunction set that satisfies this property. For example,

• Łukasiewicz: x ∧ y = max(x+y-1, 0) and x ∨ y = min(x+y, 1) with negation ¬ x = 1 - x.
• Drastic: x ∧ y = y if x = 1, x if y = 1, 0 otherwise. x ∨ y = y if x = 0, x if y = 0, 1 otherwise. Negation can be any that is strictly monotonic.

What else might satisfy this property?

 

[lpetrich]

Let's look at negation more closely. Most fuzzy-logic work assumes simple reflection:

¬ x = 1 - x

It is easy to show involution, self-inversion, that ¬ (¬ x) = x. But Wikipedia's pages contain bilinear reflection, with parameter p:

¬ x = (1 - x) / (1 + p*x)

It is also an involution.

In analogy with the binary operations, one can create a function f and its inverse fi that do this mapping:

{0, m, 1} - f -> {-1, 0, 1} - fi -> {0, m, 1}

where ¬ x = fi(- f(x))

For reflection, f(x) = 2x-1 and fi(x) = (1+x)/2.

 

[lpetrich]

These functions can be used to set up an exclusive-or function that satisfies the xor-inversion axioms:

fxor(x) = - fneg(x), fixor(x) = fineg(-x)

x ⊕ y = fi( f(x) * f(y) )

For plain reflection, x ⊕ y = x + y - 2*x*y

For bilinear reflection, x ⊕ y = (x + y - 2*x*y) / (1 + p*x*y)

 

[lpetrich]

As I'd mentioned earlier, (distributiveness) > (absorption) > (idempotence) > (Gödel-Zadeh minmax and-or) > (Idempotence), (absorption), (distributiveness) -- one can prove idempotence, absorption, and distributiveness from minmax. Since these implications go in both directions, that means that these properties have equivalent truth value:

(distributiveness) == (absorption) == (idempotence) == (and-or is minmax)

I was unable to track down the reference, but I earlier found an extended or super kind of absorption:

x ∧ ((¬ x) ∨ y) = x ∧ y
x ∨ ((¬ x) ∧ y) = x ∨ y

This can be verified for crisp logic, so let us see what it implies in fuzzy logic.

First one, y = 0 ... x ∧ (¬ x) = 0
Second one, y = 1 ... x ∨ (¬ x) = 1
One finds complementation.

y = x ... x = x ∧ x = x ∨ x
One also finds idempotence.

But these two properties cannot coexist in fuzzy logic, therefore, this extended absorption is not satisfied in fuzzy logic.

 

[lpetrich]

Exclusive or again. The previous versions:

• Quadratic (simple negation): x ⊕ y = x + y - 2*x*y
• Biquadratic (bilinear negation): x ⊕ y = (x + y - 2*x*y) / (1 + p*x*y)

I have discovered a piecewise linear version that satisfies the axioms with simple negation. For (condition 1) and (condition 2), it has (value).

Cond 1	Cond 2	Value
y >= x	y >= 1-x	1-x
y >= x	y <= 1-x	y
y <= x	y >= 1-x	1-y
y <= x	y <= 1-x	x

If some xor satisfies the axioms with some negation, then

0 ⊕ x = x ⊕ 0 = x
1 ⊕ x = x ⊕ 1 = ¬ x
For m = ¬ m,
m ⊕ x = x ⊕ m = m

 

[lpetrich]

This piecewise linear version is equivalent to

x ⊕ y = min( max(x,y), max(1-x,1-y) ) = max( min(x,1-y), min(y,1-x) )

and all three definitions can be extended to alternative negations, by replacing 1-x with some other ¬ x.