Quantitative Merkmale von Beziehungen

Die Beziehungstheorie in der Mathematik und in einer Reihe von Fachgebieten (Entscheidungsfindung, Wissens- und Datenbanken, mathematische Linguistik, Prozessmodellierung usw.) spielt eine sehr bemerkenswerte Rolle, ist jedoch noch lange nicht vollständig. Wie in anderen Bereichen des mathematischen Wissens beziehen sich ihre bekannten Ergebnisse in größerem Maße auf Fragen und Probleme der Existenz bestimmter Objekte als auf die Probleme ihrer Aufzählung. Es scheint, dass jeder Forscher in einem bestimmten Zweig der Theorie an dem allgemeinen und vollständigen Bild der interessierenden Objekte und ihrer Abhängigkeiten interessiert sein sollte, um das vollständige Panorama zu beobachten. Leider ist dies sehr problematisch, da niemand ein solches Panorama erstellt hat oder anbietet (Bild). Selbst der in der Arbeit vorgeschlagene Beziehungskatalog schließt das Problem nicht.



Ein einfaches Beispiel. Vor vielen Jahren bin ich in dem Buch [1 S. 207] auf einen solchen Absatz gestoßen.

Die Theorie der teilweise geordneten Mengen enthält noch viele ungelöste Probleme. Selbst die Frage nach der Anzahl solcher Mengen, die aus einer gegebenen Anzahl n von Elementen aufgebaut werden können, existiert noch nicht, wenn n ≥ 6 ist. Direkte Berechnungen konnten nur feststellen, dass wenn S (n) die Anzahl der teilweise geordneten Mengen ist, S (2) = 3, S (3) = 19, S (4) = 219, S (5) = 4231 und die Zahlen Sn (n) für nicht-isomorphe Mengen wurden nur für n = 4 und n = 5 Elemente gefunden: Sn (4) = 16 und Sn (5) = 63.

Darüber schreibt der Leiter der Abteilung der Moskauer Staatlichen Universität Rybnikov K.A. Ich wollte das tiefer verstehen und es schien, als könnte ich versuchen, nach einer Lösung zu suchen, zumindest irgendwie die Liste zu erweitern und vor allem - die Teilordnungen aufzulisten, ihre Streuung in der Realität mit ihren Eigenschaften zu sehen. Nur um die Ergebnisse an die Wand zu hängen. Ich gebe zu, dass viel Aufwand aufgewendet wurde, um ein Forschungsprogramm zu entwickeln, ein funktionsfähiges Modell der Teilordnung zu erstellen, ein Programm zu schreiben und es zu debuggen. Computer haben die programmierten Algorithmen zehn Stunden lang gedreht. Jemandes (von den Großen) Bemerkung kam mir in den Sinn, dass die Grundlage der Mathematik keine Zahl, sondern eine Ordnung sein sollte, dann hätten angeblich viele Theoreme einfachere und transparentere Beweise erhalten.



Wir haben gelernt, die Anzahl der Relationen über große Mengen-Träger zu berechnen und die Relationen aufzuzählen, aber wir haben selbst für die Anzahl S (n) keine strengen Formeln erhalten. Ich erinnere mich an diese Zeit als eine Zeit intensiven kreativen Wachstums meiner eigenen und meiner Kollegen, in der nach fast jeder Ausgabe der Computerergebnisse und deren Analyse Ideen zur Änderung, Verbesserung des Modells, der Algorithmen und Korrekturen entstanden, um neue Hypothesen zu testen, aber etwas Bedeutendes ( möglicherweise das Gehirn ) nicht genug.



Was ich öffnen (bekommen) habe, gebe ich unten im Text an. Übrigens stimmten die Ergebnisse anderer ausländischer Forscher mit unseren überein, aber sie gaben nur die Zahl S (n) an und erwähnten nicht die Aufzählung von Teilaufträgen.



Wir haben klein angefangen. Die vollständige Liste der binären Beziehungen für jeden n-Träger-Satz ist bekannt und kann leicht erhalten werden. Sie suchten nach einer Antwort auf die Fragen: Wie viele gibt es für ein gegebenes n Beziehungen zu einer festen Eigenschaft, zu einem Eigenschaftspaar, zu einem Tripel usw. Tatsache ist, dass es mit diesen Daten möglich war, keine Aufzählung zu erstellen, sondern direkte Algorithmen zur Aufzählung solcher Beziehungen, die Wenn sie der Occam-Rasiermesser-Regel folgen, produzieren sie keine zusätzlichen Essenzen.



Hier werden wir weiter darüber sprechen, solche Ergebnisse für binäre Beziehungen (BO) zu erhalten.

Es gibt also einen n-Mengen-Träger von BO und eine vollständige Liste aller BOs sowie eine Liste der BO-Eigenschaften:



- Reflexivität; Antireflexivität; partielle Reflexivität;

- Symmetrie; Antisymmetrie; Asymmetrie; Asymmetrie;

- Transitivität; Anti-Transitivität;

- schwache Ordnung; strenge Ordnung; Teilbestellung; perfekt (linear);

- Toleranz;

- Äquivalenz;

- Zyklizität;

- Vollständigkeit.

Quantitative Merkmale der Arten von binären Beziehungen

Beziehungen können nicht nur eine bestimmte Eigenschaft haben, sondern auch Sätze von Paaren, Tripletts usw. von Eigenschaften. Die Verwendung solcher Beziehungen in der Praxis ist eine häufige Situation. So hat beispielsweise jede Toleranzhaltung (Gleichgültigkeit) zwei Eigenschaften: Symmetrie und Reflexivität. Dieser Satz von Eigenschaften bestimmt die Art der Toleranzbeziehung.



Eine andere Art von Beziehung ergibt sich aus Toleranzbeziehungen, wenn wir von solchen Beziehungen die Machbarkeit einer erweiterten Liste von Eigenschaften verlangen: Symmetrie, Reflexivität und Transitivität. Es ist klar, dass sich möglicherweise nicht alle Toleranzbeziehungen als transitiv herausstellen werden, aber diejenigen, die eine Reihe von drei benannten Eigenschaften haben, werden eine neue Art von Beziehungen bilden, die Äquivalenzen genannt werden.



Die Menge der Äquivalenzbeziehungen ist in der Menge der Toleranzbeziehungen verschachtelt. Im Katalog werden diese Arten von Beziehungen beispielsweise durch Füllen hervorgehoben (8 Toleranzen und nur 5 davon sind Äquivalenzen). Es stellt sich die Frage nach der Anzahl der BOs mit einer Reihe von Eigenschaften oder einer davon.

Reflexivität

Die Beziehung α = <, A> auf der Menge A = {$$${_1,_2,...,_n}$ } ist reflexiv (hat die Eigenschaft der Reflexivität), wenn jedes Paar ($$$_ i, _ i$ ) erfüllt diese Beziehung. Hier ist M ein Graph (kein Graph) der Beziehung$$$_ i α _ i , _i є A , i = 1(1)|A|$...



Mit anderen Worten, die Hauptdiagonale der Graphmatrix, das Verhältnis, ist mit Einsen gefüllt. In einem Reflexionsbeziehungsgraphen haben alle Eckpunkte Schleifen. Die Haltung ist antireflexiv, wenn nicht$$$_i є A , i = 1(1)|A|$ nicht ausgeführt $$$_ i α _ i$... In diesem Fall hat die Matrix der antireflexiven Beziehung α auf der Hauptdiagonale keine einzige Einheit, d.h. Es gibt Nullen, und der entsprechende Graph hat an keinem Scheitelpunkt Schleifen.



Schließlich ist die Beziehung α für einige nicht reflektierend$$$_i є A ,_ i α _ i$wird ausgeführt, für andere jedoch nicht. Wir werden solche Beziehungen als teilweise reflexiv betrachten. Die Matrix der nicht reflektierenden Beziehung auf der Hauptdiagonale enthält teilweise Einsen, teilweise Nullen. Der Graph einer solchen nicht reflektierenden Beziehung weist an allen Eckpunkten keine Schleifen auf.



Ein klassisches Beispiel einer reflexiven Beziehung ist die Hauptdiagonale einer Matrixdarstellung, das Einheitsverhältnis (E = & Dgr;), d.h. Gleichheitsverhältnis (im Katalog Nr. 68). Der Graph dieses Verhältnisses wird durch Punkte (Paare) gebildet, die auf der Hauptdiagonale der Matrix liegen, und die entsprechenden Paare$$$( i , i ) , i =1(1)|A|$enthält das Diagramm keine weiteren Punkte.



Die Matrixdarstellung dieses Verhältnisses entspricht der Identitätsmatrix (E). Der diagonale Beziehungsgraph wird durch die Eckpunkte gebildet, die den Elementen aus der Menge A entsprechen, denen die Schleifen zugeordnet sind. Die diagonale Beziehung wird oft durch das Symbol gekennzeichnet$$$Δ_$...



Im Fall einer reflexiven Beziehung ist der entsprechende Graph auch reflexiv, im Fall einer antireflexiven Beziehung ist sein Graph antireflexiv. Wenn für eine Beziehung α bekannt ist, dass sie reflexiv ist, dann ist das Komplement ᾱ immer antireflexiv und$$$α ∩ ᾱ =∅ , α ∩ Δ_ = Δ_$...



Für die antireflexive Beziehung β ist es wahr$$$β ∩Δ_= ∅$...



Beispiel 1 . Die Beziehung ≤ (nicht mehr) auf der Menge N ist reflexiv, und die Beziehung <(weniger) auf derselben Menge ist antireflexiv.



Die Einstellung „ein Sohn sein“ ist antireflexiv, da niemand sein eigener Sohn ist.

Aus praktischen Gründen ist es manchmal erforderlich, die Anzahl der verfügbaren reflexiven Beziehungen in der vollständigen Menge der auf der Menge A angegebenen Beziehungen mit der Kardinalität | A | zu zählen = n.

Lassen Sie uns zeigen, wie eine solche Berechnung durchgeführt werden kann. Wir werden auf der Ebene die Matrix der binären Reflexionsbeziehung α betrachten. Es enthält immer alle diagonalen Punkte.



Andere Punkte, die Paaren (i, j) entsprechen, deren Anzahl von n × n - n = n (n - 1) , können in unterschiedlicher Zusammensetzung und Anzahl k enthalten sein, k = 0 (1) (n × n - n)in mögliche Beziehungen, die natürlich reflektieren werden. Durch Summieren über k Kombinationen von n (n-1) über k wird die Gesamtzahl der Reflexionsbeziehungen bestimmt,



wobei K = n (n-1) / 2 die Anzahl der Bögen (Kanten) in einem n- Scheitelpunktgraphen ohne Schleifen ist.



Die Anzahl der nicht reflektierenden Beziehungen ist definiert als die Differenz zwischen der Gesamtzahl der Beziehungen auf A und der Anzahl der reflexiven Beziehungen.





Aus diesem Ausdruck folgt, dass die Menge der nicht reflektierenden Beziehungen in enthält$$$(2^n -1)$mal mehr Beziehungen als es reflexive gibt. Dieser Überschuss an Verhältnissen wird durch die Vielzahl von Kombinationen von nur diagonalen Punkten in der Grafik erzeugt, während die Zusammensetzungen und die Anzahl der verbleibenden Punkte einfach wiederholt werden.



Die Anzahl der antireflexiven Beziehungen aus der Menge der nichtreflexiven Beziehungen ist genau gleich der Anzahl der reflexiven, d.h.$$$2^{n^2-n}$... Dies folgt aus der Tatsache, dass eine Eins-zu-Eins-Entsprechung zwischen reflexiven und antireflexiven Beziehungen hergestellt werden kann: Aus jeder reflexiven Beziehung kann durch Entfernen aller Punkte der Diagonale eine einzelne antireflexive Beziehung erhalten werden und umgekehrt.

Symmetrie

Durch die Eigenschaft der Symmetrie wird der gesamte Satz von Beziehungen nicht in vier Klassen unterteilt: symmetrisch, asymmetrisch. Letztere fallen wiederum in drei Klassen: antisymmetrisch, asymmetrisch und die verbleibende asymmetrisch.



Die Beziehung α = <, A> auf der Menge A ist symmetrisch (sie hat die Eigenschaft der Symmetrie in Bezug auf die gerade Linie, die mit der Hauptdiagonale des Graphen zusammenfällt), wenn für ein Paar$$$(i, j) є A×A$ von $$$_i α _j$sollte $$$_j α _i$... Mit anderen Worten, für jedes Paar$$$((_i, _j) є Å)$entweder in beide Richtungen oder überhaupt nicht ausgeführt.



Wenn im Diagramm einer symmetrischen Beziehung ein Paar von Eckpunkten i und j durch einen Bogen (i, j) verbunden ist, ist es notwendigerweise durch einen Bogen (j, i) verbunden. Ein symmetrischer Beziehungsgraph ist ein symmetrisch orientierter oder einfach ungerichteter gewöhnlicher Graph.



Das Verhältnis α ist antisymmetrisch, wenn von$$$_i α _j$ und $$$_j α _i$Daraus folgt, dass i = j.



Die antisymmetrische Verhältnismatrix enthält nicht notwendigerweise alle auf der Hauptdiagonale und enthält diejenigen in einer von zwei Positionen, die in Bezug auf die Hauptdiagonale symmetrisch sind: über der Diagonale oder unter der Diagonale. Der Graph dieser Beziehung wird durch Eckpunkte mit Schleifen für alle oder einige von ihnen gebildet, und wenn ein Paar von Eckpunkten (i, j) im Graphen verbunden ist, ist es immer ein Bogen von nur einer Richtung. Beachten Sie, dass für eine symmetrische und antisymmetrische Beziehung einige diagonale Punkte entweder darin enthalten sein können oder nicht.



Wenn eine antisymmetrische Beziehung keinen einzelnen diagonalen Punkt enthält, sagen sie, dass eine solche Beziehung asymmetrisch ist , d.h. es ist immer antireflexiv.



Beispiel 2... Die Beziehung (≤) auf der Menge N ist antisymmetrisch und die Beziehung (<) auf derselben Menge ist asymmetrisch. In der Tat im ersten Fall von$$$_i ≤_j$ und $$$_j ≤_i$ kann nur folgen $$$i = j$... Die Gleichheitsrelation (=) auf N ist symmetrisch, die Relation α = A × A ist ebenfalls symmetrisch.



Für jedes symmetrische Verhältnis α ist es immer wahr$$$α = α^{-1}$ und $$$α^{-1}$auch symmetrisch. Für eine antisymmetrische Beziehung$$$α ∩ α^{-1}⊆∆_A$... Eine allgemeine Beziehung, deren Graph sowohl symmetrische als auch asymmetrische Punkte enthält, ist nicht symmetrisch. Diese Beziehung ist asymmetrisch, aber nicht antisymmetrisch und nicht asymmetrisch.



Die Eigenschaft der Symmetrie manifestiert sich auch in n-fachen Beziehungen. Die Beziehung R am Set$$$= { x_1, x_2,…,x_n}$ ist eine symmetrische n-ary Beziehung, wenn sie zusammen mit dem Element $$$<x_{i1}, x_{i2}, …,x_{in}>є R$ enthält beliebige Sequenzen $$$< x_{j1}, x_{j2},…, x_{jn}>$gebildet durch die Permutation der Mitglieder der Menge X.



Beachten Sie auch, dass die asymmetrische Beziehung immer antireflexiv ist; Eine nicht reflektierende und transitive binäre Beziehung ist immer asymmetrisch. Für die Praxis und zur Durchführung von Berechnungen ist die Anzahl der Beziehungen von Interesse, die eine bestimmte Eigenschaft in Bezug auf die Symmetrie des Graphen haben. Berechnen wir solche Verhältnisse für eine beliebige Menge A der Kardinalität | A | = n.



In unseren Argumenten werden wir uns auf die Eigenschaft der Reflexivität stützen, die wie viele andere noch nicht gründlich genug untersucht wurde. Selbst eine oberflächliche Analyse der Menge aller Beziehungen lässt den Schluss zu, dass sie immer unterteilt werden kann$$$2^n$Klassen gleicher Größe und die Zusammensetzung der Beziehungen, die diese Klassen bilden, folgen einem bestimmten Muster.



Die Mengen von Beziehungen in allen Klassen haben die gleiche Struktur, unterscheiden sich nur in der Anzahl und Zusammensetzung der diagonalen Punkte, deren gesamte Vielfalt durch die Anzahl bestimmt wird$$$2^n$... Definieren wir den Zustand der Diagonale einer Beziehung für ein festes n durch die Anzahl und Zusammensetzung der Punkte darauf, die zu einer bestimmten Beziehung gehören. Es ist klar, dass für eine feste Menge der Füllzustände der Zellen der Diagonale durch den Booleschen Wert bestimmt wird$$$2^∆$, wobei ∆ der vollständige Satz von Punkten der Diagonale des Graphen des kartesischen Kardinalitätsquadrats | ∆ | ist = n.



Daher wurden in der Beziehungstheorie traditionell nur zwei Extremzustände betrachtet und untersucht: Entweder sind alle Punkte der Diagonale in der Beziehung enthalten und sie ist reflexiv, oder die Beziehung enthält keinen diagonalen Punkt und ist dann antireflexiv.



Wir werden alle Zwischenzustände mit einem diagonalen Punkt, mit zwei usw. Teilreflexivität der k-ten Ordnung k = 0 (1) n nennen, und Beziehungen dieser Art sind teilweise reflexiv. Eine teilweise reflexive Beziehung der Ordnung Null ist also eine antireflexive Beziehung, und teilweise ist eine reflexive Beziehung der Ordnung n nur eine reflexive Beziehung.



Beachten Sie, dass alle Zustände als Elemente des Booleschen Werts der Menge ∆ geordnet werden können. Der vorgeschlagene Ansatz ermöglicht es uns, die Art und Weise der Analyse verschiedener Eigenschaften und die Zählung der Anzahl von Beziehungen zu einzelnen Eigenschaften oder deren Aggregaten zu skizzieren.



Lassen Sie die Beziehung als reflexiv und symmetrisch betrachtet werden. Die Symmetrie des Verhältnisses wird durch das Vorhandensein von Punktpaaren bestimmt, die sich in der Verhältnismatrix symmetrisch zur relativen Diagonale befinden. Für beliebige n solcher Paare gibt es$$$C_n^2$... Bezeichnen wir die Menge dieser Paare mit dem Symbol S.



Dann wird die gesamte Vielfalt der symmetrischen und reflexiven Beziehungen durch den Booleschen Wert bestimmt$$$2^S$... Viele dieser Beziehungen werden etwas später genauer betrachtet, aber hier werden wir sagen, dass sie einen Raum der Gleichgültigkeit oder Toleranz bilden. Es ist klar, dass die Anzahl der Toleranzverhältnisse durch die Potenz des Booleschen Werts bestimmt wird$$$2^S$d.h. $$$2^{C_n^2}$...



Unten in der Tabelle. 1 zeigt die Werte der Anzahl von Toleranzverhältnissen für die Anfangswerte n aus einem Segment natürlicher Zahlen.



Tabelle 1 . Die Anzahl der toleranten BOs





Es ist jetzt einfach, die Kardinalität aller symmetrischen Beziehungen zu berechnen, da das Vorhandensein oder Fehlen von diagonalen Punkten die Symmetrieeigenschaften nicht verändert. Die Menge der symmetrischen Beziehungen wird mit dem Symbol SM bezeichnet. Dann wird die Kardinalität dieser Menge für ein festes n durch die Formel bestimmt

$$

$$|SM| = 2^n·2^{C_n^2} = 2^{C_{n+1}^2},$$

Dabei ist n die Anzahl der diagonalen Punkte des Verhältnisses. Tabelle 2 zeigt die Werte | SM | für einige n.



Tabelle 2 . Die Anzahl der symmetrischen BOs





Wenden wir uns nun der Berechnung asymmetrischer Beziehungen zu, deren Menge mit AS bezeichnet wird. Diese Beziehungen sind dadurch gekennzeichnet, dass alle Punkte der Diagonale in ihnen fehlen und keine der Zellen der Matrix der Beziehung, die außerhalb der Diagonale liegt, eine symmetrische hat. Mit anderen Worten, es handelt sich um eine Reihe von antireflexiven und antisymmetrischen Beziehungen.



Die Kardinalität dieser Menge kann aus den Ausdrücken bestimmt werden

$$

$$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$$

wo K =$$$C_n^2$...



Wir erhalten die reduzierte Formel zur Berechnung der Kardinalität der Menge AS - asymmetrische Beziehungen für eine gegebene Kardinalität des Trägers | A | = n. Per Definition sind alle Beziehungen der Menge AS antireflexiv, daher ist die Hauptdiagonale in der Beziehungsmatrix leer, und die Einheitselemente können nur in der Hälfte der verbleibenden Positionen der Matrix angeordnet sein, d.h. beim$$${C_n^2} =(n^2-n):2$Zellen.



Angenommen, eine asymmetrische Beziehung enthält k-Elemente (Punkte, geordnete Paare) 0 ≤ k ≤$$${C_n^2}$... Die Anzahl der Beziehungen mit einer solchen Anzahl von Elementen ist offensichtlich gleich der Anzahl der Kombinationen aus$$$C_n^2$von k.



In diesem Fall ordnen wir jedem der k Elemente ein Paar symmetrischer Positionen zu: eine über der Hauptdiagonale der Matrix, die andere unter der Diagonale. Da sich in jedem Paar ein Element in einer von zwei Positionen befinden kann, scheint ein Boolescher Wert k Elemente aufzunehmen$$$2^n$Chancen.



Auf diese Weise,$$$C_n^2$ Ist die Anzahl der Auswahlmöglichkeiten von k Positionspaaren aus $$$C_n^2 = K$ verfügbare Paare in der Matrixdarstellung von Beziehungen und $$$2^n$- die Anzahl der Möglichkeiten, k Elemente in Positionen in jedem Paar anzuordnen. Die Anzahl von Beziehungen, die k Elemente enthalten, ist definiert als das Produkt der Anzahl von Auswahlen von Positionspaaren durch die Anzahl von Optionen zum Anordnen dieser k Elemente, d.h.$$$2^kC_K^k$...



Die Gesamtzahl der Beziehungen in der Menge AS wird erhalten, indem die erhaltenen Produkte über alle Werte von k von Null bis zum maximal zulässigen K = summiert werden$$$C_n^2 = K$d.h.

$$

$$|AS| = Σ_{k=0}^K C_K^k·2^k = 3^{C_n^2},$$

wo K =$$$C_n^2$...



Beispiel 3. Lassen Sie die Kardinalität der Menge der Unterstützung | A | = 5. Berechnen Sie die Anzahl der asymmetrischen Beziehungen mit der gefundenen Formel. Bestimmen wir den Wert der Obergrenze K in der Summe K =$$$C_n^2$= 10. Die Berechnungsdaten für die Summe sind in der Tabelle angegeben. 3.



Tabelle 3 . BO Eigenschaften





Es gibt eine andere Möglichkeit, die Kardinalität einer Menge AS zu berechnen. Es basiert auf dem Zählen der Anzahl von Abbildungen eines Satzes von Paaren symmetrischer Positionen in einen Satz von Zuständen, in denen jedes solche Paar sein kann. In einer asymmetrischen Beziehung gibt es$$$K = C_n^2$Positionspaare.



Jede Position in einem Zellenpaar kann mit 0 oder 1 belegt werden, aber für ein Positionspaar gibt es S = 3 Zustände, die wir wie folgt bezeichnen:



- 1, wenn Element (1) über der Diagonale platziert ist;

- 2, wenn Element (1) unter der Diagonale platziert ist;

- 3, wenn beide Positionen leer sind (mit Nullen belegt).



Somit kann sich in jeder

Beziehung ein Paar symmetrischer Positionen (in der Beziehungsmatrix) in einem von drei Zuständen befinden. Die Formel zur Berechnung aller möglichen Abbildungen der Menge von Positionspaaren (bezeichnet mit dem Symbol K) in die Menge S von Zuständen, die wir haben:

$$$φ: K → S =>|AS| =|S|^{|K|}$



Beispiel 4 . Für die Bedingungen des vorherigen Beispiels hat die Form | A | = 5, K = | K | =$$$K = C_5^2 = 10,$| S | = 3 also$$$|AS| = 3^10 = 59049$...



Die Berechnungsergebnisse stimmen auf zwei verschiedene Arten überein, was wiederum von der Richtigkeit der erhaltenen Formeln überzeugt. Somit haben wir die Beziehung erhalten

$$

$$3^{C_n^2} = Σ_{k=0}^K C_K^k·2^k,$$

wo K =$$$C_n^2.$



Lassen Sie uns in Tabelle geben. 4 Zahlen asymmetrischer Beziehungen | AS | für kleine Werte von n.



Tabelle 4. Die Anzahl der asymmetrischen BOs





Mit einer Formel zur Bestimmung der Anzahl asymmetrischer Beziehungen kann man eine andere erhalten - zur Berechnung der Anzahl antisymmetrischer Beziehungen, da das Vorhandensein oder Fehlen diagonaler Punkte die Eigenschaften der Antisymmetrie der Beziehung nicht verändert.



Wir bezeichnen also die Menge der antisymmetrischen Beziehungen mit dem Symbol ANS, dann wird die Kardinalität dieser Menge durch die Formel bestimmt$$$|ANS| =2^n$

$$

$$|ANS| =2^n Σ_{k=0}^K C_K^k·2^k =Σ_{k=0}^K C_K^k·2^{k+n} =2^n3^{C_n^2},$$

wo K =$$$C_n^2$



Unten ist eine Tabelle. 5 enthält die (ANS) -Werte für n = 3 (1) 5.



Tabelle 5 . Die Anzahl der antisymmetrischen BOs





Im Folgenden brauchen wir Konzepte, die hier bequem vorgestellt werden können.



Der symmetrische Teil der binären Beziehung α heißt (und wird bezeichnet$$$α^{(S)}$ ) Einstellung $$$α^{(S)} =α∩α^{-1}$und das Verhältnis $$$α^{()} = α \α^{(S)}$ (bezeichnet $$$α^{()}$) heißt sein asymmetrischer Teil. In dem speziellen Fall, in dem das Verhältnis α symmetrisch ist,$$$α^{(S)} = α$ und $$$α^{(S)}$immer symmetrisch; wenn α asymmetrisch ist, dann$$$α^{()}= α$ und $$$α^{()}$ immer asymmetrisch.

Transitivität (lateinischer Transitivus - Übergang, vom Transitus - Übergang)

- eine der Eigenschaften von Beziehungen. Die in der Menge A definierte Beziehung = <M, A> ist gegebenenfalls transitiv$$$_i, _ j, _k є A$ die Bedingung ist erfüllt: von $$$_iα _ j$ und $$$_jα _k$ sollte $$$_iα _ k$...



Mit anderen Worten, für eine transitive Beziehung aus dem Vorhandensein von Elementen in ihrer Zusammensetzung ($$$_iα _ k$) und ($$$_kα _ j$) Daraus folgt, dass es das Element enthält ( $$$_iα _ j$). Für ein Beziehungsdiagramm bedeutet diese Eigenschaft, dass wenn ein Paar von Eckpunkten ($$$_iα _ j$) ist durch einen orientierten Pfad verbunden, der durch den Scheitelpunkt k verläuft und durch 2 aufeinanderfolgende Bögen ( $$$_iα _ k$), ( $$$_kα _ j$), dann werden dieselben Eckpunkte direkt durch einen einzelnen Bogen verbunden ($$$_iα _ j$). Für Matrixelemente [$$$_{ij}$] einer transitiven Beziehung α aus $$$_{ik}·_{kj} =1$ sollte $$$_{ij} = 1$...



Die Definition der Transitivitätseigenschaft für binäre Beziehungen setzt voraus, dass die Beziehung mindestens drei Elemente (geordnete Paare) enthält. Und wie manifestiert sich diese Eigenschaft in einer Beziehung von einem Element, leer oder nur zwei Elementen enthaltend?



Alle Singleton- und leeren Beziehungen sind transitiv. Eine Zwei-Elemente-Beziehung kann transitiv und nichttransitiv sein, wenn die darin enthaltenen Paare ein gemeinsames Element j enthalten. Die Graphbögen, die geordneten Paaren entsprechen, sind in eine Richtung gerichtet (bilden eine orientierte Nichttransitivitätsroute).



Zum Beispiel sei ($$$_i, _ j$ ) є α und ($$$_j, _ k$) є α. Die formulierte Definition erfordert: Damit die Beziehung α transitiv ist, muss sie ein drittes Paar (Bogen) enthalten, nämlich ($$$_i, _ k$), aber da es nicht existiert, ist die Transitivitätseigenschaft für α nicht erfüllt.



Wenn die Beziehung nach wie vor nur zwei Paare mit einem gemeinsamen Element enthält$$$_j є A$, aber so, dass das gemeinsame Element $$$_j є A$ ist in beiden Paaren in der gleichen Position ($$$_j, _ i$), ($$$_j, _ k$ ) oder ($$$_i, _ j$),

($$$_k, _ j$) und die Bögen auf dem Graphen sind in verschiedene Richtungen gerichtet, dann ist eine solche Beziehung transitiv, da die Einbeziehung des dritten Paares in die Beziehung nicht erforderlich ist.



Eine transitive Beziehung liegt auch dann vor, wenn zwei Paare keine gemeinsamen Elemente haben. Beispiele für transitive Beziehungen sind: "Gleichheit" (=), da i = k, k = j impliziert i = j; "Ich bin größer als j"; in der Geometrie - "Parallelität von Geraden". Beispiele für nicht-transitive Beziehungen: "Rechtwinkligkeit gerader Linien" in der Geometrie; "Ich bin nicht gleich j".



In der Literatur zu Beziehungen finden sich verschiedene Konzepte, die die Transitivität charakterisieren: schwache Transitivität, starke Transitivität, negative Transitivität, Antitransitivität, schwache Antitransitivität, generalisierte Transitivität, transitiver Verschlussund einige andere. Hier wird versucht, die verschiedenen Erscheinungsformen der Eigenschaft der Transitivität in Beziehungen zu systematisieren.



Für eine transitive Beziehung α ist die Beziehung$$$α^{–1}$ist auch immer transitiv. Der Schnittpunkt einer beliebigen Anzahl von transitiven Beziehungen ist eine transitive Beziehung. Wenn wir die Beziehung ᾰ betrachten, die der Schnittpunkt aller transitiven Beziehungen ist, die die Beziehung α enthalten, dann heißt ᾰ der transitive Abschluss der Beziehung α.



Der transitive Verschluss ᾰ kann für jede Beziehung α gemäß der Regel aus konstruiert werden$$$_i ᾰ _j$ folgt:



$$$(∃_{1}, _{2}, …,_{s})( _iα _{1}Λ_{1}α _{2}Λ… Λ _{s}α _j)$...



Die Beziehung ᾰ ist die kleinste transitive Beziehung, die α enthält. Wenn α transitiv ist, fällt es mit seinem transitiven Verschluss α = ᾰ zusammen und umgekehrt.



Wenn eine transitive binäre Beziehung durch einen gerichteten Graphen dargestellt wird, ist es möglich, nicht den gesamten Digraphen darzustellen, sondern nur sein transitives Skelett, d.h. Bögen, die den Anfang und das Ende jeder Route länger als eine verbinden, werden nicht gezeichnet. In diesem Fall sagen wir, dass das transitive Skelett des Graphen für die Beziehung α genommen wird . Diese Operation ist im Wesentlichen die Umkehrung der transitiven Schließoperation , bei der Anfang und Ende jedes Netzes durch einen Bogen verbunden sind.



Im allgemeinen Fall ist die Transitivitätseigenschaft in Bezug auf die Operation des Kombinierens von Beziehungen nicht erfüllt. Zwei transitive Beziehungen kombinieren$$$α_1$ und $$$α_2$ist genau dann transitiv, wenn einer von ihnen in Bezug auf den anderen transitiv ist. Für ein Paar binärer Beziehungen$$$α_1$ und $$$α_2$man kann die Transitivität eines von ihnen relativ zum anderen betrachten.



Damit$$$α_1$ist transitiv in Bezug auf $$$α_2$unter folgenden Bedingungen:



1) aus$$$( _i, _k) є α_1 ( _k, _j) є α_2$ sollte $$$(_i, _j) є _1$;;

2) von$$$( _i, _k) є α_2 ( _k, _j) є α_1$ sollte $$$( _i, _j) є α_1$...



In dem Fall, wenn$$$α_1= α_2=α$Die relative Transitivität ist die übliche Transitivität.



Die folgende Aussage ist über die Eigenschaften der Transitivität, Symmetrie und Asymmetrie einer Beziehung bekannt. Wenn eine binäre Beziehung transitiv ist, dann ihr symmetrischer Teil$$$α^{(S)}$ und $$$α^{()}$Der asymmetrische Teil ist ebenfalls transitiv.



Das Gegenteil ist nur dann der Fall, wenn$$$α^{(S)}$, $$$α^{()}$ transitiv und $$$α^{()}$ transitiv relativ $$$α^{(S)}$... Im Allgemeinen von der Transitivität$$$α^{(S)}$ und $$$α^{()}$Die Transitivität von α folgt nicht.



Die Zusammensetzung der transitiven Beziehung α mit sich selbst erfüllt die Beziehung α · α ⊆ α. Eine Beziehung α ist negativ transitiv (nicht transitiv), wenn ihr Komplement transitiv ist, d.h. ᾱ. In der Matrix einer solchen Beziehung [$$$α_{ij}$ ] von $$$α_{ik} = 0$ und $$$α_{kj} = 0$ sollte $$$α_{ij} = 0$... Eine negative Transitivität von α schließt nicht aus, dass α selbst auch transitiv sein kann.



In diesem Fall soll α eine stark transitive Beziehung sein. Matrixelemente [$$$α_{ij}$ ] Eine solche Haltung ist dadurch gekennzeichnet, dass $$$_{ik}·_{kj} =1$ sollte $$$_{ij} = 1$, ein aus $$$_{ik} = _{kj} =0$ sollte $$$_{ij} = 0$...



Zusammen mit stark transitiven Beziehungen betrachten wir schwach transitive (pseudotransitive) Beziehungen, einschließlich jener Beziehungen, aus denen die Bedingungen stammen$$$_iα^{(S)}_$ und $$$_α_j$ sollte $$$_iα_j$... Seine Transitivität ergibt sich aus Asymmetrie und negativer Transitivität.



Eine Beziehung α ist transitiv vollständig, wenn für irgendein δ von$$$_{K1}α_{K2}, _{K2}α_{K3},…, _{K(δ-1)}α_{Kδ}$

folgt die Vergleichbarkeit$$$_{K1}$ und $$$_{Kδ}$d.h. werden entweder durchgeführt$$$_{K1}α_{Kδ}$ oder $$$_{Kδ}α_{K1}$...

Zyklizität

Auf der Menge A definierte Beziehungen können unter dem Gesichtspunkt des Vorhandenseins von Zyklen in ihnen betrachtet werden. Es ist zweckmäßig, eine solche Betrachtung an Graphen von Beziehungen durchzuführen. Ein zyklischer Beziehungsgraph enthält immer mindestens eine geschlossene Kontur (Route). Durch Ignorieren der Pfeile wird der Pfad in eine Schleife umgewandelt. Ein Graph einer azyklischen Beziehung enthält keine Zyklen und wird als azyklisch oder unkontrolliert bezeichnet .



Die Beziehung = <Å, A> ist zyklisch, wenn mindestens eine Kette der Form aus den Elementen der Menge A gebildet werden kann$$$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_{Kδ},_{Kδ}α_{Ki}$beliebige Länge δ. Der Graph M des transitiven Verschlusses für eine zyklische Beziehung enthält mindestens ein Paar ($$$_i, _i$) und für eine azyklische Beziehung enthält α kein solches Paar.



Die Beziehung = <, A> ist azyklisch, wenn für irgendein δ ≥ 1 die Bedingung von$$$_iα_{K1}, _{K1}α_{K2},…, _{K(δ-1)}α_j$ sollte $$$_i ≠ _j$... In der Matrix [$$$α_{ij}$] azyklische Beziehung von $$$_{iK1}_{K1K2}..._{K(δ-1)j}=1$i ≠ j folgt. Die azyklische Beziehung ist immer asymmetrisch, aber das Gegenteil ist nicht der Fall. Mit anderen Worten, wenn einige Spitzen$$$_i$ und $$$_j$Graph α azyklische Beziehungen sind über einen Weg verbunden; dann gibt es keinen Bogen in der Grafik ($$$_j, _i$). Transitive Turniere



sind klassische Beispiele für Grafiken mit dieser Eigenschaft . Die Eckpunkte solcher Graphen können neu nummeriert werden, unter denen für jeden Bogen ($$$_i, _j$) Die Nummer des Scheitelpunkts j ist größer als der Scheitelpunkt i.



Wenn α eine antireflexive transitive binäre Beziehung ist, ist es azyklisch. Die Azyklizität und transitive Vollständigkeit der Beziehung impliziert ihre Transitivität.

Vollständigkeit

Vollständigkeitseigenschaft (Perfektion, Linearität). Die gesamte Reihe von Beziehungen ist in unvollständige und vollständige Beziehungen unterteilt , von denen wiederum stark vollständige hervorstechen. Wir werden die Eigenschaft der Vollständigkeit von Beziehungen anhand von Beziehungsgraphen veranschaulichen.



Der Graph einer vollständigen Beziehung ist vollständig, d.h. zwei beliebige seiner Eckpunkte sind direkt durch mindestens einen Bogen verbunden, d.h. sind benachbart. Da jeder Bogen in der Grafik einem Punkt (Element, Paar) der Grafik der Beziehung entspricht, kann auf der Grundlage der obigen Ausführungen eine Definition formuliert werden.



Die Beziehung = <Å, A> ist genau dann vollständig (perfekt, linear), wenn alle Elemente der Menge A vergleichbar oder gleich sind. Somit ist die allgemeine Einstellung reflektierend. Mit anderen Worten, für zwei beliebige Elemente$$$_i$ und $$$_j$ Messe $$$(_i α _j V _j α _i V _i = _j)$...



Wenn in Beziehung α mindestens ein Paar vorhanden ist$$$_i$, $$$_j$unvergleichliche und ungleiche Elemente, dann ist diese Beziehung unvollständig. Für jedes Gesamtverhältnis α,$$$∆UαUα^{-1}=A×A$ oder von $$$_i ᾱ _j$ sollte $$$_j α _i$... Die binäre Beziehung α ist genau dann vollständig, wenn$$$^{(a)} =^{(d)}$d.h. wenn sein asymmetrischer Teil mit der dualen Beziehung (Punkt 9) zusammenfällt .



Eine binäre Beziehung α ist stark vollständig, wenn ihr Graph mit A × A übereinstimmt. Ein Graph einer solchen Beziehung ist ein vollständiger Graph, in dem jedes Scheitelpunktpaar durch eine Kante verbunden ist und jeder Scheitelpunkt eine Schleife hat. Ein solcher Graph wird als stark vollständiger Graph bezeichnet. Das Gesamtverhältnis α erfüllt immer die Beziehungen$$$ᾱ ⊂ α^{-1}$ und $$$α^{-1}⊂ᾱ ∪(α∩α^{-1})$... Einstellung$$$α∪(ᾱ∩α^{d}) = α∪(ᾱ)^{(S)}$Immer voll.



Wenn$$$α_1$ und $$$α_2$ vollständige Beziehung also $$$α_1·α_2$voll. In der Matrix [$$$α_{ij}$] volle Beziehung $$$α_{ij} = 1$ oder $$$α_{ji} = 1$für jedes i, j oder beide Gleichheiten ist wahr. Eine Beziehung α ist schwach vollständig (schwach verbunden), falls vorhanden$$$_i,_j є A$ so dass $$$_i ≠ _j$oder $$$_i α _j$oder $$$_j α _i$...



In der Matrix [$$$α_{ij}$] einer schwach vollständigen Beziehung für jedes i ≠ j oder $$$α_{ij} = 1$oder $$$α_{ji} = 1$oder beide Gleichheiten sind wahr. Eine Beziehung α ist transitiv vollständig, wenn für ein beliebiges n aus$$$_iα_{K1}, _{K1}α_{K2},…, _{K(n-1)}α_{in}$ Vergleichbarkeit folgt $$$_{i1}≡ _{in}$ jene. $$$_{i1}α _{in}$ oder $$$_{in}α _{i1}$...



Zählen wir die Anzahl der vollständigen Beziehungen. Betrachten Sie zunächst das Leitungsproblem. Eine Linie in einer Verhältnismatrix ist ein gerades Liniensegment senkrecht zur Hauptdiagonale der Verhältnismatrix, das die Zentren zweier Zellen (Zellen) der Matrix verbindet, die symmetrisch zu dieser Diagonale angeordnet sind.



Wenn zwei oder mehr Paare symmetrischer Positionen auf eine Linie (gerade Linie) in der Verhältnismatrix fallen, bleibt die Anzahl der Linien dennoch gleich der Anzahl solcher Positionspaare. Die Gesamtzahl der Positionspaare für ein beliebiges n ist definiert als$$$C_n^2 = L$...



In der Matrix für eine beliebige Beziehung über der Menge A gibt es also eine Menge L paralleler Segmente (Linien). Bezeichnen wir die Endpositionen der Segmente (Linien) durch die Symbole L - links und P - rechts. Auch erhältlich | L | Chips, die an den Enden der Linien platziert werden können. Die Herausforderung besteht darin, die Anzahl der Möglichkeiten zu bestimmen, wie | L | angeordnet werden kann Chips, so dass sich auf jeder Leitung mindestens ein Chip befindet.



Es ist klar, dass das Problem auf die Bestimmung der Anzahl F von Abbildungen f: L → π der Menge L von Linien in die Menge von π-Positionen (n = {A, P}) reduziert werden kann. Es ist bekannt, dass die Anzahl solcher Abbildungen durch die Formel bestimmt wird$$$F = ||^{|L|}$... Eine bestimmte Abbildung (Bild) kann die Form <P, P, L, L, L, ..., L, P> der Folge von Indizes für | haben L | Positionen. Das Symbol L entspricht einer Position unter der Hauptdiagonale und das dazu symmetrische Symbol P über der Diagonale.



Aus der Definition des Gesamtverhältnisses folgt, dass sein Graph mindestens K Punkte enthält, K =$$$C_n^2$lokalisiert: so dass alle Leitungen von mindestens einem Chip belegt sind. Die Anzahl k von Punkten in der Grafik kann zusätzlich zu der minimal erforderlichen Anzahl durch den Wert k = 0 (1) K = laufen$$$C_n^2$...



Für jede feste Anzahl von k Punkten wird die Auswahl der Positionen, an denen sie platziert werden können, durch den Wert bestimmt$$$C_^k$, wobei K die Menge der nicht besetzten Positionen ist. Da k zusätzliche Punkte k Linien vollständig ausfüllen, bleibt es, um die Eigenschaft der Vollständigkeit des Verhältnisses sicherzustellen, K - k Positionen mit Chips zu füllen (Punkte aus der Menge des erforderlichen Minimums), und die Anzahl solcher Füllungen ist$$$2^{-k}$...



Die Wahl der Positionen für k zusätzliche Punkte und die Methoden zum Füllen von K-k Linien mit Chips sind unabhängig. Folglich wird die Gesamtzahl der Möglichkeiten, K + k-Punkte an 2 ∙ K-Positionen zu platzieren, so dass alle Linien von mindestens einem Punkt besetzt sind, durch den Ausdruck bestimmt$$$C_^k ·2^{-k}, k = 0(1).$



Wenn wir diesen Ausdruck summieren, erhalten wir die Anzahl der vollständigen Beziehungen, die nicht von der Situation bei der Platzierung diagonaler Punkte abhängt. Mit anderen Worten, es ist die Anzahl der teilweise reflexiven vollständigen Beziehungen, zum Beispiel antireflexiv und vollständig reflexiv und vollständig usw.



Beispiel 5 . Die Vielfalt der Situationen zum Platzieren diagonaler Punkte wird durch die Anzahl bestimmt$$$2^n$... Dann wird die Kardinalität der Menge aller vollständigen Beziehungen für ein festes n durch die Formel bestimmt



$$$= 2^n·∑_{k=0}^C_^k2^{-k} = ∑_{k=0}^C_^k2^{ + n - k}$...



Für Beziehungen mit drei erforderlichen Eigenschaften



Für Äquivalenzbeziehungen mit drei erforderlichen Eigenschaften. Es gibt ein bemerkenswertes Ergebnis: Jede Äquivalenzbeziehung über eine Menge von n Elementen steht in Eins-zu-Eins-Entsprechung mit einer Partition dieser Menge. Die Anzahl solcher Beziehungen wird durch die Formel bestimmt



$$$B_n = ∑_{m=0}^nS(n, m)$wobei S (n, m) die Stirlingzahl der zweiten Art ist, Bn die Glockennummer ist

oder in wiederkehrender Form



$$$B_{n+1} = ∑_{k=0}^nC_n^kB_k.$



Für geordnete Mengen (Teilbestellungen) sind solche Formeln nicht offen und ihre Anzahl wird durch direkte Berechnungen bestimmt, d.h. Modellieren. Für kleine Werte von n sind die Daten in



Tabelle 6 angegeben . Quantitative Merkmale binärer Beziehungen





Tabelle 6. zeigt: n = | A | - die Kardinalität des Set-Carriers;

$$$2^{n^2}$- die Anzahl aller binären Beziehungen auf der Menge A;

| In (n) | - die Anzahl der Klassen nichtisomorpher Beziehungen;

| (n) | - die Anzahl der Beziehungen teilweiser Ordnung;

| Gn (n) | - Die Anzahl der Klassen sind nicht-isomorphe Beziehungen partieller Ordnung.

| Gl (n) | = n! - die Anzahl der linearen Ordnungsrelationen.

Fazit

In dieser Arbeit wurde eine detaillierte Analyse der Haupteigenschaften und der Struktur des binären Verhältnisses durchgeführt, auf deren Grundlage quantitative Eigenschaften für BO mit einer oder mehreren Eigenschaften erhalten werden konnten. Die ursprünglichen Verhältnisse für die Anzahl einiger Arten von Beziehungen mit zwei und drei erforderlichen Eigenschaften werden gefunden und dargestellt. Diese Ergebnisse eröffnen die Möglichkeit, BO und Beziehungen höherer Arität zu modellieren und zu untersuchen.

Liste der verwendeten Literatur

1. Aigner M. Kombinatorische Theorie. - M.: Mir, 1982.
2. Birkhoff G. Theorie der Strukturen. - M.: IL, 1952.-408 p.
3. Noden P., Kitte K. Algebraische Algorithmen. - M.: Mir, 1999. - 720 p.
4. Rybnikov K.A. Eine Einführung in die kombinatorische Analyse. -M.: Ed. Moskauer Staatliche Universität, 1972. -256s.
5. Stanley R. Enumerative Combinatorics. Vol. 1.- M .: Mir, 1990 .-- 440p.
6. Stanley R. Enumerative Combinatorics. T.2.- M.: Mir, 2005. - 767s.
7. Shikhanovich Yu.A. Einführung in die moderne Mathematik. Anfängliche Konzepte.-M .: Nauka, 1965. - 376p.