12,080
edits
Changes
TeX
{| align="center" cellpadding="8" width="90%"
{| align="center" cellpadding="8" width="90%"
|
| <math>\begin{matrix}X & = & \{ 1, 2, 3, 4, 5, 6, 7 \}\end{matrix}</math>
<math>\begin{matrix}
X & = & \{ 1, 2, 3, 4, 5, 6, 7 \}
\end{matrix}</math>
|}
|}
|}
|}
The composite relation ''G'' ο ''H'' is itself a dyadic 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 <math>G \circ H\!</math> is itself a dyadic relation over the same space <math>X,\!</math> in other words, <math>G \circ H \subseteq X \times X,\!</math> and this means that <math>G \circ H\!</math> must be amenable to being written as a logical sum of the following form:
{| align="center" cellpadding="8" width="90%"
| <math>G \circ H ~=~ \sum_{ij} (G \circ H)_{ij} (i\!:\!j).\!</math>
|}
In this formula, (''G'' ο ''H'')<sub>''ij''</sub> is the coefficient of ''G'' ο ''H'' with respect to the elementary relation ''i'':''j''.
In this formula, <math>(G \circ H)_{ij}\!</math> is the coefficient of <math>G \circ H\!</math> with respect to the elementary relation <math>i\!:\!j.\!</math>
One of the best ways to reason out what ''G'' ο ''H'' should be is to ask oneself what its coefficient (''G'' ο ''H'')<sub>''ij''</sub> should be for each of the elementary relations ''i'':''j'' in turn.
One of the best ways to reason out what <math>G \circ H\!</math> should be is to ask oneself what its coefficient <math>(G \circ H)_{ij}\!</math> should be for each of the elementary relations <math>i\!:\!j\!</math> in turn.
So let us pose the question:
So let us pose the question:
{| align="center" cellpadding="8" width="90%"
| <math>(G \circ H)_{ij} ~=~ ?\!</math>
|}
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:
{| align="center" cellpadding="8" width="90%"
| <math>G \circ H ~=~ (\sum_{ik} G_{ik} (i\!:\!k))(\sum_{kj} H_{kj} (k\!:\!j)).\!</math>
|}
A moment's thought will tell us that (''G'' ο ''H'')<sub>''ij''</sub> = 1 if and only if there is an element ''k'' in ''X'' such that ''G''<sub>''ik''</sub> = 1 and ''H''<sub>''kj''</sub> = 1.
A moment's thought will tell us that <math>(G \circ H)_{ij} = 1\!</math> if and only if there is an element <math>k\!</math> in <math>X\!</math> such that <math>G_{ik} = 1\!</math> and <math>H_{kj} = 1.\!</math>
Consequently, we have the result:
Consequently, we have the result:
{| align="center" cellpadding="8" width="90%"
| <math>(G \circ H)_{ij} ~=~ \sum_{k} G_{ik} H_{kj}.\!</math>
|}
This follows from the properties of boolean arithmetic, specifically, from the fact that the product ''G''<sub>''ik''</sub>''H''<sub>''kj''</sub> is 1 if and only if both ''G''<sub>''ik''</sub> and ''H''<sub>''kj''</sub> are 1, and from the fact that ∑<sub>''k''</sub> ''F''<sub>''k''</sub> is equal to 1 just in case some ''F''<sub>''k''</sub> is 1.
This follows from the properties of boolean arithmetic, specifically, from the fact that the product <math>G_{ik} H_{kj}\!</math> is <math>1\!</math> if and only if both <math>G_{ik}\!</math> and <math>H_{kj}\!</math> are <math>1\!</math> and from the fact that <math>\textstyle\sum_{k} F_{k}\!</math> is equal to <math>1\!</math> just in case some <math>F_{k}\!</math> is <math>1.\!</math>
All that remains in order to obtain a computational formula for the relational composite ''G'' ο ''H'' of the dyadic relations ''G'' and ''H'' is to collect the coefficients (''G'' ο ''H'')<sub>''ij''</sub> 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 <math>G \circ H\!</math> of the dyadic relations <math>G\!</math> and <math>H\!</math> is to collect the coefficients <math>(G \circ H)_{ij}\!</math> as <math>i\!</math> and <math>j\!</math> range over <math>X.\!</math>
{| align="center" cellpadding="8" width="90%"
|
<math>\begin{matrix}G \circ H
& = & \displaystyle \sum_{ij} (G \circ H)_{ij} (i\!:\!j)
& = & \displaystyle \sum_{ij} (\sum_{k} G_{ik} H_{kj}) (i\!:\!j).
\end{matrix}</math>
|}
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 ∑<sub>''k''</sub> (''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>) is what is usually called a "scalar product". In this case it is the scalar product of the ''i''<sup>th</sup> row of ''G'' with the ''j''<sup>th</sup> column of ''H''.
By way of disentangling this formula, one may notice that the form <math>\textstyle \sum_{k} G_{ik} H_{kj}\!</math> is what is usually called a ''scalar product''. In this case it is the scalar product of the <math>i^\text{th}\!</math> row of <math>G\!</math> with the <math>j^\text{th}\!</math> column of <math>H.\!</math>
To make this statement more concrete, let us go back to the examples of <math>G\!</math> and <math>H\!</math> we came in with:
To make this statement more concrete, let us go back to the examples of <math>G\!</math> and <math>H\!</math> we came in with:
The formula for computing <math>G \circ H\!</math> says the following:
The formula for computing <math>G \circ H\!</math> says the following:
{| cellpadding="2"
{| align="center" cellpadding="8" width="90%"
|
<math>\begin{array}{ccl}
(G \circ H)_{ij}
& = & \text{the}~ {ij}^\text{th} ~\text{entry in the matrix representation for}~ G \circ H
\\[2pt]
& = & \text{the entry in the}~ {i}^\text{th} ~\text{row and the}~ {j}^\text{th} ~\text{column of}~ G \circ H
\\[2pt]
& = & \text{the scalar product of the}~ {i}^\text{th} ~\text{row of}~ G ~\text{with the}~ {j}^\text{th} ~\text{column of}~ H
\\[2pt]
& = & \sum_{k} G_{ik} H_{kj}
\end{array}</math>
|}
|}
As it happens, it is possible to make exceedingly light work of this example, since there is only one row of ''G'' and one column of ''H'' that are not all zeroes. Taking the scalar product, in a logical way, of the fourth row of ''G'' with the fourth column of ''H'' produces the sole non-zero entry for the matrix of ''G'' ο ''H''.
As it happens, it is possible to make exceedingly light work of this example, since there is only one row of <math>G\!</math> and one column of <math>H\!</math> that are not all zeroes. Taking the scalar product, in a logical way, of the fourth row of <math>G\!</math> with the fourth column of <math>H\!</math> produces the sole non-zero entry for the matrix of <math>G \circ H.\!</math>
{| cellpadding="2px" style="text-align:center"
{| align="center" cellpadding="8" width="90%"
|
<math>G \circ H ~=~ \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 1 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\\
0 & 0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}</math>
|}
|}