Fuzzy logic and Ferrers diagrams.
Section 9. The AND and OR operations discussed beginning in section 4 on the home page need not be limited to the crisp variety, where values are either TRUE (also written 1) or FALSE (also written 0). Instead, fuzzy logic can be employed where the values are any real numbers in the range 0 to 1.
Below is a sample Ferrers diagram:
9:1
|
Had all the numbers in green boxes been 0 or 1, this diagram would have corresponded precisely to the kind of Ferrers diagrams found on the home page, where 0 = empty and 1 = star.
Among fuzzy logics, there are countless ways to define the AND and OR operations, usually relying on t-norms to produce the results. For this report, however, two examples will suffice.
A pair of operations named for Gödel are defined thus:
G_AND (x, y) = min (x, y)
G_OR (x, y) = max (x, y)
Gödel's are the most popular choices, with some authors neglecting to mention that other formulas even exist.
An alternative pair of operations is based on the probability of independent events:
P_AND (x, y) = xy
P_OR (x, y) = x + y − xy
The G_AND, P_AND and ordinary crisp AND operations are all commutative and associative. Hence an expression like G_AND (0.2, 0.7, 1.0, 0.3, 0.6) is unambiguous when decomposed into binary operations, and will equal 0.2. The various OR operations exhibit the same virtues.
Unary operations can be defined to extend the formalism:
AND (x) = G_AND (x) = P_AND (x) = x
OR (x) = G_OR (x) = P_OR (x) = x
The nullary version:
AND () = G_AND () = P_AND () = 1
OR () = G_OR () = P_OR () = 0
The best-known fuzzy NOT operation is implemented with subtraction, and does not admit of an obvious nullary counterpart:
NOT (x) = 1 − x
To go further, it helps to establish a coordinate system for the green boxes of a Ferrers diagram:
9:2
|
What eventually follows is a method to calculate the size of the Durfee square in the fuzzy case — but in order to set up a useful analogy it is best to briefly retreat by explaining the star-or-no-star case from the home page in a particular way:
| Action | Comment |
|---|---|
| Start with a sum that equals zero. | |
| If (1, 1) is empty, quit. Otherwise, add 1 to the sum. | |
| If (2, 2) is empty, quit. Otherwise, add 1 to the sum. | If (2, 2) has a star, then because of consolidation (2, 1) and (1, 2) must also contain stars. This means that there are a total of 3 stars involved. |
| If (3, 3) is empty, quit. Otherwise, add 1 to the sum. | If (3, 3) has a star, then (3, 1), (3, 2), (2, 3) and (1, 3) must also contain stars, for 5 stars total. |
| If (4, 4) is empty, quit. Otherwise, add 1 to the sum. | If (4, 4) has a star, then (4, 1), (4, 2), (4, 3), (3, 4), (2, 4), and (1, 4) must also contain stars, for 7 stars total. |
| Continue similarly until an empty cell on the main diagonal is reached. | The final value of the sum is the size of the Durfee square. |
That prompts a plan for defining a fuzzy version of the Durfee square size, using G_AND for an example:
| Start with a sum that equals zero. |
| If (1, 1) contains a 0, quit. Otherwise add the contents of (1, 1) to the sum. |
| If (2, 2) contains a 0, quit. Otherwise add G_AND ( (2, 1), (2, 2), (1, 2) ) to the sum. |
| If (3, 3) contains a 0, quit. Otherwise add G_AND ( (3, 1), (3, 2), (3, 3), (2, 3), (1, 3) ) to the sum. |
| If (4, 4) contains a 0, quit. Otherwise add G_AND ( (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (1, 4) ) to the sum. |
| Continue similarly until a cell on the main diagonal that contains a 0 is reached. The final value of the sum is the size of the Durfee square. |
In the case of the Ferrers diagram 9:1, the G_AND size of the Durfee square is figured thus:
| G_AND (0.84) + |
| G_AND (0.71, 0.71, 0.75) + |
| G_AND (0.53, 0.44, 0.33, 0.66, 0.73) |
which equals 0.84 + 0.71 + 0.33 = 1.88.
Using P_AND gives a different answer:
| P_AND (0.84) + |
| P_AND (0.71, 0.71, 0.75) + |
| P_AND (0.53, 0.44, 0.33, 0.66, 0.73) |
which equals 0.84 + 0.378075 + 0.0370774008 = 1.2521524008
There is a similar procedure for finding the size of the Durfee triangle:
| Start with a sum of 0. |
| If (1, 1) contains a 0, quit. Otherwise, add the contents of (1, 1) to the sum. |
| Find G_AND ((2, 1), (1, 2)). If 0, quit. Otherwise, add it to the sum. |
| Find G_AND ((3, 1), (2, 2), (1, 3)). If 0, quit. Otherwise, add it to the sum. |
| Find G_AND ((4, 1), (3, 2), (2, 3), (1, 4)). If 0, quit. Otherwise, add it to the sum. |
| Continue similarly until reaching a G_AND that equals 0. The final value of the sum is the size of the Durfee triangle. |
Returning to Ferrers diagram 9:1, the G_AND size of the Durfee triangle is
| G_AND (0.84) + |
| G_AND (0.71, 0.75) + |
| G_AND (0.53, 0.71, 0.73) + |
| G_AND (0.12, 0.44, 0.66, 0.46) + |
| G_AND (0.08, 0.08, 0.33, 0.45, 0.41) + |
which equals 0.71 + 0.53 + 0.12 + 0.08 = 1.44.
The P_AND size of the Durfee triangle is
| P_AND (0.84) + |
| P_AND (0.71, 0.75) + |
| P_AND (0.53, 0.71, 0.73) + |
| P_AND (0.12, 0.44, 0.66, 0.46) + |
| P_AND (0.08, 0.08, 0.33, 0.45, 0.41) + |
which equals 0.84 + 0.5325 + 0.274699 + 0.01603008 + 0.000389664 = 1.6636187440.
Unbounded Ferrers diagrams are also susceptible to fuzzy treatment. In 9:3, the green boxes of each row hold the terms of a geometric series with ratio 2⁄3; and each column a geometric series with ratio 3⁄4. All the series converge, with their respective sums in the blue, red, and yellow boxes.
9:3
|
Using G_AND, the size of the Durfee square necessarily (because of consolidation) comes from the main diagonal:
1 + 1⁄2 + 1⁄4 + 1⁄8 + 1⁄16 + 1⁄32 + … = 2
Using G_AND, the size of the Durfee triangle happens in this case to come from the first row:
1 + 2⁄3 + 4⁄9 + 8⁄27 + 16⁄81 + 32⁄243 + 64⁄729 + … = 3
Using P_AND, the size of the Durfee square is:
2−0 + 2−2 + 2−7 + 2−15 + 2−26 + 2−40 + 2−57 + … ≈ 1.247843
where the exponents are the negative second pentagon numbers.
Using P_AND, the size of the Durfee triangle is:
2−0 + 2−1 + 2−3 + 2−6 + 2−10 + 2−15 + … ≈ 1.641633
where the exponents are the negative triangle numbers.