Mathematische Grundlagen

Gruppe

 aufwärts

Eine Gruppe ist eine häufig vorkommende mathe­matische Struktur. Sie besteht aus einer Menge, deren Elemente sich verknüpfen lassen. Außerdem gelten drei sogenannte Gruppen­axiome: Die Verknüpfung ist assoziativ, es ist ein neutrales Element vorhanden und jedes Element hat ein inverses Element.

Verknüpfung

Definition:  Sei M eine Menge. Eine Verknüpfung auf M ist eine Abbildung

 •   :  M × M Pfeil nach rechts M,

die je zwei Elementen a, b Element M ein Element c Element M zuordnet. Die Schreibweise ist

a • b  =  c.

Wenn die Menge M endlich ist, lassen sich die Ergebnis­werte der Verknüpfung in Form einer Ver­knüpfungstafel angeben.

Definition:  Eine Ver­knüpfungstafel ist eine Tabelle, die für alle Elemente a, b Element M das Ergebnis der Verknüpfung a • b in Zeile a und Spalte b enthält.

Beispiel:  Sei M die Menge boolesche Werte = {0, 1}. Auf boolesche Werte sei eine Verknüpfung entweder oder in folgender Weise definiert:

 

entweder oder01
001
110

Das Ergebnis von 1entweder oder0 beispiels­weise ergibt sich als Eintrag in Zeile 1 und Spalte 0, nämlich als 1entweder oder0 = 1.

Beispiel:  Die Menge M sei die Menge natürliche Zahlen der natürlichen Zahlen. Dann sind + (Addition), · (Multi­plikation) und "hoch" (Potenzierung) Ver­knüpfungen.

Welche Zahl das Ergebnis der Verknüpfung etwa von 5 + 3 oder von 7·4 oder von 23 ist, müssen wir im allgemeinen ausrechnen (um 3 weiterzählen von 5 aus, die 7 viermal addieren, bzw. die 2 dreimal mit sich selbst multi­plizieren). Schneller geht es, wenn wir die Ver­knüpfungstafeln der einstelligen Zahlen auswendig lernen (z.B. kleines Einmaleins). Für die Verknüpfung von größeren Zahlen gibt es die Rechen­verfahren der Arithmetik (Kopfrechnen, schrift­liches Addieren und Multi­plizieren).

Eigen­schaften von Ver­knüpfungen

Es kommt bei einer Verknüpfung im allgemeinen auf die Reihenfolge der Elemente an. Ver­knüpfungen, bei denen es nicht auf die Reihenfolge ankommt, heißen kommutativ.

Definition:  Sei M eine Menge mit einer Verknüpfung  • . Die Verknüpfung  •  heißt kommutativ, wenn für alle Elemente a, b Element M gilt

a • b  =  b • a.

Beispiel:  Die oben angegebenen Ver­knüpfungen entweder oder, + und · sind kommutativ. Die Verknüpfung "hoch" ist jedoch nicht kommutativ, denn es ist z.B. 23 = 8, aber 32 = 9.

Wenn wir nicht nur zwei, sondern drei Elemente a, b, c miteinander verknüpfen wollen, gehen wir wie folgt vor: wir verknüpfen die ersten beiden Elemente, und das Ergebnis verknüpfen wir mit dem dritten Element (Auswertung von links nach rechts):

(a • b) • c.

Wir hätten jedoch auch erst das zweite und dritte Element verknüpfen und dann das erste Element mit diesem Ergebnis verknüpfen können (Auswertung von rechts nach links):

a • (b • c).

Welche Art der Auswertung ist die richtige? Nun, es stellt sich heraus, dass es bei vielen Ver­knüpfungen egal ist: in beiden Fällen kommt dasselbe Ergebnis heraus. Derartige Ver­knüpfungen heißen assoziativ.

In den anderen Fällen muss man sich auf eine Auswertungsart einigen, z.B. Auswertung von links nach rechts, oder durch Klammern die Reihenfolge der Auswertung vorschreiben.

Definition:  Sei M eine Menge mit einer Verknüpfung  • . Die Verknüpfung  •  heißt assoziativ, wenn für alle Elemente a, b, c Element M gilt

(a • b) • c  =  a • (b • c).

Beispiel:  Die oben angegebenen Ver­knüpfungen entweder oder, + und · sind assoziativ. Die Verknüpfung "hoch" ist jedoch nicht assoziativ, denn es ist z.B. (22)3 = 43 = 64, aber 2(23) = 28 = 256.

Aufgabe 1:  Sei M die Menge ganze Zahlen der ganzen Zahlen. Welche Eigen­schaften hat die Verknüpfung "–"  (Subtraktion)?

assoziativ   ja   nein    ?
kommutativ   ja   nein    ?

Halbgruppe

Im Folgenden bezeichnen wir eine Menge M, auf der eine Verknüpfung  •  definiert ist, mit (M,  • ). Wir betrachten nun Eigen­schaften solcher Mengen. Je nach dem, welche von insgesamt vier Eigen­schaften erfüllt sind, bilden diese Mengen unter­schiedliche mathe­matische Strukturen. Die einfachste dieser Strukturen ist die Halbgruppe. Bei einer Halbgruppe wird lediglich verlangt, dass die Verknüpfung assoziativ ist.

Definition:  Eine Menge mit einer assoziativen Verknüpfung ist eine Halbgruppe.

Beispiel:  Sei A ein Alphabet und A+ die Menge der nichtleeren Wörter über dem Alphabet. Auf A+ sei die Verkettung von Wörtern als Verknüpfung  •  definiert. Zwei Wörter werden verkettet, indem sie einfach hinter­einander geschrieben werden, z.B.

ab  •  aacc = abaacc.

Die Verknüpfung ist offensichtlich assoziativ. Die Menge A+ mit der Verkettung als Verknüpfung bildet daher eine Halbgruppe.

Die Menge der natürlichen Zahlen mit der Addition (natürliche Zahlen, +) ist eine Halbgruppe. Ebenso ist (natürliche Zahlen, ·) eine Halbgruppe.

Monoid

Definition:  Eine Halbgruppe (M,  • ) ist ein Monoid, wenn sie ein neutrales Element enthält. Ein Element e Element M heißt neutrales Element, wenn für alle a Element M gilt

e • a  =  a • e  =  a.

Das neutrale Element wird auch als Nullelement oder als Einselement bezeichnet, je nach dem, ob die Verknüpfung als Addition oder als Multi­plikation verstanden wird.

Beispiel:  Die Menge A* der Wörter über einem Alphabet A (einschließ­lich des leeren Wortes ε) mit der Verkettung als Verknüpfung ist ein Monoid. Das leere Wort ε ist das neutrale Element, denn es gilt

ε • w  =  w • ε  =  w   für alle Wörter w Element A*.

Sei X eine Menge und Potenzmenge(X) die Potenzmenge von X, d.h. die Menge aller Teilmengen von X. Dann ist Potenzmenge(X) mit der Vereinigung von Mengen  vereinigt  als Verknüpfung und der leeren Menge  leere Menge  als neutralem Element ein Monoid.

Die Menge der natürlichen Zahlen mit der Multi­plikation (natürliche Zahlen, ·) ist ein Monoid mit der 1 als neutralem Element. Die Menge der natürlichen Zahlen einschließ­lich der Null mit der Addition (natürliche Zahlen0, +) ist ein Monoid. Die Null ist das neutrale Element bezüglich der Addition. Ferner ist (boolesche Werte, entweder oder) ein Monoid mit der 0 als neutralem Element.

Satz:  Sei (M,  • ) ein Monoid. Dann ist das neutrale Element eindeutig bestimmt, d.h. es gibt nicht mehrere neutrale Elemente in (M,  • ).

Beweis:  Seien e und f neutrale Elemente. Dann gilt

f  =  e • f  =  e,

denn f  =  e • f, weil e neutral ist, und e • f  =  e, weil f neutral ist.

Im Folgenden schreiben wir ein Monoid M mit Verknüpfung  •  und neutralem Element e als Tripel (M,  • , e). So sind beispiels­weise (Potenzmenge(X),  vereinigt ,  leere Menge ), (natürliche Zahlen, ·, 1), (natürliche Zahlen0, +, 0) sowie (boolesche Werte, entweder oder, 0) Monoide.

Gruppe

Definition:  Ein Monoid (M,  • , e) ist eine Gruppe, wenn es zu jedem Element a Element M ein inverses Element in M gibt. Ein Element a' Element M heißt invers zu a Element M, wenn

a • a'  =  e

ist, d.h. wenn die Verknüpfung von a und a' das neutrale Element e ergibt.

Beispiel:  Die Menge der ganzen Zahlen mit der Addition (ganze Zahlen, +, 0) ist eine Gruppe. Zu jeder Zahl a ist -a das inverse Element.

Die Menge (boolesche Werte, entweder oder, 0) ist eine Gruppe. Die 0 und die 1 sind jeweils zu sich selbst invers.

Satz:  Sei (M,  • , e) eine Gruppe. Für jedes a Element M gilt: wenn a' zu a invers ist, dann auch a zu a'.

Beweis:  Sei zunächst a'' das zu a' inverse Element, d.h. a' • a'' = e. Dann ist

a  =  a • e  =  a • a' • a''  =  e • a''  =  a''

d.h. a = a'' ist zu a' invers.

Abelsche Gruppe

Definition:  Eine Gruppe (M,  • , e) heißt abelsche Gruppe (nach N.H. Abelzur Person), wenn die Verknüpfung  •  kommutativ ist, d.h. wenn für alle Elemente a, b Element M gilt

a • b  =  b • a.

Beispiel:  (ganze Zahlen, +, 0) ist abelsche Gruppe.

Die additive Gruppe modulo n (ganze Zahlenn, +n, 0) ist eine abelsche Gruppe. Die Menge ganze Zahlenn besteht aus den ganzen Zahlen 0, ..., n-1. Die Verknüpfung +n bezeichnet die Addition modulo n.

Die multi­plikative Gruppe modulo n (ganze Zahlenn*, ·n, 1) ist eine abelsche Gruppe. Die Menge ganze Zahlenn* besteht aus allen Elementen von ganze Zahlenn, die teilerfremd zu n sind. Die Verknüpfung ·n bezeichnet die Multi­plikation modulo n.

Die Menge aller Permutationen von n Elementen mit der Komposition (Hinter­einanderausführung von Abbildungen) als Verknüpfung ist eine Gruppe, jedoch keine abelsche Gruppe.

Zusammenfassung

Eine Gruppe ist zunächst eine Menge M, auf der eine Verknüpfung  •  definiert ist. Eine Verknüpfung ist eine Abbildung von M × M in M. Es müssen darüber hinaus drei Eigen­schaften erfüllt sein, diese heißen die Gruppen­axiome:

Bei einer abelschen Gruppe gilt zusätzlich:

 

Weiter mit:   [Gruppentheorie]   [Literatur]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 28.08.2000   Updated: 21.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik