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:

• Each number in a green box is between 0 and 1, and represents a fuzzy value.
• Each number in a green box is not less than the number below it, and is not less than the number to its right; this is how consolidation works.
• Each number in a blue box is the sum of the numbers below it, and each number in a red box is the sum of the numbers to its right.
• The number in the yellow box is the sum of all the numbers in green boxes.

9:1
7.81   2.28  2.06   1.76  0.92   0.63  0.16
3.350.840.75 0.730.460.410.16
2.750.710.71 0.660.450.220
1.310.530.44 0.330.0100
0.220.120.08 0.02000
0.180.080.08 0.02000

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 + yxy

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

(1, 1)(1, 2) (1, 3)(1, 4)(1, 5)
(2, 1)(2, 2) (2, 3)(2, 4)(2, 5)
(3, 1)(3, 2) (3, 3)(3, 4)(3, 5)
(4, 1)(4, 2) (4, 3)(4, 4)(4, 5)
(5, 1)(5, 2) (5, 3)(5, 4)(5, 5)

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
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 23; and each column a geometric series with ratio 34. All the series converge, with their respective sums in the blue, red, and yellow boxes.

9:3
 12 4 8⁄3 16⁄9 32⁄27 64⁄81 128⁄243 256⁄729 ⋯ 3 1 2⁄3 4⁄9 8⁄27 16⁄81 32⁄243 64⁄729 ⋯ 9⁄4 3⁄4 1⁄2 1⁄3 2⁄9 4⁄27 8⁄81 16⁄243 ⋯ 27⁄16 9⁄16 3⁄8 1⁄4 1⁄6 1⁄9 2⁄27 4⁄81 ⋯ 81⁄64 27⁄64 9⁄32 3⁄16 1⁄8 1⁄12 1⁄18 1⁄27 ⋯ 243⁄256 81⁄256 27⁄128 9⁄64 3⁄32 1⁄16 1⁄24 1⁄36 ⋯ 729⁄1024 243⁄1024 81⁄512 27⁄256 9⁄128 3⁄64 1⁄32 1⁄48 ⋯ 2187⁄4096 729⁄4096 243⁄2048 81⁄1024 27⁄512 9⁄256 3⁄128 1⁄64 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋱

Using G_AND, the size of the Durfee square necessarily (because of consolidation) comes from the main diagonal:

1 + 12 + 14 + 18 + 116 + 132 + … = 2

Using G_AND, the size of the Durfee triangle happens in this case to come from the first row:

1 + 23 + 49 + 827 + 1681 + 32243 + 64729 + … = 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.