SUO: Re: Relations And Their Divisitudes
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
RATD. Note 29
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Relational Composition as Logical Matrix Multiplication (cont.)
If the 2-adic relations G and H are viewed as logical sums,
then their relational composition G o H can be regarded as
a product of sums, a fact that can be indicated as follows:
G o H = (Sum_ij G_ij (i:j))(Sum_ij H_ij (i:j)).
G o H is itself a 2-adic relation over the same space X,
in other words, G o H c X x X, and this means that G o H
must be amenable to being written as a logical sum of the
following form:
G o H = Sum_ij (G o H)_ij (i:j).
In this formula, (G o H)_ij is the coefficient of
G o H with respect to the elementary relation i:j.
One of the best ways to reason out what G o H should be is to ask
oneself what its coefficient (G o H)_ij should be for each of the
elementary relations i:j in turn.
So let us pose the question:
(G o H)_ij = ?
In order to answer this question, it helps to realize
that the indicated product given above can be written
in the following equivalent form:
G o H = (Sum_ik G_ik (i:k))(Sum_kj H_kj (k:j)).
A moment's thought will tell us that (G o H)_ij = 1
if and only if there is an element k in X such that
G_ik = 1 and H_kj = 1.
Consequently, we have the result:
(G o H)_ij = Sum_k (G_ik H_kj).
This follows from the properties of boolean arithmetic,
specifically, the fact that the product G_ik H_kj is 1
if and only if both G_ik and H_kj are 1, and from the
fact that Sum_k F_k is 1 if and only if some F_k is 1.
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o