Mathematische Grundlagen

Verband

 aufwärts

Verband

Definition:  Eine Menge M mit zwei Ver­knüpfungen  eckiger Durchschnitt  und  eckige Vereinigung  ist ein Verband, wenn für alle a, b, c Element M folgende Bedingungen erfüllt sind:

(a eckige Vereinigung beckige Vereinigung c  =  a eckige Vereinigung (b eckige Vereinigung c) (Assoziativität)
(a eckiger Durchschnitt beckiger Durchschnitt c  =  a eckiger Durchschnitt (b eckiger Durchschnitt c)  
a eckige Vereinigung b  =  b eckige Vereinigung a (Kommutativität)
a eckiger Durchschnitt b  =  b eckiger Durchschnitt a 
a eckige Vereinigung (a eckiger Durchschnitt b)  =  a (Absorption)
a eckiger Durchschnitt (a eckige Vereinigung b)  =  a 

Diese Bedingungen heißen Verbands­axiome.

Satz:  Sei G eine Menge und M = Potenzmenge(G) die Potenzmenge von G, d.h. die Menge aller Teilmengen von G. Dann bildet M mit den Ver­knüpfungen  vereinigt  (Vereinigung) und  Durchschnitt  (Durchschnitt) einen Verband, den Teilmengen­verband von G.

Beweis:  Um den Satz zu beweisen, müssen die Verbands­axiome nach­gerechnet werden. So ist z.B. als erstes zu zeigen, dass für alle Mengen A, B, C Element M gilt

(A vereinigt Bvereinigt C  =  A vereinigt (B vereinigt C)

Nach Definition der Vereinigung von Mengen ist

(A vereinigt Bvereinigt C  =  { x  |  (x Element A oder x Element Boder x Element C }

Mithilfe einer Wahrheits­tafel lässt sich zeigen, dass die logische Oder-Verknüpfung assoziativ ist:

(a oder boder c genau dann wenn a oder (b oder c)   für alle a, b, c.

Damit ist

(A vereinigt Bvereinigt C  =  { x  |  (x Element A oder x Element Boder x Element C }
  =  { x  |  x Element A oder (x Element B oder x Element C) }  =  A vereinigt (B vereinigt C)

In ähnlicher Weise lässt sich auch zeigen, dass die anderen Verbands­axiome gelten.

Satz:  Sei k Element natürliche Zahlen und Tk die Menge der positiven Teiler von k, also z.B. k = 24 und Tk = {1, 2, 3, 4, 6, 8, 12, 24}. Dann sind kgv (kleinstes gemeinsames VielfachesDefinition) und ggt (größter gemeinsamer Teiler) Ver­knüpfungen in Tk. Mit diesen Ver­knüpfungen bildet Tk einen Verband, den Teiler­verband von k.

Beweis:  Zunächst ist zu zeigen, dass die Verknüpfung ggt assoziativ ist, d.h. dass für alle a, b, c Element Tk gilt

ggt(ggt(a, b), c)  =  ggt(a, ggt(b, c))

Wir zeigen dies, indem wir nachweisen, dass die linke Seite die rechte Seite teilt und umgekehrt, also

ggt(ggt(a, b), c) | ggt(a, ggt(b, c))   und

ggt(a, ggt(b, c)) | ggt(ggt(a, b), c).

 

Sei d = ggt(ggt(a, b), c). Dann gilt nach Definition des größten gemeinsamen Teilers

d | ggt(a, b),  also d | a und d | b,  und d | c.

Dann aber gilt

d | ggt(b, c),  denn d | b und d | c

und ferner

d | ggt(a, ggt(b, c)),  denn d | a und d | ggt(b, c).

Damit ist bewiesen, dass die linke Seite die rechte Seite teilt. Die umgekehrte Richtung lässt sich genauso zeigen.

In ähnlicher Weise lässt sich auch die Assoziativität der Verknüpfung kgv zeigen.

Das dritte und vierte Verbands­axiom fordert die Kommutativität von kgv und ggt. Offen­sichtlich sind kgv und ggt kommutativ.

Schließlich sind noch die Absorptions­gesetze zu beweisen. Dies ist Gegenstand der folgenden Aufgabe.

Aufgabe 1:  Zeigen Sie die Gültigkeit des Absorptions­gesetzes

ggt(a, kgv(a, b))  =  a,

indem Sie nachweisen, dass die linke Seite die rechte Seite teilt und umgekehrt.   Lösung zeigen

Zeigen Sie auf dieselbe Weise die Gültigkeit des anderen Absorptions­gesetzes

kgv(a, ggt(a, b))  =  a.

Satz:  Sei (M,  eckige Vereinigung ,  eckiger Durchschnitt ) ein Verband. Dann gilt für alle a Element M:

a eckige Vereinigung a  =  a (Idempotenz)
a eckiger Durchschnitt a  =  a 

Der Beweis ist Gegenstand der folgenden Aufgabe.

Aufgabe 2:  Sei (M,  eckige Vereinigung ,  eckiger Durchschnitt ) ein Verband. Zeigen Sie, dass die Ver­knüpfungen  eckige Vereinigung  und  eckiger Durchschnitt  idempotent sind.   Lösung zeigen

Boolescher Verband

Definition:  Ein Verband ist ein distributiver Verband, wenn die beiden Distributiv­gesetze gelten:

a eckige Vereinigung (b eckiger Durchschnitt c)  =  (a eckige Vereinigung beckiger Durchschnitt (a eckige Vereinigung c)   und

a eckiger Durchschnitt (b eckige Vereinigung c)  =  (a eckiger Durchschnitt beckige Vereinigung (a eckiger Durchschnitt c)

Beispiel:  Sei G eine Menge. Dann ist der Teilmengen­verband von G ein distributiver Verband.

Definition:  Sei (M,  eckige Vereinigung ,  eckiger Durchschnitt ) ein Verband. Ein Element n Element M heißt Nullelement, wenn es bezüglich der Verknüpfung  eckige Vereinigung  neutral ist, d.h. wenn gilt

a eckige Vereinigung n = a   für alle a Element M.

Ein Element e Element M heißt Einselement, wenn es bezüglich der Verknüpfung  eckiger Durchschnitt  neutral ist, d.h. wenn gilt

a eckiger Durchschnitt e = a   für alle a Element M.

Beispiel:  Sei G eine Menge und M = Potenzmenge(G) der Teilmengen­verband von G. Dann ist die leere Menge  leere Menge  das neutrale Element bezüglich der Verknüpfung  vereinigt , denn es gilt für alle Mengen A Element Potenzmenge(G)

A vereinigt  leere Menge  = A.

Die Grundmenge G ist das neutrale Element bezüglich der Verknüpfung  Durchschnitt . Jede Menge A Element Potenzmenge(G) ist ja Teilmenge von G, und daher gilt

A Durchschnitt G = A.

Aufgabe 3:  Sei (M,  eckige Vereinigung ,  eckiger Durchschnitt ) ein Verband mit Nullelement n und Einselement e. Zeigen Sie, dass Nullelement und Einselement jeweils eindeutig bestimmt sind (zeigen Sie, indem Sie die Definition des Null- bzw. Eins­elementes heranziehen: wenn m und n Nullelemente sind, folgt m = n, bzw. wenn d und e Einselemente sind, folgt d = e).   Lösung zeigen

Aufgabe 4:  Sei (M,  eckige Vereinigung ,  eckiger Durchschnitt ) ein Verband mit Nullelement n und Einselement e. Zeigen Sie mithilfe der Absorptions­gesetze, dass für alle a Element M gilt:

a eckiger Durchschnitt n = n   und

a eckige Vereinigung e = e.

Aufgabe 5:  Zeigen Sie, dass jeder endliche Verband ein Nullelement und ein Einselement hat.

Anleitung: Sei (M,  eckige Vereinigung ,  eckiger Durchschnitt ) ein Verband, wobei M = {a1, ..., am} eine endliche Menge ist. Zeigen Sie mit mithilfe der Absorptions­gesetze, dass

n  =  a1 eckiger Durchschnitt . . . eckiger Durchschnitt am

das Nullelement ist, d.h. dass für jedes ai Element M gilt

ai eckige Vereinigung n = ai.

Führen Sie einen ent­sprechenden Nachweis für das Einselement.

Aufgabe 6:  Sei k Element natürliche Zahlen und Tk der Teiler­verband von k. Welches Element von Tk ist das neutrale Element n der Verknüpfung kgv und welches Element ist das neutrale Element e der Verknüpfung ggt?

Definition:  Sei (M,  eckige Vereinigung ,  eckiger Durchschnitt ) ein Verband mit Nullelement n und Einselement e. Zwei Elemente a und a' heißen komplementär zueinander, wenn folgendes gilt:

a eckige Vereinigung a' = e   und

a eckiger Durchschnitt a' = n

Das Element a' ist das Komplement von a (und umgekehrt).

Wenn jedes Element von M ein Komplement hat, dann heißt der Verband M komplementär.

Beispiel:  Sei G eine Menge. Dann ist der Teilmengen­verband von G ein komplementärer Verband. Das Komplement einer jeweiligen Menge A Element Potenzmenge(G) ist die Menge G \ A = { x  |  x Element G  und  x nicht Element A}.

Bemerkung:  Bisher haben wir eine Menge mit zwei Ver­knüpfungen, Assoziativität, Kommutativität, Distributivität, neutrale Elemente, und mit dem Komplement jetzt auch noch eine Art inverses Element. Die entstehende Struktur hat auf den ersten Blick große Ähnlichkeit mit einem Körper.

Tatsächlich jedoch ist das Komplement etwas anderes als ein inverses Element in einem Körper. Wird in einem Körper ein Element mit seinem inversen Element verknüpft, so kommt das neutrale Element bezüglich derselben Verknüpfung heraus. Wird dagegen in einem Verband ein Element mit seinem Komplement verknüpft, so kommt zwar auch ein neutrales Element heraus, aber das neutrale Element bezüglich der anderen Verknüpfung. Bild 1 zeigt schematisch diese Situation; die beiden Ver­knüpfungen sind einheitlich mit + und · bezeichnet, die neutralen Elemente mit 0 und 1.

Bild 1: Unterschied zwischen inversen Elementen und Komplement
Bild 1: Unterschied zwischen inversen Elementen und Komplement

Definition:  Ein distributiver, komplementärer Verband wird Boolescher Verband oder Boolesche Algebra genannt (nach G. Boolezur Person).

Aufgabe 7:  Zeigen Sie, dass der Teiler­verband von 24 nicht komplementär ist und deshalb kein Boolescher Verband ist (zeigen Sie: es gibt ein Element in T24, das kein Komplement hat).

Aufgabe 8:  Zeigen Sie, dass der Teiler­verband von 42 komplementär ist (zeigen Sie: alle Elemente in T42 haben ein Komplement).

Halbordnung

In jedem Verband lässt sich vermittels der Ver­knüpfungen  eckige Vereinigung  und  eckiger Durchschnitt  eine Halbordnung  eckige Teilmenge  definieren.

Definition:  Sei (M,  eckige Vereinigung ,  eckiger Durchschnitt ) ein Verband. Auf M sei die Relation  eckige Teilmenge  wie folgt definiert:

a eckige Teilmenge b genau dann wenn a eckige Vereinigung b = b     für alle a, b Element M.

Behauptung:  Die Relation  eckige Teilmenge  ist eine Halbordnung.

Aufgabe 9:  Zeigen Sie, dass die Relation  eckige Teilmenge  eine Halbordnung ist. Es ist zu zeigen, dass die Relation reflexiv, anti­symmetrisch und transitiv ist, d.h. dass für alle a, b, c Element M gilt:

a eckige Teilmenge a

a eckige Teilmenge b   und   b eckige Teilmenge a  folgt  a = b

a eckige Teilmenge b   und   b eckige Teilmenge c  folgt  a eckige Teilmenge c

Aufgabe 10:  Zeigen Sie unter Anwendung des Absorptions­gesetzes, dass folgendes gilt

a eckige Teilmenge b genau dann wenn a eckiger Durchschnitt b = a     für alle a, b Element MHinweis zur Lösung zeigen

Beispiel:  Im Teilmengen­verband einer Menge G ist die Relation  enthalten in  ("ist enthalten in", "ist Teilmenge von") die ent­sprechende Halbordnung; im Teiler­verband einer Zahl k ist die Relation | ("teilt") die ent­sprechende Halbordnung.

Typisch für eine Halbordnung ist, dass im allgemeinen nicht jedes Element mit jedem anderen vergleichbar ist (wie dies bei einer totalen Ordnung der Fall ist). So ist z.B im Teilmengen­verband der Menge G = {1, 2, 3} die Menge {1, 2} weder eine Teilmenge von {2, 3}, noch umgekehrt. Im Teiler­verband T24 ist 6 kein Teiler von 8, und umgekehrt auch nicht.

Hasse-Diagramm

Bei einem endlichen Verband M lässt sich mithilfe des Hasse-Diagramms ver­anschaulichen, welche Elemente miteinander vergleichbar sind.

Definition:  Sei M eine endlicher Verband mit einer Halbordnung  eckige Teilmenge  und sei eckig enthalten die zu  eckige Teilmenge  gehörige strenge Halbordnung. Das Hasse-Diagramm von M ist ein gerichteter Graph G = (M, E) mit der Knotenmenge M. Zwei Knoten u, w Element M werden durch eine Kante verbunden, wenn ueckig enthaltenw gilt und es kein v Element M gibt mit ueckig enthaltenveckig enthaltenw.

Beispiel:  Der Teiler­verband T24   =  {1, 2, 3, 4, 6, 8, 12, 24} hat folgendes Hasse-Diagramm (Bild 2):

Bild 2: Hasse-Diagramm des Teilerverbandes T24
Bild 2: Hasse-Diagramm des Teilerverbandes T24

Die Knoten werden so angeordnet, dass die Kanten stets von unten nach oben gerichtet sind. Richtungs­pfeile an den Kanten können dann weggelassen werden.

Beispiel:  Der Teiler­verband T42   =  {1, 2, 3, 7, 6, 14, 21, 42} hat folgendes Hasse-Diagramm (Bild 3):

Bild 3: Hasse-Diagramm des Teilerverbandes T42
Bild 3: Hasse-Diagramm des Teilerverbandes T42

 

Weiter mit:   [Matrix]   [Literatur]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 14.08.2003   Updated: 21.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik