Beziehungen. Teil I.

Die formale Modellierungstheorie verwendet algebraische Beziehungen, einschließlich dieser in den Signaturen von Modellen algebraischer Strukturen, die reale physikalische, technische und informative Objekte beschreiben, die Prozesse ihrer Funktionsweise. Zu letzteren gehören beispielsweise Datenbanken (relationale Datenbanken (RDBs)). Ich halte den Bereich der Entscheidungsfindung für nicht weniger wichtig, der aus zwei statistischen und algebraischen Hauptbereichen besteht, die ausschließlich auf der Theorie der Beziehungen beruhen. Das Bildungsniveau der Spezialisten für diese Theorie liegt nahe bei Null.



Öffnen Sie das Lehrbuch über Spezialisierung und dort sehen Sie bestenfalls Äquivalenzen, die von den Autoren auf sehr eigenartige Weise interpretiert werden. Ich frage einen bereits verteidigten DTN: Betrachten Sie das Äquivalenzverhältnis, indem Sie weder den Träger der Beziehung noch eine bestimmte Beziehung angeben, wie es in Ihrer Akte aussieht? Antwort: Wie es aussieht - normalerweise. Es stellt sich heraus, dass er eine sehr vage Vorstellung von all dem hat.



Ich finde es schwierig, Veröffentlichungen zum Design einer ReDB zu benennen, außer für ausländische Artikel. In den 90er Jahren war er ein Gegner, schrieb eine Rezension einer These, die hierarchische, vernetzte und relationale Datenbanken berücksichtigte. Aber einmal im Jahr, vor anderthalb Jahren, kam die Arbeit wieder zur Überprüfung, der Autor schreibt bereits nur über die DB, über die Normalisierung der DB-Beziehungen, zeigte aber keine theoretische Neuheit. Viele Universitäten unterrichten einen Kurs über Datenbanken, aber nicht darüber, wie man sie erstellt, ein DBMS erstellt, sondern in der Regel darüber, wie man eine vorgefertigte (ausländische) Datenbank betreibt.



Rev. Das Personal ist nicht bereit, IT-Spezialisten das Erstellen von DBMS, Betriebssystemen und Programmiersprachen im Inland beizubringen, ganz zu schweigen von LSI, VLSI und benutzerdefiniertem LSI. Hier fuhr der Zug offenbar lange und lange ab. Vergebens sind einige Wangen vor Stolz aufgeblasen (lesen Sie Snobismus). Dies geht aus den Kommentaren zu den Veröffentlichungen anderer Leute hervor. Zeigen Sie sich selbst, dass Sie es können, und lassen Sie sich nicht um des Stolzes willen auf nutzlose Übersetzungen und Umschreibungen anderer ein - "Bewertung" und "Karma". Beeinträchtigt nicht nur den Mangel an Kreativität, sondern auch die einfache Bildung und Erziehung.



Die zweite Domäne, die untrennbar mit Beziehungen verbunden ist, ist die Entscheidungsfindung. Jeder von uns ist ständig damit beschäftigt. Wir werden keinen Finger rühren ohne eine Entscheidung des Bewussten oder Unbewussten. Nur wenige verstehen und noch weniger schreiben über Lösungen. Die Entscheidung eines Entscheidungsträgers (Entscheidungsträgers) basiert auf der Präferenz für Alternativen. Und das Präferenzmodell ist genau diese Art von Beziehung, die als "Raum der Präferenzbeziehungen" bezeichnet wird. Aber wer studiert sie? Als ich zu einem „Spezialisten“ für Beziehungen mit einer Frage nach der Anzahl der Beziehungen jedes Typs kam, „tötete“ er, ohne die Antwort zu kennen, mit einer Gegenfrage, warum brauchen Sie sie?

Beziehungskonzept

Ich denke, dass der Begriff Haltung jedem Leser vertraut ist, aber nach einer Definition zu fragen, wird die meisten verwirren. Dafür gibt es viele Gründe. Sie sind am häufigsten bei Lehrern anzutreffen, die, wenn sie im Unterricht Beziehungen verwendeten, sich nicht auf diesen Begriff konzentrierten und anscheinend keine denkwürdigen Beispiele anführten.



In meiner Erinnerung gibt es einige denkwürdige Beispiele für ein Leben lang. Über Mappings und über Beziehungen. Ich werde zuerst über Zuordnungen sprechen. Es gibt zwei Farbeimer. In einem Weiß, in dem anderen - Schwarz. Und es gibt eine Schachtel Würfel (viel). Die Gesichter haben geprägte Zahlen. Auf wie viele Arten können Sie die Gesichter der Würfel in zwei Farben färben? Die Antwort ist unerwartet - bis zu 6-Bit-Binärzahlen oder 2 ⁶= 64. Lassen Sie mich näher erläutern f: 2 → 6 2 Objekte werden in 6 angezeigt. Jede Zeile der Tabelle ist eine diskrete Anzeige von fi.



Erstellen wir eine Tabelle mit 6 Spalten, und die Farben stimmen mit der Zahl Weiß - Null, Schwarz - Eins überein, und die Flächen des Würfels sind Spalten. Wir beginnen mit der Tatsache, dass alle 6 Gesichter weiß sind - dies ist ein 6-dimensionaler Nullvektor. Die zweite Zeile ist eine Fläche schwarz, dh das niedrigstwertige Bit wird mit 1 usw. gefüllt, bis die 6-Bit-Binärzahlen erschöpft sind. Wir legen die Würfel in eine gemeinsame lange Reihe. Jeder von ihnen scheint eine Zahl von 0 bis 63 zu haben.



Jetzt ist die Anzeige umgekehrt. Eine Packung Papier (viele) und 6 Farben (Filzstifte).

Markieren Sie beide Seiten der Papierblätter mit Filzstiften in verschiedenen Farben. Wie viele Blätter werden benötigt? Antwort f: 6 → 2 oder 6 ² = 36. Dies sind beliebige Zuordnungen.



Kommen wir zu den Beziehungen. Beginnen wir mit einer abstrakten Menge - dem Träger der Beziehung

= {a1, a2, a3, ..., an}.

Sie können darüber lesen Sie hier . Zum besseren Verständnis werden wir die Menge auf 3 Elemente reduzieren, d.h. A = {a1, a2, a3}. Nun führen wir eine kartesische Multiplikation durch × = ² ,

× = {(a1, a1), (a1, a2), (a1, a3), (a2, a1), (a2, a2), (a2, a3) ), (a3, a1), (a3, a2), (a3, a3)}.



Wir haben 9 geordnete Elementpaare von A × A erhalten, in einem Paar ist das erste Element vom ersten Faktor, das zweite vom zweiten. Versuchen wir nun, alle Teilmengen aus dem kartesischen A × A-Quadrat zu erhalten. Zunächst ein einfaches Beispiel.



Beispiel 1... Eine Menge A = {a, b, c, d} von 4 Elementen ist gegeben. Schreiben Sie alle Teilmengen auf. B (A) = {Ø}; {a}; {b}; {c}; {d}; {ab}; {ac}; {ad}; {bc}; {bd}; {cd}; { abc}; {abd}; {acd}; {bcd}; {abcd}; 2 ⁴ = 16 Teilmengen. Dies ist der Boolesche Wert B (A) der Menge A und enthält eine leere Teilmenge.



Die Teilmengen enthalten von A × A eine andere Anzahl von Elementen (Paaren): eins, zwei, drei usw. Bis zu allen 9 Paaren nehmen wir auch die leere Menge (Ø) in diese Liste auf. Wie viele Untergruppen gibt es? Viele, nämlich 2 ⁹ = 512 Elemente.



Definition . Jede Teilmenge des kartesischen Produkts (wir haben ein Quadrat) einer Menge wird als Beziehung bezeichnet . Beachten Sie, dass die Arbeit denselben Satz verwendet. Wenn die Mengen unterschiedlich sind, gibt es keine Beziehung, sondern eine Entsprechung...



Wenn es ein kartesisches Produkt zweier Faktoren ist, dann ist die Beziehung binär , wenn von 3 es intern ist, von 4 tetrar ist und von n n-ary ist. Arity ist die Anzahl der Orte in einer Beziehung. Beziehungen erhalten die Namen der Großbuchstaben R, H, P, S ... Lassen Sie uns auf binäre Beziehungen (BO) eingehen, da sie eine sehr wichtige Rolle in der Beziehungstheorie spielen. Tatsächlich können alle anderen auf binäre Beziehungen reduziert werden.



Das Beziehungssymbol befindet sich links von den Elementen R (x, y) oder zwischen ihnen x R y; x, y є A.

Definition Die Menge aller Teilmengen der Menge A wird als Boolescher Wert bezeichnet . Unser Boolescher Wert besteht aus 2 ^{| A × A |} Elemente, hier | A × A | Ist die Kardinalität der Menge.



Beziehungen können in verschiedenen Darstellungen über A = {a1, a2, a3, a4} gesetzt werden:

• Aufzählung von Elementen; R1 = {(a1, a2), (a1, a3), (a2, a3) (a2, a4) (a3, a2) (a3, a4}
• binär n = 16-Bit-Vektor; <0110001101010000>;
• Matrix;

Abbildung 1.2. a) 4 × 4-Matrix der binären Beziehung b) Nummerierung der Zellen der Matrix



Hier werden Zellennummern verwendet, die mit denen in Fig. 1 gefüllt sind. 1b)

- Vektordarstellung. Ein binärer Vektor zur Darstellung einer binären Beziehung wird aus den Elementen {0,1} wie folgt gebildet:



Das betrachtete Beispiel für das Festlegen einer Beziehung in Vektorform sieht folgendermaßen aus:





- Graphendarstellung. Verknüpfen wir die Elemente der Menge

A = {x1, x2, z3, ..., xn} mit Punkten in der Ebene, d. H. die Eckpunkte des Graphen G = [Q, R].



Zeichnen Sie einen Bogen im Diagramm von (xi) nach (xj) genau dann, wenn das Paar (xi, xj) є R (für i = j wird der Bogen (xi, xi) am Scheitelpunkt (xi) zu einer Schleife. Beispiel (Abb. 1a) Die Darstellung der binären Beziehung A [4 × 4] durch ein Diagramm ist in Abb. 2.2 dargestellt.



Abbildung 2.2. Darstellung einer Beziehung durch einen gerichteten Graphen



Katalog binärer Beziehungen (n = 3)



Groß ist in einiger Entfernung zu sehen. Um ein Gefühl für die Beziehung und ihre Vielfalt zu bekommen, musste ich manuell einen Katalog von binären Beziehungen über einen Satz von 3 Elementen erstellen, die alle (mehr als 500 Beziehungen) Beziehungen umfassten. Danach kam oder ging es um die Beziehung.



Offensichtlich wird der Katalog 2 ^{3 × 3} = 2 ^{9 enthalten}Beziehungen, und jeder von ihnen wird mit einer Reihe von inhärenten Eigenschaften ausgestattet. Unten (Tabelle 3) finden Sie eine vollständige Liste aller 512 Beziehungen über die Menge A, | A | = 3 von drei Elementen. Die Ergebnisse der Berechnung der Anzahl von Verhältnissen (Tabelle 2), dargestellt durch Kombinationen der Anzahl von Zellen des kartesischen Quadrats 3 × 3, verschiedener Unterklassen für verschiedene Werte der Kardinalität des Trägersatzes (n = 3) sind ebenfalls angegeben. Für jede Beziehung sind ihre grundlegenden Eigenschaften und ihr Typ angegeben (Tabelle 3). Die im Katalog verwendeten Abkürzungen sind in Tabelle 2,

Tabelle 2 angegeben. Quantitative Eigenschaften des Katalogs für verschiedene n





Es ist zweckmäßig, die Essenz von Operationen mit Beziehungen und ihre Technik anhand von Beispielen zu erklären, die für binäre Beziehungen besonders einfach und verständlich sind. Operationen können zwei und / oder mehr Beziehungen umfassen. Operationen, die an einzelnen Beziehungen ausgeführt werden, sind unäre Operationen. Zum Beispiel Operationen zum Umkehren (Erhalten einer Umkehrung) einer Beziehung, Nehmen eines Komplements, Verengen (Begrenzen) einer Beziehung. Ein Beispiel zeigt, wie der Katalog verwendet wird.



Beispiel 2 . Betrachten Sie die Zeile Npr = 14 der Katalogtabelle. Es hat die Form



Die ersten 9 Zeichen der Zeile (rechts von der Gleichheit) sind ein binärer Vektor, der einer Kombination von 9 bis 2 entspricht, dh die Nummer der ersten Zelle (von links nach rechts gezählt) ist die Nummer der 5. Zelle der Matrix der binären Beziehung, d. H. Elemente a1a1 = a2a2 = 1. Diese Kombination hat eine Seriennummer Ncc = 4 und eine Durchgangsnummer Npr = 14 in der Liste aller Beziehungen. Der Rest dieser Zeile enthält entweder Nullen oder Einsen. Nullen zeigen das Fehlen einer Eigenschaft an, die dem Namen der Nullspalte entspricht, und Einsen zeigen das Vorhandensein einer solchen Eigenschaft in der betrachteten Beziehung an.

Eigenschaften und quantitative Eigenschaften von Beziehungen

Betrachten wir die wichtigsten Eigenschaften von Beziehungen, die es uns ermöglichen, die Arten (Klassen) von Beziehungen, die in relationalen Datenbanken in der Theorie der Wahl und Entscheidungsfindung und in anderen Anwendungen verwendet werden, weiter hervorzuheben. Im Folgenden bezeichnen wir die Beziehung mit dem Symbol [R, Ω]. R ist der Name der Beziehung, Ω ist der Trägersatz der Beziehung.



1. Reflexivität. Die Beziehung [R, Ω] heißt reflexiv, wenn sich jedes Element der Menge in der Beziehung R zu sich selbst befindet (Abb. 2.3). Der Graph eines reflexiven BO hat an allen Eckpunkten Schleifen (Bögen), und die Beziehungsmatrix enthält (E) die Hauptdiagonale der Einheit.





Abbildung 2.3. Reflexive Haltung



2. Antireflexivität . Die Beziehung [R, Ω] wird als antireflexiv bezeichnet, wenn sich kein Element der Menge in der Beziehung R zu sich selbst befindet (Abb. 2.4). Eine Antireflexionsbeziehung wird als streng bezeichnet.





Abbildung 2.4. Anti-



Reflexions Haltung 3. Teil Reflexivität. Die Beziehung [R, Ω] wird als teilweise

reflexiv bezeichnet, wenn sich ein oder mehrere Elemente aus der Menge nicht in der Beziehung R zu sich selbst befinden (Abb. 2.5).





4. Symmetrie. Eine Beziehung [R, Ω] heißt symmetrisch, wenn die Beziehung zusammen mit einem geordneten Paar (x, y) auch ein geordnetes Paar (y, x) enthält (Abb. 2.6).





5. Antisymmetrie. Eine Beziehung [R, Ω] heißt antisymmetrisch, wenn für jedes geordnete Paar (x, y) є R ein geordnetes Paar

(y, x) єR ist, nur im Fall x = y. Für solche Verhältnisse gilt R∩R ^-1 ⊆ E (Abb. 2.7).





6. Asymmetrie. Eine Beziehung [R, Ω] heißt asymmetrisch, wenn sie antireflexiv ist und für jedes geordnete Paar (x, y) є R ein geordnetes Paar (y, x) ∉ R, für die Beziehungen R ∩ R ^-1 = Ø (Abb. 2.8).





7. Transitivität. Die Beziehung [R, Ω] wird als transitiv bezeichnet, wenn für geordnete Paare (x, y), (y, z) є R in Beziehung R ein geordnetes Paar (x, z) є R vorliegt oder wenn R × R⊆R (Abb. 2.9).





8. Zyklizität. Eine Beziehung [R, Ω] heißt zyklisch, wenn es für ihre Elemente {x1, x2, z3, ..., xn} eine Teilmenge der Elemente {xi, xi + 1, ... xr, ..., xj, xi} gibt. für die wir die Folge xiRxi + 1R ... RxjRxi ausschreiben können. Eine solche Sequenz wird als Zyklus oder Schleife bezeichnet (Abbildung 2.10).





9. Zyklizität. Beziehungen, in denen es keine Konturen gibt, werden als azyklisch bezeichnet. Für azyklische Beziehungen gilt die Beziehung R ^k ∩R = Ø für jedes k> 1 (Abb. 2.11).







10. Vollständigkeit (Konnektivität). Die Beziehung [R, Ω] heißt vollständig (verbunden), wenn für zwei beliebige Elemente (y, z) є Ω eines von ihnen in Beziehung zum anderen steht (Abb. 2.12). Linearität. Lineare Beziehungen sind minimal vollständige Beziehungen.





Abbildung 2.12. Lineare Beziehung



Wir haben also festgestellt, dass Beziehungen als mathematische Objekte bestimmte Eigenschaften haben, deren Definition zuvor angegeben wurde. Im nächsten Absatz werden wir das Wesentliche und die Manifestation einiger Eigenschaften betrachten:

1. Reflexivität x є A (xRx).
2. Antireflexivität x є A ¬ (xRx).
3. Symmetrie x, y є A (xRy → yRx).
4. Antisymmetrie (xRy & yRx → x = y).
5. Transitivität; x, y, z є A (xRy & yRz → xRz).
6. Zyklizität; x, y є A; ...
7. Vollständigkeit x, y є x (xRy, yRx);
8. Konnektivität (x ≠ y → xRy, yRx).
9. Linearität x, y є (xRy, yRx).

Die Analyse des Beziehungsraums ist eine komplexe Aufgabe der Theorie und, sollte angemerkt werden, bei weitem nicht vollständig. Die Hauptergebnisse sollten die Auswahl von Teilmengen von Beziehungen umfassen, die vollständige Beziehungsräume mit allen sich daraus ergebenden Konsequenzen bilden.



Quantitative Beziehungen solcher diskreten Räume sind sowohl von

theoretischem als auch von praktischem Interesse. Einige Aspekte quantitativer Merkmale, die mit den Eigenschaften von Beziehungen verschiedener Typen verbunden sind, werden nachstehend betrachtet.

Operationen auf Beziehungen

Wie die meisten Zahlensysteme mit Beziehungen werden die folgenden Operationen ausgeführt:

• einstellig;
• binär;
• n-ary.

Unten sind Tabellen der Booleschen ⊕ Addition und Multiplikation & von zwei Variablen x1 und x2, Mod 2 Addition und binäre Summation:





Oben wurde das Konzept einer binären Beziehung als Teilmenge geordneter Paare des kartesischen Mengenprodukts eingeführt, und die Eigenschaften von Beziehungen wurden ebenfalls berücksichtigt. Zusätzlich wurden binäre Beziehungen und Matrixdarstellung von Beziehungen erwähnt. Betrachten wir nun das Konzept einer Beziehung genauer und betrachten wir zusätzlich die Grundoperationen binärer Beziehungen, die wichtigsten ihrer Menge für Beziehungen.



Für sie müssen folgende Bedingungen erfüllt sein:

• Die Arität der Operanden in der Operation muss übereinstimmen.
• Das Ergebnis der Operation muss eine Beziehung derselben Arität sein.

Für binäre und n-fache Beziehungen muss Folgendes erfüllt sein: Der Ankunftsbereich des ersten Operanden muss mit dem Ursprungsbereich des zweiten Operanden übereinstimmen.



Unäre Operationen auf Beziehungen



Umkehrung von Beziehungen . Die Umkehrung der Beziehung R ist das Verhältnis R ^-1 , definiert durch die Bedingung xR ^-1 y <=> yRx. Richtiger sollte diese Operation als Pseudoinversion bezeichnet werden, da p · p ^-1 ≠ E = Δ ist.



Die Beziehung sei in Form einer Auflistung der darin enthaltenen geordneten Paare geschrieben. Wenn in jedem Paar die Komponenten vertauscht sind, bilden die neuen Paare das Verhältnis P ^-1 , das als Inverse zu P bezeichnet wird.



Die umgekehrte Beziehung zur Beziehung P ist die Beziehung, die durch Paare (ai aj) gebildet wird, für die (aj ai) є P ^{-1 ist} . Für Relationen in Matrixform werden inverse Relationen durch Transposition der Matrix P erhalten.



9. Die doppelte Relation (P ^d ) zur Relation P ist die Relation, die von all jenen Paaren gebildet wird, die zur universellen Relation gehören und nicht zur inversen Relation gehören (zusätzlich zur inversen Relation):



P ^d = {(ai aj) | ((ai aj) єA × A) & (ai aj) ∉ P ^-1 )} = (A × A) \ P ^-1 .



Die dualen und inversen Beziehungen im Aggregat enthalten alle Paare des kartesischen Produkts A × A und haben keine gemeinsamen Paare, sie mögen die Beziehungen P und P. bilden eine Partition A × A.





Es ist zu beachten, dass für jede Beziehung P nicht erfüllt ist P P = ^d .



Verengung (PA1). Die Beziehung [R1, A1] wird als Beschränkung der Beziehung [R, A] auf die Menge Ω1 bezeichnet, wenn Ω1⊆ Ω und R1 = R∩Ω1 × Ω1. Das Verhältnis PA1 auf der Menge A1 ⊆ A ist das Verhältnis PA1 auf der Menge A1, das aus allen Paaren gebildet wird, die zur Beziehung P gehören und gleichzeitig Teil des kartesischen Produkts A1 × A1 sind. Mit anderen Worten ist PA1 der Schnittpunkt der Beziehungen P und A1 × A1. Sei A1 = {a1, a3, a4}, dann haben für die Beziehungen P und Q in Matrixform die sich verengenden Beziehungen die Form:





Binäre Operationen



Operationen, die mindestens zwei Beziehungen erfordern, sind n-ary (n-ary). Nur Beziehungen derselben Art können an solchen Operationen teilnehmen. Beispiele für solche Operationen: Schnittmenge, Vereinigung, Differenz, symmetrische Differenz von Beziehungen und einige andere. Wenn die Operation mehr als zwei Relationen verwendet, wird sie nacheinander für die ersten beiden und dann für die letzte Relation und die dritte usw. ausgeführt.



Mit anderen Worten, diese Operationen sind für zwei Beziehungen definiert. Bei Operationen auf Beziehungen wird angenommen, dass die Bereiche der Spezifizierung von Beziehungen (Operanden und das Ergebnis) zusammenfallen, die Aritäten der Beziehungen zusammenfallen und das Ergebnis der Operation wieder eine Beziehung derselben Arität ist. Als Beispiele betrachten wir Operationen an binären Beziehungen P und Q, die auf einer diskreten Menge definiert sind

= {a1, a2, a3, a4} durch boolesche Matrizen (in der Regel passen Nullen nicht in die Matrix):





1. Schnittpunkt (P ∩ Q) ist eine Beziehung, die von allen Elementpaaren aus A gebildet wird, die in beiden Beziehungen enthalten sind, d. H. gemeinsam für P und Q ist

P ∩ Q = {(ai aj) | ((ai aj) є P) & ((ai aj) є Q)}.



Die Verhältnismatrix P ∩ Q wird als Boolescher Schnittpunkt der Matrizen P und Q erhalten:





In Abwesenheit solcher gemeinsamen Paare wird der Schnittpunkt von Beziehungen als leer bezeichnet, d.h. es ist eine Nullbeziehung. Der Schnittpunkt der Beziehungen R1 und R2 (R1∩R2) ist die Beziehung, die durch den Schnittpunkt der entsprechenden Teilmengen von A × A bestimmt wird.



2. Union (PUQ). Die Vereinigung der Beziehungen R1 und R2 (R1UR2) ist die Beziehung, die durch die Vereinigung der entsprechenden Teilmengen von A × A definiert ist. Das Verhältnis, das von allen Paaren gebildet wird, die entweder das Verhältnis P oder das Verhältnis Q bilden, d.h. durch Paare, die zu mindestens einer der Beziehungen gehören (die verbindende ∨ - oder die verbindende)

PUQ = {(ai aj) | ((ai aj) є P) ∨ ((ai aj) є Q)}.



Wenn in der Menge A × A keine anderen Paare vorhanden sind, die nicht in der Beziehung PUQ enthalten sind, und ihr Schnittpunkt Null ist, werden die Beziehungen P und Q in Kombination als vollständige Beziehung A × A bezeichnet, und ihr System ist eine Partition dieser vollständigen Beziehung. Die Vereinigung von Beziehungsmatrizen wird als boolesche Summe von Beziehungsmatrizen gebildet:





3. Die Differenz (P \ Q) ist das Verhältnis, das von den Paaren aus P gebildet wird, die nicht in der Beziehung Q

P \ Q = {(ai aj) | enthalten sind ((ai aj) є P) & ((ai aj) ∉Q)}.



Der Unterschied für Beziehungen in der Matrixdarstellung ist





4. Beziehungen multiplizieren. Die geordneten Paare, die die Beziehung bilden, können dieselben Elemente enthalten oder nicht. Lassen Sie uns unter den Paaren, die dieselben Elemente in ihrer Zusammensetzung haben, solche geordneten Paare herausgreifen, die wir als benachbart (angrenzend) bezeichnen und die das 1. Element im zweiten Paar und das 2. Element im ersten Paar gleich haben. Definieren wir das Produkt benachbarter Paare als geordnetes Paar:

(ai ak) ∙ (ak aj) => (ai aj).



In Bezug auf die Graphentheorie bedeutet dies, dass benachbarte Paare eine Route von Punkt (ai) zu Punkt (aj) auf dem Weg durch Punkt (ak) bilden, der aus 2 benachbarten Bögen besteht. Das Produkt dieser Bögen ist der dritte Bogen von Punkt (ai) zu Punkt (aj), der den Übergang zwischen den Extrempunkten der Route in derselben Richtung unter Umgehung des Zwischenpunkts (ak) implementiert. Der Bogen (ai aj) soll diese Punkte direkt schließen.



5. Symmetrische Differenz (P∆Q) - das Verhältnis, das von den Paaren gebildet wird, die in der Vereinigungs-PUQ enthalten sind, aber nicht in der Schnittmenge P∩Q enthalten sind. Eine andere Form der Definition erklärt den Namen der Operation: P∆Q wird durch die geordneten Paare gebildet, die die Vereinigung der Differenzen P \ Q und Q \ P darstellen. Somit kann der Ausdruck für die symmetrische Differenz auf zwei verschiedene Arten geschrieben werden:

P∆ Q = (PU Q) \ (P ∩ Q) = (P \ Q) U (Q \ P).



Die symmetrische Differenzmatrix lautet:





Aus dem letzten Datensatz folgt, dass die Operation der symmetrischen Differenz die Permutation der Operanden ermöglicht, dh kommutativ ist.



5. Zusammensetzung oder Produkt (P ∙ Q) - die Beziehung, die von allen Paaren gebildet wird, für die:

P ∙ Q = {(ai aj) | ((ai ak) є P) & ((ak aj) є Q)}.



Mit anderen Worten, jedes geordnete Paar in der resultierenden Beziehung ist das Ergebnis der Multiplikation benachbarter Paare, von denen das 1. Paar zur ersten Faktorrelation gehört, das 2. - zur zweiten Faktorrelation. Die Kompositionsoperation ist nicht kommutativ.



Die Zusammensetzung (◦Q) auf einer Menge M ist eine Beziehung R, die auf derselben Menge M definiert ist und ein Paar (x, y) enthält, wenn Z є M existiert, so dass (x, z) є P und (z, y) є Q.



In der Matrixdarstellung von Beziehungen ist die Zusammensetzungsmatrix von Beziehungen gleich dem Booleschen Produkt der Matrizen der ursprünglichen Beziehungen:





Ein Sonderfall der Zusammensetzung von Beziehungen ist das Quadrat der Beziehung.



Mit Induktion kann gezeigt werden, dass der n-te Grad einer Beziehung rekursiv durch die Formel definiert ist: P ⁿ = P ^n-1 ◦, dh das Paar (x, y) є P ⁿ in dem Fall, in dem in der Matrix eine Kette vorhanden ist Elemente: so dass (xi, xi + 1) є P, 1 <i <n - 1.



Die Kompositionsoperation hat die Eigenschaft der Assoziativität (wie ein Produkt von Matrizen).



Die Zusammensetzung der Beziehungen auf der Menge M ist das Ergebnis einer paarweisen Zusammensetzung der Beziehungen für jede Anordnung von Klammern. Der Bereich zum Einstellen des Kompositionsergebnisses ändert sich nicht.



Die Zusammensetzung für Boolesche Beziehungsmatrizen wird als Ergebnis des Booleschen Produkts von Matrizen dieser Beziehungen gebildet.



Tabelle 3. Katalog der binären Beziehungen (n = 3). Klickbar