2. Grundlagen: Mengen, Funktionen, elementare Logikhome.uni-leipzig.de/doelling/veranstaltungen/Satzsemantik_02... · nung – die Reihenfolge, in der wir die Elemente angeben, spielt

© Manfred Krifka, Institut für deutsche Sprache und Linguistik, HU Berlin

2. Grundlagen: Mengen, Funktionen, elementare Logik Bevor wir die Bedeutung sprachlicher Ausdrücke in der Art des vorausgegangenen Kapitels zu untersuchen, sollten wir uns mit einigen wichtigen theoretischen Hilfsmitteln vertraut ma-chen, insbesondere mit den Begriffen Menge, Relation und Funktion und den verschiedenen Möglichkeiten, sie zu beschreiben, wie beispielsweise der Lambda-Notation. Ferner eignen wir uns einige Grundbegriffe und –schreibweisen der Aussagen- und Prädikatenlogik an.

2.1 Elementare Mengenlehre 2.1.1 Der Begriff der Menge Die Mengenlehre wurde gegen Ende des 19. Jahrhunderts von dem Mathematiker Georg Cantor als theoretische Basis der Mathematik entwickelt. Der Grundgedanke war, eine ele-mentare, einfache und konsistente Theorie zu schaffen, auf deren Grundlage sich die gesamte Mathematik aufbauen ließe. Nachfolgend die klassische Definition einer Menge (englisch: set).

(1) Eine Menge ist eine abstrakte Zusammenfassung bestimmter wohlunterschiedener Ob-jekte unserer Anschauung oder unseres Denkens zu einem Ganzen.

Betrachten wir die Bestandteile dieser Definition genauer: • “abstrakt”: Die Objekte brauchen nicht physisch zusammengefasst zu werden, wie etwa

die Marken einer Briefmarkensammlung in einem Album. • “Zusammenfassung”: Es muss klar sein, welche Objekte dazugehören und welche nicht.

Des Weiteren handelt es sich lediglich um eine Zusammenfassung, nicht um eine Anord-nung – die Reihenfolge, in der wir die Elemente angeben, spielt daher keine Rolle. (Strukturen, in denen die Reihenfolge relevant ist, heißen Tupel oder Listen.)

• “wohlunterschieden”: Die Objekte müssen identifizierbar sein, das heißt, man muss sie auseinanderhalten können. Insbesondere kann in einer Menge ein und dasselbe Objekt nicht mehrfach auftauchen. Strukturen, die auch das mehrfache Vorkommen von Objek-ten erlauben, heißen Multimengen.

• “Anschauung”/“Denken”: Die Objekte können konkret sein (z.B. die Studenten im Semi-narraum) oder abstrakt (wie die sieben Kardinaltugenden oder die natürlichen Zahlen zwischen 3 und 17).

Einige Beispiele und weitere Begriffe: • Die Objekte, die zu einer Menge gehören, nennt man Elemente der Menge. Von den E-

lementen wird nichts weiter vorausgesetzt. Insbesondere kann es sich bei ihnen selbst um Mengen handeln.

• Mengen können klein sein (wie die Menge der natürlichen Zahlen zwischen 3 und 17) oder groß (wie die Menge der natürlichen Zahlen zwischen 3 und 17 Milliarden). Diese Mengen sind endlich, aber es gibt auch unendliche Mengen (z.B. die Menge aller natür-lichen Zahlen 1, 2, 3, 4, …).

• Mengen können nur ein einziges Objekt enthalten (sogenannte Einermengen); man be-achte, dass die Menge, die Manfred Krifka als einziges Element besitzt, verschieden ist von Manfred Krifka selbst (beispielsweise ist die Menge abstrakt, ich bin hoffentlich konkret).

• Mengen können auch überhaupt keine Objekte enthalten (die leere Menge, ∅). Ein paar Vereinbarungen zur Schreibweise: • Mengen werden gewöhnlich mit Großbuchstaben A, B, C, X, Y etc. bezeichnet. • Elemente bezeichnet man gewöhnlich mit Kleinbuchstaben a, b, c, x, y etc. • a∈A “a ist Element von A”, a∉A “a ist kein Element von A”

Elementare Mengenlehre 2


Wann sind zwei Mengen gleich? Wir sollten mindestens folgendes verlangen: Wenn zwei Mengen A und B gleich sind, dann besitzen sie dieselben Elemente. Das kann man wie folgt ausdrücken:

(2) Wenn A = B gilt, dann gilt auch für alle x: Wenn x∈A, dann x∈B, und wenn x∈B, dann x∈A.

Dies ist jedoch noch keine Definition für die Gleichheit, nur eine notwendige Bedingung: Wenn immer A = B gilt, gilt notwendigerweise auch, dass die beiden Mengen die gleichen Elemente haben. Man kann nun weitergehen und fordern, dass zwei Mengen, welche diesel-ben Elemente besitzen, gleich sind:

(3) Wenn für alle x gilt: Wenn x∈A dann x∈B, und wenn x∈B, dann x∈A, dann gilt auch: A = B

Dies ist eine hinreichende Bedingung: Wenn immer zwei Mengen die gleichen Elemente haben, dann sind sie gleich. Das heißt, die Mengen sind ausschließlich durch ihre Elemente definiert. In dieser Hinsicht unterscheiden sich Mengen von Ausschüssen, Musikgruppen etc. Es kann beispielsweise sein, dass Hans, Bill und Maria freitagabends Rockmusik als ‘The Rocking Stones’ spielen, und samstagabends Country als ‘The Rattlesnakes’; diese beiden Bands haben natürlich recht unterschiedliche Eigenschaften, auch wenn die Mitglieder die-selben sind. Wir müssen nun nur noch ausschließen, dass zwei Mengen auch unter anderen Umständen gleich sind. Das tun wir, indem wir die beiden Gesetzmäßigkeiten (2) und (3) kombinieren:

(4) Definition: A = B gilt genau dann wenn (gdw.) Für alle x, wenn x∈A, dann x∈B, und wenn x∈B, dann x∈A.

Das heißt, zwei Mengen sind gleich genau dann, wenn sie dieselben Elemente besitzen.

2.1.2 Spezifikation von Mengen: Aufzählung und Abstraktion Es gibt verschiedene Weisen, wie man Mengen angeben kann. Hier wollen wir zwei Metho-den einführen: die Aufzählung und die Abstraktion.

Aufzählung Wir können die Elemente einer Menge einfach aufzählen. Das nennt man auch die “Listen-notation”.1 Gewöhnlich verwendet man dazu geschweifte Klammern sowie Kommata, um die Elemente voneinander zu trennen. Beispiele:

(5) a. {Haydn, Mozart, Beethoven} (Menge von Komponisten, die wir KK nennen wollen). b. {Mozart, Sirius, 3} c. {Haydn, {Mozart, Beethoven}} (verschieden von KK) c. {Mozart} (eine Einermenge) d. {} (die leere Menge, auch Ø geschrieben)

Beachte: • Die Reihenfolge der Aufzählung ist irrelevant: {Mozart, Beethoven, Haydn} = KK • Das mehrfache Vorkommen eines Elementes spielt keine Rolle:

{Haydn, Mozart, Mozart, Beethoven} = KK

Abstraktion Die Abstraktion, auch Prädikatsnotation genannt, beschreibt die Elemente, die zu der Men-ge gehören, in einer Sprache – auf Deutsch beispielsweise oder in einer mathematischen 1 Diese Benennung ist etwas irreführend; denn für Listen ist die Reihenfolge der Elemente wichtig, für Mengen hingegen nicht.

3 Grundlagen: Mengen, Funktionen, elementare Logik


Sprache. Alle Objekte, auf welche die Beschreibung zutrifft, und nur diese Objekte, sind dann in der Menge enthalten. Die folgende Schreibweise ist gebräuchlich:

(6) {Variable | Beschreibung} Typischerweise verwenden wir x, y, z als Buchstaben für Variablen. Einige Beispiele:

(7) a. {x | x ist ein bedeutender Komponist der klassischen Wiener Periode} (= unsere Menge KK) b. {x | x ist ein ägyptischer Pharao} (= {Cheops, Chefren, … Cleopatra}) c. {x | x ist eine natürliche Zahl größer/gleich 1 und kleiner/gleich einer Milliarde} (= {1, 2, … 1,000,000,000}) d. {x | x ist eine gerade Zahl} (= {2, 4, 6, 8, …}, wir wollen diese Menge mit GG bezeichnen).

Beispiel (7.a) liest man “die Menge aller x so, dass x ein bedeutender Komponist der klassi-schen Wiener Periode ist”. Die allgemeine Form der Prädikationsnotation ist also wie folgt zu verstehen:

(8) {x | Aussage}: die Menge aller x, sodass die Aussage wahr ist

Was passiert, wenn die Variable x gar nicht in der Aussage vorkommt, wie in den folgenden Beispielen?

(9) a. {x | Potsdam ist die Hauptstadt von Brandenburg} b. {x | Cottbus ist die Hauptstadt von Brandenburg}

Nach unserer Definition ist (a) die Menge aller x so, dass “Potsdam ist die Hauptstadt von Brandenburg” wahr ist. Diese Beschreibung ist wahr unabhängig davon, welchen Wert x hat. Das bedeutet, dass alles in dieser Menge enthalten ist. Eine analoge Überlegung ergibt, dass in der Menge (b) nichts enthalten ist, dass es sich also um die leere Menge ∅ handelt.

2.1.3 Mächtigkeit von Mengen Manchmal interessiert uns lediglich die “Größe” einer Menge, d. h. die Anzahl der Elemente in ihr, ihre sogenannte Mächtigkeit (oder Kardinalität). Die Mächtigkeit einer Menge A wird durch |A|, #(A), #A oder card(A) bezeichnet. Beispiele:

(10) a. #{Mozart, Haydn, Beethoven} = 3 b. #{Mozart, {Haydn, Beethoven}} = 2 (!) c. #{Mozart, Haydn, Haydn, Beethoven} = 3 (!) d. #Ø = 0

Der Begriff der Mächtigkeit lässt sich auf unendliche Mengen wie unsere Menge GG ausdeh-nen. Offenbar kann #GG keine natürliche Zahl sein. Für die Mächtigkeit unendlicher Mengen wie GG benutzen Mathematiker das Symbol ℵ0 (Aleph-Null).2

2.1.4 Die Teilmengenbeziehung und Potenzmengen Wir wollen ausdrücken, dass alle Elemente einer Menge A auch in einer Menge B enthalten sind. Dazu schreiben wir A ⊆ B und sagen, dass A eine Teilmenge von B und B eine Ober-menge von A ist. Um auszudrücken, dass A keine Teilmenge von B ist, schreiben wir A ⊄ B.

(11) a. Definition: A ⊆ B gdw. für alle x: Wenn x∈A, dann x∈B. b. Definition: A ⊄ B gdw. nicht gilt: A ⊆ B.

2 Es gibt mehr als eine Art von Unendlichkeit – tatsächlich existieren unendlich viele Arten von Unendlichkeit. Leider haben wir in diesem Kurs zu wenig Zeit, um darauf einzugehen.



Beispiele:

(12) a. KK ⊆ {Haydn, Mozart, Beethoven, Schubert} b. GG ⊆ {x|x ist eine natürliche Zahl} c. KK ⊆ KK

Im letzten Fall gilt die Teilmengenbeziehung in beiden Richtungen. Wollen wir diesen Fall ausschließen und die echte Teilmengenbeziehung ausdrücken, verwenden wir das Symbol ⊂ und schreiben A ⊂ B für “A ist eine echte Teilmenge von B”. Wir können diese Beziehung folgendermaßen definieren:

(13) Definition: A ⊂ B gdw. A ⊆ B und B ⊄ A. (Hier und im folgenden steht “gdw. ��” für “genau dann, wenn”). Um zum Ausdruck zu brin-gen, dass A keine echte Teilmenge von B ist, schreibt man A ⊄ B. Beispiele:

(14) a. KK ⊂ {Haydn, Mozart, Beethoven, Schubert}, b. KK ⊄ KK

Man beachte, dass nach unserer Definition die leere Menge ∅ Teilmenge einer jeden Menge A ist (zur Erinnerung: ∅ ⊆ A ist definiert als “jedes Element von ∅ ist auch Element von A”; diese Forderung ist trivialerweise erfüllt, da ∅ kein einziges Elemente besitzt).

(15) Ø ⊆ A, für jede Menge A. Bei Einermengen müssen wir genau zwischen der Teilmengen- und der Element-von-Beziehung unterscheiden. Zum Beispiel:

(16) a. 4 ∈ GG, aber nicht: 4 ⊆ GG. b. {4} ⊆ GG, aber nicht: {4} ∈ GG.

Die Menge aller Teilmengen einer Menge A heißt die Potenzmenge von A, englisch: power set. Wir schreiben dafür pow(A) oder auch ℘(A).

(17) Definition: pow(A) = {X | X ⊆ A} Wie viele Elemente besitzt eine Potenzmenge? Schauen wir uns zunächst ein paar Beispiele an:

(18) a. pow({a, b, c}) = {{a, b, c}, {a, b}, {b, c}, {a, c}, {a}, {b}, {c}, ∅} (Ausgangsmenge: 3 Elemente, Potenzmenge: 8 Elemente) b. pow({a, b}) = {{a, b}, {a}, {b}, ∅} (Ausgangsmenge: 2 Elemente, Potenzmenge: 4 Elemente) c. pow({a}) = {{a}, ∅} (Ausgangsmenge: 1 Element, Potenzmenge: 2 Elemente) d. pow(∅) = {∅} (Ausgangsmenge: 0 Elemente, Potenzmenge: 1 Element)

Allgemein gilt: Wenn eine Menge A aus n Elementen besteht, so besitzt die Potenzmenge von A 2 ⋅ 2 ⋅ 2 ⋅ … (n-mal) Elemente :

(19) Mächtigkeit von Potenzmengen: Wenn #(A) = n, dann #(pow(A)) = 2n. Diese Gesetzmäßigkeit kann man sich wie folgt klarmachen: Hat die Menge A ein Element, z.B. A = {a}, dann hat pow(A) offensichtlich zwei Elemente: {∅, {a}}. Hat A ein zweites Element, z.B. A = {a, b}, dann hat pow(A) doppelt so viele Elemente: die Mengen, die bere-its vorher präsent waren, und die Mengen, die als Kombination dieser Mengen mit dem neuen Element {b} entstehen, also {∅, {a}, {b}, {a,b}}. Dies kann man verallgemeinern: Wenn immer pow(A) n-viele Elemente enthält, und ein neues Element zu A hinzukommt, dann enthält pow(A + neues Element) 2n-viele Elemente.



2.1.5 Mengentheoretische Operationen Es gibt eine Anzahl wichtiger Operationen, die man mit Mengen vornehmen kann. Die Ver-einigung (englisch: union) zweier Mengen A und B, geschrieben A ∪ B, ist diejenige Men-ge, welche alle Elemente, die in A oder B vorkommen, und nur diese enthält.

(20) Definition: A ∪ B = {x| x ∈ A oder x ∈ B} Zum Beispiel:

(21) a. {1,2,3} ∪ {3,4,5} = {1,2,3,4,5} b. {1,2,3} ∪ {2,3} = {1,2,3} c. {1,2,3} ∪ Ø = {1,2,3}

Der Durchschnitt (englisch: intersection) zweier Mengen A und B, geschrieben A ∩ B, ist diejenige Menge, welche alle Elemente, die sowohl in A wie auch in B vorkommen, und nur diese enthält:

(22) Definition: A ∩ B = {x| x ∈ A und x ∈ B} Zum Beispiel:

(23) a. {1,2,3} ∩ {3,4,5} = {3} b. {1,2,3} ∩ {7,8,9} = Ø c. {1,2,3} ∩ Ø = Ø

Die mengentheoretische Differenz (englisch: subtraction) A \ B ist diejenige Menge, welche genau die Elemente aus A enthält, die nicht in B enthalten sind:

(24) Definition: A \ B = {x| x ∈ A und x ∉ B} Zum Beispiel:

(25) a. {1,2,3} \ {3,4,5} = {1,2} b. {1,2,3} \ {7,8,9} = {1,2,3} c. {1,2,3} \ Ø = {1,2,3}

Man beachte, dass die mengentheoretischen Operationen ∪, ∩ und \ etwas anderes sind als die Teilmengenbeziehung. Wenn wir beispielsweise A ∪ B schreiben, so bezeichnen wir damit eine neue Menge. Schreiben wir stattdessen A ⊆ B, so erhalten wir keine neue Menge, sondern eine Behauptung, die wahr oder falsch sein kann. Häufig beschränken wir uns auf eine bestimmte Menge von Objekten, z.B. die Menge der natürlichen Zahlen, und betrachten Teilmengen dieser Menge. Eine solche Menge nennt man Universum, oft mit U bezeichnet. Bezüglich eines Universums U definieren wir das Kom-plement einer Menge A (wobei A ⊆ U), geschrieben A′, mittels

(26) A′ =def U \ A. Zum Beispiel gilt bezüglich der natürlichen Zahlen als Universum

(27) a. {1,2,3}′ = {x | x ist eine natürliche Zahl und x≥4} b. GG ′ = {x | x ist eine ungerade Zahl}

2.1.6 Venn-Diagramme Eine nützliche Methode zur Darstellung mengentheoretischer Beziehungen bilden die soge-nannten Venn-Diagramme (nach dem Mathematiker John Venn), auch Euler-Kreise ge-nannt (nach dem im 18. Jahrhundert lebenden Mathematiker Leonhard Euler, der sie als di-daktisches Hilfsmittel in seinen im Jahre 1768 in St. Petersburg veröffentlichten Lettres à une Princesse d’Allemagne einführte). Wir haben im vorausgegangenen Kapitel schon so etwas wie Venn-Diagramme benutzt. In einem Venn-Diagramm werden die Elemente durch Punkte in der Ebene dargestellt, and Mengen von Elementen durch geschlossene Flächen. Beispiele:



(28) A B B ⊆ A

(29) A A A B B B A ∪ B A ∩ B A \ B

(30) U A′ (Komplement von A, = U \ A) A

2.1.7 Mengentheoretische Gesetze Die mengentheoretischen Begriffe wie Vereinigung, Durchschnitt, Teilmenge, Komplement etc. sind durch einfache strukturelle Beziehungen, die wir in Gleichungen ausdrücken kön-nen, miteinander verbunden. Im Folgenden seien X, Y, Z beliebige Mengen. Die jeweiligen Gesetze lassen sich mit Hilfe von Venn-Diagrammen darstellen.

(31) a. Idempotenz: X∪X = X X∩X = X

• b. Kommutativität: X∪Y = Y∪X X∩Y = Y∩X

c. Assoziativität: (X∪Y)∪Z = X∪(Y∪Z) (X∩Y)∩Z = X∩(Y∩Z) Wegen der Assoziativität von Vereinigung und Durchschnitt spielt die Klammerung in Aus-drücken, die entweder nur ∪ oder nur ∩ enthalten, keine Rolle. Wir dürfen daher z.B. X∪Y∪Z für (X∪Y)∪Z schreiben. Die Schreibweise für Vereinigung und Durchschnitt können wir noch verallgemeinern. Sei X eine Menge von Mengen, dann:

(32) a. Definition: ∪X =def die Vereinigung aller Mengen in X. b. Definition: ∩X =def der Durchschnitt aller Mengen in X.

Beispiele:

(33) a. ∪{{a,b,c}, {c,d,e}, {e,f,g}} = {a,b,c,d,e,f,g} b. ∩{{a,b,c}, {b.c.d}, {c.d.e}} = {c}

(34) a. Distributivität: X∪(Y∩Z) = (X∪Y)∩(X∪Z) X∩(Y∪Z) = (X∩Y)∪(X∩Z) das heißt, ∪ “distribuiert” (verteilt) über ∩ und umgekehrt.

b. Identitätsgesetze: X∪Ø = X X∩Ø = Ø X∪U = U X∩U = X d.h, leere Menge Ø und Universum U spielen besondere Rollen hinsichtlich Vereinigung und Durchschnitt.



c. Komplementgesetze: X∪X′ = U X∩X′ = Ø (X′)′ = X X\Y = X∩Y′

d. de Morgansche Gesetze: (X∪Y)′ = X′∩Y′ (X∩Y)′ = X′∪Y′

e. Konsistenz: X⊆Y gdw. X∪Y = Y X⊆Y gdw. X∩Y = X Das Konsistenzgesetz erlaubt es uns, ⊆ durch ∪ oder ∩ zu definieren oder umgekehrt ∪ bzw. ∩ durch ⊆. Das heißt, es stellt eine Beziehung auf zwischen der Teilmengenbeziehung und den Mengenoperationen. Ein mathematisches Modell, das die oben angeführten Gesetzmäßigkeiten erfüllt, nennt man eine Boolesche Algebra (nach dem Logiker George Boole, 1815-1864). Boolesche Algebren spielen eine sehr bedeutende Rolle in vielen Bereichen, unter anderem auch in der Informa-tik. Die mengentheoretischen Gesetze ermöglichen es, manche Ausdrücke zu vereinfachen. Bei-spiel:

(35) (A∪B) ∪ (B∩C)′ = (A∪B) ∪ (B′∪C′) = (de Morgan) A ∪ (B ∪ (B′∪C′)) = (Assoziativität) A ∪ ((B∪B′) ∪ C′) = (Assoziativität) A ∪ (U ∪ C′) = (Komplement) A ∪ U = (Identität) U (Identität)

Solch eine Rückführung eines Ausdrucks auf einen anderen, für gewöhnlich einfacheren Ausdruck nennt man einen Beweis: Ein Beweis ist eine Folge von Ausdrücken, in der jeder Ausdruck von seinem Vorgänger mittels Anwendung eines Gesetzes ableitbar ist. Betrachten wir ein weiteres Beispiel; darin zeigen wir, dass eine bestimmte Tatsache gilt:

(36) a. Zeige: A∩B ⊆ A∪B ! b. Nach Konsistenz: X⊆Y gdw. X∩Y=X; setze X:=(A∩B) und Y:=(A∪B), dann bleibt zu zeigen: (A∩B)∩(A∪B) = A∩B.

c. Zum Beweis bedienen wir uns der mengentheoretischen Gesetze: (A∩B)∩(A∪B) ((A∩B)∩A) ∪ ((A∩B)∩B) (Distributivität) (A∩(A∩B)) ∪ ((A∩B)∩B) (Kommutativität) ((A∩A)∩B) ∪ (A∩(B∩B)) (Assoziativität, zweimal) (A∩B) ∪ (A∩B) (Idempotenz, zweimal) A∩B (Idempotenz) q.e.d. (“quod erat demonstrandum” – was zu zeigen war).

2.2 Mengenlehre und semantische Beziehungen Wir haben hier die Grundlagen der Mengenlehre eingeführt, weil sie sich als geeignet er-weisen wird, wichtige semantische Beziehungen darzustellen. Wir wollen dies hier bereits an zwei Beispielen aufzeigen: Die Beziehungen zwischen Wörtern wie Nomina, Adjektiven und Verben, und die Verknüpfung von Sätzen

2.2.1 Mengenlehre und Wortbedeutungen Mithilfe der Mengenlehre können wir wesentliche Aspekte von Wortbedeutungen modellie-ren. Als die Bedeutung eines Nomens, eines prädikativen Adjektivs oder eines intransitiven

Mengenlehre und semantische Beziehungen 8


Verbs α nehmen wir die Menge derjenigen Objekte, auf die sich α funktional anwenden lässt, an. Erinnern wir uns, dass die Bedeutung von α durch [[α]] bezeichnet wird. Zum Beispiel:

(37) a. [[Pferd]]= {x| x ist ein Pferd} b. [[rot]] = {x| x ist rot} c. [[spricht]]= {x| x spricht}

Hyponymie lässt sich als Teilmengenbeziehung ausdrücken: [[Pferd] ] ⊆ [[Tier]]. Im allgemei-nen gilt:

(38) α ist ein Hyponym von β gdw. gilt: [[α]] ⊆ [[β]]. Kombinationen von Ausdrücken mittels und, oder und nicht (den sogenannten Boolschen Operatoren) lassen sich durch Vereinigung, Durchschnitt bzw. Komplementbildung darstel-len:

(39) a. [[rot und rund]] = [[rot]] ∩ [[rund]] b. [[rot oder rund]] = [[rot]] ∪ [[rund]] c. [[nicht rot]] = [[rot]] ′

Wir können dies zu den folgenden Regeln verallgemeinern:

(40) a. [[α und β]] = [[α]] ∩ [[β]] b. [[α oder β]] = [[α]] ∪ [[β]] c. [[nicht α]] = [[α]]′

Die mengentheoretischen Gesetze sagen das semantische Verhalten voraus:

(41) a. [[rot und rund]] = [[rund und rot]], weil [[rot]] ∩ [[rund]] = [[rund]] ∩ [[rot]] (Kommutativität)

b. [[rot und [rund und weich]]] = [[[rot und rund] und weich]], weil [[rot]] ∩ ([[rund]] ∩ [[weich]]) = ([[rot]]∩ [[rund]]) ∩ [[weich]] (Assoziativität)

c. [[nicht [rot und rund]]] = [[[nicht rot] oder [nicht rund]]], weil ([[rot]] ∩ [[rund]])′ = [[rot]]′ ∪ [[rund]]′ (de Morgan)

d. [[rot und [rund oder weich]]] = [[[rot und rund] oder [rot und weich]]], weil [[rot]] ∩ ([[rund]] ∪ [[weich]]) = ([[rot]] ∩ [[rund]]) ∪ ([[rot]]∩[[weich]]) (Distributivität)

Mengenlehre kann also verwendet werden, um Theorien zur Semantik natürlicher Sprachen darzustellen – sowohl hinsichtlich der semantischen Beziehungen zwischen Wörtern wie auch hinsichtlich der semantischen Beziehungen zwischen komplexen Ausdrücken.

2.2.2 Mengenlehre und Satzbedeutungen Die Mengenlehre kann nicht nur zur Darstellung von Wortbedeutungen eingesetzt werden; auch wesentliche Eigenschaften der Beziehung zwischen Sätzen und der Verknüpfung von Sätzen kann durch sie dargestellt werden. Wir haben im ersten Kapitel gesehen, dass die Be-deutung eines (Aussage-)satzes weitgehend mit den Wahrheitsbedingungen des Satzes identifizierbar ist. Die Wahrheitsbedingungen wiederum sind mit den Situationen oder möglichen Welten identifizierbar, in denen der Satz wahr ist. Das führt zu folgender Defini-tion der Satzbedeutung in der Wahrheitsbedingungen-Semantik:

(42) Die Bedeutung eines Satzes Φ ist die Menge der möglichen Welten, in denen der Satz wahr ist. [[Φ]] = {w | Φ ist in w wahr}



Wir nehmen generell Φ, Ψ als metasprachliche Variablen über (Aussage-)sätze an, und Vari-ablen w, w′ usw. als Variablen über mögliche Welten. W stehe für die Menge aller möglichen Welten. Eine Menbe von möglichen Welten wird Proposition genannt. – Ein Beispiel:

(43) [[Es regnet.]] = {w | Es regnet in w} Es lassen sich mit dieser Modellierung von Satzbedeutungen bestimmte semantische Bezie-hungen zwischen Sätzen darstellen. Eine wichtige Beziehung ist die der logischen Folgerung (auch Implikation und englisch Entailment genannt). Aus einem Satz Φ folgt ein Satz Ψ, wenn in jeder Welt, in der Φ wahr ist, auch Ψ wahr ist, d.h. wenn die Bedeutung von Φ eine Teilmenge der Bedeutung von Ψ ist. Wenn wir für die logische Folgerung ⇒ schreiben, kön-nen wir das wie folgt ausdrücken:

(44) Φ ⇒ Ψ gdw. [[Φ]] ⊆ [[Ψ]]. Die logische Folgerung ist also gewissermassen die Hyponymie-Relation für Sätze (vgl. (38)). Ein Beispiel:

(45) Lola rennt. ⇒ Lola bewegt sich. da [[Lola rennt]] = {w | Lola rennt in w}, [[Lola bewegt sich]] = {w | Lola bewegt sich in w} und {w | Lola rennt in w} ⊆ {w | Lola bewegt sich in w}

Ebenso können die Satzverbindungen mit und, oder und der Satznegation nicht oder es ist nicht der Fall, dass mit den elementaren Mengenoperationen dargestellt werden:

(46) a. [[Φ und Ψ]] = [[Φ]] ∩ [[Ψ]] b. [[Φ oder Ψ]] = [[Φ]] ∪ [[Ψ]]. c. [[es ist nicht der Fall dass Φ]] = [[Φ]]′ = W \ [[Φ]]

Einige Beispiele:

(47) a. [[Es ist nicht der Fall dass Lola rennt.]] = [[Lola rennt]]′ , = W \ [[Lola rennt]] = W \ {w | Lola rennt in w} = {w | Lola rennt nicht in w}

b. [[Lola rennt und Manne flennt.]] = [[Lola rennt]] ∩ [[Manne flennt]] = {w | Lola rennt in w} ∩ {w | Manne flennt in w} = {w | Lola rennt in w und Manne flennt in w}

c. [[Lola rennt oder es ist nicht der Fall dass Manne flennt]] = [[Lola rennt]] ∪ [[es ist nicht der Fall dass Manne flennt]] = [[Lola rennt]] ∪ [[Manne flennt]]′ = {w | Lola rennt in w} ∪ [W \ {w | Manne flennt in w}] = {w | Lola rennt in w oder Manne flennt nicht in w}

Unsere Modellierung von Satzbedeutungen erlaubt es auch bereits, Gesetze für notwendige semantische Beziehungen aufzustellen. Zum Beispiel gilt das folgende Gesetz:

(48) Φ und Ψ ⇒ Φ Beispiel: Aus Lola rennt und Manne flennt folgt logisch: Lola rennt. Dies folgt aus dem mengentheoretischen Gesetz der Konsistenz, das die Durchschnittsbildung und die Teilmen-genbeziehung miteinander verbindet (vgl. (34.e)):

(49) [[[Φ]] ∩ [[Ψ]]] ⊆ [[Φ]]

Funktionen 10


2.3 Funktionen Ein weiterer grundlegender Begriff der Mathematik ist der der Funktion. Funktionen kann man als einen Spezialfall von Relationen ansehen, mit denen wir uns zunächst beschäftigen wollen.

2.3.1 Geordnete Paare und Relationen Mit Hilfe von Mengen sind wir in der Lage, einstellige Prädikate wie rot, Ball, oder rennen zu modellieren. Wie sieht es aber mit transitiven Verben wie lieben oder Nomen wie Vater (von) aus? Man beachte, dass ein solches Prädikat nicht von einem einzelnen Objekt gelten kann, sondern nur von einem Paar von zwei Objekten. Es handelt sich dabei also um Relati-onen zwischen zwei Entitäten. Beispiele:

(50) a. Maria liebt Hans. b. Abraham ist der Vater von Isaak.

Brauchen wir völlig neue Begriffe, um Relationen zu beschreiben, oder reicht unser Wissen aus der Mengenlehre dafür aus? Wir könnten versuchen, Relationen als Mengen von zweie-lementigen Mengen darzustellen:

(51) [[Vater]] = {{Isaak, Abraham}, {Jakob, Isaak}, {Esau, Isaak}, ...} = {{x,y}| y ist der Vater von x}

Dabei gibt es ein Problem: Bei vielen Relationen ist die Reihenfolge wichtig, bei Mengen dagegen nicht. Gemäß unserer obigen Definition würde auch Isaak als ein Vater von Abra-ham gelten. Zweiter Versuch: Relationen als Mengen geordneter Paare. Geordnete Paare sind Mengen mit genau zwei Elementen ähnlich, außer dass bei ihnen die Reihenfolge der Elemente wich-tig ist. Wir schreiben geordnete Paare so:3 〈Isaak, Abraham〉 Nun müssen wir sicherstellen, dass ein Paar wie 〈Isaak, Abraham〉 verschieden ist von einem Paar wie 〈Abraham, Isaak〉. Das folgt, wenn wir das folgende Identitätskriterium für geordne-te Paare annehmen:

(52) Definition: Zwei geordnete Paare 〈x,y〉, 〈u,v〉 sind gleich gdw. x = u und y = v. Mit Hilfe des Begriffes des geordneten Paares können wir folgende Interpretation angeben:

(53) [[Vater]] = {〈Isaak, Abraham〉, 〈Jakob, Isaak〉, 〈Esau, Isaak〉, ...} = {〈x,y〉| y ist der Vater von x}

Es gibt verschiedene Arten anzuzeigen, dass zwei Elemente x, y in einer Relation R stehen. Jede der folgenden Schreibweisen erfüllt diesen Zweck:

3 Eine Frage, die an dieser Stelle auftritt, ist: Müssen wir geordnete Paare als eine neue mathematische Entität einführen, oder lassen sie sich mit Hilfe von Mengen rekonstruieren? Es zeigt sich, dass Letzteres zutrifft. Geordnete Paare können wir als Mengen definieren. Das ist die Standardrekonstruktion nach Wiener und Kuratowski: Definition: 〈x,y〉 = {{x}, {x,y}} Man kann sich leicht überzeugen, dass wir aus der Mengendarstellung die Paardarstellung gewinnen können. Beispielsweise stehen {{7}, {7, 9}} oder {{7}, {9, 7}} oder {{7, 9}, {7}} oder {{9, 7}, {7}} alle für das Paar 〈7, 9〉. Ein gleichelementiges Paar wie 〈7, 7〉 wird als {{7}, {7,7}} dargestellt, was natürlich mit {{7}, {7}} und {{7}} identisch ist. Man beachte, dass diese Rekonstruktion geordneter Paare aus Mengen dem Identitätskriterium für geordnete Paare genügt: {{x}, {x,y}} = {{u}, {u,v}} gdw. x=u und y=v. Insbesondere erhalten wir {{x}, {x,y}} ≠ {{y}, {x,y}} (falls x ≠ y). Wir können also die Schreibweise 〈x,y〉 als eine Abkür-zung für die zugrundeliegende Darstellung {{x}, {x,y}} ansehen. Dies ist nur ein Beispiel dafür, wie komplexere mathema-tische Begriffe auf Mengen zurückgeführt werden.



(54) a. 〈x, y〉 ∈ R b. xRy c. R(x,y)

Die Idee, die Gesamtheit aller Paare zu betrachten, die sich aus zwei gegebenen Mengen bil-den lassen, indem man das erste Element immer aus der einen, das zweite Element immer aus der anderen Menge nimmt, führt auf das Kartesische Produkt:

(55) Definition: A×B = {〈x, y〉 | x∈A, y∈B}. Zum Beispiel:

(56) {a, b, c, d} × {1, 2, 3} = {〈a, 1〉, 〈a, 2〉, 〈a, 3〉, 〈b, 1〉, 〈b, 2〉, 〈b, 3〉, 〈c, 1〉, 〈c, 2〉, 〈c, 3〉, 〈d, 1〉, 〈d, 2〉, 〈d, 3〉}

Eine Relation R zwischen einer Menge A und einer Menge B ist eine Teilmenge des Kartesi-schen Produkts A×B. Sobald wir den Begriff eines geordneten Paares zur Verfügung haben, können wir ohne Schwierigkeit Tripel, Quadrupel etc., allgemein n-Tupel definieren:

(57) a. Tripel: 〈x, y, z〉 =def 〈〈x, y〉, z〉 (Rückführung auf Paare) b. Quadrupel: 〈u, x, y, z〉 =def 〈〈u, x, y〉, z〉 (Rückführung auf Tripel) c. n-Tupel: 〈x1, x2, ... xn〉 =def 〈〈x1, x2, ... xn-1〉, xn〉 (Rückführung auf (n-1) Tupel)

Der jeweils links stehende Ausdruck kann wieder als Abkürzung des Ausdrucks auf der rech-ten Seite angesehen werden. Wir werden Tripel zur semantischen Beschreibung ditransitiver Verben benötigen; z.B. können wir die Bedeutung von geben wiedergeben als:

(58) [[geben]] = {〈x, y, z〉 | x gibt y an z} Eine Menge von Paaren nennen wir eine zweistellige Relation, eine Menge von Tripeln eine dreistellige Relation. (Eine Menge einfacher Entitäten könnte man eine einstellige Relation nennen).

2.3.2 Funktionen als Relationen Relationen sind Paarungen von Objekten; beispielsweise ordnet die Relation [[Vater]] jeder Person x den Vater von x zu. Diese Relation hat eine wichtige Eigenschaft: Jede Person be-sitzt genau einen Vater. Von solchen Relationen sagen wir, dass sie die Eigenschaft der Rechtseindeutigkeit haben, welche folgendermaßen definiert ist:

(59) Eine Relation R ist rechtseindeutig gdw. gilt: Für jedes x, y, z mit 〈x, y〉 ∈ R und 〈x, z〉 ∈ R ist y = z.

Offenbar ist [[Vater]] rechtseindeutig. Die folgenden Relationen sind nicht rechtseindeutig:

(60) a. {〈x, y〉 | y ist Sohn von x} (man beachte, dass Jakob und Esau denselben Vater haben!) b. {〈x, y〉 | x, y sind reelle Zahlen, and y ist größer als x}

Rechtseindeutige Relationen nennt man Funktionen. Die Eigenschaft der Rechtseindeutig-keit erlaubt eine neue Schreibweise, die aus dem Matheunterricht in der Schule bekannt ist. Anstelle von 〈x,y〉∈R oder einer äquivalenten Notation können wir Folgendes schreiben:

(61) y = R(x). Wir sagen, dass x das Argument and y der Wert ist. Wir sprechen davon, dass R auf x an-gewendet wird und dass R x auf y abbildet. Häufig verwenden wir für Funktionen Buchsta-

Die Lambda-Notation für Funktionen 12


ben wie f, F, g, G. Man beachte, dass die obige Schreibweise nicht zulässig ist für Relationen, die keine Funktionen sind. Wir können sagen: der Vater von Jakob IST Isaak, aber wir können unmöglich sagen: der Sohn von Isaak IST Jakob – schließlich hatte Isaak einen zweiten Sohn, nämlich Esau. Ein weiteres wichtiges Begriffspaar sind der Definitionsbereich (auch Argumentbereich, englisch domain und der Wertebereich (Englisch range) einer Funktion f:

(62) a. Definitionsbereich einer Funktion f, DOM(f): {x | es gibt y so, dass 〈x, y〉 ∈ f} b. Wertebereich einer Funktion f, RNG(f): {y | es gibt x so, dass 〈x, y〉 ∈ f}

Im Definitionsbereich von f sind also die möglichen Argumente von f enthalten, im Wertebe-reich von f die möglichen Werte von f. Der Definitionsbereich von [[Vater]] ist die Menge der Personen (jeder hat einen Vater), der Wertebereich von [[Vater]] ist die Menge der Väter. Es sei f eine Funktion. Ist A der Definitionsbereich von f, B der Wertebereich, so sagen wir, dass f eine Funktion von A auf B ist. Ist nun B eine Teilmenge von C, so sagen wir, dass f eine Funktion von A nach (oder in) C ist. (Technisch gesprochen ist f auch eine Funktion nach B, da ja auch B eine Teilmenge von B ist). Ist f eine Funktion von A nach C, so schrei-ben wir dafür f: A → C. Ist weiter A eine Teilmenge von D, so sagen wir, dass f eine partiel-le Funktion von D nach C ist. (Technisch gesprochen ist f auch eine partielle Funktion von A auf B). Eine Funktion, in der kein Element ein Wert von mehr als einem Element ist, heißt ein-eindeutig. (Genauer, es sie heißt ein-eindeutig, wenn auch jedes Element des Wertebe-reichs der Wert eines Arguments des Definitionsbereichs ist.)

(63) A B A B A B A B a 1 a 1 a 1 a 1 b 2 b 2 b 2 b 2 c 3 c 3 c 3 c 3 d 4 d 4 d 4 d 4 e e e f f f Funktion von A Funktion von A partielle Funktion ein-eindeutige Funk- auf / nach B nach B von A auf/nach B tion von A auf B

Oft ist es vorteilhaft, Funktionen in der folgenden Notation anzugeben:

(64) [[Vater]] = Isaak → Abraham Jakob → Isaak Esau → Isaak ...

Dies macht klar, dass es sich bei Funktionen im wesentlichen um Zuweisungsvorschriften oder Abbildungen (englisch mappings) handelt. Beispielsweise weist die Funktion [[Vater]] dem Isaak den Abraham zu, dem Jakob den Isaak usw.

2.4 Die Lambda-Notation für Funktionen Der Lambda-Notation ist eine sehr klar durchschaubare Art, Funktionen zu beschreiben und mit Funktionen zu arbeiten, derer wir uns im gesamten Kurs bedienen werden. Dieser Ab-schnitt ist eine praktische Einführung in die Notation des Lambda-Kalküls (den Vorschriften, wie mit Ausdrücken in der Lambda-Notation umgeganben wird), sowie in einige Anwendun-gen der Notation und des Kalküls. Wir werden dabei in der Hauptsache mathematische Bei-spiele heranziehen, aber wir werden bald sehen, wie sich der Kalkül anwenden lässt, um Be-deutungen darzustellen.



2.4.1 Beschreibung von Funktionen Eine Funktion kann man angeben, indem man ihre Argument-Werte-Paare aufzählt – entwe-der als eine Menge von Paaren oder in der Pfeilnotation wie in (64). Oftmals ist eine solche explizite Auflistung unpraktisch oder sogar unmöglich. In diesem Fall können wir eine Funk-tion beschreiben. Ein gängiges Format ist das Folgende:

(65) a. [[Mutter]] m: Personen → Personen, x |→ die Mutter von x.

b. [[Alter]] a: Personen → natürliche Zahlen x |→ das Alter von x, in Jahren.

c. [[Nachfolger]] s: natürliche Zahlen → natürliche Zahlen, x |→ x + 1

d. [[Quadrat]]: q: natürliche Zahlen → natürliche Zahlen, x |→ x2

Die Funktion f sei definiert als eine Funktion von Personen nach Personen, wobei f jedes x auf den Vater von x abbildet; z.B. ist f(Isaak) = Abraham. Die Funktion s sei definiert als eine Funktion von den natürlichen Zahlen in die natürlichen Zahlen, wobei s jede natürliche Zahl x auf den Nachfolger von x abbildet, d. h. die Zahl x + 1. So ist z.B. s(13) = 14. Aus der Algebra ist uns eine andere Schreibweise für Funktionen bekannt:

(66) f(x) = x2 + x + 1 Dies ist eine Funktion f, die jede Zahl x auf x2 + x + 1 abbildet. Wir haben z.B. f(2) = 7.

2.4.2 Die Lambda-Notation als kompakte Funktionsbeschreibung In den bisherigen Schreibweisen haben wir Funktionen wie m, s, q, f definiert. Das bedeutet, wann immer wir m, s, q oder f verwenden, z.B. in Ausdrücken wie m(Isaak) oder s(13), müs-sen wir nachschauen, wie diese Funktionen definiert wurden. Die Lambda-Notation bietet uns die Möglichkeit, Funktionen in einer Weise zu benennen, sodass sofort klar ist, wie sie definiert sind. In dieser Notation hätten m, s, q und f folgende Gestalten:

(67) m: λx[die Mutter von x] s: λx[x+1] q: λx[x2] f: λx[x2 + x + 1]

Wir nennen solche Ausdrücke Lambda-Terme. Die Struktur von Lambda-Termen sieht fol-gendermaßen aus:

(68) λ Variable [Beschreibung des Wertes der Variablen] Dieser Ausdruck steht für diejenige Funktion, welche jedem Objekt, für das ‘Variable’ stehen kann, den Wert der Variablen gemäß der Beschreibung im sogenannten Rumpf des Lambda-Terms zuordnet. Die Bildung eines Lambda-Terms aus einer Beschreibung, die eine Variable enthält, wie z.B. “Mutter von x” oder “x2 + x + 1”, heißt (Lambda) Abstraktion. Wie schon angedeutet, ist eine nette Eigenschaft der Lambda-Notation die, dass den Funktio-nen ihre Definition auf der Stirn geschrieben steht. Das macht es möglich, den Wert einer Funktion angewendet auf ein Argument anzugeben, indem man einfach die Lambda-Variable durch das Argument ersetzt. Dieser Vorgang heißt (Lambda) Konversion bzw. Reduktion:



(69) a. λx[Mutter von x](Isaak) b. λx[x2 + x + 1](3) = Mutter von Isaak = 32 + 3 + 1 = Sarah = 9 + 3 + 1 = 13

2.4.3 Lambda-Notation mit Angabe des Definitionsbereichs Nach dem, was wir bisher gesehen haben, ist die Lambda-Notation weniger flexibel als eini-ge andere Schreibweisen. Das liegt daran, dass sie nicht explizit den Definitionsbereich der Funktion angibt. Betrachten wir ein Beispiel:

(70) a. f: NN → NN x |→ x2 + x + 1

b. g: GG → NN x |→ x2 + x + 1

Hier ist (70.a) eine Funktion von den natürlichen Zahlen in die natürlichen Zahlen, wohinge-gen der Definitionsbereich von (b) stärker eingeschränkt ist, da die Funktion nur für die gera-den Zahlen definiert ist. Unsere gegenwärtige Schreibweise unterscheidet nicht zwischen diesen beiden Funktionen. Aber wir können sie einfach erweitern. Es gibt hierfür keine all-gemein eingeführte Schreibweise; wir werden hier die folgenden verwenden:

(71) a. λx∈GG [x2 + x + 1] b. λx〈x∈GG〉 [x2 + x + 1]

Die erste Schreibweise ist günstiger, wenn wir, wie hier, den Definitionsbereich unmittelbar durch eine Menge angeben können; die zweite dann, wenn wir die Bedingung beschreiben, denen die Variable x gehorchen soll. Das allgemeine Format lässt sich also wie folgt veran-schaulichen:

(72) a. λ Variable ∈ Definitionsbereich [Wert der Variable] b. λ Variable 〈Bedingung für die Variable〉 [ Wert der Variable]

Wir werden diese Schreibweise immer dann verwenden, wenn der Definitionsbereich einer Funktion relevant ist, was häufig der Fall sein wird. Wird eine Funktion auf eine Entität au-ßerhalb ihres Definitionsbereiches angewendet, so ist der Wert an jener Stelle natürlich nicht definiert. So gibt es einen wichtigen Unterschied zwischen den beiden Funktionen aus dem vorigen Beispiel, wie die folgende Anwendung zeigt:

(73) a. λx∈NN[x2 + x + 1](3) = 13 b. λx∈GG [x2 + x + 1](3): nicht definiert.

2.4.4 Funktionen mit Funktionen als Argumente In den Beispielen, die wir bis jetzt gesehen haben, waren die Argumente, auf die wir eine Funktion angewendet haben, immer einfach – eine Zahl oder eine Person. Aber Funktionen können auch komplexe Argumente erwarten, zum Beispiel Mengen oder andere Funktionen. Das wird oftmals durch unterschiedliche Variablennamen angedeutet, wie z.B. X für Mengen oder f für Funktionen. (74.a) ist eine Funktion, die eine Menge als Argument nimmt und sie mit der Menge {1, 2, 3} schneidet. Durch Anwendung auf die Menge {2, 3, 4} erhalten wir die Menge {2, 3}; An-wendung auf die Menge {4, 5, 6} ergibt die leere Menge, und die Funktion ist nur definiert für Mengen und nicht definiert für eine Person wie Isaak.



(74) a. λX[X ∩ {1, 2, 3}] b. λX[X ∩ {1, 2, 3}]({2, 3, 4}) = {2, 3} c. λX[X ∩ {1, 2, 3}]({4, 5, 6}) = ∅ d. λX[X ∩ {1, 2, 3}](Isaak): nicht definiert

Die Funktion ist nicht definiert für die Anwendung auf eine Person, weil die Durschnittsbil-dung ∩ nur für Mengen definiert ist. Das könnten wir in unserer erweiterten Lambda-Notation explizit machen:

(75) λX 〈X ist eine Menge〉 [X ∩ {1, 2, 3}] Im nächsten Beispiel sehen wir eine Funktion, die eine Funktion als Argument nimmt und als Wert das Ergebnis liefert, welches wir erhalten, wenn wir die Argumentfunktion auf die Zahl 3 anwenden.

(76) λf[f(3)] Wir können mit solchen Funktionen höherer Ordnung wie gewohnt arbeiten. Wieder ersetzen wir die Variable, in unserem Fall f, durch das Argument. Typischerweise können wir die re-sultierende Beschreibung des Wertes noch weiter vereinfachen, indem wir nämlich die Funk-tion f auf ihr Argument, hier die Zahl 3, anwenden:

(77) a. λf[f(3)](λx[x2]) b. λf[f(3)](λx[x2 + x + 1]) = λx[x2](3) = λx[x2 + x + 1](3) = 9 = 13

Ein komplizierteres Beispiel einer Funktion höherer Ordnung mit Anwendung auf ein Argu-ment:

(78) a. λf[f(3) + f(4)] b. λf[f(3) + f(4)](λx[x2 + x + 1]) = λx[x2 + x + 1](3) + λx[x2 + x + 1](4) = 13 + 21 = 34

Und noch ein Beispiel, um den Dreh rauszukriegen. In der Ableitung habe ich jeweils den Teilausdruck unterstrichen, der in der darauffolgenden Zeile manipuliert wird.

(79) a. λf[f(f(3)–9)] b. λf[f(f(3)–9)](λx[x2 + x + 1]) = λx[x2 + x + 1](λx[x2 + x + 1](3) – 9) = λx[x2 + x + 1](13 – 9) = λx[x2 + x + 1](4) = 21

Solche Funktionen zu berechnen ist nicht wirklich schwierig; allerdings kann man sich leicht vertun. Das ist eines der Dinge, in denen Computer besser sind als Menschen. In der Tat ba-sierte eine der ersten Programmiersprachen, LISP, auf dem Lambda-Kalkül, und LISP ist noch immer in Gebrauch, besonders in der Forschung zur Künstlichen Intelligenz. Bei Funktionen, die Funktionen als Argumente nehmen, müssen wir besonders auf Fälle ach-ten, in denen die Funktion nicht definiert ist, was sich bisweilen erst recht spät in der Ablei-tung herausstellt. Betrachten wir das folgende Beispiel:

(80) λf[f(f(4)–8)](λx 〈x∈ GG〉 [x2 + x + 1]) = λx 〈x∈ GG〉 [x2 + x + 1](λx 〈x∈ GG〉 [x2 + x + 1](4) – 8) = λx 〈x∈ GG〉 [x2 + x + 1](21 – 8) = λx 〈x∈ GG〉 [x2 + x + 1](13): nicht definiert



Im letzten Schritt zeigt sich, dass die Funktion für das Argument, die Zahl 13, nicht definiert ist, weil 13 keine gerade Zahl ist. Folglich ist die Ausgangsfunktion λf[f(f(4)–8)] für das Ar-gument λx〈x∈GG〉 [x2 + x + 1] nicht definiert.

2.4.5 Funktionen mit Funktionen als Werte Wir haben gesehen, dass wir Funktionen definieren können, die Funktionen als Argumente nehmen; nun wollen wir Fälle von Funktionen betrachten, die Funktionen als Werte liefern. Ein Beispiel ist das folgende:

(81) λxλy[x2 + y] Diese Funktion nimmt einen Wert x und liefert eine Funktion, die ihrerseits einen Wert y nimmt und den Wert x2 + y ausgibt. Man betrachte das folgende Beispiel, in dem wir zuerst die Funktion λxλy[x2 + y] auf das Argument 3 anwenden, woraus sich die Funktion λy[9 + y] ergibt. Dann wenden wir diese Funktion auf das Argument 4 an.

(82) λxλy[x2 + y](3)(4) = λy[9 + y](4) = 9 + 4 = 13

2.4.6 Skopus, Variablenbindung, Variablenumbenennung An dieser Stelle ist es angebracht, etwas zur Benennung von Variablen zu sagen. Prinzipiell sollte der Name einer Variablen in der Funktionsbeschreibung keinen Einfluss auf die Bedeu-tung dieser Beschreibung haben. Schließlich sind Variablen nur Platzhalter, und es sollte kei-ne Rolle spielen, wie die Platzhalter heißen. Die beiden folgenden Ausdrücke beschreiben genau dieselbe Funktion:

(83) a. λx[x2 + x + 1] b. λy[y2 + y + 1]

Bei Funktionen, die Funktionen als Werte liefern, müssen wir gewöhnlich die Variablen von-einander unterscheiden. Während wir Variablen austauschen können und trotzdem dieselbe Funktion erhalten, dürfen wir Unterscheidungen, die sich aus unterschiedlichen Variablen-namen ergeben, nicht aufgeben.

(84) a. λxλy[x2 + y] b. = λyλx[y2 + x] c. ≠ λxλx[x2 + x]

Hat (84.c) überhaupt eine Bedeutung? Ja! Grundlegend dafür, wie die Lambda-Notation in-terpretiert werden soll, ist der Begriff des Skopus eines mit einer Variablen besetzten Lamb-da-Operators. Das ist jener Teil der Beschreibung, in welchem die Vorkommen der Variablen durch das Argument ersetzt werden müssen. Allgemein gilt:

(85) In einem Lambda-Term λ v […] ist “[…]” der Skopus von “λv”. Skopus ist mit Bezug auf ein konkretes Vorkommen einer Variablen (ein Token) definiert, nicht allgemein für einen Variablennamen (auch Typ genannt). In dem folgenden Beispiel sind Variablentoken wo nötig durch Striche identifiziert.

(86) a. λx[x2 + x + 1] b. λx[3x + λx′[x′2 + x′ + 1](x)] Skopus von λx Skopus von λx′ Skopus von λx



Es gilt die Konvention, dass ein Variablen-Token in einer Beschreibung im Skopus des nächst höheren Lambda-Operators mit derselben Variablen ist. Wir sagen dann, dass der Lambda-Operator jene Variable bindet. Obwohl Lambda-Ausdrücke wie (84.c) oder (86.b) korrekt sind, trägt es viel zur Verständlichkeit bei, verschiedene Variablennamen zu benut-zen, wie z.B. im Folgenden:

(87) a. λxλy[y2 + y] b. λx[3x + λy[y2 + y + 1](x)]

Man beachte, dass im Fall von (87.a) die Variable x im Rumpf des Lambda-Terms überhaupt nicht vorkommt. Das ist kein Problem; es bedeutet vielmehr, dass eine konstante Funktion vorliegt. Das kann beispielsweise eine Funktion sein, die alles auf die Zahl 13 abbildet:

(88) λx[13] Da der konkrete Name einer Variablen keine Rolle spielt, solange er verschieden ist von de-nen anderer Variablen, die von anderen Lambda-Operatoren gebunden werden, können wir nach Belieben Variablen umbenennen, vorausgesetzt dass wir dies auf konsistente Weise tun. Umbennung von Variablen ist oft notwendig, um einen Lambda-Term besser lesbar zu ma-chen oder um mit der Berechnung der Werte fortfahren zu können.

2.4.7 Verknüpfung von Funktionen Wir können Funktionen nicht nur auf Argumente anwenden; wir können Funktionen (und allgemeiner Relationen) auch miteinander verknüpfen. Als Beispiel ist die Verknüpfung der Funktionen f: {A, B, C, D} → {1, 2, 3, 4} und g: {1, 2, 3, 4} → {α, β, γ, δ} in dem folgen-den Diagramm dargestellt. (89)

A 1 α B 2 β C 3 γ D 4 δ f: g ° f: g:

Wir schreiben g°f für die Verknüpfung der Funktion f mit der Funktion g. Warum aber in dieser Reihenfolge, die auf den ersten Blick unserer Intuition zu widersprechen scheint? Weil dann für jede zwei Funktionen f und g gilt:

(90) Für alle x im Definitionsbereich von f: g(f(x)) = [g°f](x) — oder kürzer: g°f(x). Wir brauchen eigentlich kein neues Symbol für die Verknüpfung von Funktionen. Wir kön-nen sie nämlich mit Hilfe von Lambda-Termen definieren:

(91) Verknüpfung von Funktionen: λg[λf[λx[g(f(x))]]] Dieser Lambda-Term nimmt als Argumente eine Funktion g und dann eine Funktion f und liefert die Verknüpfung der beiden Funktionen g°f, die sich als λx[g(f(x))] beschreiben lässt. Nehmen wir das folgende Beispiel, die Verknüpfung der Nachfolgerfunktion mit der Verdopplungsfunktion für natürliche Zahlen:

(92) λg[λf[λx[g(g(x)))]]](λy[y + 1])(λz[z + z]) = λf[λx[λy[y + 1](f(x))]](λz[z + z]) = λx[λy[y + 1](λz[z + z](x))] = λx[λy[y + 1](x + x)] = λx[x + x + 1]

Charakteristische Funktionen 18


Frage: Erhalten wir das gleiche Ergebnis für die Verknüpfung der Verdopplungsfunktion mit der Nachfolgerfunktion? Verknüpfung von Funktionen mag den Anschein erwecken, von rein mathematischem Inte-resse zu sein. Ist sie aber nicht. Zum Beispiel lässt sich die Bedeutung von Großvater mütter-licherseits als Verknüpfung der Bedeutungen von Vater und von Mutter definieren:

(93) [[Großvater mütterlicherseits]] = λf[λg[λx[f(g(x)))]]](λy[der Vater von y])(λz[die Mutter von z]) = λg[λx[λy[der Vater von y](g(x))]](λz[die Mutter von z]) = λx[λy[der Vater von y](λz[die Mutter von z](x))] = λx[λy[der Vater von y](die Mutter von x)] = λx[der Vater der Mutter von x]

Einige Sprachen besitzen ein recht transparentes System zum Ausdruck dieser Beziehungen. Ein Beispiel ist Schwedisch, das morfar, wörtl. ‘Mutter Vater’, für Großvater mütterlicher-seits (und entsprechend mormor, farmor und farfar) kennt. Die Bedeutung des komplexen Terms morfar ist offenbar von den Bedeutungen der einfacheren Terme mor und far mittels Verknüpfung von Funktionen abgeleitet:

(94) [[morfar]] = λf[λg[λx[f(g(x)))]]]([[far]])([[mor]]), = [[far]] ° [[mor]]

2.5 Charakteristische Funktionen Wir haben oben den Begriff einer Menge eingeführt. Auf der Grundlage dieses Begriffes haben wir Relationen eingeführt und Funktionen als eine spezielle Art von Relationen. Jetzt wollen wir Funktionen verwenden, um eine neue Notation für Mengen zu entwickeln.

2.5.1 Wahrheitswertige Funktionen Mengen haben wir als Zusammenfassungen von Elementen (eines gegebenen Universums) definiert. Eine Menge zu kennen bedeutet, in der Lage zu sein, die Elemente jener Menge zu identifizieren. Das heißt, von jedem Objekt müssen wir wissen, ob es in der Menge enthalten ist oder nicht. Diese Information kann als eine Funktion gegeben sein, als diejenige Funktion nämlich, die jedem Objekt in dem Universum genau einen von zwei möglichen Werten zu-ordnet: • den Wert wahr (1), falls das Objekt in der Menge enthalten ist; • den Wert falsch (0), falls das Objekt nicht in der Menge enthalten ist. Dabei sind wahr und falsch die beiden Wahrheitswerte, über die wir in der Einführung ge-sprochen haben. Solche Funktionen heißen charakteristische Funktionen einer Menge, weil sie die jeweilige Menge “charakterisieren”. Wir schreiben χA (“chi-A”) für die charakteristische Funktion der Menge A. Sei U ein Universum und A eine Menge mit A ⊆ U, dann haben wir die folgende Definition für die charakteristische Funktion von A:

(95) χA: U → {0, 1}, x → 1, wenn x ∈ A, x → 0, wenn x ∉ A.

Beispiel:

(96) Sei das Universum U die Menge der Kleinbuchstaben {a, b, c, ..., z}. Dann gilt: χ{b, c} = {〈a, 0〉, 〈b, 1〉, 〈c, 1〉, 〈d, 0〉, 〈e, 0〉, ..., 〈z, 0〉}

Der Begriff einer charakteristischen Funktion erlaubt es uns, eine wichtige Beziehung zwi-schen der Prädikatsnotation bzw. Abstraktion für Mengen und der Lambda-Notation für Funktionen zu klären. Man betrachte die folgende Menge:



(97) {x | x ist eine Frau} Dies ist die Menge aller Frauen. Ihre charakteristische Funktion ist diejenige Funktion, die jedes x auf 1 abbildet, falls x eine Frau ist, und auf 0, falls x keine Frau ist:

(98) χ{x | x ist eine Frau} U → {0, 1} x |→ 1 wenn x ∈ {x | x ist eine Frau}, i.e. falls x eine Frau ist x |→ 0 wenn x ∉ {x | x ist eine Frau}, i.e. falls x keine Frau ist.

2.5.2 Charakteristische Funktionen als Lambda-Terme Können wir charakteristische Funktionen als Lambda-Terme ausdrücken? Nicht ganz, weil Lambda-Terme keine disjunktiven Beschreibungen der Art “wenn x so-und-so, dann ist der Wert der-und-der, aber wenn x solch-und-solch, dann ist der Wert das-und-das” erlauben. Wir können jedoch die folgende Konvention für Beschreibungen in Lambda-Termen einfüh-ren, die intuitiv Sätze sind:

(99) In einem Lambda-Term “λ Variable ∈ Definitionsbereich [Beschreibung des Wertes]”, in dem die Beschreibung des Wertes ein Satz ist, der entweder wahr oder falsch sein kann, steht diese für 1, wenn der Satz für ein gegebenes Argument wahr ist, und für 0, wenn der Satz für ein gegebenes Argument falsch ist.

Damit sind wir in der Lage, die charakteristische Funktion der Menge {x | x ist eine Frau} folgendermaßen darzustellen:

(100) λx[x ist eine Frau] Statt z.B. “Maria ∈ {x | x ist eine Frau}” zu schreiben, können wir die Funktionsnotation benutzen und schreiben:

λx[x ist eine Frau](Maria) = 1, wenn Maria eine Frau ist, = 0, wenn Maria keine Frau ist.

Diese Schreibweise können wir auch für mathematische Beispiele einsetzen. Zum Beispiel können wir die Menge der natürlichen Zahlen größer oder gleich 7 statt in der Mengennotati-on

{x | x∈NN und x≥7} in der Lambda-Notation durch die zugehörige charakteristische Funktion darstellen:

λx[x∈NN und x≥7] Die Lambda-Notation ist allerdings ausdrucksstärker. Die gerade definierte Funktion bildet jedes Objekt ab – auf 1, falls es sich um eine natürliche Zahl größer oder gleich 7 handelt, und auf 0 sonst. Mit Hilfe der Lambda-Notation können wir die folgende Funktion definie-ren:

λx∈NN [x≥7] Diese Funktion bildet jede natürliche Zahl auf 1 ab, falls sie größer oder gleich 7 ist, und auf 0 sonst. Wenden wir die Funktion auf etwas an, das keine natürliche Zahl ist, so erhalten wir gar nichts, weil das Argument nicht im Definitionsbereich der Funktion enthalten ist. In folgender Hinsicht ist daher die Schreibweise mit charakteristischen Funktionen aus-drucksstärker als die Mengennotation: • In der Mengennotation {x | ...x...} gibt es für jedes bestimmte Objekt e genau zwei Mög-

lichkeiten: Entweder gilt e ∈ {x | ...x...} (was bedeutet, dass die Beschreibung ...e... wahr ist), oder e ∉{x | ...x...} (was bedeutet, dass die Beschreibung ...e... nicht wahr ist).

Funktionen und sprachliche Bedeutungen 20


• In der Funktionsnotation λx∈D[...x...] gibt es für jedes bestimmte Objekt e genau drei Möglichkeiten: Entweder ist e im Definitionsbereich D und die Beschreibung ...e... ist wahr, oder e ist im Definitionsbereich D und die Beschreibung ...e... ist falsch, oder e ist nicht einmal im Definitionsbereich der Funktion.

2.5.3 Mengentheoretische Operationen für charakteristische Funktionen Da charakteristische Funktionen mit Mengen eng verwandt sind, können wir die mengenthe-oretischen Beziehungen Teilmenge ⊆ und echte Teilmenge ⊂ sowie die Operationen Durch-schnitt ∩, Vereinigung ∪ und Differenz \ auf charakteristische Funktionen ausweiten. Aber wir müssen vorsichtig sein; wir haben gesehen, dass charakteristische Funktionen ausdrucks-stärker als Mengen sind, insofern als man zwischen den beiden Fällen, dass nämlich die Funktion für ein gegebenes Objekt den Wert 0 liefert oder aber für dieses Objekt gar nicht definiert ist, unterscheiden kann. Wir werden die mengentheoretischen Begriffe in folgendem Sinne gebrauchen:

(101) Seien c, d zwei charakteristische Funktionen, dann gilt: a. c ⊆ d ist definiert, wenn DOM(c) ⊆ DOM(d). Wenn definiert, ist es wahr, falls {x | c(x)} ⊆ {x | d(x)}, sonst falsch. b. c ⊂ d ist definiert, wenn DOM(c) ⊆ DOM(d). Wenn definiert, ist es wahr, falls {x | c(x)} ⊂ {x | d(x)}, sonst falsch. c. c ∩ d = λx〈x∈DOM(c)∩DOM(d)〉 [x ∈ {x| c(x)} ∩ {x | d(x)}] d. c ∪ d = λx〈x∈DOM(c)∩DOM(d)〉 [x ∈ {x| c(x)} ∪ {x | d(x)}] e. c \ d = λx〈x∈DOM(c)∩DOM(d)〉 [x ∈ {x| c(x)} \ {x | d(x)}] f. c′ = λx〈x∈DOM(c)〉 [x ∉ {x | c(x)}]

Zum Beispiel ist die Vereinigung zweier charakteristischer Funktionen c und d eine Funktion, welche für alle x definiert ist, die sowohl im Definitionsbereich von c als auch im Definiti-onsbereich von d enthalten sind. Sie bildet x auf den Wert wahr ab, falls x in der Vereinigung der Objekte, die c auf wahr abbildet, mit denjenigen, die d auf wahr abbildet, enthalten ist, sonst ordnet sie x den Wert falsch zu.

2.6 Funktionen und sprachliche Bedeutungen Es sollte bereits klargeworden sein, dass der Begriff der Funktion ganz zentral ist, um sprachliche Bedeutungen zu beschreiben – eine Erkenntnis, die auf Frege zurückgeht. Wir wollen uns hier einige Aspekte näher betrachten.

2.6.1 Darstellung von Relationen als Funktionen: Die Schönfinkelisierung Wir haben in 2.3.1 gesehen, dass wir die Bedeutung transitiver Verben wie liebt als Relatio-nen darstellen können. Diese Relation ist sicher keine Funktion, da sie nicht rechtseindeutig ist: Eine Person kann mehr als nur eine Person lieben. Auch viele Nomina haben relationale, und nicht funktionale Bedeutung, so etwa Tochter im Gegensatz zu Mutter. Es sieht daher so aus, als ob wir grundsätzlich von relationalen, und nicht funktionalen Bedeutungen ausgehen sollten. Allerdings gibt es Verfahren, mit denen wir Relationen als Funktionen darstellen können. Wir haben gesehen, dass charakteristische Funktionen es uns erlauben, Mengen als Funktio-nen darzustellen. Relationen sind auch Mengen, nämlich Mengen von Paaren, und folglich können wir sie ebenfalls als Funktionen darstellen. Man betrachte z.B. die folgende Relation, die Bedeutung von Vorfahr:

(102) a. [[Vorfahr]] als Relation: {〈x, y〉 | y ist ein Vorfahr von x}. b. [[Vorfahr]] als Funktion: λ〈x,y〉∈{〈x,y〉| x∈Person, y∈Person} [y ist ein Vorfahr von x]



Zum Beispiel ist λ〈x,y〉[y ist ein Vorfahr von x](〈Isaak, Abraham〉) = 1. Die erste Darstellung erlaubt Aussagen der Art:

〈Isaak, Abraham〉 ∈ {〈x, y〉 | y ist ein Vorfahr von x}, da Abraham ein Vorfahr von Isaak ist.

Bei der zweiten Darstellung müssen wir Paare von Variablen zulassen, dann können wir funktionale Applikation auch für Argumente benutzen, die ihrerseits Paare sind. Damit ist funktionale Applikation wie im Folgenden möglich:

λ〈x,y〉[y ist ein Vorfahr von x](〈Isaak, Abraham〉) = 1, da Abraham ein Vorfahr von Isaak ist.

Aber es gibt noch einen anderen Weg, die Funktionsnotation zu nutzen. Statt die Bedeutung von Vorfahr als Funktion über Paare aufzufassen, können wir sie als Funktion ansehen, die erst das eine Argument (den Nachfahren z.B.) und dann das andere nimmt. Diese Reduktion auf einstellige Funktionen geht auf die Logiker Schönfinkel und Curry zurück und wird Schönfinkelisierung genannt.

(103) [[Vorfahr]], auf einstellige Funktionen reduziert: λx∈Person[λy∈Person[y ist ein Vorfahr von x]]

Damit sind Aussagen wie die folgende möglich: λx∈Person[λy∈Person[y ist ein Vorfahr of x]](Isaak)(Abraham)

= λy∈Person[y ist ein Vorfahr von Isaak](Abraham) = 1, da Abraham ein Vorfahr von Isaak ist.

Dieselbe Technik lässt sich natürlich auch auf dreistellige Relationen anwenden:

(104) a. [[geben]] als Relation: {〈x, y, z〉 | x gibt y an z} b. [[geben]] als Funktion: λ〈x,y,z〉[x gibt y an z] c. [[geben]] als reduzierte Funktion: λz[λy[λx[x gibt y an z]]]

Es gibt natürlich verschiedene Arten, eine Funktion zu reduzieren. Zum Beispiel ist anstelle von (103) auch die folgende Reduktion möglich, welche sich nur in der Reihenfolge, in der die Funktion die Argumente erwartet, unterscheidet:

(105) [[Vorfahr]] auf andere Art reduziert: λy∈Person[λx∈Person[y ist ein Vorfahr von x]]

Für die semantische Analyse bietet der Gebrauch einstelliger Funktionen einen wichtigen Vorteil. Natürlichsprachliche Ausdrücke, die zwei oder mehr Argumente besitzen, behandeln diese oft unterschiedlich, wobei ein Argument dem Ausdruck “näher” zu sein scheint als das andere. Zum Beispiel zeigt die syntaktische Konstruktion des Nomens Vater, dass das Kind-Argument näher als das Vater-Argument ist. Das Kind-Argument bildet mit dem Nomen eine syntaktische Konstituente, eine sogenannte Nominalphrase (NP).

(106) a. Abraham ist [NP Isaaks Vater]. b. Abraham ist [NP der Vater von Isaak].

Entsprechend ist das Objekt-Argument von lieben näher als das Subjekt-Argument – das Ob-jekt bildet eine syntaktische Konstituente mit dem Verb, die sogenannte Verbalphrase (VP).

(107) Abraham [VP liebte Sarah]. Bei dem dreiargumentigen Verb geben werden die Dinge ein bisschen kompliziert. Es ist klar, dass das Subjekt-Argument am weitesten entfernt steht. Aber die beiden Formen im folgenden Beispiel legen die Vermutung nahe, dass geben in zwei verschiedenen Rahmen auftritt, die sich nur darin unterscheiden, ob das Objekt dem Verb am nächsten steht oder der Rezipient.

(108) a. Eva [VP gab einen Apfel Adam]. b. Eva [VP gab Adam einen Apfel].

Funktionen und sprachliche Bedeutungen 22


Allgemein finden wir syntaktische Evidenz, die für binär-verzweigende Strukturen gegenüber tertiär-verzweigenden Strukturen spricht:

(109) Abraham liebte Sarah Abraham liebte Sarah

Und das wiederum spricht für den Gebrauch von Funktionen, die ein einfaches Argument nehmen, gegenüber der Verwendung von mehr-als-einstelligen Relationen, wie wir im nächs-ten Kapitel sehen werden.

2.6.2 Charakteristische Funktionen und Satzbedeutungen Wir haben in 2.2.2 gesehen, dass die Bedeutung eines Satzes als eine Menge von möglichen Welten darstellbar sind – diejenigen möglichen Welten, in denen der Satz wahr ist. Wir ha-ben ebenfalls gesehen, dass Mengen als Funktionen gedeutet werden können – als charak-terische Funktionen, die den Elementen des Grundbereichs die Wahrheitswerte 0 oder 1 zu-weisen. Wir können nun sehr leicht charakteristische Funktionen verwenden, um Satzbedeu-tungen (Propositionen) wiederzugeben:

(110) Die Bedeutung eines Satzes Φ, ist die Funktion [[Φ]] von der Menge aller möglichen Welten W in die Menge der Wahrheitswerte {0, 1}, sodass für jedes w∈W gilt: [[Φ]](w) = 1 gdw. Φ wahr in w ist, sonst 0.

Mit der Lambda-Notation können wir dies wie folgt darstellen:

(111) [[Φ]] = λw∈W[Φ ist wahr in w] Wenn Φ in w wahr ist, dann wird durch diese Funktion der Welt w der Wert 1 zugewiesen; wenn Φ in w nicht wahr ist, dann wird der Welt w der Wert 0 zugewiesen. – Ein Beispiel:

(112) [[es regnet]] = λw∈W[es regnet ist in w wahr], = λw∈W[es regnet in w]

Wir können solche Propositionen, wie andere charakterische Funktionen auch, mit den men-gentheoretischen Operationen ∪, ∩ und der Komplementbildung verknüpfen, wie in (101) definiert. Einige Beispiele:

(113) [[es donnert und blitzt]] = [[es donnert]] ∩ [[es blitzt]] = λw[es donnert in w] ∩ λw[es blitzt in w] = λw[es donnert in w und es blitzt in w]

(114) [[es ist nicht der Fall, dass es donnert]] = λw[es donnert in w]′ = λw[es donnert nicht in w]

2.6.3 Zum Aufbau von Sätzen Wir wollen hier vorwegnehmen, wie wir uns den kompositionalen Aufbau von sehr einfachen Sätzen wie Lola rennt vorstellen können. Wir haben die Bedeutung von intransitiven Verben wie rennt oben dargestellt als Funktionen von Entitäten in Wahrheitswerte. Das liefert nun aber keine charakteristische Funktion einer Menge von möglichen Welten, wenn wir solche Verbbedeutungen auf die Bedeutung von Namen anwenden. Wir sollten daher mit Bedeutungen der folgenden Art für intransitive Ver-ben rechnen:

(115) [[rennt]] = λx∈Uλw∈W[x rennt in w]



Dies ist eine Funktion von der Grundmenge U aller Entitäten zu Funktionen von der Menge der möglichen Welten w in die Wahrheitswerte {0, 1}. Wir können uns dann den Aufbau eines Satzes wie folgt vorstellen:

(116) [[Lola rennt]] = [[rennt]] ([[Lola]]) = λxλw[x rennt in w](Lola) = λw[Lola rennt in w]

Dies ist eine Funktion, die jede mögliche Welt w auf den Wahrheitswert 1 abbildet, wenn Lola in w schläft, und sonst auf den Wahrheitswert 0.

2.7 Aussagen- und Prädikatenlogik

2.7.1 Warum Logik? Der Grundbegriff der Logik ist die logische Folgerungsbeziehung: Was heißt es, dass aus bestimmten Annahmen eine andere Annahme folgt. Bereits der Begründer der Logik, Aristo-teles, hat sie so verstanden. Das Ziel war, komplexe Beweisführungen auf einfache Schritte zu reduzieren, die als solche unmittelbar einsichtig waren, sogenannte Syllogismen. Ein Beispiel eines solchen Syllogismus: Aus den Annahmen Alle Menschen sind sterblich und Alle Athener sind Menschen folgt: Alle Athener sind sterblich. Damit ist die Logik aber un-mittelbar für die Semantik relevant, da logische Folgerungen kraft der Bedeutung der Aus-drücke in den Annahmen gelten. In der Wissenschaftsgeschichte hat sich die Logik allerdings von der natürlichen Sprache gelöst. Philosophen und Logiker seit Leibniz haben in den Ambiguitäten und Vagheiten der natürlichen Sprache ein großes Hindernis für die logische Forschung gesehen und haben daher auf die Entwicklung von formalen Kunstsprachen gedrängt, deren syntaktische und auch semantische Eigenschaften genau definiert und bekannt waren. Ein wichtiger Meilen-stein dieser Bewegung ist die “Begriffsschrift”, die Frege 1879 publizierte. Heute gibt es eine schier unüberschaubare Vielfalt von solchen logischen Kunstsprachen, mit unterschiedlichen Eigenschaften und Folgerungsbeziehungen. An dieser Stelle kann man selbstverständlich keine Einführung in die Logik erwarten – hier-für gibt es ausgezeichnete Lehrbücher. Es sollen lediglich einige logische Schreibweisen und ihre Interpretationen vorgestellt werden, die sich für die Metasprache, in der wir Bedeutungen beschreiben, als praktisch herausgestellt haben.

2.7.2 Aussagenlogik: Syntax Die Aussagenlogik ist der Teil der Logik, der lediglich Aussagesätze und deren Kombina-tionen betrachtet, sich also für Phänomene unterhalb der Satzebene nicht interessiert. Die Syntax der Aussagenlogik kann man mit ein paar Regeln behandeln. Es gibt eine Menge von einfachen oder atomaren Sätzen und einige wenige Regeln, wie aus Sätzen neue Sätze gebildet werden. Auf diese Weise wird die Menge der wohlgeformten Sätze festgelegt.

(117) Menge der atomare Sätze: {p, q, r, ...} (eine endliche oder auch unendliche Menge)

Aussagen- und Prädikatenlogik 24


(118) Menge der wohlgeformten Sätze: a. Jeder atomare Satz ist ein wohlgeformter Satz. b. Wenn Φ, Ψ wohlgeformter Sätze sind, dann sind auch die folgenden Ausdrücke wohlgeformte Sätze: ¬Φ (die Negation von Φ, gesprochen non Φ) [Φ ∧ Ψ], (Konjunktion, gesprochen Φ und Ψ; auch & geschrieben) [Φ ∨ Ψ], (Disjunktion, Φ oder Ψ) [Φ → Ψ], (Konditional, materiale Implikation, wenn Φ dann Φ, auch ⊃ ) [Φ ↔ Ψ]. (Bikonditional, Äquivalenz, Φ genau dann wenn Ψ; auch ≡)

Einige Beispiele und Nicht-Beispiele von wohlgeformten Sätzen:

(119) wohlgeformt nicht wohlgeformt p p ∧ [p ∧ q] [p ∧ → q] [¬[p ∧ q] ∨ r] → q [[[p ∧ q] → ¬q] ∨ ¬¬p] [[[p ∧ q] → ¬q] ∨ ¬¬p]]

Es sollte deutlich sein, dass die Definition der wohlgeformten Sätze eine unendliche Menge erzeugt, selbst wenn die Menge der atomaren Sätze endlich ist. Dies ist der Fall, weil die syn-taktischen Regeln rekursiv sind: Der “Output” einer Regel kann wiederum als “Input” der Regel dienen. Aus der Regel für die Negation folgt zum Beispiel, dass es sich bei den fol-genden Ausdrücken um wohlgeformte Sätze handelt:

(120) p, ¬p, ¬¬p, ¬¬¬p, ¬¬¬¬p, ¬¬¬¬¬p, … Die Klammerung dient dazu, Ambiguitäten zu vermeiden. Zum Beispiel erzeugen die Regeln sowohl den Ausdruck ¬[p ∧ q] als auch den Ausdruck [¬p ∧ q], die durchaus verschiedenes bedeuten sollen. Lässt man die Klammern weg, so erhielte man den Ausdruck ¬ p ∧ q, der ambig ist, und gerade das will ja die logische Notation vermeiden. Es gibt allerdings Konven-tionen, die es erlauben, Klammern zur Vereinfachung der Schreibweise wegzulassen.

2.7.3 Aussagenlogik: Semantik Die übliche Semantik der Aussagenlogik ist sehr einfach: Sätze sind entweder wahr oder falsch. Die Logik selbst kann dabei nichts über die Bedeutung der atomaren Sätze sagen, wohl aber übe die Bedeutung von komplexen Sätzen, die sich systematisch auf komposition-ale Weise aus den Bedeutungen ihrer Teile ergibt. Es gelten dabei folgende Regeln:

(121) a. ¬Φ ist wahr wenn Φ falsch ist, sonst wahr. b. [Φ ∧ Ψ] ist wahr wenn sowohl Φ als auch Ψ wahr ist, sonst falsch. c. [Φ ∨ Ψ] ist falsch wenn sowohl Φ als auch Ψ falsch ist, sonst wahr. d. [Φ → Ψ] ist falsch gdw. Φ wahr und Ψ falsch ist, sonst wahr. e. [Φ ↔ Ψ] ist wahr gdw. Φ und Ψ den gleichen Wahrheitswert haben, sonst falsch.

Man kann diese Bedeutungsregeln für komplexe Aussagen in sog. Wahrheitstafeln darstellen, wobei wir wie üblich die Wahrheitswerte 0 und 1 für falsch und wahr annehmen. Wir be-trachten hierzu alle möglichen Kombinationen von Wahrheitswerten für zwei Sätze Φ, Ψ und geben für jede Kombination den Wahrheitswert für die komplexen Sätze [Φ ∧ Ψ], [Φ ∨ Ψ], [Φ → Ψ] und [Φ ↔ Ψ] an. Die Bedeutung von ¬Φ hängt dabei natürlich nur von der Bedeu-tung von Φ ab.



(122) Wahrheitswert-Tabelle

Φ Ψ ¬Φ [Φ ∧ Ψ] [Φ ∨ Ψ] [Φ → Ψ] [Φ ↔ Ψ] 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1

Damit kann man den Wahrheitswert eines komplexen Satzes errechnen, wenn die Wahr-heitswerte der atomaren Sätze bekannt ist. Ein Beispiel:

(123) [[p ∨ q] → [r ∧ p]]

0 1 1 0 [Wahrheitswerte der atomaren Sätze: p: 0, q: 1, r: 1]

1 0

0 [Abgeleiteter Wahrheitswert des komplexen Satzes]

2.7.4 Die Aussagenlogik als Boolesche Algebra Nicht zufällig erinnern die aussagenlogischen Symbole ∧ und ∨ and die mengentheoretischen Operationen ∩ und ∪: Die aussagenlogischen Verknüpfungen bilden nämlich eine mathema-tische Struktur, in der dieselben Gesetzmäßigkeiten gelten wie bei den mengentheoretischen Verknüpfungen, also eine Boolesche Algebra. Die Rolle des Universums wird dabei von der Tautologie T übernommen, die immer den Wahrheitswert 1 hat; die Rolle der leeren Menge von der Kontradiktion ⊥ , die immer den Wahrheitswert 0 hat. Dann gelten die folgenden Gesetze:

(124) a. Idempotenz: [Φ ∧ Φ] ⇔ Φ, [Φ ∨ Φ] ⇔ Φ

b. Kommutativität: [Φ ∧ Ψ] ⇔ [Ψ ∧ Φ], [Φ ∨ Ψ] ⇔ [Ψ ∨ Φ]

c. Assoziativität: [Φ ∧ [Ψ ∧ Ξ]] ⇔ [[Φ ∧ Ψ] ∧ Ξ] [Φ ∨ [Ψ ∨ Ξ]] ⇔ [[Φ ∨ Ψ] ∨ Ξ]

d. Distributivität: [Φ ∧ [Ψ ∨ Ξ]] ⇔ [[Φ ∧ Ψ] ∨ [Φ ∧ Ξ]] [Φ ∨ [Ψ ∧ Ξ]] ⇔ [[Φ ∨ Ψ] ∧ [Φ ∨ Ξ]]

e. de Morgan: ¬[Φ ∧ Ψ] ⇔ [¬Φ ∨ ¬Ψ] ¬[Φ ∨ Ψ] ⇔ [¬Φ ∧ ¬Ψ]

f. Negationsregeln: [Φ ∨ ¬Φ] ⇔ T ¬[Φ ∧ ¬Φ] ⇔ ⊥ ¬T ⇔ ⊥

2.7.5 Prädikatenlogik Eine etwas ausdrucksreichere logische Sprache bietet die Prädikatenlogik. In dieser Logik gibt es neben atomaren Sätzen auch Ausdrücke, welche Individuen bezeichnen, und solche, welche Eigenschaften und Relationen zwischen Individuen ausdrücken. Die Prädikatenlogik enthält die folgenden atomaren Ausdrücke:

Aussagen- und Prädikatenlogik 26


(125) a. Menge der Namen: {a, b, c, …}, eine endiche oder unendliche Menge. b. Menge der Sätze: {p, q, r, …}, eine endliche oder unendliche Menge. b. Menge der Prädikate: {P, Q, R, …}, eine endliche oder unendliche Menge. c. Menge der zweistelligen Relationen {P2, Q2, R2, …}, allgemein: für n ≥ 2: Menge der n-stelligen Relationen {Pn, Qn, Rn, …}

Hierbei können Prädikate als einstellige Relationen und Sätze als nullstellige Relationen ver-standen werden. Zusätzlich zu den syntaktischen Regeln der Aussagenlogik gibt es noch die folgende Regel zum Aufbau von Sätzen:

(126) a. Wenn α ein einstelliges Prädikat und ν ein Name ist, dann ist α(ν) eine Aussage. b. Allgemein: Wenn α ein n-stelliges Prädikat und ν1, ν2, … νn n Namen sind, dann ist α(ν1, ν2, … νn) eine Aussage.

Die zugrundeliegende Semantik – die hier nicht weiter entwickelt wird – sagt, dass ein Aus-druck der Art α(ν) besagt: Der Träger des Namens ν hat die Eigenschaft α. Wenn beispiels-weise P intuitiv als ‘rot’ und a als Name für einen bestimmten Apfel verstanden wird, dann steht P(a) für die Aussage ‘a ist rot’; diese kann wahr oder falsch sein. Wenn R intuitiv für die Relation ‘kennt’ und b und c für die Personen Bill und Carl stehen, dann steht R(b, c) für die Aussage ‘Bill kennt Carl’.

2.7.6 Variablen und Quantoren Eine wesentliche Bereicherung ihrer Ausdruckskraft bekommt die Prädikatenlogik durch die Verwendung von Variablen und Quantoren. Variablen stehen wie Namen für Individuen, aber nicht für ein bestimmtes Individuum. Namen und Variablen zusammen werden Terme genannt. Zusammen mit Quantoren können Variablen allgemeine Sätze ausdrücken. Die Prädikatenlogik verwendet vor allem zwei Quantoren: Den Existenzquantor ∃ und den Allquantor ∀. Die folgenden Bestimmungen legen fest, wie Variablen und Quantoren ver-wendet werden.

(127) a. Menge von Variablen {x, y, z, …} b. Menge von Termen: Menge von Namen ∪ Menge von Variablen c. Wenn τ1, τ2, … τn Terme sind und Pn eine P-stellige Relation, dann ist P(τ1, τ2, … τn) eine Aussage. d. Wenn χ eine Variable und Φ eine Aussage ist, dann sind ∃χ Φ und ∀χ Φ ebenfalls Aussagen.

Einige Beispiele für Aussagen, in denen Quantoren vorkommen, und ihre intendierte Inter-pretationen:

(128) a. ∃x P(x) ‘Es gibt ein Individuum x mit Eigenschaft P’ b. ∀x P(x) ‘Alle Individuen x haben die Eigenschaft P’ c. ∃x [P(x) ∧ Q(x)] ‘Es gibt ein x, sodass P(x) und Q(x) gilt’ d. ∀x [P(x) → Q(x)] ‘Für jedes x gilt: Wenn P(x) gilt, dann gilt Q(x)’ ≈ ‘Jedes x, das ein P ist, ist auch ein Q’ e. ∀x [P(x) → ∃y [R(x, y)]] ‘Für jedes x gilt: Wenn P(x), dann gibt es ein y, sodass R(x, y) gilt’

Mithilfe der Prädikatenlogik kann man bereits komplexe Gedanken auf klare Weise for-mulieren. Beispielsweise kann man den Unterschied zwischen den Interpretationen des fol-genden ambigen Satzes ausdrücken:



(129) Jeder Filmfan bewundert eine Schauspielerin. a. ∀x[Filmfan(x) → ∃y[Schauspielerin(y) ∧ bewundert(x, y)]] ‘Für jeden Filmfan gibt es eine Schauspielerin, die er bewundert.’ b. ∃y[Schauspielerin(y) ∧ ∀x[Filmfan(x) → bewundert(x,y)]] ‘Es gibt eine Schauspielerin, die jeder Filmfan bewundert.’

Auf der anderen Seite gibt es Hinweise dafür, dass die natürliche Sprache von höherer Kom-plexität ist als die Prädikatenlogik (jedenfalls die sogenannte Prädikatenlogik erster Stufe, die hier dargestellt wurde). Beispielsweise kann man schon die Bedeutung eines Satzes wie Die meisten Filmfans bewundern Franka Polente nicht darstellen. Ferner ist auffällig, dass prädikatenlogische Aussagen offensichtlich syntaktisch anders auf-gebaut sind als solche von natürlichen Sprachen. Vergleichen wir die syntaktische Struktur der folgenden Sätze:

(130) a. Jeder Filmfan bewundert Franka Polente

b. ∀x [Filmfan(x) → bewundert(x, F.P.)] ‘Für jedes x: Wenn x ein Filmfan ist, dann bewundert x Franka Polente.’

In der natürlichsprachigen Ausdrucksweise (a) bildet jeder Filmfan eine syntaktische Konsti-tutente; in der prädikatenlogischen Darstellung (b) ist diese auseinandergerissen in einen Quantorteil ∀x und dem ersten Teilsatz eines komplexen Satzes, Filmfan(x). Wir werden in dem Kapitel zu Quantoren sehen, dass es möglich ist, eine logische Repräsentationssprache zu entwickeln, welche der syntaktischen Struktur des Deutschen besser entspricht. Im folgenden werden wir die Mittel der Prädikatenlogik in der Metasprache verwenden, um die Bedeutung von Sätzen der Objektsprache – also des Deutschen – zu beschreiben.

2.8 Zusammenfassung In diesem Kapitel haben wir einige Begriffe und Hilfsmittel kennen gelernt, die wichtig für die Untersuchung natürlichsprachlicher Ausdrücke sein werden, darunter vor allem Mengen, Relationen und Funktionen. Wir haben gesehen, dass sich Funktionen in einer besonders durchsichtigen Weise in der Lambda-Notation darstellen lassen. Wir haben auch herausge-funden, dass Mengen sich als wahrheitswertige Funktionen rekonstruieren lassen, und dass Relationen als Funktionen angegeben werden können. Das erlaubt es uns, Bedeutungen in einer Art zu strukturieren, die mit der Syntax menschlicher Sprachen besser in Einklang steht als die Auffassung von Relationen als Mengen geordneter Tupel. Wir haben schließlich eini-ges über die Sprache und Interpretation der formalen Logik – genauer, der Aussagenlogik und der Prädikatenlogik – kennengelernt.

Zusammenfassung 28


Aufgaben Kapitel 2: Grundlagen: Mengen, Funktionen, elementare Logik

1. Es sei A = {1, 2, 3, 4}, B = {3, 4, 5, 6}, C = {2, 4, 8}, U (Universum) = {x| 0 ≤ x ≤ 10} Geben Sie die folgenden Mengen in der Aufzählungsnotation an: a. A ∩ B c. A \ B e. (A ∪ B)′ g. (A′ ∪ B′)′ i. (C ∩ A) ∪ (C ∩ B) b. A ∪ B d. A′ f. A′ ∪ B′ h. C ∩ (A ∪ B) j. C ∪ (A ∩ B)

2. Definieren Sie “∩”, mithilfe der Operationen ∪ und ′. D.h., geben Sie eine Gleichung A ∩ B = ..., wobei “...” das “∩”-Zeichen nicht enthält.

3. Die mengentheoretischen Regeln für ∪ und ∩ sind den Regeln der Addition + und Mul-tiplikation • ähnlich. Beispielsweise ist + kommutativ: a+b = b+a. Vergleichen Sie die mengentheoretischen Gesetze (Kommutativität, Assoziativität, Dis-tributivität, Idempotenz) mit den entsprechenden arithmetischen und stellen Sie Ähnlichkeiten und Unterschiede fest.

4. Zeigen Sie mithilfe von Venn-Diagrammen, dass die folgenden beiden Sätze äquivalent sind: a. Es ist nicht der Fall, dass Lola rennt und Manne flennt b. Es ist nicht der Fall, dass Lola rennt, oder es ist nicht der Fall, dass Manne flennt.

5. Wie viele mögliche Relationen gibt es von einer Menge A in eine Menge B (abhängig von der Mächtigkeit von A und der Mächtigkeit von B). Hinweis: Jede Relation von A nach B ist eine Teilmenge des kartesischen Produkts A × B, jede Teilmenge von A × B ist eine Relation von A nach B. Die Frage ist: Wie viele Teilmengen gibt es in A × B, wenn #(A) = n und #(B) = m gilt.

6. Betrachten Sie die folgenden Mengen von Paaren. R1 = {〈1, a〉, 〈2, b〉, 〈3, c〉, 〈4, d〉} R2 = {〈1, a〉, 〈2, b〉, 〈3, c〉, 〈3, d〉, 〈4,d〉} R3 = {〈1, a〉, 〈2, b〉, 〈3, c〉, 〈4, c〉} R4 = {〈1, a〉, 〈2, b〉, 〈3, c〉} a) Welche dieser Relationen sind Funktionen? b) Welche dieser Relationen sind eineindeutige Funktionen? c) Welche dieser Relationen sind Funktionen auf die Menge {a, b, c, d}? d) Welche dieser Relationen sind Funktionen in die Menge {a, b, c, d}? e) Welche dieser Relationen sind partielle Funktionen von der Menge {1, 2, 3, 4}?

7. Reduzieren Sie die folgenden Lambda-Terme so weit wie möglich. Geben Sie dabei jeden einzelnen Ableitungsschritt an. a) λx[x • x](3) b) λx[x • x](λy[2 • y](3)) c) λxλy[(2 • x) + y](3)(4) d) λf[f(3)](λy[5+y]) e) λf[f(3) + f(4)](λy[5+y]) f) λf[f(3)(4)](λxλy[(2 • x) + y]) g) λf[f(f(f(1)](λx[x+1]) h) λfλg[f(g(f(3)))](λy[5 + y])(λx[2 • x]) i) λfλgλx[g(5)(f(2)(x))](λxλy[x+y])(λxλy[x-y])(8)

8. Geben Sie die charakteristischen Funktionen für die folgenden Mengen an,mit der Menge {a, b, c, d} als Universum. Sie können die Darstellung als Menge von Paaren oder die Pfeilnotation verwenden. a) ∅ b) {a, c} c) {a, b, c, d}

Documents

2. Grundlagen: Mengen, Funktionen, elementare Logikhome.uni-leipzig.de/doelling/veranstaltungen/Satzsemantik_02... · nung – die Reihenfolge, in der wir die Elemente angeben, spielt