Verknüpfungstafel

Eine Verknüpfungstafel ist eine Tabelle, mit der in der Mathematik und insbesondere der Algebra zweistellige Verknüpfungen dargestellt werden. Zum Beispiel zeigt die folgende Verknüpfungstafel die Multiplikation $\cdot :\ \mathbb {Z} _{2}\times \mathbb {Z} _{2}\to \mathbb {Z} _{2}$ auf der Menge $\mathbb {\mathbb {Z} } _{2}=\{-1,1\}$:

$\cdot$	1	−1
1	1	−1
−1	−1	1

Verknüpfungstafeln treten zum Beispiel in der Aussagenlogik in Form von Wahrheitstafeln auf. In der Gruppentheorie können sie verwendet werden, um (kleine) Gruppen aufzuschreiben oder zu konstruieren.

Tafeln zweistelliger Verknüpfungen

Die Darstellung als Verknüpfungstafel eignet sich für jede beliebige Verknüpfung $\circ \colon A\times B\to C$. Eine solche Verknüpfung $c=a\circ b$ ordnet jedem Paar von Elementen $a\in A$ und $b\in B$ ein Element $c\in C$ zu. Diese Zuordnung kann in einer Tabelle folgendermaßen dargestellt werden:

$\circ$	$\dots$	$b$	$\dots$
$\vdots$
$a$		$a\circ b$
$\vdots$

In der Eingangsspalte steht das erste Argument $a\in A$, in der Kopfzeile das zweite Argument $b\in B$, im Schnittpunkt von $a$-Zeile und $b$-Spalte findet sich das Ergebnis $c=a\circ b$ der Verknüpfung.

Um die Tabelle vollständig aufschreiben zu können, setzt man zudem voraus, dass die Mengen $A$ und $B$ endlich sind, und für praktische Zwecke auch noch hinreichend klein.

Häufig werden Verknüpfungstafeln für innere Verknüpfungen verwendet (also im Fall $A=B=C$) und hier insbesondere für Gruppen.

Beispiele

Beispiele aus der Logik

Wahrheitstafeln dienen in der Aussagenlogik dazu, das Ergebnis der logischen Verknüpfungen (Junktoren) zu beschreiben bzw. zu definieren. Drei typische Beispiele sind

• der Konjunktor $\wedge$ (logisches "und"),
• der Disjunktor $\vee$ (logisches "oder"),
• die Implikation $\Rightarrow$ (logisches "wenn... dann...").

Die folgenden Tabellen zeigen die Verknüpfungstafeln dieser Junktoren:

$\wedge$ wahr falsch wahr wahr falsch falsch falsch falsch

$\vee$ wahr falsch wahr wahr wahr falsch wahr falsch

$\Rightarrow$ wahr falsch wahr wahr falsch falsch wahr wahr

Die ersten beiden Tabellen sind unmittelbar einleuchtend. Die dritte hingegen ist weniger intuitiv: Sie drückt die Tatsache aus, dass man durch korrektes Schließen aus wahren Voraussetzungen nur wahre Folgerungen gewinnen kann (erste Zeile), dass man aus falschen Voraussetzungen aber sowohl falsche als auch wahre Folgerungen ziehen kann (zweite Zeile). Dieses Beispiel zeigt, dass auch die logischen Verknüpfungen einer klärenden Definition bedürfen, und die Wahrheitstafeln sind hierzu eine geeignete Schreibweise.

Beispiele aus der Algebra

Auf der Menge $A=\{0,1,2,3,4,5,6,7,8,9,10,11\}$ betrachten wir zwei Verknüpfungen, die Addition $a+b\,{\bmod {5}}$ und die Multiplikation $a\cdot b\,{\bmod {5}}$. Diese entsprechen den folgenden beiden Verknüpfungstafeln:

$+$ 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3

$\cdot$ 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1

Manche Eigenschaften einer inneren zweistelligen Verknüpfung $\circ \colon A\times A\to A$ lassen sich leicht aus der Verknüpfungstafel ablesen:

Kommutativität

Die Verknüpfung $\circ$ ist genau dann kommutativ, erfüllt also $a\circ b=b\circ a$ für alle $a,b\in A$, wenn die Verknüpfungstafel symmetrisch bezüglich der Hauptdiagonale ist. Dies ist in beiden obigen Beispielen der Fall.

Neutrales Element

Ein Element $e\in A$ ist genau dann linksneutral, erfüllt also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e \circ a = a} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \in A} , wenn die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} -Zeile eine Kopie der Kopfzeile ist. Gleiches gilt für ein rechtsneutrales Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} und die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} -Spalte. Im obigen Beispiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (A,+)} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} ein beidseitig neutrales Element. Im Beispiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (A,\cdot)} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} ein beidseitig neutrales Element.

Inverse Elemente

Wir nehmen nach dem vorherigen Beispiel an, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} ein beidseitig neutrales Element für die Verknüpfung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \circ} ist. Zu einem gegebenen Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} genau dann rechtsinvers, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \circ b = e} gilt. Die Existenz eines solchen Rechtsinversen ersieht man daran, dass in der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} -Zeile das Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} auftaucht. Gleiches gilt für ein Linksinverses und die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} -Spalte. Im obigen Beispiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (A,+)} ist etwa Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3} beidseitig invers zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2} . Im Beispiel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (A,\cdot)} hat Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} kein Inverses, jedes andere Element besitzt genau ein Inverses.

Assoziativität

Die Verknüpfung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \circ} ist assoziativ, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \circ (b \circ c) = (a \circ b) \circ c} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a,b,c \in A} gilt. Ob eine Verknüpfung diese Eigenschaft hat, ist beim Anblick ihrer Tafel nicht direkt ersichtlich und lässt sich nur durch mühsames Ausprobieren überprüfen.

Quasigruppen und lateinische Quadrate

Eine Quasigruppe ist eine nichtleere Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q} mit einer Verknüpfung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \circ \colon Q \times Q \to Q} , sodass für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q} die Gleichungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \circ x = b} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y \circ a = b} jeweils genau eine Lösung in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q} haben. Dies äußert sich in der Verknüpfungstafel dadurch, dass jede Zeile eine Permutation der Kopfzeile ist und jede Spalte eine Permutation der Eingangsspalte. Eine solche Tabelle nennt man auch lateinisches Quadrat.

Für weitere Beispiele von Verknüpfungstafeln siehe: Kleinsche Vierergruppe, Quaternionengruppe, Sedenion, S3 (Gruppe), A4 (Gruppe).

Geschichte

Verknüpfungstafeln wurden in der Gruppentheorie zuerst von Arthur Cayley verwendet. In einer Arbeit von 1854 nennt er sie schlicht Tafeln (engl. tables) und benutzt sie zur Erläuterung von Gruppen. Ihm zu Ehren werden Verknüpfungstafeln in der Gruppentheorie auch Cayley-Tafeln genannt. Zur Konstruktion von Gruppen sind Verknüpfungstafeln jedoch nur für sehr kleine Gruppen geeignet, da das systematische Ausprobieren bei größerer Elementezahl hoffnungslos ineffizient ist. Diese Herangehensweise wurde daher in der Gruppentheorie durch leistungsfähigere Konstruktionen ergänzt und schließlich ersetzt, und spielt für die Theorie heute keine Rolle mehr. Die Verknüpfungstafel einer Gruppe führt jedoch unmittelbar zum Satz von Cayley und damit zu einem natürlichen Ausgangspunkt der Darstellungstheorie von Gruppen.

• Arthur Cayley: "On the theory of groups, as depending on the symbolic equation θ ⁿ = 1", Philosophical Magazine, Vol. 7, pp. 40–47. Online verfügbar bei GoogleBooks als Teil seiner Gesammelten Werke.
• Arthur Cayley: On the Theory of Groups. In: American Journal of Mathematics, Vol. 11, No. 2 (Januar 1889), S. 139–157, Online frei verfügbar bei JSTOR 2369415.

Weblinks

• Applet zur Erstellung von Gruppentafeln (englisch)