Kurs:Diskrete Mathematik/25/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	3	0	0	4	0	0	0	3	3	8	0	0	0	0	0	0	0	27

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Reflexivität einer Relation ${}R$ auf einer Menge ${}M$.
2. Das kleinste gemeinsame Vielfache von natürlichen Zahlen

   $a_{1},\ldots ,a_{n}.$

3. Die kanonische Projektion zu einer Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Der Restgraph ${}G\setminus F$ eines Graphen  ${}G=(V,E)$  zu einer Teilmenge  ${}F\subseteq E$  der Kantenmenge.
5. Die Zusammenhangskomponente zu einem Punkt  ${}v\in V$  in einem Graphen  ${}G=(V,E)$. 
6. Eine Knotenüberdeckung in einem Graphen  ${}G=(V,E)$. 

Lösung

1. Die Relation ${}R$ heißt reflexiv, wenn ${}xRx$ für alle ${}x\in M$ gilt.
2. Eine natürliche Zahl ${}b$ ist das kleinste gemeinsame Vielfache dieser Zahlen, wenn ${}b$ ein gemeinsames Vielfaches der ${}a_{i}$ ist und wenn jedes gemeinsame Vielfache der Zahlen ein Vielfaches von ${}b$ ist.
3. Man nennt die Abbildung

   $q\colon M\longrightarrow M/\sim ,\,x\longmapsto [x],$

   die kanonische Projektion.

4. Der Restgraph ${}G\setminus F$ ist derjenige Graph, dessen Punktemenge ${}V$ ist und dessen Kantenmenge aus ${}E\setminus F$ besteht.
5. Die Zusammenhangskomponente von ${}v$ ist

   ${}Z(v)={\left\{u\in V\mid {\text{es gibt einen Weg, der }}u{\text{ und }}v{\text{ verbindet}}\right\}}\,.$

6. Eine Knotenüberdeckung ist eine Teilmenge  ${}W\subseteq V$  mit der Eigenschaft, dass jede Kante mindestens einen Knoten aus ${}W$ trifft.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

Lösung

1. /Fakt
2. /Fakt
3. /Fakt

Aufgabe (3 (1+1+1) Punkte)

Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze ${}1,2,3,4$ nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz ${}3$ bestreiten. Von einer solchen Runde seien die Mannschaften ${}A,B,C,D$ und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.

1. Welche Information über die Platzierung kann man stets aus den Daten erschließen?
2. Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
3. unter welcher nicht?

Lösung

1. Es gibt genau eine Mannschaft, die zweimal gewinnt, diese ist Weltmeister, und genau eine Mannschaft, die zweimal verliert, diese ist Vierter. Die beiden anderen Mannschaften gewinnen einmal und verlieren einmal und sind Zweiter oder Dritter.
2. Wenn der Erste gegen den Vierten (die ja beide bekannt sind) spielt, so muss dieses Spiel ein Hauptfinale sein. Das komplementäre Spiel ist ebenfalls ein Halbfinale, das andere Spiel des Ersten muss das Finale und das andere Spiel des Vierten muss das Spiel um Platz drei sein. Somit sind alle Platzierungen bekannt.
3. Wenn der Erste nicht gegen den Vierten spielt, so kann man den Zweiten nicht vom Dritten unterscheiden.

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (4 (0.5+0.5+1+1+1) Punkte)

Wir betrachten die Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(a,b)\longmapsto a*b,$

die einem Paar ${}(a,b)$ diejenige Zahl zuordnet, die entsteht, wenn man im Zehnersystem die Zahl ${}b$ ${}a$-fach hintereinander schreibt.

1. Bestimme ${}7*6$.
2. Bestimme ${}4*13$.
3. Ist die Verknüpfung kommutativ?
4. Ist die Verknüpfung assoziativ?
5. Besitzt die Verknüpfung ein neutrales Element?

Lösung

1. Es ist

   ${}7*6=6666666\,.$

2. Es ist

   ${}4*13=13131313\,.$

3. Die Verknüpfung ist nicht kommutativ, es ist  ${}2*1=11$,  aber  ${}1*2=2$. 
4. Die Verknüpfung ist nicht assoziativ, es ist  ${}2*(2*2)=2*(22)=2222$,  aber  ${}(2*2)*2=22*2$  besteht aus ${}22$ Zweien.
5. Die Verknüpfung besitzt kein neutrales Element. Von links ist zwar  ${}1*b=b$,  daher ist ${}1$ der einzige Kandidat, von rechts ist aber im Allgemeinen (beispielsweise für ${}b=2$)

   ${}b*1\neq b\,.$

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (3 Punkte)

Zeige, dass für natürliche Zahlen die folgenden Teilbarkeitsbeziehungen gelten.

1. Für jede natürliche Zahl ${}a$ gilt ${}1\,{|}\,a$ und ${}a\,{|}\,a$.
2. Für jede natürliche Zahl ${}a$ gilt ${}a\,{|}\,0$.
3. Gilt ${}a\,{|}\,b$ und ${}b\,{|}\,c$, so gilt auch ${}a\,{|}\,c$.
4. Gilt ${}a\,{|}\,b$ und ${}c\,{|}\,d$, so gilt auch ${}ac\,{|}\,bd$.
5. Gilt ${}a\,{|}\,b$, so gilt auch ${}ac\,{|}\,bc$ für jede natürliche Zahl ${}c$.
6. Gilt ${}a\,{|}\,b$ und ${}a\,{|}\,c$, so gilt auch ${}a\,{|}\,{\left(rb+sc\right)}$ für beliebige natürliche Zahlen ${}r,s$.

Lösung

1. Ist klar wegen

   ${}a=a\cdot 1\,.$

2. Ist klar wegen

   ${}0=a\cdot 0\,.$

3. Die beiden Voraussetzungen bedeuten die Existenz von  ${}s,t\in \mathbb {N}$  mit  ${}b=as$  und  ${}c=bt$.  Somit ist

   ${}c=bt=(as)t=a(st)\,$

   und ${}a$ ist auch ein Teiler von ${}c$.

4. Aus den Voraussetzungen  ${}b=as$  und  ${}d=tc$  ergibt sich direkt

   ${}bd=astc=acts\,,$

   also ist ${}ac$ ein Teiler von ${}bd$.

5. Aus der Voraussetzung  ${}b=as$  ergibt sich direkt

   ${}bc=acs\,,$

   also ist ${}ac$ ein Teiler von ${}bc$.

6. Aus den Voraussetzungen  ${}b=at$  und  ${}c=au$  ergibt sich direkt mit dem Distributivgesetz

   ${}rb+sc=rat+sau=a(rt+su)\,,$

   also ist ${}a$ ein Teiler von ${}rb+sc$.

Aufgabe (3 Punkte)

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}1085$ und ${}806$ und schreibe die beiden Zahlen als Vielfache des größten gemeinsamen Teilers.

Lösung

Es ist

${}1085=1\cdot 806+279\,,$

${}806=2\cdot 279+248\,,$

${}279=1\cdot 248+31\,,$

${}248=8\cdot 31\,.$

Der größte gemeinsame Teiler ist also ${}31$. Aus den Rechnungen erhält man

${}806=2\cdot 279+248=2(248+31)+248=3\cdot 248+2\cdot 31=3\cdot 8\cdot 31+2\cdot 31=26\cdot 31\,$

und

${}1085=806+279=26\cdot 31+9\cdot 31=35\cdot 31\,.$

Aufgabe (8 (3+2+3) Punkte)

Wir betrachten auf der Menge ${}C$ aller stetigen Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$ die folgende Relation: Es ist ${}f\sim g$, falls es eine nullstellenfreie stetige Funktion ${}\alpha \colon \mathbb {R} \rightarrow \mathbb {R}$ mit

${}f=g\cdot \alpha \,$

gibt.

1. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.
2. Zeige, dass aus ${}f\sim g$ folgt, dass die Nullstellenmenge von ${}f$ und von ${}g$ übereinstimmen.
3. Zeige, dass die beiden Funktionen

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

   und

   ${}g(x)=x^{2}\,$

   nicht zueinander äquivalent sind.

Lösung

1. Es ist ${}f\sim f$, da

   ${}f=1\cdot f\,$

   ist, man also für ${}\alpha$ die konstante Funktion mit dem Wert ${}1$ nehmen kann, die stetig ist und keine Nullstelle besitzt. Zum Nachweis der Symmetrie sei

   ${}f=g\cdot \alpha \,$

   mit einer stetigen nullstellenfreien Funktion ${}\alpha$. Dann ist auch die Funktion

   ${\frac {1}{\alpha }}\colon \mathbb {R} \longrightarrow \mathbb {R} ,\,x\longmapsto {\frac {1}{\alpha (x)}},$

   wohldefiniert, nullstellenfrei und nach Lemma 10.6 (Mathematik für Anwender (Osnabrück 2020-2021)) auch stetig. Damit gilt

   ${}f\cdot {\frac {1}{\alpha }}=g\,.$

   Zum Nachweis der Transitivität gelte

   ${}f=g\cdot \alpha \,$

   und

   ${}g=h\cdot \beta \,$

   mit stetigen nullstellenfreien Funktionen ${}\alpha ,\beta$. Dann ist

   ${}f=g\cdot \alpha =h\cdot \beta \cdot \alpha \,$

   und ${}\beta \cdot \alpha$ ist ebenfalls nach Lemma 10.6 (Mathematik für Anwender (Osnabrück 2020-2021)) eine stetige nullstellenfreie Funktion.

2. Es sei

   ${}f=g\cdot \alpha \,$

   mit ${}\alpha$ stetig und nullstellenfrei. Dann ist für jedes ${}x\in \mathbb {R}$

   ${}f(x)=g(x)\cdot \alpha (x)\,.$

   Wegen

   ${}\alpha (x)\neq 0\,$

   gilt

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

   genau dann, wenn

   ${}g(x)=0\,$

   ist. Dies bedeutet, dass ${}f$ und ${}g$ die gleichen Nullstellen besitzen.

3. Nehmen wir an, dass ${}x$ und ${}x^{2}$ im beschriebenen Sinne äquivalent sind. Dann gibt es eine stetige nullstellenfreie Funktion ${}\alpha$ mit

   ${}x^{2}=\alpha (x)\cdot x\,$

   für alle ${}x\in \mathbb {R}$. Für  ${}x\neq 0$  bedeutet dies

   ${}\alpha (x)={\frac {x^{2}}{x}}=x\,.$

   Wegen der vorausgesetzten Stetigkeit von ${}\alpha$ bedeutet dies nach Lemma 51.7 (Grundkurs Mathematik (Osnabrück 2022-2023))  (2), dass auch

   ${}\alpha (0)=0\,$

   sein muss. Dies widerspricht aber der vorausgesetzten Nullstellenfreiheit von ${}\alpha$.

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