Changes

{| cellpadding=8 style="text-align:center"

{| cellpadding=8 style="text-align:center"

|   || ''G'' || = || ∑_''ij''''G''_''ij''(''i'':''j'')

|   || ''G'' || = || ∑_''ij'' ''G''_''ij''(''i'':''j'')

|-

|-

|   || ''H'' || = || ∑_''ij''''H''_''ij''(''i'':''j'')

|   || ''H'' || = || ∑_''ij'' ''H''_''ij''(''i'':''j'')

|}

|}

If the 2-adic relations ''G'' and ''H'' are viewed as logical sums, then their relational composition ''G'' ο ''H'' can be regarded as a product of sums, a fact that can be indicated as follows:

If the 2-adic relations ''G'' and ''H'' are viewed as logical sums, then their relational composition ''G'' ο ''H'' can be regarded as a product of sums, a fact that can be indicated as follows:

: ''G'' ο ''H'' = (∑_''ij''''G''_''ij''(''i'':''j''))(∑_''ij''''H''_''ij''(''i'':''j'')).

: ''G'' ο ''H'' = (∑_''ij'' ''G''_''ij''(''i'':''j''))(∑_''ij'' ''H''_''ij''(''i'':''j'')).

The composite relation ''G'' ο ''H'' is itself a 2-adic relation over the same space ''X'', in other words, ''G'' ο ''H'' ⊆ ''X'' × ''X'', and this means that ''G'' ο ''H'' must be amenable to being written as a logical sum of the following form:

The composite relation ''G'' ο ''H'' is itself a 2-adic relation over the same space ''X'', in other words, ''G'' ο ''H'' ⊆ ''X'' × ''X'', and this means that ''G'' ο ''H'' must be amenable to being written as a logical sum of the following form:

: ''G'' ο ''H'' = ∑_''ij''(''G'' ο ''H'')_''ij''(''i'':''j'').

: ''G'' ο ''H'' = ∑_''ij'' (''G'' ο ''H'')_''ij''(''i'':''j'').

In this formula, (''G'' ο ''H'')_''ij'' is the coefficient of ''G'' ο ''H'' with respect to the elementary relation ''i'':''j''.

In this formula, (''G'' ο ''H'')_''ij'' is the coefficient of ''G'' ο ''H'' with respect to the elementary relation ''i'':''j''.

In order to answer this question, it helps to realize that the indicated product given above can be written in the following equivalent form:

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'' ο ''H'' = (∑_''ik''''G''_''ik''(''i'':''k''))(∑_''kj''''H''_''kj''(''k'':''j'')).

: ''G'' ο ''H'' = (∑_''ik'' ''G''_''ik''(''i'':''k''))(∑_''kj'' ''H''_''kj''(''k'':''j'')).

A moment's thought will tell us that (''G'' ο ''H'')_''ij'' = 1 if and only if there is an element ''k'' in ''X'' such that ''G''_''ik'' = 1 and ''H''_''kj'' = 1.

A moment's thought will tell us that (''G'' ο ''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:

Consequently, we have the result:

: (''G'' ο ''H'')_''ij'' = ∑_k''G''_''ik''''H''_''kj''.

: (''G'' ο ''H'')_''ij'' = ∑_k ''G''_''ik''''H''_''kj''.

This follows from the properties of boolean arithmetic, specifically, from 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 ∑_''k''''F''_''k'' is equal to 1 just in case some ''F''_''k'' is 1.

This follows from the properties of boolean arithmetic, specifically, from 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 ∑_''k'' ''F''_''k'' is equal to 1 just in case some ''F''_''k'' is 1.

All that remains in order to obtain a computational formula for the relational composite ''G'' ο ''H'' of the 2-adic relations ''G'' and ''H'' is to collect the coefficients (''G'' ο ''H'')_''ij'' over the appropriate basis of elementary relations ''i'':''j'', as ''i'' and ''j'' range through ''X''.

All that remains in order to obtain a computational formula for the relational composite ''G'' ο ''H'' of the 2-adic relations ''G'' and ''H'' is to collect the coefficients (''G'' ο ''H'')_''ij'' over the appropriate basis of elementary relations ''i'':''j'', as ''i'' and ''j'' range through ''X''.

: ''G'' ο ''H'' = ∑_''ij''(''G'' ο ''H'')_''ij''(''i'':''j'') = ∑_''ij''(∑_''k''''G''_''ik''''H''_''kj'')(''i'':''j'').

: ''G'' ο ''H'' = ∑_''ij'' (''G'' ο ''H'')_''ij''(''i'':''j'') = ∑_''ij''(∑_''k'' ''G''_''ik''''H''_''kj'')(''i'':''j'').

This is the logical analogue of matrix multiplication in linear algebra, the difference in the logical setting being that all of the operations performed on coefficients take place in a system of boolean arithmetic where summation corresponds to logical disjunction and multiplication corresponds to logical conjunction.

This is the logical analogue of matrix multiplication in linear algebra, the difference in the logical setting being that all of the operations performed on coefficients take place in a system of boolean arithmetic where summation corresponds to logical disjunction and multiplication corresponds to logical conjunction.

By way of disentangling this formula, one may notice that the form ∑_''k''(''G''_''ik''''H''_''kj'') is what is usually called a "scalar product".  In this case it is the scalar product of the ''i''^th row of ''G'' with the ''j''^th column of ''H''.

By way of disentangling this formula, one may notice that the form ∑_''k'' (''G''_''ik''''H''_''kj'') is what is usually called a "scalar product".  In this case it is the scalar product of the ''i''^th row of ''G'' with the ''j''^th column of ''H''.

To make this statement more concrete, let us go back to the particular examples of ''G'' and ''H'' that we came in with:

To make this statement more concrete, let us go back to the particular examples of ''G'' and ''H'' that we came in with: