Mengenlehre

Ich lese zur Zeit "Computerlinguistik und Sprachtechnologie. Eine Einführung" in der 2. Auflage von Klabunde (et al.) und habe mir gedacht, dass ich vielleicht ein paar Grundlagen der Computerlinguistik erörtern könnte. Ich fange bei der Mengenlehre an und gehe dann zur Aussagenlogik und Prädikatenlogik über. Es soll eine Serie werden, die wirklich kurz und verständlich auf Grundlagen veingeht, zur Vertiefung empfehle ich entsprechende (mathematische) Fachliteratur. Folgende kurze Zusammenfassung basiert dementsprechend auf Klabunde et al. (2004: 26ff.), manchmal wurde wörtlich zitiert.


1. Einführung

1.1 Mengenbegriff

Die Mengenlehre wurde von Georg Cantor begründet. Unter einer Menge versteht Cantor

[...] jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welche die „Elemente“ von M genannt werden) zu einem Ganzen. (Cantor 1895)

Sprich die Ansammlung von Elementen. Nehmen wir die deutsche Flagge und bezeichnen die Menge ihrer Farben als G. Sie besteht aus den drei Farben schwarz, rot und gold. Als Formel würde man das folgendermaßen schreiben:

G = { schwarz, rot, gold }

Sprich: Die Menge G besteht aus den Elementen schwarz, rot und gold. die Reihenfolge und mehrfaches Vorkommen der einzelnen Elemente ist egal. Die Menge { rot, rot, gold, gold, gold, schwarz } ist also das selbe wie die Menge { schwarz, rot, gold }.


1.2 Beschreibung einer Menge durch Charakteristika

Um eine Menge zu beschreiben muss man aber nicht unbedingt alle Elemente angeben, man kann auch ein Charakteristika angeben. So könnte man zum Beispiel die Menge G anders beschreiben:

G' = { x | x ist eine Farbe der deutschen Flagge }

Damit gilt:

G = G'

1.3 Elemente

Rot ist ein Element der Menge G, dies drückt man folgendermaßen aus:

{ rot } ∈ G

Im Gegensatz dazu ist grün nicht in der deutschen Flagge vorhanden, was man so ausdrückt:

{ grün } ∉ G

1.4 Leere Menge

Wenn eine Menge, warum auch immer, keine Elemente enthält, dann spricht man von der leeren Menge L, zum Beispiel:

G = { x | x ist eine Farbe der deutschen Flagge und auch in der irischen Flagge enthalten }

die irische Flage (hier als Menge I definiert) hat die Farben { grün, weiss, orange }, also gilt:

L = { ∅ }

1.5 Kardinalität

Kardinalität ist die Anzahl der Elemente die eine Menge enthält. In unserem Fall:

|G| = 3

2. Beziehungen von Mengen

2.1 (Echte) Teilmenge

Definieren wir die Menge der ungeraden Zahlen als:

U = { 1, 3, 5, ... }

und die Menge der natürlichen Zahlen als:

ℕ = { 1, 2, 3, ... }

dann ist die Menge U ein Teil der natürlichen Zahlen und damit der Menge ℕ. Wir sprechen von einer Teilmenge:

U ⊆ ℕ

Dies bedeutet, dass jedes Element von U auch Element von ℕ ist. Will man ausdrücken, dass U eine Teilmenge von ℕ ist, aber nicht gleich ℕ, so benutzt man den Begriff der echten Teilmenge:

U ⊂ ℕ

2.2 (Echte) Obermenge

Daraus folgt, dass ℕ die Obermenge von U ist:

ℕ ⊇ U

und natürlich, dass ℕ die echte Obermenge von U ist:

ℕ ⊃ U

2.3 Potenzmenge

Die Potenzmenge ℘(A) einer Menge A ist diejenige Menge, die alle Teilmengen der Menge umfasst (und sich selbst plus die leere Menge), also:

℘(A) = { X | X ⊆ A }

Im konkreten Fall mit der deutschen Flagge wäre die Potenzmenge von G:

℘(G) = { ∅, {schwarz}, {rot}, {gold}, {schwarz, rot}, {schwarz, gold}, {rot, gold}, {schwarz, rot gold} }

3. Mengenoperationen

3.1 Vereinigung

Die Vereinigung von zwei Mengen enthält alle Elemente, die in der einen (hier: A) oder in der anderen Menge (hier: B) vorkommen, also:

A ∪ B = { x | x ∈ A oder x ∈ B }

konkret heißt das für unser Beispiel mit den natürlichen und ungeraden Zahlen:

U ∪ ℕ = ℕ

Alle ungeraden Zahlen kommen auch in den natürlichen Zahlen vor, ist also Teilmenge der natürlichen Zahlen und die Vereinigung damit ℕ. Nehmen wir unser anderes Beispiel mit der deutschen und irischen Flagge:

G ∪ I = { schwarz, rot, gold, grün, weiss, orange }

3.2 Schnitt

Der Schnitt zweier Mengen enthält alle Elemente die sowohl in der einen, als auch in der anderen Menge vorkommen, also:

A ∩ B = { x | x ∈ A und x ∈ B }

Konkret bei unserem Flaggenbeispiel:

G ∩ I = { ∅ }

Leere Menge, da die beiden Mengen keine gemeinsamen Elemente haben.



3.3 Differenz

Eine Differenz zweier Mengen enthält alle Elemente, die zwar in A vorkommen aber nicht in B, also:

A \ B = { x | x ∈ A und x ∉ B }

Nehmen wir die Flagge des Vereinigten Königreichs ({ blau, rot, weiss } = B), also:

B \ G = { blau, weiss }

3. 4 Komplement

Hat man eine Grundmenge G so ist das Komplement Ā einer Teilmenge A ⊆ G definiert durch:

Ā = G \ A

Konkret für unser beispiel mit den ungeraden und natürlichen Zahlen:

Ū = ℕ \ U

Um es wirklich konkret zu sagen, das Komplement der ungeraden Zahlen sind die geraden Zahlen, also:

Ū = { 2, 4, 6, ... }

3.5 Charakteristische Funktion

Wir haben oben G als Grundmenge und A als eine Teilmenge von G definiert. Die charakteristische Funktion ist deshalb:

C_A(x) = {0 x ∉ A
_______{1 x ∈ A

Dadurch kann man Mengenoperation anders beschreiben, z.B.:

C_A∩B = C_A ⋅ C_B

4. Mengengesetze

Im Rahmen von Mengenoperation gelten einige logische Mengengesetze, die ich hier noch erwähnen will.


4.1 Kommunikativgesetz

A ∩ B = B ∩ A
A ∪ B = B ∪ A

4.2 Assoziativgesetz

A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ∩ (B ∩ C) = (A ∩ B) ∩ C


4.3 Distributivgesetz

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) (A ∩ C)


4.4 Gesetze von DeMorgan
_____
(A ∪ O) = (Ā ∩ Ō)
_____
(A ∩ O) = (Ā ∪ Ō)

Ich hab kein B mit Makron gefunden, also stellt euch vor das O wäre ein B.


5. Schlussbemerkung

Die Mengenlehre braucht man für alle Bereiche der Computerlinuistik und ist notwendiges Arbeitswerkzeug. Ich hoffe ihr freut euch schon auf den nächsten Beitrag über Aussagenlogik, denn das wird richtig knackig.