|
|
|
|
|
|
on a set
 |
(1) |
of two elements of 
, denoted
 |
(2) |
form a set
 |
(3) |
in 
a word 
is
contained in another word 
, 
succeeds 
module 
forms a part of module 
, socket 
is connected with socket 
;
Besides
the element notation eq. (2)
the set notation eq. (3) (enumerating descriptive representation)
on 
may also be represented by its relation graph:
a directed graph with nodes 
and
| directed edges | corresponding to |
 |
 |
 |
 |
 |
 |
 |
 |
a characteristic function:
a mapping 
where
 |
corresponds to |
| = 1 |  |
| = 0 |  |
a relation matrix:
matrix 
table of 
 |
(4) |
| classical matrix notation | cartesian notation |
 |
 |
In the entire application domain of computer science,
electrical engineering,... , the specific classes of binary relations listed
in table 1 are of high importance. Closely related to these classes is the
question, how such binary relations can be identified, generated,
extracted,... by algorithms in an efficient manner (notably for large 
). The characteristic
function 
and the
relation matrix 
provide a good basis for these tasks. Therefore, in table 1, all definitions
are given in 
- and
-notation.
A binary relation  is said to be ..., |
if the following conditions hold: | |
 -notation |
 -Notation |
|
| reflexive |   |
 |
| irreflexive |  |
 |
| symmetrical |  |
 |
| antisymmetrical |   |
   |
| asymmetrical |  |
 Clearly,  , i.e., an asymmetrical binary relation is
always irreflexive. |
| transitive |  |
 This equation has the form  expression=constant. It can be transformed
into 
variable=expression:
Thus, we arrive at the explicit definition |
| intransitive |  |
  where  
(inhibition).Clearly,  , i.e., an intransitive binary relation is
always irreflexive. |
| equivalence relation | reflexivity |  |
| symmetry |  |
|
| transitivity |  |
|
| irreflexive partial ordering |
asymmetry |  |
| transitivity |  |
|
| reflexive partial ordering |
reflexivity |  |
| antisymmetry |   |
|
| transitivity |  |
|
on 
The marked definitions from table 1 which are given in
-notation shall now
be applied to the relation matrix 
of eq. (4).
For this, we first introduce two matrix operations describing the reflexive and
symmetry of a binary relation 
, respectively:
extraction of the entries on the main diagonal of 
 |
(5) |
extraktion of the symmetrical component of 
 |
(6) |
-notation.
A binary relation  is said to be ..., |
if it satisfies the following conditions: (  -notation) |
| reflexive |  (identity matrix) |
| irreflexive |  (zero matrix) |
| symmetrical |  |
| antisymmetrical |  |
| asymmetrical |  |
on 
, 
-notation
 |
(7) |
- in index notation -
 |
(8) |
(fig. 1), eq. (8) has to be rearranged once more:
 |
(9) |
(cartesian notation)
According to eq. (9), the condition
 |
(10) |
 |
(11) |
of the relation matrix 
. The right hand side of equation (11) can be
computed for all entries 
of the work space (compare fig. 2) by the algorithm (A1)
given below:
The entries of the work space are traversed in the order given below (one row after the other, jumping from the end of a row to the beginning of the next).
Doing so, for each entry 
where 
and 
is formed according to the ,,entry command`` schlkA1
and inserted in the work space (overwriting the previous column).
.
und it
fig. 2: Algorithm (A1),
work space
Now, the other definitions from table 1 can be given in succinct 
-notation: table 3.
A binary relation  is said to be ..., |
if it satisifies the condition -notation |
| transitive | it |
| intransitive | it |
| equivalence relation |  |
 |
|
it |
|
| irreflexive |  |
| partial ordering | it |
| reflexive |  |
| partial ordering | it |
| table 3: | classes of binary relations  in  ,  -notation |
By reduction:
down-iteration of the corresponding relation matrix 
- elimination of all "transitive
bridges" in the corresponding relation graph (cmp. fig. 4)
on 
, exactly one reflexive
/irreflexive symmetrical/antisymmetrical binary relation 
on 
can be obtained, which constitutes a
"backbone" of 
. By
reconstruction:
up-iteration of the relation matrix 
of 
- the "backbone matrix"
Addition of all transitive bridges
(fig. 3); thus reconstruction is the reversal of reduction.
fig. 3:
main theorem about transitive relations
| fig. 4: |
example to the main theorem about transitive relations
transitive closure
|
and 
satisfy the following conditions:
 |
(12) |
 |
(13) |
 |
(14) |
 |
(15) |
can be
represented as a power series on the algebraic structure 
:
 |
(16) |
 | (17) |  | (18) |  | (19) |
.
 |
(20) |
has the form
 |
(21) |
on 
is cycle-free if and
only if
 |
(22) |
with 
such that
 |
(23) |
there is a smallest natural number 
with 
such that
 |
(24) |
 |
(25) |
on 
which is both transitive and intransitive.
the minimal transitive relation containing a given binary relation
on 
;
the maxiaml transitive relation conatained in a given binary relation
on 
.
