Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 6/kontrolle

Die Pausenaufgabe

Aufgabe Referenznummer erstellen

Lege in der Skizze für die drei Häuser überschneidungsfrei Wege zu den zugehörigen gleichfarbigen Gartentoren an.

Übungsaufgaben

Aufgabe Referenznummer erstellen

Finden Sie in Ihrem Alltagsleben möglichst viele Relationen.

(Suchen Sie auch in Ihrem (Zweit-)Studienfach.)

Aufgabe Referenznummer erstellen

Wir betrachten zu der Flussmenge

${}F=\{{\text{Rhein}},{\text{Weser}},{\text{Donau}},{\text{Tiber}},{\text{Themse}},{\text{Nil}}\}\,$

und zu der Ländermenge

${}L=\{{\text{Deutschland}},{\text{Niederlande}},{\text{Schweiz}},{\text{Frankreich}},{\text{Italien}},{\text{Österreich}},{\text{Ungarn}},{\text{Uganda}}\}\,$

die Relation „fließt durch dieses Land“.

1. Beschreibe diese Relation durch eine Tabelle.
2. Beschreibe diese Relation durch ein Verbindungsdiagramm.
3. Beschreibe diese Relation durch Auflistung der zugehörigen Paare.
4. Bestimme die Faser zum Rhein bezüglich dieser Relation.
5. Bestimme die Faser zur Donau bezüglich dieser Relation.
6. Bestimme die Faser zu Deutschland bezüglich dieser Relation.
7. Untersuche die Begriffe Links- und Rechtseindeutigkeit, Links- und Rechtsvollständigkeit für diese Relation.

Aufgabe * Referenznummer erstellen

Anna-Lena, Marie-Simone, Hans-Peter und Fritz-Franz gehen zur Farbberatung. Es ergibt sich folgende Empfehlung. Anna-Lena stehen die Farben grün, gelb und pink, Marie-Simone steht gelb und feuerrot, Hans-Peter steht grün, grau und graublau, Fritz-Franz stehen alle bisher genannten Farben außer graublau, dafür zusätzlich noch violett. Es sei ${}P$ die Menge der vier Personen und ${}F$ die Menge der erwähnten Farben zuzüglich blau.

1. Erstelle eine Tabelle und ein Verbindungsdiagramm, die die Relation aus Personen und Farben wiedergibt.
2. Bestimme die Fasern zu blau, zu grün und zu Marie-Simone.

Aufgabe Referenznummer erstellen

Beim Speeddating treffen sich ${}n$ Frauen und ${}n$ Männer und jede Frau plaudert mit jedem Mann fünf Minuten lang. Danach schreibt jede Frau auf einen Zettel, welche Männer sie wiedersehen möchte, und ebenso schreibt jeder Mann auf einen Zettel, welche Frauen er wiedersehen möchte. Die Moderatorin sammelt die Zettel ein und erstellt daraus eine Liste von Paaren, bei denen sich beide wiedersehen wollen. Beschreibe diese Situation mit Relationen.

Aufgabe Referenznummer erstellen

Es sei ${}S$ die Menge der Städte und ${}A$ die Menge der Autobahnen und ${}L\subseteq S\times A$ die in Beispiel 6.3 beschriebene Relation.

Beschreibe formal die Menge ${}T$ derjenigen Städte, die an mindestens einer Autobahn liegen.

Beschreibe formal die Menge ${}U$ derjenigen Städte, die an mindestens zwei Autobahnen liegen.

Interpretiere die Aussage

$\forall s_{1}\forall s_{2}\exists a(s_{1}La\wedge s_{2}La),$

wobei ${}s_{1}$ und ${}s_{2}$ aus ${}T$ seien. Ist die Aussage wahr?

Formuliere formal die Aussage, dass zwei Städte stets durch maximal zwei Autobahnen miteinander verbunden sind (man darf annehmen, dass jedes Autobahnkreuz an mindestens einer Stadt liegt).

Aufgabe Referenznummer erstellen

Skizziere den Graphen der Addition

$+\colon \mathbb {R} \times \mathbb {R} \longrightarrow \mathbb {R} ,\,(x,y)\longmapsto x+y.$

Aufgabe Referenznummer erstellen

Skizziere den Graphen der Multiplikation

$\cdot \colon \mathbb {R} \times \mathbb {R} \longrightarrow \mathbb {R} ,\,(x,y)\longmapsto x\cdot y.$

Aufgabe Referenznummer erstellen

Wir betrachten in ${}\mathbb {Q} ^{2}$ die Punkte ${}P=(0,0)$, ${}Q=(0,1)$, ${}R=(2,3)$ und ${}S=(6,7)$ und die Geraden ${}G={\begin{pmatrix}0\\1\end{pmatrix}}+\mathbb {Q} {\begin{pmatrix}1\\1\end{pmatrix}}$, die ${}x$-Achse, die ${}y$-Achse und die durch die Gleichung ${}-4x+3y=1$ gegebene Gerade ${}H$. Beschreibe die zugehörige Inzidenzrelation.

Aufgabe Referenznummer erstellen

Erstelle eine Tabelle für die Inzidenzrelation zu einer ${}0,1,2$ und ${}3$-elementigen Menge.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine ${}n$-elementige Menge. Bestimme die Anzahl der Elemente in der Inzidenzrelation zu ${}M$.

Kommentar:

Bei einer Relation ist es wichtig, sich zuerst klar zu machen, was die beteiligten Mengen sind, und insbesondere, ob es sich um eine Relation auf einer Menge oder eine Relation auf zwei Mengen handelt, und wie dann die Paare grundsätzlich aussehen, bevor man schaut, welche davon zur Relation gehören und welche nicht. Bei der Inzidenzrelation geht es um zwei Mengen, nämlich um eine Menge ${}M$ und ihre Potenzmenge ${}{\mathfrak {P}}\,(M)$. Die Inzidenzrelation ist also eine Teilmenge von

$M\times {\mathfrak {P}}\,(M)$

(es gibt also zwar eine Beziehung zwicshen den beiden Mengen, sie sind aber nicht gleich). Es geht also um Paare der Form

$(x,T),$

wobei ${}x$ ein Element von ${}M$ und ${}T$ eine Teilmenge von ${}M$ ist. Die Definition der Inzidenzrelation ist dann sehr einfach, es geht einfach darum, ob ${}x$ zu ${}T$ gehört oder nicht. Wenn ${}M=\{a,b,c\}$ ist, so gehören beispielsweise die Paare

$(a,\{a\}),\,(a,\{a,b\}),\,(a,\{a,c\}),\,(a,\{a,b,c\}),\,(b,,\{a,b,c\}),\,...$

dazu, aber ${}(a,\{b,c\})$ nicht. Wir hatten gesagt, dass die Potenzmenge die Menge der Partys ist, die mit einer gegebenen Menge an Leuten gefeiert werden kann, wobei eine Party nur durch die teilnehmenden Leute festgelegt sei. Diese Interpretation kann man hier erweitern, indem man von Geburtstagspartys mit einem Geburtstagskind spricht. Das Element ${}x$ ist das Geburtstagskind und ${}T$ sind die Teilnehmer, wo ${}x$ dazugehört.

Wie bestimmt man nun die Anzahl der Geburtstagspartys, wenn ${}n$ Leute die Grundmenge bilden? Da gibt es zwei Möglichkeiten. Man kann zuerst das Geburtstagskind ${}x$ fixieren und sich fragen, wie viele Partys es mit diesem Geburtstagskind gibt.

Dies führt auf

$n2^{n-1},$

da die Party ja einer Teilmenge der anderen Leute entspricht.

Oder man kann zuerst die teilnehmenden Leute fixieren und dann ein Geburtstagskind davon bestimmen. Dies führt auf

$\sum _{k=1}^{n}k{\binom {n}{k}}.$

Welches stimmt?

 

Aufgabe Referenznummer erstellen

Es sei ${}M$ die Menge aller Geraden in der Ebene. Wir sagen, dass die Geraden ${}G$ und ${}H$ in Relation stehen, wenn sie (mindestens) einen gemeinsamen Schnittpunkt haben. Welche Relationseigenschaften treffen für diese Relation zu, welche nicht?

Aufgabe Referenznummer erstellen

Bestimme, ob die durch die Relationstabelle

	A	B	C
A		x	x
B	x	x
C	x	x	x

beschriebene Relation auf der Menge ${}\{A,B,C\}$ reflexiv, symmetrisch, transitiv, antisymmetrisch ist.

Aufgabe Referenznummer erstellen

Beschreibe, wie sich die Eigenschaften reflexiv, symmetrisch und antisymmetrisch einer Relation ${}R$ auf einer Menge ${}M$ in der Relationstabelle zu ${}R$ widerspiegeln.

Aufgabe Referenznummer erstellen

Zeigen Sie, dass für Relationen die Konzepte Reflexivität, Symmetrie und Transitivität voneinander unabhängig sind (das heißt, dass zwei der Eigenschaften gelten können, ohne dass die dritte gelten muss).

Aufgabe * Referenznummer erstellen

Es sei ${}M$ eine Menge mit ${}n$ Elementen. Bestimme die Anzahl der Relationen auf ${}M$, die

1. reflexiv
2. symmetrisch
3. reflexiv und symmetrisch

sind.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine Menge mit ${}n$ Elementen. Bestimme die Anzahl der Relationen auf ${}M$, die gleichzeitig symmetrisch und antisymmetrisch sind.

Aufgabe * Referenznummer erstellen

Es sei ${}M=\{a,b\}$ eine zweielementige Menge. Beschreibe vollständig (durch Auflistung aller zugehörigen Paare) die Relation auf der Potenzmenge ${}{\mathfrak {P}}\,(M)$, die durch die Teilmengenbeziehung gegeben ist.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine Menge, ${}f\colon M\rightarrow M$ eine Abbildung und

${}\Gamma =\Gamma _{f}\subseteq M\times M\,$

der zugehörige Graph, den wir als Relation auf ${}M$ auffassen.

1. Was bedeutet es für ${}f$, dass ${}\Gamma _{f}$ reflexiv ist?
2. Was bedeutet es für ${}f$, dass ${}\Gamma _{f}$ transitiv ist?
3. Was bedeutet es für ${}f$, dass ${}\Gamma _{f}$ symmetrisch ist?
4. Was bedeutet es für ${}f$, dass ${}\Gamma _{f}$ antisymmetrisch ist?

Man gebe jeweils Abbildungen aus der Analysis und der linearen Algebra an, die diese Relationseigenschaften jeweils erfüllen.

Kommentar:

Eine Warnung vorneweg: es sind nicht die allerwichtigsten Eigenschaften einer Abbildung, die durch die wichtigsten Relationseigenschaften beschrieben werden. Dies liegt darin begründet, dass bei einer Abbildung jedes ${}x\in M$ nur mit genau einem Element ${}y$ rechts in Relation steht, nämlich eben mit ${}y=f(x)$. Von daher handelt es sich um eine „dünn besetzte“ Relation. Die Relationseigenschaften haben aber häufig (symmetrisch, transitiv) die Form, dass wenn etwas in Relation steht, dass dann auch etwas anderes in Relation steht, was typischerweise bedeutet, dass viele Paare zur Relation gehören.

Machen wir uns die in Frage stehende Relation noch mal kurz klar. ${}xRy$ bedeutet hier einfach ${}f(x)=y$. also dass ${}x$ auf ${}y$ abgebildet wird.

Die Reflexivität bedeutet ${}xRx$, also hier ${}f(x)=x$ für alle ${}x\in M$. D.h. die einzige Abbildung mit einem reflexiven Graphen ist die Identität.

Die Transitivität bedeutet, dass wenn ${}x$ unter ${}f$ auf ${}y$ und ${}y$ unter ${}f$ auf ${}z$ abgebildet wird, dass dann ${}x$ unter ${}f$ auf ${}z$ abgebildet wird. Das hört sich erst mal komisch an, grad wurde ja ${}x$ auf ${}y$ abgebildet und jetzt soll es auf ${}z$ abgebildet werden. Die einzige verbleibende Möglichkeit ist ${}y=z$. D.h. die Transitivität des Graphen bedeutet, dass Elemente, die zum Bild der Abbildung gehören, auf sich selbst abgebildet werden, also ${}f(f(x))=f(x)$ für alle ${}x\in \mathbb {R}$.

Hier gibt es aus der linearen Algebra wichtige Beispiele, die sogenannten Projektionen im Sinne von Definition .. Beispielsweise ist die lineare Abbildung

$\mathbb {R} ^{2}\longrightarrow \mathbb {R} ^{2},\,(x,y)\longmapsto (x,0),$

eine solche Projektion, nämlich die Projektion auf die ${}x$-Achse, aufgefasst im ${}\mathbb {R} ^{2}$.

Symmetrie und Antisymmetrie haben mit Fixpunkteigenschaften zu tun.

 

Aufgabe Referenznummer erstellen

Wir betrachten die Ländermenge

${}L=\{{\text{Deutschland}},{\text{Niederlande}},{\text{Belgien}},{\text{Schweiz}},{\text{Frankreich}},{\text{Italien}},{\text{Österreich}},{\text{Spanien}},{\text{Portugal}},{\text{Polen}},{\text{Ungarn}}\}\,$

und die Relation „besitzt eine gemeinsame Grenze mit“.

1. Untersuche diese Relation in Hinblick auf die Begriffe reflexiv, (anti-)symmetrisch, transitiv.
2. Bestimme die Faser zu Deutschland in dieser Relation.
3. Bestimme die Faser zu Frankreich in dieser Relation.
4. Stelle die Relation durch ein Verbindungsdiagramm dar.

Aufgabe Referenznummer erstellen

Wir studieren die Relation „kann gut leiden“ in verschiedenen Dreier-WGs, die wir durch Relationstabellen ausdrücken, wobei in der Leitspalte das grammatische Subjekt steht. Untersuche die einzelnen Relationen hinsichtlich der Eigenschaften reflexiv, transitiv (anti-)symmetrisch.

	Andrea	Bernd	Heinz
Andrea	x
Bernd		x
Heinz			x

	Anja	Ben	Horst
Anja	x	x	x
Ben	x	x	x
Horst	x	x	x

	Hinz	Kunz	Schlonz
Hinz	x	x	x
Kunz		x
Schlonz	x	x	x

	Hänsel	Gretel	Hexe
Hänsel	x	x
Gretel	x	x
Hexe			x

	Oma	Wolf	Rotkäppchen
Oma	x		x
Wolf		x
Rotkäppchen	x		x

	Jan	Jens	Jennifer
Jan
Jens
Jennifer

	Hase	Fuchs	Igel
Hase		x
Fuchs			x
Igel	x

Aufgabe * Referenznummer erstellen

Bei einem vollständigen ungerichteten Graphen mit ${}4$ Ecken ist jede Ecke mit jeder (anderen) Ecke verbunden. Zeichne einen solchen Graphen in der Ebene ohne Überschneidungen.

Aufgabe * Referenznummer erstellen

Wir betrachten das Spiel Schnick Schnack Schnuck mit den Objekten Schere, Stein, Papier und Brunnen als eine Gewinnrelation.

1. Skizziere diese Gewinnrelation durch einen gerichteten Graphen (Pfeildiagramm).
2. Ist die Gewinnrelation transitiv?
3. Gibt es eine dreielementige Teilmenge der Objekte derart, dass die darauf eingeschränkte Relation transitiv ist?

Aufgabe Referenznummer erstellen

Eine (Fußball-)Spielgruppe bei einer Europa- oder Weltmeisterschaft besteht aus vier Mannschaften, und jede spielt gegen jede. Ein Spiel kann unentschieden oder mit einem Sieg für eine der beiden Mannschaften enden. Wir interessieren uns für die diskrete Struktur einer Spielgruppe, die man durch einen gerichteten Graphen beschreiben kann, wobei man einen Sieg von ${}A$ über ${}B$ durch einen Pfeil von ${}A$ nach ${}B$ (und ein Unentschieden durch keine Verbindung) ausdrücken kann.

Definiere einen Isomorphiebegriff für Spielgruppen und klassifiziere die Spielgruppen entlang geeigneter numerischer Invarianten. Wie viele Spielgruppen gibt es? Aus welchen Isomorphietypen lässt sich die Tabellenordnung ableiten, aus welchen nicht?

Aufgabe Referenznummer erstellen

Es seien ${}M$ und ${}N$ Mengen. Zeige, dass man jede Relation zwischen ${}M$ und ${}N$ als eine Relation auf der Menge ${}M\uplus N$ auffassen kann. Welche Relationen auf ${}M\uplus N$ treten in dieser Weise auf?

Aufgabe * Referenznummer erstellen

Es sei ${}M$ eine Menge und ${}P$ die Potenzmenge von ${}M$. Betrachte die Relation ${}T$ auf ${}P$, die durch

$T(A,B){\text{ genau dann, wenn }}A\subseteq B$

gegeben ist (dabei sind also ${}A$ und ${}B$ Teilmengen von ${}M$). Bestimme die Anzahl der Elemente dieser Relation, wenn ${}M$ ${}n$ Elemente besitzt.

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine Menge und ${}P$ die Potenzmenge von ${}M$. Betrachte die Relation ${}D$ auf ${}P$, die durch

$D(A,B){\text{ genau dann, wenn }}A\cap B=\emptyset$

gegeben ist (dabei sind also ${}A$ und ${}B$ Teilmengen von ${}M$). Bestimme die Anzahl der Elemente dieser Relation, wenn ${}M$ ${}n$ Elemente besitzt.

Aufgabe Referenznummer erstellen

Jedes Paket hat einen eindeutig bestimmten Absender und Empfänger. Modelliere diesen Sachverhalt mit Abbildungen bzw. Relationen. Welche Pfeildiagramme sind sinnvoll, um die Situation zu beschreiben?

Aufgabe Referenznummer erstellen

Es sei ${}R\subseteq M\times N$ eine Relation zwischen ${}M$ und ${}N$. Zeige, dass man eine Relation ${}S$ zwischen ${}N$ und ${}M$ erhält, indem man

${}S={\left\{(y,x)\mid (x,y)\in R\right\}}\,$

setzt. Sie heißt die Umkehrrelation zu ${}R$. Zeige ferner, dass bei ${}M=N$ die Relation ${}R$ genau dann symmetrisch ist, wenn ${}R=S$ ist.

Aufgabe Referenznummer erstellen

Beim neutralgeschlechtlichen Speeddating treffen sich ${}n$ Personen, und jede Person plaudert mit jeder von ihr verschiedenen Person fünf Minuten lang. Danach schreibt jede Person auf einen Zettel, welche Personen sie wiedersehen möchte. Die Moderatorin sammelt die Zettel ein und erstellt daraus eine Liste von Paaren, bei denen sich beide wiedersehen wollen.

1. Beschreibe diese Situation mit einer Relation und einer Umkehrrelation.
2. Es sei ${}n=6$. Zeichne ein Diagramm mit sechs Punkten und verschiedenfarbigen Verbindungsstrecken zwischen den Punkten, das beschreibt, in welcher Reihenfolge die Personen miteinander plaudern (die erste Farbe soll die Gesprächspartner der ersten Runde angeben u.s.w.).

Aufgabe Referenznummer erstellen

Es sei ${}M$ eine Menge und ${}{\mathfrak {P}}\,(M)$ die Potenzmenge davon. Zeige, dass durch

$S\preccurlyeq T,{\text{wenn es eine injektive Abbildung }}S\rightarrow T{\text{ gibt}},$

eine reflexive und transitive Relation auf ${}{\mathfrak {P}}\,(M)$ definiert wird, die in aller Regel weder symmetrisch noch antisymmetrisch ist.

Aufgabe Aufgabe 6.32 ändern

In einer Wohngemeinschaft wohnen Albert, Beowulf, Clara, Dora, Emil und Gundula. Dabei können Albert und Beowulf kochen, die anderen vier nicht. Emil findet Beowulf doof, Dora findet Albert und Clara doof, Clara und Gundula finden beide ebenfalls den Albert doof. Charakterisiere jede Person durch einen sprachlichen Ausdruck, in dem nur auf die Kochfähigkeit und das Dooffinden Bezug genommen wird  (insbesondere dürfen in den Charakterisierungen keine Namen vorkommen).

Kommentar:

Den Albert mit „Albert“ bezeichnen oder drauf zeigen, kann jeder. Es geht in dieser Aufgabe darum, die Personen ohne diese direkten Wege zu charakterisieren, zu adressieren, wo allein auf die beiden angegebenen Relationen Bezug genommen wird.

Diese Situation kennt man aus dem Alltag, man möchte beispielsweise bei einer Party vom Gastgeber wissen, wie denn eine Person heißt, die man selber nicht kennt. Dann sagt man vielleicht etwas wie: ich meine diejenige, die den Kartoffelsalat mitgebracht hat, viel Sekt getrunken hat und zum Schluss mit jemanden, der keinen Kartoffelsalat mitgebracht hat, auf den Tischen getanzt hat. Zwar haben viele Leute Kartotoffelsalat mitgebracht und auch viele von diesen viel Sekt getrunken, aber von diesen hat nur eine Person mit einem auf den Tischen getanzt, der keinen Kartoffelsalat mitgebracht hat (die andern haben eben nur mit anderen Kartoffelsalatmitbringern auf den Tischen getanzt), deshalb ist diese Charakterisierung eindeutig. Dabie können die Konstruktion wie „diejenige, die ... “ beliebig verschachtelt werden.

Ein einfacheres Beispiel: Wenn nur A und C da sind, und A kochen kann und C nicht, so sagt man einfach:

„derjenige, der kochen kann“.

Zum vorliegenden Beispiel. Generell ist es sinnvoll, mit den Leuten anzufangen, die zu einem kleinen Personenkreis gehören, der durch eine Relation beschrieben werden kann. Im vorliegenden Fall beginnt man mit der Kochfähigkeit, da das nur zwei Leute erfüllen. Diese beiden (also A und B) müssen jetzt unter Bezug auf die zweite Relation, das Dooffinden, von voneinander getrennt werden. Da A von drei Leuten doof gefunden wird, und B nur von einer Person, kann man dies direkt verwenden, es ist also

„diejenige Person, die kochen kann und von genau einer Person doof gefunden wird“

eine Charakterisierung von B.

Die schon gewonnenen Charakterisierungen kann man dann zur Charakterisierung weitere Personen heranziehen. Da E den B doof findet, ist

„diejenige Person, die diejenige Person doof findet, die kochen kann und nur von einer Person doof gefunden wird“

eine Charakterisierung von E.

Dagegen wäre

„diejenige Person, die genau eine Person doof findet, die kochen kann“

keine Charakterisierung von E, da dies auch auf G zutrifft.

 

Aufgaben zum Abgeben

Aufgabe (2 Punkte)Referenznummer erstellen

Bestimme, ob die durch die Relationstabelle

${}\,$	${}A$	${}B$	${}C$	${}D$
${}A$	${}\times$	${}\,$	${}\times$	${}\,$
${}B$	${}\times$	${}\times$	${}\,$	${}\,$
${}C$	${}\,$	${}\,$	${}\times$	${}\,$
${}D$	${}\,$	${}\times$	${}\,$	${}\times$

beschriebene Relation auf der Menge ${}\{A,B,C,D\}$ reflexiv, symmetrisch, transitiv, antisymmetrisch ist.

Aufgabe (2 Punkte)Referenznummer erstellen

Es sollen drei Häuser jeweils mit Leitungen an Wasser, Gas und Elektrizität angeschlossen werden. Beschreibe eine Möglichkeit, bei der es nur eine Überschneidung gibt.

Aufgabe (4 Punkte)Referenznummer erstellen

Beim Speeddating nehmen Anna, Berta, Clara, Dora und Elfriede und Richard, Stefan, Thomas, Uwe und Volkmar teil. Auf den Wiedersehwunschlisten schreibt Anna die Namen Richard und Thomas auf, Berta schreibt Richard und Volkmar auf, Clara schreibt alle Namen außer Uwe auf, Dora schreibt Stefan auf und Elfriede schreibt Stefan, Uwe und Volkmar auf. Richard und Thomas schreiben alle Namen auf, Stefan schreibt Dora auf, Uwe schreibt Anna, Berta und Clara auf und Volkmar gibt einen leeren Zettel ab.

1. Stelle die Frauenwunschrelation durch eine Tabelle dar.
2. Stelle die Männerwunschrelation durch ein Verbindungsdiagramm dar.
3. Was ist die Faser zu Stefan unter der Frauenwunschrelation?
4. Was ist die Faser zu Volkmar unter der Männerwunschrelation?
5. Was ist die Faser zu Berta unter der Männerwunschrelation?
6. Diskutiere die Begriffe Links- und Rechtseindeutigkeit, Links- und Rechtsvollständigkeit für die beiden Wunschrelationen.
7. Beschreibe die resultierende Wiedersehensrelation.

Aufgabe (6 (1+1+2+1+1) Punkte)Referenznummer erstellen

Wir betrachten die Einheitskreisscheibe

${}{\left\{(x,y)\mid x^{2}+y^{2}\leq 1\right\}}\subseteq \mathbb {R} ^{2}\,$

als Relation auf ${}\mathbb {R}$.

1. Gehört ${}\left({\frac {2}{3}},\,{\frac {3}{4}}\right)$ zur Relation?
2. Bestimme die Faser zu ${}0$ in der ersten Komponente.
3. Ist die Relation reflexiv, symmetrisch, transitiv?
4. Wenn ${}(x,y)$ zur Relation gehört, gehört dann auch ${}(-y,-x)$ zur Relation?
5. Es sei ${}\varphi \colon \mathbb {R} ^{2}\rightarrow \mathbb {R} ^{2}$ eine lineare Abbildung. Wenn ${}(x,y)$ zur Relation gehört, gehört dann auch ${}\varphi (x,y)$ zur Relation?

Aufgabe (4 Punkte)Referenznummer erstellen

Es sei ${}M=\{a,b,c\}$ eine dreielementige Menge. Beschreibe vollständig (durch Auflistung aller zugehörigen Paare) die Relation auf der Potenzmenge ${}{\mathfrak {P}}\,(M)$, die durch die Teilmengenbeziehung gegeben ist.

Aufgabe (2 Punkte)Referenznummer erstellen

Wir betrachten das Spiel Schnick Schnack Schnuck mit den Objekten Schere, Stein, Papier, Brunnen. Charakterisiere jedes Objekt mit einem Ausdruck, in dem nur auf die Gewinnrelation Bezug genommen wird.

Aufgabe (8 Punkte)Referenznummer erstellen

Klassifiziere (bis auf Isomorphie) die möglichen Gewinnstrukturen bei einer Vierergruppe (wie bei einer Fußballweltmeisterschaft).

(Bemerkung: Es wird also eine vollständige Liste aller möglichen Isomorphietypen verlangt. Die Liste muss systematisch sein und die Vollständigkeit begründet werden.)

Fußnoten