Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

ONT Re: Relations And Their Divisitudes


o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

RATD.  Note 27

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Relational Composition as Logical Matrix Multiplication

We have it within our reach to pick up another way of representing
2-adic relations, namely, the representation as logical matrices,
and also to grasp the analogy between relational composition and
ordinary matrix multiplication as it appears in linear algebra.

First of all, while we still have the data of a very simple
concrete case in mind, let us reflect on what we did in our
last Example in order to find the composition G o H of the
2-adic relations G and H.

Here is the setup that we had before:

   X  =  Y  =  Z  =  {1, 2, 3, 4, 5, 6, 7}

   G  =  4:3 + 4:4 + 4:5  c  X x Y ~=~ X x X

   H  =  3:4 + 4:4 + 5:4  c  Y x Z ~=~ X x X

Let us recall the rule for finding the relational composition of a pair
of 2-adic relations.  Given the 2-adic relations P c X x Y, Q c Y x Z,
the "relational composition" of P and Q, in that order, is commonly
denoted as "P o Q" or more simply as "PQ" and obtained as follows:

To compute PQ, in general, where P and Q are 2-adic relations,
simply multiply out the two sums in the ordinary distributive
algebraic way, subject only to the following rule for finding
the product of two elementary relations of shapes a:b and c:d.

   (a:b)(c:d)  =  (a:d)  if b = c,

   (a:b)(c:d)  =    0    otherwise.

To find the relational composition G o H,
we write it as a quasi-algebraic product:

   G o H  =  (4:3 + 4:4 + 4:5)(3:4 + 4:4 + 5:4).

Multiplying this out in accord with the applicable form
of distributive law one obtains the following expansion:

   G o H  =  (4:3)(3:4) + (4:3)(4:4) + (4:3)(5:4) +
             (4:4)(3:4) + (4:4)(4:4) + (4:4)(5:4) +
             (4:5)(3:4) + (4:5)(4:4) + (4:5)(5:4)

Applying the rule that determines the product
of elementary relations, we obtain this array:

   G o H  =  (4:4) +   0   +   0   +
               0   + (4:4) +   0   +
               0   +   0   + (4:4)

Since the plus sign in this context represents an operation of
logical disjunction or set-theoretic aggregation, all positive
multiplicites count as one, and this gives the ultimate result:

   G o H  =  4:4

It's that simple.

Jon Awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o