Fuzzy Relations and Composition: Max-Min Concepts and a Worked Example

The definition of a fuzzy relation is short, but composition becomes error-prone when min and max are applied in the wrong order or incompatible matrices are multiplied. Two finite relations can be represented as matrices, with every output cell of one max-min composition calculated explicitly. The same relation matrices expose the max-product contrast, while a square relation provides a numerical transitivity test. If two attempts give different answers for the same composition, a fixed routine tells you whether the wrong min/max order or a dimension mismatch caused it.

Fuzzy relations replace pair membership with a grade in [0,1]

For X={x1,x2} and Y={y1,y2,y3}, the Cartesian product X × Y contains all six possible ordered pairs. A crisp relation is a subset of that product. A fuzzy relation R instead assigns every pair a grade through μ_R: X × Y → [0,1].

A grade of 0 means no relation under the chosen model, 1 means full relation, and an intermediate value means partial relation. It is not the probability that the pair exists. If crisp ordered pairs need a refresher, start with Set Theory and Relations Explained for GATE.

Lock the row and column order before calculating:

R=[[0.2,0.7,1.0],[0.6,0.4,0.8]]

Rows are [x1,x2] and columns are [y1,y2,y3]. Thus, μ_R(x1,y2)=0.7 and μ_R(x2,y1)=0.6. The six grades could be listed as labelled pairs, but the matrix keeps every grade addressable by position, which is what composition needs. The same labelled matrix layout carries across the relational topics collected under GATE CS Exam Preparation.

Reading a fuzzy-relation matrix

Using the max-projection convention, the fuzzy domain grade for each row is its maximum:

dom(R)=[max(0.2,0.7,1.0),max(0.6,0.4,0.8)]=[1.0,0.8]

The fuzzy range grade for each column is also its maximum:

ran(R)=[max(0.2,0.6),max(0.7,0.4),max(1.0,0.8)]=[0.6,0.7,1.0]

State this projection convention because some applications define other projections. The inverse swaps the positions in every ordered pair, so its matrix is the transpose:

R⁻¹=[[0.2,0.6],[0.7,0.4],[1.0,0.8]]

Its rows are [y1,y2,y3] and columns are [x1,x2]. Inverse does not replace a grade with 1-grade. That operation is complement.

At α=0.7, the ordinary cut uses ≥:

R_0.7={(x1,y2),(x1,y3),(x2,y3)}

The strong cut uses >:

R_0.7+={(x1,y3),(x2,y3)}

The boundary pair (x1,y2) belongs only to the ordinary cut.

Max-min composition: check dimensions before arithmetic

Let Z={z1,z2} and define a second relation from Y to Z:

S=[[0.9,0.3],[0.5,0.8],[0.7,0.6]]

Its rows are [y1,y2,y3] and columns are [z1,z2]. R is 2 × 3 and S is 3 × 2. The shared Y dimension matches, so the result is 2 × 2 over X × Z.

Here, T=R ∘ S means follow R from X to Y, then S from Y to Z:

μ_T(x,z)=max_(y ∈ Y) min(μ_R(x,y),μ_S(y,z))

Some texts reverse the written order, so inspect the domains and the supplied formula. The mechanical sequence is pair, min, max. For each (x,z), take the minimum along every two-edge path, then take the maximum across those paths. With grades restricted to {0,1}. Max-min relation composition extends membership grades across a shared intermediate set; the broader foundation in membership functions and fuzzy-set operations is established in Fuzzy Sets in AI: Membership Functions and Worked Examples.

Worked max-min composition, one cell at a time

Do not skip an intermediate y. The four cells are:

• t11=max(min(0.2,0.9),min(0.7,0.5),min(1.0,0.7))=max(0.2,0.5,0.7)=0.7

• t12=max(min(0.2,0.3),min(0.7,0.8),min(1.0,0.6))=max(0.2,0.7,0.6)=0.7

• t21=max(min(0.6,0.9),min(0.4,0.5),min(0.8,0.7))=max(0.6,0.4,0.7)=0.7

• t22=max(min(0.6,0.3),min(0.4,0.8),min(0.8,0.6))=max(0.3,0.4,0.6)=0.6

Therefore:

T=R ∘ S=[[0.7,0.7],[0.7,0.6]]

Rows are [x1,x2] and columns are [z1,z2]. For μ_T(x2,z2)=0.6, the strongest bottleneck path is x2→y3→z2. Its edge grades are 0.8 and 0.6, whose minimum is 0.6.

Two quick checks catch many errors. Every output grade must remain in [0,1], and each cell cannot exceed the largest relevant input grade. Do not add edge grades or treat the result as a path probability.

Max-min is not max-product or ordinary multiplication

Keep R and S fixed and change only the operator. Max-product uses u_ij=max_k(r_ik·s_kj). The complete calculation gives:

• u11=max(0.2·0.9,0.7·0.5,1.0·0.7)=max(0.18,0.35,0.70)=0.70

• u12=max(0.2·0.3,0.7·0.8,1.0·0.6)=max(0.06,0.56,0.60)=0.60

• u21=max(0.6·0.9,0.4·0.5,0.8·0.7)=max(0.54,0.20,0.56)=0.56

• u22=max(0.6·0.3,0.4·0.8,0.8·0.6)=max(0.18,0.32,0.48)=0.48

Ordinary matrix multiplication sums products. Elementwise min is not even dimensionally defined here because the matrices are 2 × 3 and 3 × 2. No fuzzy operator is universally correct for every application. Read the operator named in the question.

Properties and traps: test definitions with numbers

Reflexive, symmetric and transitive tests require a homogeneous relation on one set. On {a,b,c}, take:

Q=[[1.0,0.6,0.2],[0.6,1.0,0.7],[0.2,0.7,1.0]]

It is reflexive because each diagonal entry is 1, and symmetric because q_ij=q_ji. It is not max-min transitive. For (a,c), the route through b gives min(q_ab,q_bc)=min(0.6,0.7)=0.6. Therefore, (Q ∘ Q)_(a,c)≥0.6>q_ac=0.2, so Q ∘ Q is not pointwise ≤ Q.

Once the routine is automatic, the exam formats become predictable. A question that asks for a single missing cell is really testing whether you take the minimum along each path before the maximum across paths. Asking for the complete matrix tests that same move in every cell, while asking only for the dimensions checks that you matched the shared intermediate set. The remaining variants reuse earlier steps: an alpha-cut tests the threshold rule, an inverse tests that you transpose rather than complement, an operator comparison tests whether you read max-min against max-product, and a transitivity counterexample tests the property on a homogeneous relation.

A small fuzzy-relations practice set is useful for focused reinforcement, not as an indicator of exam weightage. For mixed timed practice across the paper, GATE Test Series is one optional route.

Fuzzy relations and composition: the short version

• A fuzzy relation maps ordered pairs to [0,1].

• A matrix must retain its row and column labels.

• Inverse is transpose.

• An ordinary alpha-cut uses ≥.

• Max-min composition takes min along each path and max across paths.

• Compatibility comes from the shared intermediate set.

For the main example, R ∘ S=[[0.7,0.7],[0.7,0.6]].

Now transfer the method. Let P=[[0.4,0.9],[0.7,0.2]] map {p1,p2} to {q1,q2}, and V=[[0.8],[0.5]] map {q1,q2} to {r1}. Find P ∘ V under max-min composition before checking the answer.

Answer: [[max(min(0.4,0.8),min(0.9,0.5))],[max(min(0.7,0.8),min(0.2,0.5))]]=[[0.5],[0.7]].

If you want the same worked, step-by-step approach across the rest of the syllabus, GATE Guidance by Sanchit Sir covers it topic by topic.