Kurs:Diskrete Mathematik/17/Klausur mit Lösungen

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Gruppe.
2. Die Eigenschaft, dass eine natürliche Zahl ${\displaystyle {}a}$ eine natürliche Zahl ${\displaystyle {}b}$ teilt
3. Ein komplementärer beschränkter Verband ${\displaystyle {}M}$.
4. Ein Sterngraph.
5. Ein Blatt ${\displaystyle {}v\in V}$ eines Graphen.
6. Die Adjazenzmatrix zu einem Graphen ${\displaystyle {}G=(V,E)}$.

Formuliere die folgenden Sätze.

1. Der Satz über die Lösbarkeit von Gleichungen in einer Gruppe ${\displaystyle {}G}$.
2. /Fakt/Name
3. /Fakt/Name

In einer U-Bahn-Station wird der Zugang und der Ausgang über eine elektronische Karte geregelt, die man an einen Sensor halten muss, damit sich die Schranke öffnet. Es gibt 5 Ausgänge, aber nur 2 Zugänge. Was haben sich die Leute dabei vermutlich gedacht?

Die Hochschule „Tellerrand“ bietet lediglich ${\displaystyle {}4}$ Fächer an, nämlich Hethitologie, Assyriologie, Ägyptologie und Semitistik. Sie bietet lediglich ${\displaystyle {}2}$-Fächer-Bachelor an in beliebiger Fächerkombination. Wie viele Fächerkombinationen gibt es (es wird nicht zwischen Erst- und Zweitfach unterschieden)? Skizziere ein Mengendiagramm, das die Studentenschaft mit ihren Fächern wiedergibt. Die zu einem Fach gehörenden Studenten und Studentinnen sollen dabei durch ein zusammenhängendes Gebiet dargestellt werden.

Es gibt ${\displaystyle {}6}$ Möglichkeiten.

Es seien ${\displaystyle {}L,M,N}$ endliche Mengen mit ${\displaystyle {}\ell ,m}$ bzw. ${\displaystyle {}n}$ Elementen. Wir betrachten die Abbildung

${\displaystyle \Psi \colon \operatorname {Abb} \,{\left(L,M\right)}\times \operatorname {Abb} \,{\left(M,N\right)}\longrightarrow \operatorname {Abb} \,{\left(L,N\right)},\,(f,g)\longmapsto g\circ f,}$

die durch die Hintereinanderschaltung von Abbildungen gegeben ist. Zeige, dass ${\displaystyle {}\Psi }$ genau dann surjektiv ist, wenn

${\displaystyle {}m\geq \operatorname {min} \left(\ell ,\,n\right)\,}$

ist.

Es sei zuerst

${\displaystyle {}m<\operatorname {min} \left(\ell ,\,n\right)\,.}$

Wir nennen das Minimum rechts ${\displaystyle {}k}$. Wir wählen Teilmengen ${\displaystyle {}S=L}$ und ${\displaystyle {}T=N}$ mit jeweils ${\displaystyle {}k}$ Elementen und eine bijektive Abbildung

${\displaystyle {\tilde {h}}\colon S\longrightarrow T.}$

Diese erweitern wir zu einer Abbildung

${\displaystyle h\colon L\longrightarrow N,}$

indem wir die Werte zu Elementen aus ${\displaystyle {}L\setminus S}$ irgendwie festlegen. Das Bild von ${\displaystyle {}h}$ besitzt zumindest ${\displaystyle {}k}$ Elemente. Diese Abbildung kann nicht durch ${\displaystyle {}M}$ faktorisieren, da ${\displaystyle {}M}$ weniger als ${\displaystyle {}k}$ Elemente besitzt.

Es sei nun

${\displaystyle {}m\geq \operatorname {min} \left(\ell ,\,n\right)\,.}$

Dabei sei zunächst

${\displaystyle {}\ell =\operatorname {min} \left(\ell ,\,n\right)\,.}$

Daher gibt es eine injektive Abbildung von ${\displaystyle {}L}$ nach ${\displaystyle {}M}$, und wir fixieren eine injektive Abbildung

${\displaystyle f\colon L\longrightarrow M.}$

Es sei

${\displaystyle h\colon L\longrightarrow N}$

vorgegeben. Wir definieren

${\displaystyle g\colon M\longrightarrow N}$

durch

${\displaystyle {}g(y)={\begin{cases}h(x),{\text{ falls }}y=f(x)\\\,z{\text{ sonst}}\,,\end{cases}}\,}$

wobei ${\displaystyle {}z\in N}$ fixiert ist. Dabei ist

${\displaystyle {}(g\circ f)(x)=g(f(x))=h(x)\,}$

nach Konstruktion.

Es sei nun

${\displaystyle {}n=\operatorname {min} \left(\ell ,\,n\right)\,.}$

Bei ${\displaystyle {}n=0}$ ist die Aussage direkt klar, sei also ${\displaystyle {}n\geq 1}$. Dann gibt es eine surjektive Abbildung von ${\displaystyle {}M}$ nach ${\displaystyle {}L}$, und wir fixieren eine surjektive Abbildung

${\displaystyle g\colon M\longrightarrow N.}$

Es sei

${\displaystyle h\colon L\longrightarrow N}$

vorgegeben. Wir definieren

${\displaystyle f\colon L\longrightarrow M}$

durch

${\displaystyle {}f(x)=y\,,}$

wobei ${\displaystyle {}y\in M}$ ein Element mit

${\displaystyle {}g(y)=h(x)\,}$

ist. Dabei ist

${\displaystyle {}(g\circ f)(x)=g(f(x))=h(x)\,}$

nach Konstruktion.

Zeige, dass für natürliche Zahlen ${\displaystyle {}a,b,g}$ folgende Aussagen gelten.

1. Für teilerfremde ${\displaystyle {}a,b}$ ist

   ${\displaystyle {}\operatorname {kgV} \,(a,b)=ab\,.}$

2. Es gibt ${\displaystyle {}c,d\in \mathbb {Z} }$ mit

   ${\displaystyle a=c\cdot \operatorname {ggT} \,(a,b)\,\,{\text{ und }}\,\,b=d\cdot \operatorname {ggT} \,(a,b),}$

   wobei ${\displaystyle {}c,d}$ teilerfremd sind.

3. Es ist

   ${\displaystyle {}\operatorname {kgV} \,(ga,gb)=g\cdot \operatorname {kgV} \,(a,b)\,.}$

4. Es ist

   ${\displaystyle {}\operatorname {ggT} \,(a,b)\cdot \operatorname {kgV} \,(a,b)=ab\,.}$

1. Zunächst ist natürlich das Produkt ${\displaystyle {}ab}$ ein gemeinsames Vielfaches von ${\displaystyle {}a}$ und ${\displaystyle {}b}$. Es sei also ${\displaystyle {}f}$ irgendein gemeinsames Vielfaches, also ${\displaystyle {}f=ua}$ und ${\displaystyle {}f=vb}$. Nach Satz 6.1 (Diskrete Mathematik (Osnabrück 2020)) gibt es im teilerfremden Fall Zahlen ${\displaystyle {}r,s\in \mathbb {Z} }$ mit ${\displaystyle {}ra+sb=1}$. Daher ist

   ${\displaystyle {}f=f\cdot 1=f(ra+sb)=fra+fsb=vbra+uasb=(vr+us)ab\,}$

   ein Vielfaches von ${\displaystyle {}ab}$.

2. Die Existenz von ${\displaystyle {}c}$ und ${\displaystyle {}d}$ ist klar. Hätten ${\displaystyle {}c}$ und ${\displaystyle {}d}$ einen gemeinsamen Teiler ${\displaystyle {}e\neq 1,-1}$, so ergäbe sich sofort der Widerspruch, dass ${\displaystyle {}e\cdot \operatorname {ggT} \,(a,b)}$ ein größerer gemeinsamer Teiler von ${\displaystyle {}a}$ und ${\displaystyle {}b}$ wäre.
3. Die rechte Seite ist offenbar ein gemeinsames Vielfaches von ${\displaystyle {}ga}$ und ${\displaystyle {}gb}$. Es sei ${\displaystyle {}n}$ ein Vielfaches der linken Seite, also ein gemeinsames Vielfaches von ${\displaystyle {}ga}$ und ${\displaystyle {}gb}$. Dann kann man ${\displaystyle {}n=uga}$ und ${\displaystyle {}n=vgb}$ schreiben. Damit ist ${\displaystyle {}uga=vgb}$ und somit ist ${\displaystyle {}k:=ua=vb}$ (bei ${\displaystyle {}g\neq 0}$; bei ${\displaystyle {}g=0}$ ist die Behauptung direkt klar) ein gemeinsames Vielfaches von ${\displaystyle {}a}$ und ${\displaystyle {}b}$. Also ist ${\displaystyle {}n=gk}$ ein Vielfaches der rechten Seite.
4. Wir schreiben unter Verwendung der ersten Teile

   ${\displaystyle {}{\begin{aligned}\operatorname {ggT} \,(a,b)\cdot \operatorname {kgV} \,(a,b)&=\operatorname {ggT} \,(a,b)\cdot \operatorname {kgV} \,(c\cdot (\operatorname {ggT} \,(a,b)),d\cdot (\operatorname {ggT} \,(a,b)))\\&=\operatorname {ggT} \,(a,b)\cdot \operatorname {ggT} \,(a,b)\cdot \operatorname {kgV} \,(c,d)\\&=\operatorname {ggT} \,(a,b)\cdot \operatorname {ggT} \,(a,b)\cdot cd\\&=c\cdot \operatorname {ggT} \,(a,b)\cdot d\cdot \operatorname {ggT} \,(a,b)\\&=ab.\end{aligned}}}$