|
|
|
|
|
|
in einer Menge
 |
(1) |
je zweier Elemente von 
, notiert durch
 |
(2) |
zu einer Menge
 |
(3) |
in 
Zeichenkette 
ist in Zeichenkette 
enthalten, 
ist Nachfolgeoperand von 
Bauelement (Baugruppe) 
wird in Baugruppe 
eingebaut, Bauelementeanschluß 
ist mit Bauelementeanschluß
leitend verbunden;
Neben
der Elementnotation Gl. (2) (beschreibende Darstellung)
der Mengennotation Gl. (3) (aufzählende bzw. beschreibende Darstellung)
in 
auch durch den Relationsgraphen:
gerichteter Graph mit Knotenmenge 
und
| gerichteten Kanten | für |
 |
 |
 |
 |
 |
 |
 |
 |
die charakteristische Funktion:
eindeutige Abbildung 
mit
 |
für |
| = 1 |  |
| = 0 |  |
die Relationsmatrix:
-Matrix 
Wertetabelle von 
 |
(4) |
| klassische Matrizennotation | kartesische Notation |
 |
 |
Für das gesamte Applikationsspektrum in
Informatik, Elektrotechnik etc. sind die in Tabelle 1 zusammengestellten
speziellen binären Relationen von großer Bedeutung. Eng verbunden
damit ist natürlich die Frage der Konstruktion von formal und
rechentechnisch (insbesondere für große 
) gut handhabbaren Algorithmen zur
Identifikation, Erzeugung, Extraktion, ... solcher spezieller binärer
Relationen. Als Basis hierfür ist die charakteristische Funktion 
bzw. deren Wertetabelle,
die Relationsmatrix 
,besonders gut geeignet. Aus diesem Grunde sind bereits in
Tabelle 1 die Definitionsgleichungen in 
- und 
-Notation angegeben.
Eine binäre Relation  heißt ..., |
wenn sie die Bedingung ... erfüllt. | |
 -Notation |
 -Notation |
|
| reflexiv |   |
 |
| irreflexiv |  |
 |
| symmetrisch |  |
 |
| antisymmetrisch |   |
   |
| asymmetrisch |  |
 Daraus erhält man sofort  , d.h. eine asymmetrische binäre Relation
ist zugleich auch irreflexiv. |
| transitiv |  |
 Diese Definitionsgleichung hat die Form  Ausdruck=Konstante. Sie läßt sich
wie folgt in 
Variable=Ausdruck, überführen:
Damit ergibt sich schließlich die explizit formulierte
Definitionsgleichung |
| intransitiv |  |
  mit  
(Inhibition). Daraus folgt sofort  d.h. eine intransitive binäre Relation
ist zugleich auch irreflexiv. |
| Äquivalenzrelation | Reflexivität |  |
| Symmetrie |  |
|
| Transitivität |  |
|
| irreflexive Halbordnungsrelation |
Asymmetrie |  |
| Transitivität |  |
|
| reflexive Halbordnungsrelation |
Reflexivität |  |
| Antisymmetrie |   |
|
| Transitivität |  |
|
in 
Die in Tabelle 1 durch Hinterlegung hervorgehobenen 
-notierten
Definitionsgleichungen sollen nun in die Relationsmatrix 
Gl. (4) implantiert werden.
Dazu werden zunächst zwei einfache Matrizenoperationen eingeführt,
die die Reflexivitäts- bzw. Symmetrieeigenschaften der binären
Relation 
beschreiben:
Extraktion der Hauptdiagonalanteile von 
 |
(5) |
Extraktion des symmetrischen Anteils von 
 |
(6) |
-notierten Definitionsgleichungen.
Eine binäre Relation  heißt ..., |
wenn sie die Bedingung
... erfüllt. -Notation |
| reflexiv |  (Einheitsmatrix) |
| irreflexiv |  (Nullmatrix) |
| symmetrisch |  |
| antisymmetrisch |  |
| asymmetrisch |  |
in 
,
-Notation
 |
(7) |
in Indexschreibweise
 |
(8) |
(Bild 1) ist eine weitere Umformung von Gl. (8)
erforderlich:
 |
(9) |
(kartesische Notation)
Gl. (9) besagt: Für alle Felder 
der Relationsmatrix 
ist die Erfüllung der
Bedingungsgleichung
 |
(10) |
 |
(11) |
gewinnt dann die Form des nachstehenden Algorithmus (A1) mit
dem Arbeitsschema Bild 2:
Die Felder des Arbeitsschemas werden getaktet einmal in der angegebenen Reihenfolge (Zeile für Zeile mit Rücksprung von Zeilenende zu Anfang der nächsten Zeile) durchlaufen.
Dabei wird für jedes Arbeitsfeld 
mit 
and 
gemäß dem ,,Feldbefehl`` schlkA1
neu gebildet und sofort in das Arbeitsschema überschrieben.
.
und
it
Bild 2: Algorithmus (A1),
Arbeitsschema
Damit können nun auch die restlichen Definitionsgleichungen von Tabelle 1
in der kompakten 
-Notation angegeben werden: Tabelle 3.
Eine binäre Relation  heißt ..., |
wenn sie die Bedingung
... erfüllt. -Notation |
| transitiv | it |
| intransitiv | it |
| Äquivalenzrelation |  |
 |
|
it |
|
| irreflexive |  |
| Halbordnungsrelation | it |
| reflexive |  |
| Halbordnungsrelation | it |
| Tabelle 3: |
Spezielle binäre Relationen  in  , -Notation
|
in 
läßt sich durch Reduktion:
Abwärtsiteration der zugehörigen Relationsmatrix 
,Entfernen aller
,,transitiven Überbrückungen``
im zugehörigen Relationsgraphen
(vgl. Bild 4)
in 
, das ,,Skelett``
von 
,zuordnen, aus der durch
Rekonstruktion:
Aufwärtsiteration der Relationsmatrix 
von 
, der Skelettmatrix,
Hinzufügen aller transitiven Überbrückungen
erhalten wird (Bild 3); die Rekonstruktion ist die Umkehrung der Reduktion.
Bild 3:
Hauptsatz über transitive Relationen
| Bild 4: |
|
und 
folgende Beziehungen gelten:
 |
(12) |
 |
(13) |
 |
(14) |
 |
(15) |
als ,,Potenzreihe``
über der algebraischen Struktur 
darstellen läßt:
 |
(16) |
 | (17) |  | (18) |  | (19) |
an.
 |
(20) |
die
Lösung
 |
(21) |
in 
ist genau dann
kreisfrei, wenn gilt
 |
(22) |
mit 
gibt, so daß gilt
 |
(23) |
eine kleinste natürliche Zahl 
mit 
gibt, so daß gilt
 |
(24) |
 |
(25) |
in 
, die zugleich transitiv und
intransitiv ist.
die minimale transitive Relation, die eine gegebene binäre
Relation 
in 
enthält;
die maximale transitive Relation, die in einer gegebenen
binären Relation 
in 
enthalten ist
