{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### Mengen:\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Was muss ich für den Test wissen?\n", "## Mengen\n", "\n", "- Was sind Mengen, und wie werden sie notiert?\n", "- endliche und unendliche Mengen\n", "- explizite und implizite Mengenbeschreibungen\n", "- Besonderheiten der leeren Menge" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Mengen\n", "## Einführung: Was ist eine Menge?\n", "> „Eine Menge ist eine Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens (welche die ‚Elemente‘ von M genannt werden) zu einem Ganzen.“ \n", "(Georg Cantor, Begründer der Mengenlehre)\n", "\n", "Eine Menge ist also eine Sammlung von Objekten.\n", "Diese Objekte heißen Elemente. \n", "Mengen notiert man in geschweiften Klammern $\\{ \\}$.\n", "\n", "Zwei Elemente einer Menge sind nie gleich (das meint Cantor mit \"wohlunterschieden\"). \n", "Die Mengen $M_1=\\{a,b,c\\}$ und $M_2=\\{a,b,a,c\\}$ enthalten also die gleichen Elemente: Die Buchstaben $a$, $b$ und $c$. Man könnte sagen, das Aufschreiben eines der beiden $a$ in $M_2$ war überflüssig.\n", "Man sagt, $M_1$ und $M_2$ sind identisch oder gleich: \n", "$$M_1=M_2$$\n", "\n", "Die Reihenfolge der Elemente in der Aufzählung ist auch nicht wichtig:\n", "$$\\{a,b,c,d\\}=\\{a,b,d,c\\}=\\{b,a,c,d\\}=\\dots$$\n", "\n", "Mengen können außerdem Elemente anderer Mengen sein: \n", "$$M_3=\\{1,2,\\{3\\}\\}$$\n", "$M_3$ enthält z.B. die Menge, die nur die Zahl $3$ enthält. \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Notation und Terminologie\n", "Um mit Mengen arbeiten zu können, brauchen wir noch ein paar weitere Symbole und Begriffe. \n", "\n", "### Schreibweisen für Variablen\n", "\n", "Eine Konvention habt ihr sicher schon mitbekommen: \n", "Die Variablen für Mengen, z.B. $M_1,M_2,M_3$ oben, sind immer groß geschrieben. Manchmal findet man auch andere Großbuchstaben als Bezeichner für Mengen, z.B. griechische: $\\Delta,\\Sigma$.\n", "\n", "Die Variablen für Elemente einer Menge (wenn die Elemente nicht selber Mengen sind) sind meist Kleinbuchstaben: $m,n,\\dots$.\n", "\n", "### Ist (kein) Element von\n", "\n", "Um zu beschreiben, dass ein Objekt $m$ das Element einer Menge $M$ ist, schreibt man: $m\\in M$\n", "\n", "Zum Beispiel ist $a$ in der Menge $M_1=\\{a,b,c\\}$ enthalten: $a \\in M_1$.\n", "\n", "Um zu zeigen, dass ein Element $m$ nicht in einer Menge $M$ enthalten ist, schreibt man: $m \\notin M$.\n", "Beispiel: $k \\notin M_1$.\n", "Man sagt: $a$ ist in $M_1$ und $k$ ist nicht in $M_1$.\n", "\n", "### sehr sehr kleine Mengen\n", "\n", "Die leere Menge enthält kein Element. Man verwendet für die leere Menge das Symbol $\\emptyset$\n", "Die leere Menge hat bei vielen Mengenoperationen eine besondere Rolle. Wir werden gleich ein paar Beispiele sehen. \n", "\n", "Ein $singleton$ oder $Einermenge$ nennt man eine Menge, die genau ein Element enthält. \n", "Natürlich kann dieses Element auch selbst eine Menge sein. Sowohl $\\{23\\}$ als auch $\\{\\{a,b,c,d,e\\}\\}$ sind also singletons." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Mengenbeschreibungen\n", "\n", "Die Beschreibung einer Menge durch Aufzählung ihrer Elemente, wie wir bereits oben gesehen haben, nennt man **explizite Mengendarstellung**: $$M_5=\\{11,12,13,14,15,16,17,18,19\\}$$\n", "\n", "Die explizite Mengendarstellung funktionert nicht bei unendlich großen Mengen - klar, man kann nicht \"alle ganzen Zahlen von 1 bis unendlich aufzählen\".\n", "\n", "Wenn man bei größeren Mengen Tinte und Zeit sparen möchte, kann man Mengen durch **implizite Mengendarstellung** beschreiben. \n", "Dabei definiert man die Elemente der Menge über ihre Eigenschaften. \n", "\n", "Es gibt dann häufig mehrere Beschreibungen für die gleiche Menge. Alle Beschreibungen folgen aber dem selben Prinzip. Das wird an einem Beispiel deutlich. Sei $U$ die Menge aller U-Bahnnen. $baujahr(u)$ ist eine Funktion, die das Baujahr einer U-Bahn $u$ beschreibt. Wir werden später genauer sehen, wie Funktionen aufgebaut sind. Sei $M_{alt}$ die Menge aller U-Bahnen, die vor 1990 gebaut wurden. Man kann diese Menge auf mindestens 4 verschiedene Arten beschreiben:\n", "\n", "\n", "$1: \\{x \\in U \\: | \\: baujahr(x) < 1990 \\}$\n", "\n", "$2: \\{x \\: | \\: x \\in U, baujahr(x) < 1990 \\}$\n", "\n", "$3: \\{x \\: | \\: x \\in U, baujahr(x) \\le 1989 \\}$\n", "\n", "$4: \\{x \\in U \\: | \\: baujahr(x) \\le 1989 \\}$\n", "\n", "Alle vier Beschreibungen enthalten die selbe Information: $M_{alt}$ besteht aus allen Objekten $x$, sodass \n", "- $x$ in der Menge der U-Bahnen ($U$) enthalten ist, und \n", "- das Baujahr dieses $x$ höchstens 1989 ist. \n", "\n", "Die Beschreibungen in $1-4$ nennt man auch Beschreibung mittels charakteristischer Eigenschaft. \n", "Das $x$ in dieser Art der Beschreibung nennt man Element. \n", "In $1$ und $4$ nennt man das $U$ aus $x \\in U$ den Grundbereich.\n", "Alles hinter dem Pipe-Symbol $|$ beschreibt die Eigenschaften, die auf das Element $x$ zutreffen müssen, damit es in der Menge enthalten ist. \n", "Man kann den Grundbereich auch in die Eigenschaften verschieben, so wie in $2$ und $3$. \n", "\n", "\n", "Manchmal findet man auch textbasierte implizierte Mengendarstellungen:\n", "\n", "$5: \\{x \\: | \\: x$ ist eine U-Bahn, die vor 1990 gebaut wurde$ \\}$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### implizite Mengenbeschreibung durch rekursive Definition" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Folie 10](Folien/01/01_Mengen-und-Mengenoperationen-21.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Rekursion wird uns später noch häufig begegnen. Es bezeichnet den Prozess in 1-3 auf der Folie. Wikipedia sagt:\n", "> Als Rekursion (lateinisch recurrere ‚zurücklaufen‘) bezeichnet man den abstrakten Vorgang, dass Regeln auf ein Produkt, das sie hervorgebracht haben, von neuem angewandt werden.\n", "\n", "Das bedeutet: Die Regel 1 - Festlegung endlich vieler Startelemente - nennt die ersten Nachkommen von Cantor - seine Kinder. \n", "Auf dieses Produkt wird Regel 2 angewendet - Die Kinder von Cantors Kindern sind seine Enkel, deren Kinder sind seine Urenkel etc. \n", "So können alle Nachkommen einer beliebigen Person aufgelistet werden.\n", "\n", "Die Regel 3 ist nötig, um Klarheit zu schaffen, damit die Menge der Nachkommen von Cantor nicht unendlich groß wird.\n", "\n", "Wenn Cantor keine Kinder hatte, ist die Menge von Cantors Nachkommen nach Schritt 1 leer. In Schritt 2 können also keine weiteren Nachkommen von Cantor gefunden werden (in Logik lernt man, warum das so ist.)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Teilmenge und echte Teilmenge" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Folie 11](Folien/01/01_Mengen-und-Mengenoperationen-22.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\"N ist eine Teilmenge der Menge M\" bedeutet also: Alle Elemente, die in N sind, müssen auch in M sein. Zum Beispiel ist die Menge der grünen U-Bahnen ($U_g$) eine Teilmenge der U-Bahnen ($U$), da alle grünen U-Bahnen U-Bahnen sind: \n", "\n", "$$U_g \\subseteq U$$\n", "\n", "Es gibt auch U-Bahnen in anderen Farben (z.B. silberne, $U_s$). Es gibt also Elemente von $U$, die nicht in $U_g$ sind.\n", "Deshalb gilt sogar, dass die Menge $U_g$ eine **echte** Teilmenge von $U$ ist:\n", "\n", "$$U_g \\subset U$$\n", "\n", "Die Übermengenbeziehung $\\supseteq$ kehrt einfach die Teilmengenbeziehung $\\subseteq$ um: \n", "\n", "$$U \\supseteq U_g$$\n", "$$U \\supseteq U_s$$\n", "\n", "Dasselbe gilt natürlich für die echte Übermenge: \n", "\n", "$$U \\supset U_g$$\n", "$$U \\supset U_s$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Beispiele zu $\\in$ und Teilmengen" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Mächtigkeit von Mengen" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Folie 13](Folien/01/01_Mengen-und-Mengenoperationen-24.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Die Mächtigkeit beschreibt man mit senkrechten Strichen: $|Menge|$. \n", "Die Mächtigkeit endlicher Mengen ist die Anzahl ihrer Elemente, wie in den Beispielen zu sehen. \n", "Bei verschachtelten Mengen wie dem Beispiel $|\\{\\{1,2\\}\\}|$ muss man wieder aufpassen: Die \"äußere\" Menge enthält nur eine einzige \"innere\" Menge, deshalb ist die Mächtigkeit im Beispiel 1. Die Mächtigkeit der \"inneren\" Menge ist 2.\n", "\n", "Daraus folgt der obere Block auf der Folie: Bei zwei Mengen, die gleich viele Elemente haben, kann man jedem Element der ersten Menge ein Element der zweiten Menge zuordnen. Diese Zuordnung deckt dann alle Elemte beider Mengen ab." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Wozu braucht ein Computerlinguist Mengenlehre?\n", "\n", "Hier ist eine kleine Sammlung von Anwendungsgebieten der Mengenlehre in der CL. Es gibt sicherlich noch viel mehr!\n", "\n", "- In vielen Programmiersprachen ist die Menge eine wichtige Datenstruktur, in der Objekte gespeichert werden (z.B. Python oder Java).\n", "- In der Computerlinguistik können natürliche Sprachen (also deutsch, englisch, japanisch...) als unendlich große Mengen von Sätzen verstanden werden. Diese Sätze werden aus einer Menge von Wörtern und einer Menge von Regeln gebildet. \n", "- In der Semantik (der Lehre von der Bedeutung) beschreiben Mengen oft die Bedeutung von Worten. Zum Beispiel beschreibt das Wort $Katze$ die Menge aller Katzen.\n", "- Außerdem arbeitet ein Computerlinguist häufig mit statistischen Verfahren, um seine Vermutungen über Sprache zu prüfen. In der Statistik spielen Mengen eine wichtige Rolle. \n", "\n", "Es lohnt sich also, die Grundlagen der Mengenlehre im Kopf zu behalten. Die gute Sache dabei ist, dass man mit einem guten Grundwissen über Mengen schon ziemlich weit kommt - die Notation wiederholt sich sehr häufig. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }