Changes

3 bytes removed ,  18:04, 23 February 2008
Line 828: Line 828:  
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''&nbsp;&omicron;&nbsp;''H'' = &sum;<sub>''ij''</sub>''G''<sub>''ij''</sub>(''i'':''j''))(&sum;<sub>''ij''</sub>''H''<sub>''ij''</sub>(''i'':''j'')).
+
: ''G''&nbsp;&omicron;&nbsp;''H'' = (&sum;<sub>''ij''</sub>''G''<sub>''ij''</sub>(''i'':''j''))(&sum;<sub>''ij''</sub>''H''<sub>''ij''</sub>(''i'':''j'')).
    
The composite relation ''G''&nbsp;&omicron;&nbsp;''H'' is itself a 2-adic relation over the same space ''X'', in other words, ''G''&nbsp;&omicron;&nbsp;''H''&nbsp;&sube;&nbsp;''X''&nbsp;&times;&nbsp;''X'', and this means that ''G''&nbsp;&omicron;&nbsp;''H'' must be amenable to being written as a logical sum of the following form:
 
The composite relation ''G''&nbsp;&omicron;&nbsp;''H'' is itself a 2-adic relation over the same space ''X'', in other words, ''G''&nbsp;&omicron;&nbsp;''H''&nbsp;&sube;&nbsp;''X''&nbsp;&times;&nbsp;''X'', and this means that ''G''&nbsp;&omicron;&nbsp;''H'' must be amenable to being written as a logical sum of the following form:
Line 850: Line 850:  
Consequently, we have the result:
 
Consequently, we have the result:
   −
: (''G''&nbsp;&omicron;&nbsp;''H'')<sub>''ij''</sub> = &sum;<sub>k</sub>(''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>).
+
: (''G''&nbsp;&omicron;&nbsp;''H'')<sub>''ij''</sub> = &sum;<sub>k</sub>''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>.
    
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 &sum;<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 ''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 &sum;<sub>''k''</sub>''F''<sub>''k''</sub> is equal to 1 just in case some ''F''<sub>''k''</sub> is 1.
Line 856: Line 856:  
All that remains in order to obtain a computational formula for the relational composite ''G''&nbsp;&omicron;&nbsp;''H'' of the 2-adic relations ''G'' and ''H'' is to collect the coefficients (''G''&nbsp;&omicron;&nbsp;''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 ''G''&nbsp;&omicron;&nbsp;''H'' of the 2-adic relations ''G'' and ''H'' is to collect the coefficients (''G''&nbsp;&omicron;&nbsp;''H'')<sub>''ij''</sub> over the appropriate basis of elementary relations ''i'':''j'', as ''i'' and ''j'' range through ''X''.
   −
: ''G''&nbsp;&omicron;&nbsp;''H'' = &sum;<sub>''ij''</sub>(''G''&nbsp;&omicron;&nbsp;''H'')<sub>''ij''</sub>(''i'':''j'') = &sum;<sub>''ij''</sub>(&sum;<sub>''k''</sub>(''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>))(''i'':''j'').
+
: ''G''&nbsp;&omicron;&nbsp;''H'' = &sum;<sub>''ij''</sub>(''G''&nbsp;&omicron;&nbsp;''H'')<sub>''ij''</sub>(''i'':''j'') = &sum;<sub>''ij''</sub>(&sum;<sub>''k''</sub>''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>)(''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.
12,080

edits