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 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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.
- Die Reflexivität einer Relation auf einer Menge .
- Teilbarkeitstheorie (N)/Kleinstes gemeinsames Vielfache/Definition/Begriff
- Die kanonische Projektion zu einer Äquivalenzrelation auf einer Menge .
- Ungerichteter Graph/Kantenteilmenge/Restgraph/Definition/Begriff
- Ungerichteter Graph/Zusammenhangskomponente/Definition/Begriff
- Graph/Knotenüberdeckung/Definition/Begriff
- Die Relation heißt reflexiv, wenn für alle gilt.
- Teilbarkeitstheorie (N)/Kleinstes gemeinsames Vielfache/Definition/Begriff/Inhalt
- Man nennt die Abbildung
die kanonische Projektion.
- Ungerichteter Graph/Kantenteilmenge/Restgraph/Definition/Begriff/Inhalt
- Ungerichteter Graph/Zusammenhangskomponente/Definition/Begriff/Inhalt
- Graph/Knotenüberdeckung/Definition/Begriff/Inhalt
Aufgabe (3 Punkte)
Formuliere die folgenden Sätze.
Aufgabe (3 (1+1+1) Punkte)
Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz bestreiten. Von einer solchen Runde seien die Mannschaften und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.
- Welche Information über die Platzierung kann man stets aus den Daten erschließen?
- Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
- unter welcher nicht?
- 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.
- 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.
- Wenn der Erste nicht gegen den Vierten spielt, so kann man den Zweiten nicht vom Dritten unterscheiden.
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (4 (0.5+0.5+1+1+1) Punkte)
Wir betrachten die Verknüpfung
die einem Paar diejenige Zahl zuordnet, die entsteht, wenn man im Zehnersystem die Zahl -fach hintereinander schreibt.
- Bestimme .
- Bestimme .
- Ist die Verknüpfung kommutativ?
- Ist die Verknüpfung assoziativ?
- Besitzt die Verknüpfung ein neutrales Element?
- Es ist
- Es ist
- Die Verknüpfung ist nicht kommutativ, es ist , aber .
- Die Verknüpfung ist nicht assoziativ, es ist , aber besteht aus Zweien.
- Die Verknüpfung besitzt kein neutrales Element. Von links ist zwar
,
daher ist der einzige Kandidat, von rechts ist aber im Allgemeinen
(beispielsweise für
)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (3 Punkte)
Zeige, dass für natürliche Zahlen die folgenden Teilbarkeitsbeziehungen gelten.
- Für jede natürliche Zahl gilt und .
- Für jede natürliche Zahl gilt .
- Gilt und , so gilt auch .
- Gilt und , so gilt auch .
- Gilt , so gilt auch für jede natürliche Zahl .
- Gilt und , so gilt auch für beliebige natürliche Zahlen .
- Ist klar wegen
- Ist klar wegen
- Die beiden Voraussetzungen bedeuten die Existenz von
mit
und
.
Somit ist
und ist auch ein Teiler von .
- Aus den Voraussetzungen
und
ergibt sich direkt
also ist ein Teiler von .
- Aus der Voraussetzung
ergibt sich direkt
also ist ein Teiler von .
- Aus den Voraussetzungen
und
ergibt sich direkt mit dem Distributivgesetz
also ist ein Teiler von .
Aufgabe (3 Punkte)
Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und und schreibe die beiden Zahlen als Vielfache des größten gemeinsamen Teilers.
Es ist
Der größte gemeinsame Teiler ist also . Aus den Rechnungen erhält man
und
Aufgabe (8 (3+2+3) Punkte)
Wir betrachten auf der Menge aller stetigen Funktionen von nach die folgende Relation: Es ist , falls es eine nullstellenfreie stetige Funktion mit
gibt.
- Zeige, dass eine Äquivalenzrelation ist.
- Zeige, dass aus folgt, dass die Nullstellenmenge von und von übereinstimmen.
- Zeige, dass die beiden Funktionen
und
nicht zueinander äquivalent sind.
-
Es ist , da
ist, man also für die konstante Funktion mit dem Wert nehmen kann, die stetig ist und keine Nullstelle besitzt. Zum Nachweis der Symmetrie sei
mit einer stetigen nullstellenfreien Funktion . Dann ist auch die Funktion
wohldefiniert, nullstellenfrei und nach Lemma 10.6 (Mathematik für Anwender (Osnabrück 2023-2024)) auch stetig. Damit gilt
Zum Nachweis der Transitivität gelte
und
mit stetigen nullstellenfreien Funktionen . Dann ist
und ist ebenfalls nach Lemma 10.6 (Mathematik für Anwender (Osnabrück 2023-2024)) eine stetige nullstellenfreie Funktion.
- Es sei
mit stetig und nullstellenfrei. Dann ist für jedes
Wegen
gilt
genau dann, wenn
ist. Dies bedeutet, dass und die gleichen Nullstellen besitzen.
- Nehmen wir an, dass und im beschriebenen Sinne äquivalent sind. Dann gibt es eine stetige nullstellenfreie Funktion mit
für alle . Für bedeutet dies
Wegen der vorausgesetzten Stetigkeit von bedeutet dies nach Lemma 51.7 (Grundkurs Mathematik (Osnabrück 2022-2023)) (2), dass auch
sein muss. Dies widerspricht aber der vorausgesetzten Nullstellenfreiheit von .
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)