TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 451

Man zeige, dass die folgenden algebraischen Strukturen Verbände sind. Welche sind außerdem distributiv, und welche sind Boolesche Algebren

a) $(\mathbb {R} ,\mathrm {min} ,\mathrm {max} )$

b) $(\mathbb {N} \setminus \{0\},\mathrm {ggT} ,\mathrm {kgV} )$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Verband äquivalent Halbordnung

Verband äquivalent Halbordnung

Satz (Idee von Leibniz):

Nach einer Idee von Leibniz kann man einen Verband $(M,\wedge ,\vee )$ auch als eine Halbordnung darstellen (und umgekehrt). Zwischen dem Verband und der Halbordnung muss dann folgende Beziehung bestehen:

$a\leq b\quad \iff \quad a=a\wedge b\quad \iff \quad b=a\vee b\quad$

Anders ausgedrückt:

$\mathrm {inf} (a,b)\iff a\wedge b\qquad \mathrm {sup} (a,b)\iff a\vee b$

Lösungsvorschlag für a) von Piri

Verband?

Bekanntlicher Weise bildet $\mathbb {R}$ mit der Relation $aRb\Longleftrightarrow a\leq b$ eine Totalordnung. Da

$\mathrm {inf} (a,b)\iff \mathrm {min} (a,b)\qquad \mathrm {sup} (a,b)\iff \mathrm {max} (a,b)$

gilt folgt daraus, dass es sich um einen Verband handelt.

Distributiver Verband?

Damit der Verband distributiv ist müssen

1. $\mathrm {min} (a,\mathrm {max} (b,c))=\mathrm {max} (\mathrm {min} (a,b),\mathrm {min} (a,c))$

2. $\mathrm {max} (a,\mathrm {min} (b,c))=\mathrm {min} (\mathrm {max} (a,b),\mathrm {max} (a,c))$

gezeigt werden. Um das zu zeigen können wir einfach naiv für alle Permutationen von $a\leq b\leq c$ in die Formeln einsetzen. Da aber die Rollen von b und c vertauschbar sind kann man es von 6 auf 3 Permutationen reduzieren:

1. $a\leq b\leq c$

2. $b\leq a\leq c$

3. $b\leq c\leq a$

Nun setzt man für die 3 Permutationen in die Formeln ein und sieht, dass die Distributivgesetze für alle Permutationen gelten. Daraus folgt, dass es sich um einen distributiven Verband handelt.

Anmerkung 1: Es reicht eigentlich nur 1. Distributivgesetz zu zeigen, das andere folgt daraus. Wir haben den Beweis meines Wissens nach nicht in der Vorlesung geführt, er findet sich aber auf Wikipedia wieder.

Anmerkung 2: Laut Wikipedia ist jede total geordnete Menge ein distributiver Verband, mir fehlt jedoch der Beweis deswegen habe ich das in meiner Lösung nicht verwendet.

Boolesche Algebra?

Damit es sich um eine Boolesche Algebra handelt muss es ein 1-Element bzgl. $\mathrm {min}$ geben. Das es kein 1-Element geben kann lässt sich schnell zeigen:

Nehmen wir an es gibt ein 1-Element $m\in \mathbb {R}$. D.h. es muss $\mathrm {min} (a,m)=a$ gelten.

Da $m\in \mathbb {R}$ ist auch $(m+1)\in \mathbb {R}$. Daraus ergibt sich der Widerspruch $\mathrm {min} (m+1,m)=m$

Also handelt es sich um keine Boolesche Algebra!

Lösungsvorschlag für b) von neo

Dass $(\mathbb {N} \setminus \{0\},ggT,kgV\})$ ein Verband ist, beweist man genauso wie oben mit der Idee von Leibniz.

$aRb\Leftrightarrow a\leq b$...Totalordnung auf $\mathbb {R}$, also auch auf $\mathbb {N} \setminus \{0\}$, da $\mathbb {N} \setminus \{0\}\subseteq \mathbb {R}$
$\forall a,b\in \mathbb {N} \setminus \{0\}:ggT(a,b)\leq kgV(a,b)$
$a\land b=ggT(a,b)=inf(a,b)$
$a\lor b=kgV(a,b)=sup(a,b)$
$\Rightarrow (\mathbb {N} \{0\},ggT,kgV)\,\,{\widehat {=}}\,\,Verband$

Nun folgt der Beweis der Distributivität, welcher ein wenig Hintergrundinfo bedarf (genaueres im orangen Buch 4.Auflage Seite 19):
Wenn für eine Primzahl $p\in \mathbb {P}$ gilt $p^{k}|a$, so schreibt man:$k=v_{p}(a)$
Des Weiteren lassen sich ggT bzw. kgV folgendermaßen darstellen:

$ggT(a,b)=\prod _{p\in \mathbb {P} }{p^{min\{v_{p}(a),v_{p}(b)\}}}$
$kgV(a,b)=\prod _{p\in \mathbb {P} }{p^{max\{v_{p}(a),v_{p}(b)\}}}$

Wir müssen beweisen:
$a\land (b\lor c)=(a\land b)\lor (a\land c)$
$ggT(a,kgV(b,c)=kgV(ggT(a,b),ggT(a,c))$

Da sich ggT bzw. kgV nur bei den Potenzen von $p$ unterscheiden ($p^{a}*p^{b}=p^{a+b}$), kann man schreiben:
$x=v_{p}(a),y=v_{p}(b),z=v_{p}(c)$ und es gelte: $x\leq y\leq z$
$min(x,max(y,z))=max(min(x,y),min(x,z))$
$min(x,z)=max(x,x)$
$x=x\,\,\Rightarrow distributiv$
Da weder ggT noch kgV ein neutrales Element besitzen, ist $(\mathbb {N} \setminus \{0\},ggT,kgV)$ ein distributiver Verband.

Hilfsmittel von Har203

Halbgruppe

Eine Halbgruppe ist ein geordnetes Paar $\left\langle H,\circ \right\rangle$ bestehend aus einer Menge $H$ und einer inneren zweistelligen Verknüpfung

$\circ \colon \,H\times H\to {H},\,(a,b)\mapsto {a}\circ b\,\in H\,,$

die „abgeschlossen“ ist, d.h.

$a,b\in H\implies \mathbf {a\circ b\in H}$

und assoziativ ist, d.h.

$\forall \,a,b,c\,\in H$ gilt$\colon \;(a\circ b)\circ c=a\circ (b\circ c)$

Verband

Eine algebraische Struktur $(M,\wedge ,\vee )$ heißt Verband, wenn folgende Eigenschaften für alle $a,\,b\in M$ erfüllt sind:

1. $(M,\wedge )$ ist eine kommutative Halbgruppe,
2. $(M,\vee )$ ist eine kommutative Halbgruppe, und
3. es gelten die Verschmelzungsgesetze

${\begin{alignedat}{1}\left.{\begin{aligned}\quad a&=a\wedge (a\vee b)\\\quad a&=a\vee (a\wedge b)\end{aligned}}\quad \right\rbrace \quad \forall \;a,b\,\in H\end{alignedat}}$

Die Verschmelzungsgesetze erscheinen etwas künstlich gewählt und vermitteln keine direkte Intuition. Sie haben aber weit reichende Folgerungen. Beispielsweise folgt daraus

$a\wedge a=a\wedge (a\vee (a\wedge b))=a\qquad$ und $\qquad a\vee a=a$

Halbordnung

Es besteht ein enger Zusammenhang zwischen Verbänden und (speziellen) Halbordnungen, nämlich solchen, die zu je zwei Elementen $a,\,b$ ein Infimum $\inf(a,\,b)$ und ein Supremum $\sup(a,\,b)$ besitzen.

Ein Element $c$ einer Halbordung heißt Infimum zweier Elemente $a,\,b$ (und wird mit $\inf(a,\,b)$ bezeichnet), wenn $c\leq a$ und $c\leq b$ ist und für jedes Element $d$ mit $d\leq a$ und $d\leq b$ auch $d\leq c$ gilt. Entsprechend heißt ein Element ${\overline {c}}$ Supremum zweier Elemente $a,\,b\in M$ (und wird mit $\sup(a,\,b)$ bezeichnet), wenn $a\leq {\overline {c}}$ und $b\leq {\overline {c}}$ ist und für jedes Element ${\overline {d}}$ mit $a\leq {\overline {d}}$ und $b\leq {\overline {d}}$ auch ${\overline {c}}\leq {\overline {d}}$ gilt. Man beachte, dass aus der Antisymmetrie-Eigenschaft einer Halbordnung folgt, dass ein $\mathbf {\inf(a,b)}$ bzw. ein $\mathbf {\sup(a,\,b)}$, falls es existiert, eindeutig bestimmt ist.

Sei $(M,\wedge ,\vee )$ ein Verband. Dann wird durch

$a\leq b\iff a=a\wedge b$

auf $M$ eine Halbordnung definiert. In dieser Halbordnung gibt es zu je zwei Elementen ein Infimum, nämlich

$\inf(a,\,b)=a\wedge b\quad$ und ein Supremum $\quad \sup(a,\,b)=a\vee b$.

Ist umgekehrt $\mathbf {\leq }$ eine Halbordnung auf $M$ mit der Eigenschaft, dass es zu je zwei Elementen ein Infimum und ein Supremum gibt, so ist $M$ mit den Operationen

$a\wedge b=\inf(a,\,b)\qquad$ und $\qquad a\vee b=\sup(a,\,b)$ 

ein Verband.

Da jede (endliche) Halbordnung durch ein Hassediagramm dargestellt werden kann, ist es auch möglich, einen Verband durch das Hassediagramm der entsprechenden Halbordnung zu repräsentieren.

Ein Verband $(M,\wedge ,\vee )$ heißt distributiver Verband, wenn die Distributivgesetze

${\begin{alignedat}{1}\left.{\begin{aligned}a\wedge (b\vee c)&=(a\wedge b)\vee (a\wedge c)\\a\vee (b\wedge c)&=(a\vee b)\wedge (a\vee c)\end{aligned}}\quad \right\rbrace \quad \forall \;a,b,\,c\,\in H\end{alignedat}}$

Boole'sche Algebra

Gewisse Verbände haben außer den Distributivgesetzen noch weitere Eigenschaften.

Beispielsweise hat der Verband $(P(A),\cap ,\cup )$ aus Beispiel 2.81 (a) die ganze Menge $A$ als gemeinsame obere Schranke und die leere Menge $\emptyset$ als gemeinsame untere Schranke. Diese Elemente sind dann natürlich neutrale Elemente für $\cap$ und $\cup$. Weiters gibt es zu jeder Menge $B\in P(A)$ das Komplement $B^{'}=A\setminus B$ mit den Eigenschaften $\inf(B,\,B^{'})=B\cap B^{'}=\emptyset$ und $\sup(B,B^{'})=B\cup B^{'}=A$. Der Verband $(P(A),\cap ,\cup )$ bildet eine so genannte Boole'sche Algebra.

Ein distributiver Verband $(M,\wedge ,\vee )$ heißt Boole'sche Algebra, wenn er die folgenden beiden zusätzlichen Eigenschaften besitzt:

1. Es gibt ein neutrales Element $\mathbf {1} \in M$ bezüglich $\wedge$ und es gibt ein neutrales Element $\mathbf {0} \in M$ bezüglich $\vee$, d.h. $(M,\wedge )$ und $(M,\vee )$ sind Monoide.
2. Zu jedem $a\in M$ gibt es ein Komplement $a'\in M$ mit $a\vee a'=\mathbf {1}$ und $a\wedge a'=\mathbf {0}$.

Eine Boole'sche Algebra $(M,\wedge ,\vee )$ hat die folgenden Eigenschaften:

1. Für alle $a\in M$ gilt $a\vee \mathbf {1} =\mathbf {1}$ und $a\wedge \mathbf {0} =\mathbf {0}$.
2. Gelten für ein $b\in M$ die Beziehungen $a\vee b=\mathbf {1}$ und $a\wedge b=\mathbf {0}$, so ist $a'=b$.
3. Für alle $a\in M$ gilt $(a')'=a$.
4. Für alle $a,\,b\in M$ gelten die DeMorgan'schen Regeln

${\begin{matrix}\neg {(a\wedge b)}\iff \neg {a}\vee \neg {b}\\\neg {(a\vee b)}\iff \neg {a}\wedge \neg {b}\end{matrix}}$ mit anderer Notation: ${\begin{matrix}{\overline {(a\wedge b)}}\iff {\overline {a}}\vee {\overline {b}}\\{\overline {(a\vee b)}}\iff {\overline {a}}\wedge {\overline {b}}\;.\end{matrix}}$

Lösung von Beispiel 451/A Har203

Für jeden der beiden Teile des Beispiels ist zu zeigen:

Halbgruppe

1. Die Halbgruppe ist abgeschlossen ist, d.h. $a,b\in H\implies \mathbf {a\circ b\in H}$ und
2. Die Halbgruppe ist assoziativ ist, d.h. $\forall \,a,b,c\,\in H$ gilt$\colon \;(a\circ b)\circ c=a\circ (b\circ c)$

Verband

1. Der Verband $(M,\wedge )$ ist eine kommutative Halbgruppe,
2. Der Verband $(M,\vee )$ ist eine kommutative Halbgruppe, und

$\quad$Es gelten die beiden Verschmelzungsgesetze:

$a=a\wedge (a\vee b)$ und $a=a\vee (a\wedge b)\quad \forall \;a,b\,\in H$

Distributiver Verband

1. Distributivgesetz: $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$ und
2. Distributivgesetz: $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$

Boole'sche Algebra

1. Neutrales Element $\mathbf {0} \in M$ bezüglich $\wedge$ und ein
2. Neutrales Element $\mathbf {1} \in M$ bezüglich $\vee$.
3. Komplement : $\forall \;a\in M$ gibt es ein Komplement $a'\in M$ mit $a\vee a'=\mathbf {1}$ und $a\wedge a'=\mathbf {0}$.

V=(R, min, max)

Abgeschlossen

${\begin{alignedat}{1}&{\text{Sei }}\,a,b\in \mathbb {R} \colon \,\,&\min(\,a,\ b)&=a\;\lor \;&min(\,a,\ b)=&b\implies &\min &{\text{ ist abgeschlossen.}}\\&{\text{Sei }}\,a,b\in \mathbb {R} \colon \,\,&\max(\,a,\ b)&=a\;\lor \;&max(\,a,\ b)=&b\implies &\max &{\text{ ist abgeschlossen.}}\end{alignedat}}$

Assoziativität

• Tabelle für die Assoziativität

Anordnung	$\min(x,y)$			Assotiativgesetz für $\mathbf {\min }$		$\max(x,y)$			Assotiativgesetz für $\mathbf {\max }$
	$(a,b)$	$(b,c)$	$(a,c)$	$(\min(a,b),c)$	$(a,\min(b,c))$	$(a,b)$	$(b,c)$	$(a,c)$	$(\max(a,b),c)$	$(a,max(b,c))$
$a\leq b\leq c$	$a$	$b$	$a$	$\min(a,c)=a$	$\min(a,b)=a$	$b$	$c$	$c$	$\max(b,c)=c$	$\max(a,c)=c$
$b\leq a\leq c$	$b$	$b$	$a$	$\min(b,c)=b$	$\min(a,b)=b$	$a$	$c$	$c$	$\max(a,c)=c$	$\max(a,c)=c$
$b\leq c\leq a$	$b$	$b$	$c$	$\min(b,c)=b$	$\min(a,b)=b$	$a$	$c$	$a$	$\max(a,c)=a$	$\max(a,c)=a$
$c\leq b\leq a$	$b$	$c$	$c$	$\min(b,c)=c$	$\min(a,c)=c$	$a$	$b$	$a$	$\max(a,c)=a$	$\max(a,b)=a$
$a\leq c\leq b$	$a$	$c$	$a$	$\min(a,c)=a$	$\min(a,c)=a$	$b$	$b$	$c$	$\max(b,c)=b$	$\max(a,b)=b$
$c\leq a\leq b$	$a$	$c$	$c$	$\min(a,c)=c$	$\min(a,c)=c$	$b$	$b$	$a$	$\max(b,c)=b$	$\max(a,b)=b$

• assoziativ $\mathbf {\min }$: $\min(\min(a,b),c)=\min(a,\min(b,c))$

In den beiden Spalten $\min(\min(a,b),c)$ und $\min(a,\min(b,c))$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $a,b,c\in \mathbb {R}$ eine Übereinstimmung besteht.

$\quad \implies$ Die Operation $min(a,b)$ ist assoziativ.

• assoziativ $\mathbf {\max }$: $\max(\max(a,b),c)=\max(a,\max(b,c))$

In den beiden Spalten $\max(\max(a,b),c)$ und $\max(a,\max(b,c))$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $a,b,c\in \mathbb {R}$ eine Übereinstimmung besteht.

$\quad \implies$ Die Operation $max(a,b)$ ist assoziativ.

Kommutativität

• Tabelle für die Kommutativität, usw

Anordnung	$\min(x,y)$		Verschmelzungsgesetze		$\max(x,y)$
	$(a,b)$	$(b,a)$	$\min(a,\max(a,b))$	$\max(a,\min(a,b))$	$(a,b)$	$(b,a)$
$a\leq b$	$a$	$a$	$min(a,b)=a$	$\max(a,a)=a$	$b$	$b$
$b\leq a$	$b$	$b$	$\min(a,a)=a$	$\max(a,b)=a$	$a$	$a$

• kommutativ $\mathbf {\min }$: $\min(a,b)=\min(b,a)$

In den beiden Spalten $\min(a,b)$ und $\min(b,a)$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $a,b\in \mathbb {R}$ eine Übereinstimmung besteht.

$\quad \implies$ Die Operation $min(a,b)$ ist kommutativ.

• kommutativ $\mathbf {\max }$: $\max(a,b)=\max(b,a)$

In den beiden Spalten $\max(a,b)$ und $\max(b,a)$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $a,b\in \mathbb {R}$ eine Übereinstimmung besteht.

$\quad \implies$ Die Operation $max(a,b)$ ist kommutativ.

Verschmelzungsgesetze

$a=\min(a,\max(a,b))$ und $a=\max(a,\min(a,b))\quad \forall \;a,b\,\in \mathbb {R}$

Verschmelzungsgesetz: $a=\min(a,\max(a,b))$:

In der Spalte $\min(a,\max(a,b))$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $a,b\in \mathbb {R}$ als Ergebnis $a$ resultiert.

Verschmelzungsgesetz: $a=\max(a,\min(a,b))$: In der Spalte $\max(a,\min(a,b))$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $a,b\in \mathbb {R}$ als Ergebnis $a$ resultiert.

$\quad \implies$ Die beiden Verschmelzungsgesetze gelten.

Distributivgesetz

Die beiden Distributivgesetze

$\min(a,\max(b,c))=\max(\min(a,b),\min(a,c))$ und $\max(a,\min(b,c))=\min(\max(a,b),\max(a,c))$

• Tabelle für die Distributivität

Anordnung	$\min(x,y)$			$\max(x,y)$			Distributivgesetze
	$(a,b)$	$(b,c)$	$(a,c)$	$(a,b)$	$(b,c)$	$(a,c)$	$\min(a,\max(b,c))$	$\max(\min(a,b),\min(a,c))$	$\max(a,\min(b,c))$	$\min(\max(a,b),\max(a,c))$
$a\leq b\leq c$	$a$	$b$	$a$	$b$	$c$	$c$	$\min(a,c)=a$	$\max(a,a)=a$	$\max(a,b)=b$	$\min(b,c)=b$
$b\leq a\leq c$	$b$	$b$	$a$	$a$	$c$	$c$	$\min(a,c)=a$	$\max(b,a)=a$	$\max(a,b)=a$	$\min(a,c)=a$
$b\leq c\leq a$	$b$	$b$	$c$	$a$	$c$	$a$	$\min(a,c)=c$	$\max(b,c)=c$	$\max(a,b)=a$	$\min(a,a)=a$
$c\leq b\leq a$	$b$	$c$	$c$	$a$	$b$	$a$	$\min(a,b)=b$	$\max(b,c)=b$	$\max(a,c)=a$	$\min(a,a)=a$
$a\leq c\leq b$	$a$	$c$	$a$	$b$	$b$	$c$	$\min(a,b)=a$	$\max(a,a)=a$	$\max(a,c)=c$	$\min(b,c)=c$
$c\leq a\leq b$	$a$	$c$	$c$	$b$	$b$	$a$	$\min(a,b)=a$	$\max(a,c)=a$	$\max(a,c)=a$	$\min(b,a)=a$

Distributivgesetz: $\min(a,\max(b,c))=\max(\min(a,b),\min(a,c))$:

In den beiden Spalten $\min(a,\max(b,c))$ und $\max(\min(a,b),\min(a,c))$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $a,b,c\in \mathbb {R}$ eine Übereinstimmung besteht.

Distributivgesetz: $\max(a,\min(b,c))=\min(\max(a,b),\max(a,c))$:

In den beiden Spalten $\max(a,\min(b,c))$ und $\min(\max(a,b),\max(a,c))$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $a,b,c\in \mathbb {R}$ eine Übereinstimmung besteht.

$\quad \implies$ Die beiden Distributivgesetze gelten.

Boole'sche Algebra

Für beide Operationen gibt es kein Neutrales Element und keine Definition für ein Komplement. $\implies$ Es handelt sich um keine Boole'sche Algebra.

Gesamtergebnis: $\implies$ Wir haben mit $(\mathbb {R} ,\min ,\max )$ einen distributiven Verband, der aber keine Boole'sche Algebra ist.

Lösung von Beispiel 451/B Har203

Man zeige, dass die folgenden algebraischen Strukturen Verbände sind. Welche sind außerdem distributiv, und welche sind Boolesche Algebren ?

$(\mathbb {N} \setminus {\{0\}},\mathrm {ggT} ,\mathrm {kgV} )$

Zuerst setzen wir die Menge $V:=\mathbb {N} \setminus {\{0\}}$ auf unseren Arbeitsbereich.

Wir schauen uns die Definition des größten gemeinsamen Teilers ($\operatorname {ggT} (a,\ b)$) bzw. des kleinsten gemeinsamen Vielfachen ($kgV$) genauer an

Berechnung des ggT mittels Primfaktorzerlegung

Für die Berechnung mittels Primfaktorzerlegung zweier Zahlen $a$ und $b$ verwendet man alle Primfaktoren, die in jeder der beiden Zahlen vorkommen, mit der jeweils kleinsten vorkommenden Potenz.

Anmerkung: Die Primfaktorzerlegung der $1$ kann als leeres Produkt betrachtet werden: $\prod _{i=1}^{0}=1$. Das leere Produkt hat den Wert $1$ (das neutrale Element der Multiplikation) – ebenso wie die leere Summe stets $0$ (das neutrale Element der Addition) ergibt. Dadurch haben wir beim $\operatorname {ggT} (a,\ b)$ kein Problem mit der Darstellung der Zahl $1$. Anderenfalls hätten wir die Zahl $1$ zusätzlich in die Menge der Primfaktoren aufnehmen müssen. Speziell: $\operatorname {ggT} (1,1)=1$ und die dazugehörende Primfaktorenzerlegung ist $\emptyset$.

Gegeben seien die Primfaktorzerlegungen:

$\left.{\begin{alignedat}{1}a=&p_{1}^{\alpha _{1}}&\cdot p_{2}^{\alpha _{2}}&\cdot \;\ldots \;\cdot &p_{m}^{\alpha _{m}}\\b=&p_{1}^{\beta _{1}}&\cdot p_{2}^{\beta _{2}}&\cdot \;\ldots \;\cdot &p_{m}^{\beta _{m}}\\c=&p_{1}^{\gamma _{1}}&\cdot p_{2}^{\gamma _{2}}&\cdot \;\ldots \;\cdot &p_{m}^{\gamma _{m}}\end{alignedat}}\qquad \right\rbrace \quad {\text{ mit }}\;\alpha _{i},\beta _{i}{\text{ und }}\,\gamma _{i}{\text{ als den Exponenten des Primfaktors }}p_{i}{\text{ der Zahlen }}a,b{\text{ und }}\,c\ \in V({\text{ für }}i=1,\ldots ,m).$

Anmerkung: Da $a.b$ und $c$ ganze Zahlen ($a,b,c\in V$) sind, sind alle diese Exponenten $\alpha _{i},\beta _{i},\gamma _{i}\in \mathbb {N} _{0}$ und $\geq 0$. Der Wert $0$ für $\alpha _{i},\beta _{i}$ und $\gamma _{i}$ kommt vor, wenn einer dieser Primfaktoren in einer der Zahlen gar nicht enthalten ist.

Wir können den $\operatorname {ggT} (a,\ b)$ auf zwei Arten definieren:

• Der $\operatorname {ggT} (a,\ b)$ zweier ganzen Zahlen $a$ und $b$, von denen mindestens eine ungleich Null ist, ist die größte ganze Zahl $m$, so dass $m$ ein Teiler sowohl von $a$ als auch von $b$ ist. Das heißt, es gibt ganze Zahlen $\alpha$ und $\beta$ , so dass $a=m\cdot \alpha$ und $b=m\cdot \beta$ ist und $m$ die größte Zahl mit dieser Eigenschaft ist.
• Der $\operatorname {ggT} (a,\ b)$ berechnet sich zu

$\operatorname {ggT} (a,\ b)=\prod _{i=1}^{m}{p_{i}^{\min(\alpha _{i},\ \beta _{i})}}\qquad$mit $\min(\alpha _{i},\ \beta _{i})$ als dem kleinsten Exponenten des Primfaktors $p_{i}$ beider Zahlen.

Wir können das $\operatorname {kgV} (a,\ b)$ auf zwei Arten definieren:

• Das kleinste gemeinsame Vielfache zweier ganzer Zahlen $a$ und $b$ ist die kleinste positive natürliche Zahl, die sowohl Vielfaches von $a$ als auch Vielfaches von $b$ ist. Zusätzlich wird für den Fall $a=0$ oder $b=0$ das $\operatorname {kgV}$ definiert als $\operatorname {kgV} (a,\,b):=0$.
• Das $\operatorname {kgV} (a,\ b)$ berechnet sich zu

$\operatorname {kgV} (a,\ b)=\prod _{i=1}^{m}{p_{i}^{\max(\alpha _{i},\ \beta _{i})}}\qquad$mit $\max(\alpha _{i},\ \beta _{i})$ als dem größten Exponenten des Primfaktors $p_{i}$ beider Zahlen.

Für den Verband setzen wir (Operationen: $\wedge \colon \,$ (Infimum) und ($\vee )$ (Supremum)):

$\mathbf {\wedge } =\mathbf {\operatorname {g} gT(a,b)}$ und $\mathbf {\vee } =\mathbf {\operatorname {k} gV(a,b)}$

Halbgruppe

1. Die Halbgruppe ist abgeschlossen, d.h. $\forall \,a,b\in V\implies \mathbf {a\circ b\in V}$ und
2. Die Halbgruppe ist assoziativ, d.h. $\forall \,a,b,c\,\in V$ gilt$\colon \;(a\circ b)\circ c=a\circ (b\circ c)$

Verband

1. Der Verband $(M,\operatorname {ggT} )$ ist eine kommutative Halbgruppe,
2. Der Verband $(M,\operatorname {kgV} )$ ist eine kommutative Halbgruppe
3. Es gelten die Verschmelzugsgesetze: $a=\operatorname {ggT} (\,a,\ \operatorname {kgV} (\,a,\ b\,))$ und $a=\operatorname {kgV} (\,a,\ \operatorname {ggT} (\,a,\ b\,))\quad (\forall \;a,b\,\in V)$

Distributiver Verband

Es müssen die beiden Distributivitätsgetze gelten

${\begin{alignedat}{1}&\operatorname {ggT} &(\,a,\,&\operatorname {kgV} &(\,b,\,c\,))&=\operatorname {kgV} &(\,\operatorname {ggT} &(\,a,\,b\,),\,\operatorname {ggT} &(\,a,\,c\,))\\&\operatorname {kgV} &(\,a,\,&\operatorname {ggT} &(\,b,\,c\,))&=\operatorname {ggT} &(\,\operatorname {kgV} &(\,a,\,b\,),\,\operatorname {kgv} &(\,a,\,c\,))\end{alignedat}}$

Boole'sche Algebra

1. Neutrales Element $\mathbf {0} \in V$ bezüglich $\operatorname {ggT}$ und ein
2. Neutrales Element $\mathbf {1} \in V$ bezüglich $\operatorname {kgV}$.
3. Komplement: $\forall \;a\in V$ gibt es ein Komplement $a'\in V$ mit $\operatorname {kgV} (\,a,a'\,)=\mathbf {1}$ und $\operatorname {ggT} (\,a,\ a')=\mathbf {0}$.

V=(N\{0}, ggT, kgV)

Abgeschlossen

Zu zeigen

${\begin{alignedat}{1}&\forall \,a,\ b\in V\implies &\mathbf {\operatorname {ggT} (a,\ b)} \in V:&{\text{ für }}a,b\in V{\text{ gilt stets }}\operatorname {ggT} (a,\ b)\,&\geq 1\in V\colon \quad &\surd \\&\forall \,a,\ b\in V\implies &\mathbf {\operatorname {kgV} (a,\ b)} \in V:&{\text{ für }}a,b\in V{\text{ gilt stets }}\operatorname {kgV} (a,\ b)\,&\geq \max(a,b)\in V\colon \quad &\surd \end{alignedat}}$

Assoziativität

Zu zeigen

${\begin{alignedat}{1}&\forall \,a,b,c\,\in V{\text{ gilt}}\,\colon \ &\operatorname {ggT} \,(&\operatorname {ggT} (a,\ b),\,c)&=\operatorname {ggT} (a,\ &\operatorname {ggT} (b,\ c))&\\&\forall \,a,b,c\,\in V{\text{ gilt}}\,\colon \ &\operatorname {kgV} (\,&\operatorname {kgV} (a,\ b),\,c)&=\operatorname {kgV} (a,\ &\operatorname {kgV} (b,\ c))&\end{alignedat}}$

• bezüglich $\operatorname {ggT} \,\colon \,\operatorname {ggT} (\operatorname {ggT} (a,\ b),\ c)=\operatorname {ggT} (a,\ \operatorname {ggT} (b,\ c))$

Seien $a,b,c\in V$, dann bildet die Menge $P=\{p_{i}\in \mathbb {N} \,|\,p_{i}\mid {a}\;\lor \;p_{i}\mid {b}\;\lor \;p_{i}\mid {c}\}$ aller Primfaktoren, die in zumindest einer dieser drei Zahlen vorkommt. Mit $\alpha _{i}$ für $a,\beta _{i}$ für $b,\gamma _{i}$ für $c$ wird angegeben, wie oft diese Primzahl ($\,p_{i}\in N$) in der entsprechenden Zahl ($a,\ b,\ c$) vorkommt.

Berechnen wir nun den $\operatorname {ggT} (\operatorname {ggT} (a,\ b),\ c)$ und $\operatorname {ggT} (\,a,\ \operatorname {ggT} (\,b,\ c\,))$

$\left.{\begin{alignedat}{1}&\operatorname {ggT} (\,\operatorname {ggT} (\,a,\ b),\ c\,)&=\,\operatorname {ggT} (\,\prod _{i=1}^{m}{\,p_{i}^{\,\min(\alpha _{i},\ \beta _{i})}},\ c\,)&={\text{ (die }}p_{i}{\text{ zusammenfassen) }}&=\prod _{i=1}^{m}{p_{i}^{\,\min(\,\min(\,\alpha _{i},\ \beta _{i}\,),\ \gamma _{i}\,)}}=\\=&\ (\min {\text{ ist assoziativ}})\ &=\,\prod _{i=1}^{m}\,{p_{i}^{\,\min(\alpha _{i},\ \min(\,\beta _{i},\ \gamma _{i}\,)}}&=\,\operatorname {ggT} (\,a,\ \prod _{i=1}^{m}\,{p_{i}^{\min(\,\beta _{i},\ \gamma _{i}\,)}}&=\operatorname {ggT} (\,a,\ \operatorname {ggT} (\,b,\ c\,))\end{alignedat}}\qquad \right\rbrace \quad \surd$

• bezüglich $\operatorname {kgV} \,\colon \,\operatorname {kgV} (\operatorname {kgV} (a,\ b),\ c)=\operatorname {kgV} (a,\ \operatorname {kgV} (b,\ c))$

Seien $a,b,c\in V$, dann bildet die Menge $P=\{p_{i}\in \mathbb {N} \,|\,p_{i}\mid {a}\;\lor \;p_{i}\mid {b}\;\lor \;p_{i}\mid {c}\}$ aller Primfaktoren, die in zumindest einer dieser drei Zahlen vorkommt. Mit $\alpha _{i}$ für $a,\beta _{i}$ für $b,\gamma _{i}$ für $c$ wird angegeben, wie oft diese Primzahl ($\,p_{i}\in N$) in der entsprechenden Zahl ($a,\ b,\ c$) vorkommt.

Berechnen wir nun das $\operatorname {kgV} (\operatorname {kgV} (a,\ b),\ c)$ und $\operatorname {kgV} (\,a,\ \operatorname {kgV} (\,b,\ c\,))$

$\left.{\begin{alignedat}{1}&\operatorname {kgV} (\,\operatorname {kgV} (\,a,\ b),\ c\,)&=\,\operatorname {kgV} (\,\prod _{i=1}^{m}{\,p_{i}^{\,\max(\alpha _{i},\ \beta _{i})}},\ c\,)&={\text{ (die }}p_{i}{\text{ zusammenfassen) }}&=\prod _{i=1}^{m}{p_{i}^{\,\max(\,\max(\,\alpha _{i},\ \beta _{i}\,),\ \gamma _{i}\,)}}=\\=&\ (\max {\text{ ist assoziativ}})\ &=\,\prod _{i=1}^{m}\,{p_{i}^{\,\max(\alpha _{i},\ \max(\,\beta _{i},\ \gamma _{i}\,)}}&=\,\operatorname {kgV} (\,a,\ \prod _{i=1}^{m}\,{p_{i}^{\max(\,\beta _{i},\ \gamma _{i}\,)}}&=\operatorname {kgV} (\,a,\ \operatorname {kgV} (\,b,\ c\,))\end{alignedat}}\qquad \right\rbrace \quad \surd$

Kommutativität

Berechnen wir nun $\operatorname {ggT} (a,\ b)=\operatorname {ggT} (b,\ a)$ und $\operatorname {kgV} (a,\ b)=\operatorname {kgV} (b,\ a)$)

$\left.{\begin{alignedat}{1}&\operatorname {ggT} (\,a,\ b)&=\prod _{i=1}^{m}{\,p_{i}^{\,\min(\,\alpha _{i},\ \beta _{i}\,)}}&={\text{ KG von min }}=\prod _{i=1}^{m}{\,p_{i}^{\,\min(\,\beta _{i},\ \alpha _{i}\,)}}=\operatorname {ggT} (b,\ a)\end{alignedat}}\quad \right\rbrace \quad \surd$

$\left.{\begin{alignedat}{1}&\operatorname {kgV} (\,a,\ b)&=\prod _{i=1}^{m}{\,p_{i}^{\,\max(\,\alpha _{i},\ \beta _{i}\,)}}&={\text{ KG von max }}=\prod _{i=1}^{m}{\,p_{i}^{\,\max(\,\beta _{i},\ \alpha _{i}\,)}}=\operatorname {kgV} (b,\ a)\end{alignedat}}\quad \right\rbrace \quad \surd$

Verband

Die Verschmelzungsgesetze

$\left.{\begin{alignedat}{1}&1.\,{\text{VG}}\colon \ a=&\,\operatorname {ggT} &(\,a,\ &\operatorname {kgV} &(\,a,\ b\,))&\\&2.\,{\text{VG}}\colon \ a=&\,\operatorname {kgV} &(\,a,\ &\operatorname {ggT} &(\,a,\ b\,))&\end{alignedat}}\quad \right\rbrace \quad \forall \;a,b\,\in V\quad \left\lbrace \quad {\begin{alignedat}{1}&a=\min(a,\max(a,b))=\ &{\textbf {if}}\ a\leq b\ &{\textbf {then}}\ a=\min(a,b)\ &{\textbf {else}}\ a=\min(a,a)\\&a=\max(a,\min(a,b))=\ &{\textbf {if}}\ a\leq b\ &{\textbf {then}}\ a=\max(a,a)\ &{\textbf {else}}\ a=\max(a,b)\end{alignedat}}\right.$

Berechnen wir nun $a=\operatorname {ggT} (a,\ \operatorname {kgV} (a,\ b))$

$\left.{\begin{alignedat}{1}\operatorname {ggT} (a,\ \operatorname {kgV} (a,\ b\,))=\operatorname {ggT} (a,\ \prod _{i=1}^{m}\,{p_{i}^{\,\max(\,\alpha _{i},\ \beta _{i}\,)}})=\prod _{i=1}^{m}\,{p_{i}^{\,\min(\,a,\ \max(\,\alpha _{i},\ \beta _{i}\,))}}=\ (a=\min(a,\ \max(a,\ b)\ =\prod _{i=1}^{m}\,{p_{i}^{\,\alpha _{i}}}=a\end{alignedat}}\qquad \right\rbrace \quad \surd$

Berechnen wir nun $a=\operatorname {kgV} (a,\ \operatorname {ggT} (a,\ b))$

$\left.{\begin{alignedat}{1}\operatorname {kgV} (a,\ \operatorname {ggT} (a,\ b\,))=\operatorname {kgV} (a,\ \prod _{i=1}^{m}\,{p_{i}^{\,\min(\,\alpha _{i},\ \beta _{i}\,)}})=\prod _{i=1}^{m}\,{p_{i}^{\,\max(\,a,\ \min(\,\alpha _{i},\ \beta _{i}\,))}}=\ (a=\max(a,\ \min(a,\ b)\ =\prod _{i=1}^{m}\,{p_{i}^{\,\alpha _{i}}}=a\end{alignedat}}\qquad \right\rbrace \quad \surd$

Distributiver Verband

Berechnen wir nun die beiden Formeln für die Distribitivität

${\begin{alignedat}{1}&\operatorname {ggT} &(\,a,\,&\operatorname {kgV} &(\,b,\,c\,))&=\operatorname {kgV} &(\,\operatorname {ggT} &(\,a,\,b\,),\,\operatorname {ggT} &(\,a,\,c\,))\\&\operatorname {kgV} &(\,a,\,&\operatorname {ggT} &(\,b,\,c\,))&=\operatorname {ggT} &(\,\operatorname {kgV} &(\,a,\,b\,),\,\operatorname {kgv} &(\,a,\,c\,))\end{alignedat}}$

Wir werden diesmal nur die Potenzen dieser Primzahlen, also $\alpha _{i},\beta _{i},\gamma _{i}$ betrachten. Für die Potenzen gilt dann:

$\left.{\begin{alignedat}{1}&\min(\,\alpha _{i},\ &\max(\,\beta _{i},\ &\gamma _{i}\,))&=\max(\,\min(\,\alpha _{i},\ &\beta _{i}\,),\ &\min(\,\alpha _{i},\ &\gamma _{i}\,))\\&\max(\,\alpha _{i},\ &\min(\,\beta _{i},\ &\gamma _{i}\,))&=\min(\,\max(\,\alpha _{i},\ &\beta _{i}\,),\ &\max(\,\alpha _{i},\ &\gamma _{i}\,))\end{alignedat}}\qquad \right\rbrace \quad \surd$

• Tabelle für die Distributivität

Anordnung	$\min(x,y)$			$\max(x,y)$			Distributivgesetze
	$(\alpha _{i},\beta _{i})$	$(\beta _{i},\gamma _{i})$	$(\alpha _{i},\gamma _{i})$	$(\alpha _{i},\beta _{i})$	$(\beta _{i},\gamma _{i})$	$(\alpha _{i},\gamma _{i})$	$\min(a,\max(\beta _{i},\gamma _{i}))$	$\max(\min(\alpha _{i},\beta _{i}),\min(\alpha _{i},\gamma _{i}))$	$\max(a,\min(\beta _{i},\gamma _{i}))$	$\min(\max(\alpha _{i},\beta _{i}),\max(\alpha _{i},\gamma _{i}))$
$\alpha _{i}\leq \beta _{i}\leq \gamma _{i}$	$\alpha _{i}$	$\beta _{i}$	$\alpha _{i}$	$\beta _{i}$	$\gamma _{i}$	$\gamma _{i}$	$\min(\alpha _{i},\gamma _{i})=\alpha _{i}$	$\max(\alpha _{i},\alpha _{i})=\alpha _{i}$	$\max(\alpha _{i},\beta _{i})=\beta _{i}$	$\min(\beta _{i},\gamma _{i})=\beta _{i}$
$\beta _{i}\leq \alpha _{i}\leq \gamma _{i}$	$\beta _{i}$	$\beta _{i}$	$\alpha _{i}$	$\alpha _{i}$	$\gamma _{i}$	$\gamma _{i}$	$\min(\alpha _{i},\gamma _{i})=\alpha _{i}$	$\max(\beta _{i},\alpha _{i})=\alpha _{i}$	$\max(\alpha _{i},\beta _{i})=\alpha _{i}$	$\min(\alpha _{i},\gamma _{i})=\alpha _{i}$
$\beta _{i}\leq \gamma _{i}\leq \alpha _{i}$	$\beta _{i}$	$\beta _{i}$	$\gamma _{i}$	$\alpha _{i}$	$\gamma _{i}$	$\alpha _{i}$	$\min(\alpha _{i},\gamma _{i})=\gamma _{i}$	$\max(\beta _{i},\gamma _{i})=\gamma _{i}$	$\max(\alpha _{i},\beta _{i})=\alpha _{i}$	$\min(\alpha _{i},\alpha _{i})=\alpha _{i}$
$\gamma _{i}\leq \beta _{i}\leq \alpha _{i}$	$\beta _{i}$	$\gamma _{i}$	$\gamma _{i}$	$\alpha _{i}$	$\beta _{i}$	$\alpha _{i}$	$\min(\alpha _{i},\beta _{i})=\beta _{i}$	$\max(\beta _{i},\gamma _{i})=\beta _{i}$	$\max(\alpha _{i},\gamma _{i})=\alpha _{i}$	$\min(\alpha _{i},\alpha _{i})=\alpha _{i}$
$\alpha _{i}\leq \gamma _{i}\leq \beta _{i}$	$\alpha _{i}$	$\gamma _{i}$	$\alpha _{i}$	$\beta _{i}$	$\beta _{i}$	$\gamma _{i}$	$\min(\alpha _{i},\beta _{i})=\alpha _{i}$	$\max(\alpha _{i},\alpha _{i})=\alpha _{i}$	$\max(\alpha _{i},\gamma _{i})=\gamma _{i}$	$\min(\beta _{i},\gamma _{i})=\gamma _{i}$
$\gamma _{i}\leq \alpha _{i}\leq \beta _{i}$	$\alpha _{i}$	$\gamma _{i}$	$\gamma _{i}$	$\beta _{i}$	$\beta _{i}$	$\alpha _{i}$	$\min(\alpha _{i},\beta _{i})=\alpha _{i}$	$\max(\alpha _{i},\gamma _{i})=\alpha _{i}$	$\max(\alpha _{i},\gamma _{i})=\alpha _{i}$	$\min(\beta _{i},\alpha _{i})=\alpha _{i}$

In den beiden Spalten $\min(\alpha _{i},\max(\beta _{i},\gamma _{i}))$ und $\max(\min(\alpha _{i},\beta _{i}),\min(\alpha _{i},\gamma _{i}))$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $\alpha _{i},\beta _{i},\gamma _{i}\in \mathbb {N} _{0}$ eine Übereinstimmung besteht. D.h. Das 1.Distributivgesetz ist gültig.

In den beiden Spalten $\max(\alpha _{i},\min(\beta _{i},\gamma _{i}))$ und $\min(\max(\alpha _{i},\beta _{)},\max(\alpha _{i},\gamma _{i}))$ sehen wir, dass für alle Möglichkeiten der Anordnung der Elemente $\alpha _{i},\beta _{i},\gamma _{i}\in \mathbb {N} _{0}$ eine Übereinstimmung besteht. D.h. Das 2.Distributivgesetz ist gültig.

$\implies$ Die beiden Distributivgesetze gelten.

Boole'sche Algebra

1. Neutrales Element $\mathbf {0} \in V$ bezüglich $\operatorname {ggT}$ und ein
2. Neutrales Element $\mathbf {1} \in V$ bezüglich $\operatorname {kgV}$.
3. Komplement: $\forall \;a\in V$ gibt es ein Komplement $a'\in V$ mit $\operatorname {kgV} (\,a,\ a'\,)=\mathbf {1}$ und $\operatorname {ggT} (\,a,\ a')=\mathbf {0}$.

Da es kein Neutrales Elemente für die Operationen $\operatorname {ggT}$ gibt, kann dieser Verband $V$ keine Boole'sche Algebra sein.

$\implies V$ ist ein Distributiver Verband.$\qquad \qquad \blacksquare$

Links

Verband