Verknüpfung – Mathe für Nicht-Freaks

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Definition der Verknüpfung[Bearbeiten]

Verknüpfungen sind dir bereits aus der Schule bekannt. Beispiele hierfür sind Addition und Multiplikation. Diese Verknüpfungen können wir als spezielle Abbildungen betrachten. Schauen wir uns dazu als Beispiel die Verknüpfung der Addition auf den reellen Zahlen genauer an:

Die Addition verknüpft zwei Zahlen und zu einer neuen Zahl . Wir können somit die Addition als Abbildung vom nach auffassen. (Wiederholung: ist die Menge aller geordneter Paare mit und ). Der Definitionsbereich ist , weil bei der Addition zwei reelle Zahlen miteinander verknüpft werden. Die Zielmenge ist , da das Ergebnis der Addition zweier reeller Zahlen wieder eine reelle Zahl ist. Damit ist die Addition eine Abbildung . Analog lässt sich auch die Multiplikation als Abbildung von nach mit der Zuordnungsvorschrift auffassen.

Das obige Beispiel können wir nun verallgemeinern. Statt betrachten wir jetzt irgendeine Grundmenge . Die Addition ist eine Verknüpfung, die zwei Objekte zu einem neuen Objekt der Grundmenge verknüpft - wir wollen jetzt aber den allgemeineren Fall betrachten, dass eine Verknüpfung Objekte zu einem neuen Objekt verknüpft. Analog zu unserem Beispiel ist dann eine solche Verknüpfung eine Abbildung , welche auch -stellige Verknüpfung genannt wird. Ein Synonym für das Wort „Verknüpfung“ ist der Begriff „Operation“

Dialog-information.svg
Definition (Verknüpfung)

Eine -stellige Verknüpfung auf einer Grundmenge ist eine Abbildung .

Verständnisfrage: Zähle Beispiele für Verknüpfungen auf.

  • Addition , Multiplikation und Potenzbildung sind zweistellige Verknüpfungen auf .
  • Quadratfunktion , Betragsfunktion und Sinusfunktion sind einstellige Verknüpfungen auf .
  • Funktionskomposition von reellwertigen Funktion ist eine binäre Verknüpfung auf der Menge aller Funktionen .
  • Vereinigung, Differenz, Durchschnitt sind binäre Verknüpfungen auf der Potenzmenge einer gegebenen Grundmenge.
  • Komplementbildung ist eine einstellige Verknüpfungen auf der Potenzmenge einer gegebenen Grundmenge.

Binäre Verknüpfungen[Bearbeiten]

Für zweistellige Verknüpfungen wird auch der Begriff binäre Verknüpfung gebraucht:

Dialog-information.svg
Definition (binäre Verknüpfung)

Eine binäre Verknüpfung ist eine zweistellige Verknüpfung. Eine binäre Verknüpfung auf einer Grundmenge ist damit eine Abbildung .

Betrachten wir eine binäre Verknüpfung auf einer Grundmenge . Damit lässt sich als eine Abbildung auffassen. Du kannst dir als eine Maschine vorstellen, die zwei Elemente und aus der Menge nimmt und daraus ein Element aus erzeugt:

Binäre Verknüpfungen dargestellt als Maschine

Für binäre Verknüpfungen wird oft die Schreibweise verwendet. Hier steht stellvertretend für eine beliebige Verknüpfung wie die Addition oder die Multiplikation . Diese Schreibweise sollte nicht mit der Funktionskomposition verwechselt werden, die auch das Symbol verwendet (Zwar ist die Funktionskomposition eine binäre Verknüpfung, aber nicht jede binäre Verknüpfung ist eine Funktionskomposition).

Eigenschaften binärer Verknüpfungen[Bearbeiten]

Sei im Folgenden eine beliebige Verknüpfung auf einer Grundmenge . Wir betrachten nun die sogenannte Kommutativität beziehungsweise Assoziativität der binären Verknüpfung.

Kommutativität[Bearbeiten]

Betrachten wir die Maschinenvorstellung einer binären Verknüpfung. Bei einer binären Verknüpfung besitzt die Maschine zwei Eingänge. In diese können wir zwei Objekte und aus der Grundmenge stecken. Ein Element stecken wir links in unsere Maschine und das andere rechts:

Binäre Verknüpfungen dargestellt als Maschine

Ist die Reihenfolge, in der wir die Argumente in die Maschine stecken, egal? Kommt immer dasselbe raus, wenn wir und vertauschen?

Kommt es auf die Reihenfolge an?

Es gibt solche Verknüpfungen, bei dem die Reihenfolge der Argumente egal ist. Bei solchen Verknüpfungen ist stets unabhängig davon, welche Argumente und gewählt wurden. Ein Beispiel hierfür ist die Addition auf den reellen Zahlen. Für die Addition gilt nämlich stets .

Weil diese Eigenschaft praktisch ist, bekommt sie einen eigenen Namen. Wir sprechen hier von Kommutativität beziehungsweise nennen solche Verknüpfungen kommutative Verknüpfungen. Der Begriff kommt vom lateinischen Wort commutare, was „vertauschen“ bedeutet. Es ist also:

Dialog-information.svg
Definition (Kommutativität)

Eine binäre Verknüpfung heißt kommutativ, wenn für alle gilt: .

Accessories-calculator.svg

Beispiel (Beispiel und Nichtbeispiel für Kommutativität)

  • Die Addition auf den reellen Zahlen ist kommutativ. Für alle reellen Zahlen und ist nämlich .
  • Die Subtraktion auf den reellen Zahlen ist nicht kommutativ. So ist , aber , also .

Assoziativität[Bearbeiten]

Was passiert, wenn wir mehr als zwei Objekte miteinander verknüpfen wollen? Nehmen wir die Addition als Verknüpfung und betrachten wir die Summe . Wie können wir diese Operation ausführen, wenn die Addition als zweistellige Verknüpfung definiert ist, also genau zwei Argumente zu einem Ergebnis zusammenfasst?

Hier haben wir zwei Möglichkeiten: Zum einen können wir zunächst die Summe von und bilden und dann hinzuaddieren. So berechnen wir . Zum anderen kann zunächst und miteinander addiert werden, um danach die Summe aus und dem Ergebnis der ersten Summe zu bilden. Hier wird gerechnet.

So haben wir bei jeder Verknüpfung zwei Möglichkeiten, um zu berechnen. Zum einen kann dieser Ausdruck als und zum anderen als berechnet werden. Im folgenden Diagramm sind beide Möglichkeiten mit dem Maschinenmodell dargestellt. Dabei stellt sich die Frage: Ist es egal, welche der beiden Methoden wir verwenden? Ist das Endergebnis gleich, egal in welcher Reihenfolge die einzelnen Verknüpfungen ausgerechnet werden?

Visualisierung zur Assoziativität von Verknüpfungen

Bei der Addition ist es egal, in welcher Reihenfolge die Verknüpfungen ausgerechnet werden. So ist für alle reellen Zahlen , und . Verknüpfungen wie die Addition, bei der die Reihenfolge der Verknüpfungsausrechnung egal ist, nennt man assoziativ. Das Wort kommt vom lateinischen associare und bedeutet „vereinigen“ beziehungsweise „verbinden“.

Dialog-information.svg
Definition (Assoziativität)

Eine binäre Verknüpfung heißt assoziativ, wenn für alle gilt: .

Accessories-calculator.svg

Beispiel (Beispiel und Gegenbeispiel für Assoziativität)

  • Die Addition auf den reellen Zahlen ist assoziativ. Die Aussage, dass für alle reellen Zahlen , und ist, nennt man auch Assoziativgesetz.
  • Die Subtraktion auf den reellen Zahlen ist nicht assoziativ. So ist , aber . Es ist also .

Weil bei einer assoziativen Verknüpfung die Reihenfolge egal ist, in der die einzelnen Verknüpfungen ausgewertet werden, können wir Klammern weglassen. Dies gilt für drei und auch für mehr Operanden. Du kannst dann also statt oder auch einfach schreiben. Beachte, dass eine Schreibweise wie ohne Klammern nur dann sinnvoll ist, wenn die Verknüpfung assoziativ ist. Bei nicht assoziativen Verknüpfungen musst du immer die Klammern setzen.

Übungsaufgaben[Bearbeiten]

Kommutativität und Assoziativität[Bearbeiten]

Accessories-text-editor.svg

Aufgabe

Welche der folgenden Verknüpfungen sind kommutativ und welche sind assoziativ?

  • Addition auf
  • Subtraktion auf
  • Multiplikation auf
  • Potenzbildung auf (x positiv, da sonst keine Verknüfung)
  • Funktionskomposition
  • Durchschnitt auf der Potenzmenge einer Menge
Applications-office.svg

Lösung

binäre Verknüpfung assoziativ kommutativ
Addition auf X X
Subtraktion auf
Multiplikation auf X X
Potenzbildung auf
Funktionskomposition X
Durchschnitt auf der Potenzmenge einer Menge X X

Eigenschaften von Verknüpfungen[Bearbeiten]

Accessories-text-editor.svg

Aufgabe (Einige Beispiele für Verknüpfungen)

Wir betrachten die folgenden drei Verknüpfungen:

  • auf
  • auf
  • auf

Entscheide, ob die folgenden Aussagen wahr oder falsch sind:

  1. Die Verknüpfung ist auf kommutativ.
  2. Die Verknüpfung ist auf assoziativ.
  3. Es gibt eine ganze Zahl , sodass für alle gilt: und .
  4. Zu jedem gibt es ein , sodass gilt: .
  5. Die Verknüpfung ist auf kommutativ.
  6. Die Verknüpfung ist auf assoziativ.
  7. Es gibt eine reelle Zahl , sodass für alle gilt: und .
  8. Es gibt , , und , sodass gilt:
  9. Die Verknüpfung ist auf kommutativ.
  10. Die Verknüpfung ist auf assoziativ.
  11. Es gibt eine natürliche Zahl , sodass für alle gilt: und .
Applications-office.svg

Lösung (Einige Beispiele für Verknüpfungen)

  1. Wahr: Wir überprüfen, ob für alle gilt:
    • Linke Seite:
    • Rechte Seite:
    Weil die Verknüpfungen und auf kommutativ sind, sind diese beiden Ergebnisse gleich. Also ist die Verknüpfung auf kommutativ.
  2. Wahr: Wir überprüfen, ob für alle gilt: . Die linke Seite ist:

    Und auf der rechten Seite erhalten wir:

    Da Addition und Multiplikation in kommutativ sind, können wir die Reihenfolge der Terme vertauschen. Wir sehen dann schnell, dass linke und rechte Seite übereinstimmen. Daher ist die Verknüpfung auf kommutativ.

  3. Wahr: Wir überprüfen, ob es eine ganze Zahl gibt, sodass für jede ganze Zahl gilt: und . Erste Gleichung:

    Dies muss nun für alle gelten. Also setzen wir 1 als Wert für ein, denn die Gleichung muss insbesondere auch dann gelten. Damit erhält man die Gleichung: . Also ist . Bisher haben wir nur ein Element gefunden, das die Gleichung für erfüllt. Deswegen prüfen wir jetzt, ob die Gleichung mit für alle ganzen Zahlen gilt. Wir setzen in die Verknüpfung ein und erhalten die allgemeingültige Aussageform . Damit haben wir gezeigt, dass die erste Gleichung für alle ganzen Zahlen gilt.

    Zweite Gleichung:

    Wir gehen vor wie bei der ersten Gleichung: Da auch die zweite Gleichung für alle gelten muss, muss insbesondere auch für die folgende Gleichung richtig sein: . Daraus folgt unmittelbar . Umgekehrt erfüllt auch die Gleichung für beliebige Werte .

  4. Falsch: Wir wollen herausfinden, ob es für jede ganze Zahl eine ganze Zahl gibt, sodass und ist. Betrachten wir zuerst die erste Gleichung:

    Achtung: Auf den ersten Blick sieht die letzte Zeile dieser Gleichungsumformung so aus, als ob wir für jede Zahl auch eine Zahl berechnen könnten, die erfüllt. Aber die Zahl muss auch eine ganze Zahl sein. Das ist zum Beispiel für nicht der Fall, wie wir durch Einsetzen in sehen: Hier ist . Also haben wir ein Gegenbeispiel zu unserer Aussage gefunden, weil es zu kein ganzzahliges gibt, sodass gilt.

  5. Wahr: Wir müssen überprüfen, ob für alle gilt:
    • Linke Seite:
    • Rechte Seite:
    Da die Addition in kommutativ ist, stimmen rechte und linke Seite überein. Also ist die Verknüpfung kommutativ.
  6. Falsch: Wir wollen überprüfen, ob die Verknüpfung assoziativ ist, also ob für alle gilt:

    • Linke Seite:
    • Rechte Seite:

    Vergleichen wir diese Seiten, dann vermuten wir schnell, dass diese nicht übereinstimmen. Wir können konkrete Werte für einsetzen und sehen

    Also ist die Verknüpfung nicht assoziativ.

  7. Falsch: Wir müssen untersuchen, ob es eine reelle Zahl gibt, sodass für alle gilt: und . Die beiden Gleichungen sind äquivalent, da wir ja schon gesehen haben, dass die Verknüpfung kommutativ ist. Wir kümmern uns also nur um die Gleichung . Willst du ein solches finden oder seine Existenz widerlegen, gehst du immer gleich vor: Du nimmst die Gleichung und stellst sie um, damit du Dinge über erfahren kannst. Da die Gleichung für alle gelten muss, kannst du auch konkrete Werte für einsetzen und so etwas über erfahren. Probieren wir das einfach mal aus. Wir betrachten die Gleichung und stellen sie um:

    Diese Gleichung soll also für alle gelten. Du musst nur zwei verschiedene Werte von einsetzen und schon siehst du, dass das unmöglich ist. Wie sollte denn gleichzeitig (für ) und (für ) gelten? Also existiert kein mit der geforderten Eigenschaft.

  8. Wahr: Zunächst solltest du erkennen, dass diese Aussage zwar sehr ähnlich zur Assoziativität aussieht, aber der Allquantor durch einen Existenzquantor ersetzt wurde. Wir müssen also nur ein Beispiel von Zahlen finden, das die altbekannte Eigenschaft erfüllt. Als wir gezeigt haben, dass nicht assoziativ ist, haben wir die die beiden obigen Terme ausgerechnet:

    Wie kannst du jetzt und wählen, damit die beiden rechten Seiten gleich sind? Du könntest zum Beispiel wählen. Und schon hast du die Existenz der Zahlen bewiesen und bist fertig.

    Accessories-text-editor.svg

    Aufgabe (Zusatzaufgabe)

    Du kannst auch versuchen zu beweisen, dass ein „halbes Assoziativgesetz“ gilt: Es gilt genau dann, wenn gilt.

  9. Falsch: Wir wollen untersuchen, ob die Gleichung für alle natürlichen Zahlen und erfüllt ist. Wie üblich setzen wir zunächst die Verknüpfungsvorschrift ein und erhalten:
    • Linke Seite:
    • Rechte Seite
    Sicherlich siehst du, dass beiden Seiten für die meisten Werte von und nicht übereinstimmen. Wir setzen zum Beispiel und und sehen:

    Also ist die Verknüofung nicht kommutativ.

  10. Falsch: Wir müssen wieder das Assoziativgesetz für beliebige nachrechnen.
    • Linke Seite:
    • Rechte Seite:
    Auf der linken Seite kommt höchstens quadratisch vor, wohingegen auf der rechten Seite sogar in vierter Potenz vorkommt. Das ist ein ganz typisches Indiz dafür, dass die beiden Seiten im Allgemeinen nicht übereinstimmen können. Allerdings ist ein Indiz eben noch kein Beweis. Was wäre denn, wenn es irgendwelche anderen Terme gäbe, die diesen Unterschied in den Größenordnungen kompensieren könnten, die wir aber einfach nicht beachten würden? Um einen stichhaltigen Beweis für die Ungleichheit anzugeben, wollen wir Zahlen wählen, bei denen man die verschiedenen Werte der beiden Seiten konkret sieht. Wir wollen natürlich möglichst einfache Werte einsetzen. Wir wählen dafür . Dazu wählen wir , damit der Unterschied zwischen und zum Tragen kommt. Jetzt vergleichen wir wieder die beiden Seiten:
    • Linke Seite:
    • Rechte Seite:
    Da die beiden Seiten sich unterscheiden, kann die Verknüpfung nicht assoziativ sein.
  11. Falsch: Wir müssen wieder prüfen, ob eine natürliche Zahl existiert, sodass für alle gilt. Wir betrachten zunächst nur die linke Gleichung und wollen einsehen, dass es kein gibt, das diese Gleichung im Allgemeinen erfüllt. Wie immer stellen wir die Gleichung dafür um:

    Nun sollen wir also einen festen Wert finden, der gleich ist – und zwar für alle natürlichen Zahlen . Wir müssen nur zwei verschiedene Werte einsetzen und sehen schon, dass das nicht funktionieren kann. Du solltest dir auch bewusst sein, dass die Zahl in jedem Fall eine natürliche Zahl sein müsste.

Emblem-important.svg

Hinweis

Das Element in 3. nennen wir neutrales Element bezüglich in . Neutrale Elemente spielen eine wichtige Rolle in der Algebra. Genauso ist in 7. das neutrale Element bezüglich in , in 11. bezüglich in .