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

Aus Wikiversity



Die Pausenaufgabe

Aufgabe

Zeige, dass in Beispiel 4.12 das Distributivgesetz nicht gilt, wenn man die Rollen von Addition und Multiplikation vertauscht.




Übungsaufgaben

Aufgabe

Betrachte die ganzen Zahlen mit dem Betrag der Differenz als Verknüpfung, also die Abbildung

Besitzt diese Verknüpfung ein neutrales Element? Ist diese Verknüpfung assoziativ, kommutativ, gibt es zu jedem Element ein inverses Element?


Aufgabe

Zeige, dass die Verknüpfung auf einer Geraden, die zwei Punkten ihren Mittelpunkt zuordnet, kommutativ, aber nicht assoziativ ist. Gibt es ein neutrales Element?


Aufgabe

Zeige, dass die Verknüpfung auf einer Geraden, die zwei Punkten ihren Mittelpunkt zuordnet, kommutativ, aber nicht assoziativ ist. Gibt es ein neutrales Element?


Aufgabe *

Wir betrachten auf der Menge

die durch die Tabelle

gegebene Verknüpfung .

  1. Berechne
  2. Besitzt die Verknüpfung ein neutrales Element?


Aufgabe *

Es sei eine -elementige Menge. Wie viele Verknüpfungen gibt es auf ?


Aufgabe *

Wir betrachten den Binomialkoeffizienten als eine Verknüpfung

wobei bei der Binomialkoeffizient als zu interpretieren ist. Diese Verknüpfung ist offenbar nicht kommutativ.

  1. Besitzt diese Verknüpfung ein neutrales Element von links?
  2. Besitzt diese Verknüpfung ein neutrales Element von rechts?
  3. Bestimme und .
  4. Ist diese Verknüpfung assoziativ?


Aufgabe *

Es sei eine Menge. Wir betrachten die Verknüpfung

Ist diese Verknüpfung assoziativ?


Aufgabe *

Es sei eine zweielementige Menge. Erstelle eine Verknüpfungstabelle für die Verknüpfung „Vereinigung“ auf der Potenzmenge .


Aufgabe *

Es sei . Betrachte das Monoid , das aus allen Abbildungen von nach besteht mit der Hintereinanderschaltung von Abbildungen als Verknüpfung.

  1. Beschreibe die Elemente in und erstelle eine Verknüpfungstabelle für .
  2. Bestimme sämtliche Untermonoide von und entscheide jeweils, ob sie kommutativ sind und ob es sich um Gruppen handelt.


Aufgabe

Es sei ein Monoid, und . Zeige die folgenden Potenzgesetze.

  1. Wenn kommutativ ist, so ist


Aufgabe

Es sei ein Monoid und .

a) Folgt aus die Beziehung ?

b) Folgt aus die Beziehung ?


Seien und Monoide. Eine Abbildung

heißt Monoidhomomorphismus, wenn und die Gleichheit

für alle gilt.


Aufgabe

Es sei ein Monoid und das Monoid der Abbildungen von nach . Zeige, dass durch

mit ein injektiver Monoidhomomorphismus gegeben ist.


Aufgabe *

Es seien und Mengen mit Verknüpfungen und es sei

eine mit den Verknüpfungen verträgliche surjektive Abbildung, es gelte also

Die Verknüpfung auf sei assoziativ. Zeige, dass auch die Verknüpfung auf assoziativ ist.


Aufgabe

Es seien Elemente in einem kommutativen Halbring . Berechne


Aufgabe

Es seien Elemente in einem kommutativen Halbring . Berechne


Aufgabe

Es seien Elemente in einem kommutativen Halbring . Berechne


Aufgabe

Berechne

mit und ohne Distributivgesetz.


Aufgabe

Es sei ein kommutativer Halbring und . Zeige die folgenden Gleichungen:

und


Bei einer Summe oder einem Produkt von mehreren Zahlen (oder Elementen eines kommutativen Halbringes) ist es nicht immer sinnvoll, eine feste Reihenfolge der Indexmenge zu haben. Häufig ist es besser, die Reihenfolge zu wechseln und oft gibt es gar keine natürliche Reihenfolge. Man muss sich zuerst klar machen, dass die Summe nicht von der Reihenfolge abhängt. Die Argumente sind ähnlich wie im Beweis zu Lemma 1.2.

Aufgabe

Es sei ein kommutativer Halbring, eine endliche Menge und seien , , Elemente aus . Man definiert die Summe , indem man eine Nummerierung (eine Bijektion)

fixiert und

setzt.

  1. Zeige, dass diese Summe unabhängig von der gewählten Nummerierung ist.
  2. Zeige

    für ein beliebiges .

  3. Es sei

    eine disjunkte Vereinigung. Zeige

  4. Formuliere die entsprechenden Gesetze für das Produkt .


Aufgabe *

Beweise die folgende Form des allgemeinen Distributivgesetzes für einen kommutativen Halbring durch Induktion über , wobei der Fall verwendet werden darf (dabei sind natürliche Zahlen und ).


Aufgabe

Es sei ein kommutativer Halbring. Zeige, dass

ist (mit einer beliebig langen Summe von Einsen).


Aufgabe

Es sei ein kommutativer Halbring, und . Zeige, dass die folgenden Potenzgesetze gelten.


Aufgabe

Zeige, dass mit der komponentenweisen Addition und der komponentenweisen Multiplikation ein kommutativer Halbring ist. Gilt in diesem Halbring die Eigenschaft, dass aus folgt, dass oder gleich ist?


Für die folgenden Aufgaben ist die allgemeine binomische Formel hilfreich.

Aufgabe *

Beweise durch Induktion, dass für die Abschätzung

gilt.


Aufgabe *

Zeige, dass für die Abschätzung

gilt.




Aufgaben zum Abgeben

Aufgabe (4 (2+2) Punkte)

Es sei eine Menge mit einer Verknüpfung darauf, die wir als Produkt schreiben.

  1. Wie viele sinnvollen Klammerungen gibt es für die Verknüpfung von vier Elementen?
  2. Die Verknüpfung sei nun assoziativ. Zeige, dass das Produkt von vier Elementen nicht von irgendeiner Klammerung abhängt.


Aufgabe (4 Punkte)

Es sei . Schreibe ein Computerprogramm, dass die Menge aller Abbildungen von nach auflistet und eine Verknüpfungstabelle für ausgibt.


Aufgabe (3 Punkte)

Wir betrachten die natürlichen Zahlen mit den beiden Verknüpfungen Addition und Potenzierung und den ausgezeichneten Elementen und . Welche Eigenschaften eines kommutativen Halbringes erfüllt diese Struktur, welche nicht?


Aufgabe (2 Punkte)

Es seien Elemente in einem kommutativen Halbring . Berechne


Aufgabe (4 (2+2) Punkte)

Es seien Elemente in einem kommutativen Halbring . Zeige die Formel für die vierte Potenz,

auf die beiden folgenden Arten.

  1. Berechne
  2. Berechne



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)