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

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	${}\sum$
Punkte	3	3	2	3	8	0	0	0	0	0	7	0	0	0	0	0	0	0	0	26

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

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

Lösung

1. Eine Menge ${}G$ mit einem ausgezeichneten Element ${}e\in G$ und mit einer Verknüpfung

   $G\times G\longrightarrow G,\,(g,h)\longmapsto g\circ h,$

   heißt Gruppe, wenn folgende Eigenschaften erfüllt sind.

   1. Die Verknüpfung ist assoziativ, d.h. für alle ${}f,g,h\in G$ gilt

      $(f\circ g)\circ h=f\circ (g\circ h).$

   2. Das Element ${}e$ ist ein neutrales Element, d.h. für alle ${}g\in G$ gilt

      $g\circ e=g=e\circ g.$

   3. Zu jedem ${}g\in G$ gibt es ein inverses Element, d.h. es gibt ein ${}h\in G$ mit

      $h\circ g=g\circ h=e.$

2. Man sagt, dass die natürliche Zahl ${}a$ die natürliche Zahl ${}b$ teilt, wenn es eine natürliche Zahl ${}c$ derart gibt, dass  ${}b=c\cdot a$  ist.
3. Ein beschränkter Verband ${}M$ heißt komplementär, wenn es zu jedem  ${}x\in M$  ein  ${}y\in M$  mit  ${}x\sqcap y=0$  und  ${}x\sqcup y=1$  gibt.
4. Ein Sterngraph ist ein Graph mit einem Knoten, der mit allen anderen Knoten verbunden ist und dies die einzigen Kanten des Graphen sind.
5. Ein Punkt  ${}v\in V$  eines Graphen mit Grad ${}1$ heißt Blatt.
6. Die Adjazenzmatrix ist diejenige ${}V\times V$- Matrix, deren Einträge durch

   ${}a_{u,v}={\begin{cases}1,\,{\text{falls }}\{u,v\}\in E,\\0\,{\text{ sonst}},\end{cases}}\,$

   gegeben sind.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

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

Lösung

1. Zu je zwei Gruppenelementen ${}a,b\in G$ besitzen die beiden Gleichungen

   $a\circ x=b{\text{ und }}y\circ a=b$

   eindeutige Lösungen ${}x,y\in G$.
2. /Fakt
3. /Fakt

Aufgabe (2 Punkte)

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?

Lösung erstellen

Aufgabe (3 Punkte)

Die Hochschule „Tellerrand“ bietet lediglich ${}4$ Fächer an, nämlich Hethitologie, Assyriologie, Ägyptologie und Semitistik. Sie bietet lediglich ${}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.

Lösung

Es gibt ${}6$ Möglichkeiten.

Aufgabe (8 Punkte)

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

$\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 ${}\Psi$ genau dann surjektiv ist, wenn

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

ist.

Lösung

Es sei zuerst

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

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

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

Diese erweitern wir zu einer Abbildung

$h\colon L\longrightarrow N,$

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

Es sei nun

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

Dabei sei zunächst

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

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

$f\colon L\longrightarrow M.$

Es sei

$h\colon L\longrightarrow N$

vorgegeben. Wir definieren

$g\colon M\longrightarrow N$

durch

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

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

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

nach Konstruktion.

Es sei nun

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

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

$g\colon M\longrightarrow N.$

Es sei

$h\colon L\longrightarrow N$

vorgegeben. Wir definieren

$f\colon L\longrightarrow M$

durch

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

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

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

ist. Dabei ist

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

nach Konstruktion.

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (7 (2+1+2+2) Punkte)

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

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

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

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

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

   wobei ${}c,d$ teilerfremd sind.

3. Es ist

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

4. Es ist

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

Lösung

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

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

   ein Vielfaches von ${}ab$.

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

   ${}{\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}}$

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen