12
Kapitel 1 Aussagenlogik Die Aussagenlogik beschäftigt sich mit der Verknüpfung mathematischer Aussagen. Dabei ist zu- nächst zu klären, was ein Mathematiker genau unter einer Aussage versteht: Definition 1 (Aussage). Eine (mathematische) Aussage ist eine Behauptung, von der eindeutig feststeht, ob sie wahr oder falsch ist. Eine Aussage im mathematischen Sinne hat also immer einen eindeutigen Wahrheitswert „wahr“ (kurz w) oder „falsch“ (kurz f). Beispiele 1. (a) Der BVB hat die letzten beiden Fussballspiele gewonnen. (b) Addieren wir zur Zahl 3 die Zahl 7, so erhalten wir 9. (c) 3+7=9 (d) Die Gleichung 5x = 10 hat genau die gleiche Lösung wie die Gleichung 10x = 20. Keine Aussagen sind: (d) Der BVB hat in der näheren Vergangenheit schlecht gespielt. (e) 3+7 (f) Rechnen Sie möglichst viele Aufgaben! 1.1 Verknüpfungen von Aussagen Auf Grundlage der Definition 1 können Aussagen miteinander verknüpft werden. Seien dazu A und B beliebige Aussagen. Hier dienen die Buchstaben A und B als Platzhalter für Aussagen in der Weise, wie zum Beispiel x, y oft als Platzhalter für reelle Zahlen verwendet werden. Wir werden im Folgenden lediglich ausnutzen, dass die Aussagen A, B wahr oder falsch sein können, der Inhalt der Aussagen spielt keine Rolle. Zum Beispiel können wir aus zwei Aussagen A und B eine dritte Aussage bilden, die genau dann wahr ist, wenn sowohl A als auch B den Wahrheitswert „wahr“ haben. In Zeichen A ^ B (A und B). 1

Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

Kapitel 1

Aussagenlogik

Die Aussagenlogik beschäftigt sich mit der Verknüpfung mathematischer Aussagen. Dabei ist zu-nächst zu klären, was ein Mathematiker genau unter einer Aussage versteht:

Definition 1 (Aussage). Eine (mathematische) Aussage ist eine Behauptung, von der eindeutigfeststeht, ob sie wahr oder falsch ist. Eine Aussage im mathematischen Sinne hat also immereinen eindeutigen Wahrheitswert „wahr“ (kurz w) oder „falsch“ (kurz f).

Beispiele 1.

(a) Der BVB hat die letzten beiden Fussballspiele gewonnen.

(b) Addieren wir zur Zahl 3 die Zahl 7, so erhalten wir 9.

(c) 3 + 7 = 9

(d) Die Gleichung 5x = 10 hat genau die gleiche Lösung wie die Gleichung 10x = 20.

Keine Aussagen sind:

(d) Der BVB hat in der näheren Vergangenheit schlecht gespielt.

(e) 3 + 7

(f) Rechnen Sie möglichst viele Aufgaben!

1.1 Verknüpfungen von Aussagen

Auf Grundlage der Definition 1 können Aussagen miteinander verknüpft werden. Seien dazu A undB beliebige Aussagen. Hier dienen die Buchstaben A und B als Platzhalter für Aussagen in derWeise, wie zum Beispiel x, y oft als Platzhalter für reelle Zahlen verwendet werden. Wir werden imFolgenden lediglich ausnutzen, dass die Aussagen A, B wahr oder falsch sein können, der Inhalt derAussagen spielt keine Rolle.

Zum Beispiel können wir aus zwei Aussagen A und B eine dritte Aussage bilden, die genau dannwahr ist, wenn sowohl A als auch B den Wahrheitswert „wahr“ haben. In Zeichen A ^ B (A und B).

1

Page 2: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 1. AUSSAGENLOGIK 2

Beispiel 2. Wir definieren die drei Aussagen

A :, Die Zahl 15 ist durch 5 teilbar,B :, Die Zahl 15 ist durch 3 teilbar,C :, Die Zahl 15 ist durch 4 teilbar.

Die Doppelpunkte mit dem Äquivalenzzeichen , zeigen an, dass eine Aussage definiert wird. Welcheder Aussagen A ^ B, A ^ C und B ^ C sind wahr?

Wir definieren eine neue Aussage A _ B (A oder B), welche genau dann wahr ist, falls mindestenseine der beiden Aussagen A und B wahr ist. Das „ausschließende oder“, in Zeichen ˙_, verknüpft zweiAussagen so, dass die resultierende Aussage genau dann wahr ist, wenn genau eine der Aussagenwahr ist. Diese Verknüpfung entspricht dem „entweder . . . oder“.

Beispiel 3. Wir betrachten die Aussagen A, B und C wie in Beispiel 2. Welche der Aussagen A_B,A _ C und A ˙_B sind wahr?

Die Aussage A , B ist genau dann wahr, wenn A und B den gleichen Wahrheitsgehalt haben, alsobeide falsch oder beide wahr sind. Wir sagen dann, dass die Aussagen A und B äquivalent sind.In vielen mathematischen Sätzen ist die Äquivalenz zweier Aussagen durch die Formulierung „ge-nau dann, wenn“ gekennzeichnet. Etwas ausführlicher: „Aussage A gilt genau dann, wenn AussageB gilt“. Natürlich können auch andere Formulierungen benutz werden, welche die Äquivalenz zweierAussagen exakt zum Ausdruck bringen: „nur dann, wenn“ usw.

Die Verneinung ¬A ist genau dann wahr, wenn A falsch ist. Offenbar gilt ¬(¬A) , A.

Eine sehr wichtige Verknüpfung ist die Implikation A ) B, die genau dann falsch ist, wenn A zwarwahr, aber B falsch ist. Diese Verknüpfung schauen wir uns im nächsten Abschnitt etwas genauer an.

Der Wahrheitsgehalt der verknüpften Aussagen lässt sich in Abhängigkeit der Wahrheitsgehalte vonA und B sehr gut in einer Wahrheitstafel ablesen:

A B A ^ B A _ B A ˙_B A , B A ) B ¬Aw w w w f w w fw f f w w f f ff w f w w f w wf f f f f w w w

1.2 Die Implikation

Sehr wichtig für die Mathematik ist die Implikation A ) B. Viele Sätze der Mathematik sindfolgendermaßen aufgebaut:

Satz Vor.: ABeh.: B

oder Satz Gelte A.Dann folgt B.

Page 3: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 1. AUSSAGENLOGIK 3

In solchen Sätzen werden wichtige Ergebnisse formuliert. Die logische Struktur entspricht dann einerImplikation

A ) B

„wenn A, so B“„aus A folgt B“„A impliziert B“„B ist notwendige Bedingung für A“„A ist hinreichende Bedingung für B“

Per Definition ist die Implikation A ) B nur dann falsch, wenn A wahr und B falsch ist. Insbesondereist die Implikation schon dann wahr, wenn die Aussage A falsch ist.

A B A ) Bw w ww f ff w wf f w

Beispiel 4. Um den definierten Wahrheitswert der Implikation bei falschem A besser zu motivieren,betrachten wir das folgende sehr konstruierte Beispiel. Wir definieren

A :, Alle natürlichen Zahlen n � 2 sind durch 2, und 1 ist nicht durch 4 teilbar.

B :, Für alle natürlichen Zahlen n � 2 gilt: n2 ist durch 4 teilbar.

Aussage A ist eine ^-Verknüpfung der falschen Aussage „Alle natürlichen Zahlen n � 2 sind durch 2teilbar“ und der wahren Aussage „1 ist nicht durch 4 teilbar“. Somit ist die Aussage A falsch.Wir zeigen zunächst A ) B. Wir nehmen also an, A gilt. Um B zu zeigen, wählen wir ein beliebigesaber im Folgenden festes n 2 N mit n � 2. Dann gilt

n2

4

=

n

2

· n

2

.

Nach A sind beide Faktoren natürliche Zahlen, also auch n2/4. Somit ist n2 durch 4 teilbar. Da n � 2

beliebig war, gilt B.

Als nächstes zeigen wir A ) ¬B. Hier steht ¬ für „nicht“. Wir nehmen also wieder an, dass A gilt.Sei n � 2 ein festes n, z. B. n = 4. Dann gilt:

(n + 1)

2

4

=

n2

+ 2n + 1

4

=

n

2

· n

2

+

n

2

+

1

4

.

Das Produkt und auch der zweite Summand sind natürliche Zahlen. Da aber 1/4 nach Voraussetzungkeine natürliche Zahl ist, gilt dies auch für (n + 1)

2/4. Behauptung B gilt nicht!

Wichtige Folgerung: „Aus etwas Falschem kann man alles schließen!“

Daher ist es sinnvoll den Wahrheitswert der Implikation A ) B bei falscher Aussage A als „wahr“festzulegen. Wir werden daher im Folgenden immer A als wahr annehmen, um die Gültigkeit derImplikation A ) B zu prüfen.

Der Beweis einer Implikation A ) B wird in der Regel durch einen Kettenschluss

A ) A1

) A2

) · · · ) B

Page 4: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 1. AUSSAGENLOGIK 4

geführt. Dabei ist die Aussage A ) B ) C definiert durch (A ) B) ^ (B ) C). Der Kettenschlussselbst ist durch mehrfache Verknüpfung von Implikationen mit der ^-Verknüpfung definiert. Jedeeinzelne Implikation/Schluss in der Kette muss also wahr sein, damit der Kettenschluss insgesamtwahr ist. Die einzelnen Schlüsse sind dabei im folgenden Sinne einsichtig: Sie sind bereits früherbewiesen worden oder folgen unmittelbar aus Axiomen. Um dieses Vorgehen auch mathematischrechtfertigen zu können, beweisen wir die Transitivität der Implikation (die Transitivität kennenSie bereits aus der Schule z. B. für das „“-Zeichen: a b und b c impliziert a c). Genauerbeweisen wir, dass die Aussage

D :,⇣

(A ) B) ^ (B ) C)

� ) (A ) C)

für jede Wahrheitsbelegung von A, B und C wahr ist, also eine sogenannte Tautologie ist.

A B C A ) B B ) C A ) C Dw w w w w w ww w f w f f ww f w f w w ww f f f w f wf w w w w w wf w f w f w wf f w w w w wf f f w w w w

Aussage D lässt sich sprachlich ausführlicher formulieren: Wenn aus Aussage A die Aussage B folgtund aus Aussage B wiederum Aussage C, so folgt aus A auch Aussage C.

Manchmal ist es einfacher statt A ) B die mathematisch äquivalente Aussage ¬B ) ¬A zu zeigen,die sogenannte Kontraposition.

Satz 1. Seien A und B beliebige Aussagen. Dann gelten die folgenden drei Äquivalenzen

(i) (A ) B) , (¬A _ B),

(ii) (A ) B) , (¬B ) ¬A),

(iii) (A , B) , �

(A ) B) ^ (B ) A)

.

Der Beweis der drei Aussagen des Satzes lässt sich anhand von Wahrheitstafeln (und nicht durchden oben beschrieben Kettenschluss) leicht nachvollziehen und ist dem Leser überlassen.

Bemerkung 1. Die Äquivalenzen im Satz (ii) begründet das wichtige Beweisprinzip der Kontrapo-sition: Statt A ) B zeigt man vielleicht leichter die mathematisch äquivalente Aussage ¬B ) ¬A.Wenn jedoch möglich sollte man die direkte Implikation der Kontraposition vorziehen. Die Aussage(iii) des Satzes besagt: Will man die Äquivalenz zweier Aussagen zeigen, so kann man äquivalentzeigen, dass aus der einen Aussage die andere folgt und dies auch umgekehrt der Fall ist.

Im Folgenden wollen wir die logische Struktur von Sätzen und den zugehörigen Beweisen an zweiBeispielen üben.

Page 5: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 1. AUSSAGENLOGIK 5

Satz 2. Sei n eine natürliche Zahl. Dann ist n genau dann gerade, wenn es n2 ist.

Wir nehmen uns die Zeit, den Beweis sehr ausführlich zu führen. Die Voraussetzung des Satzes istn 2 N. Wir gehen von der Gültigkeit dieser Aussage aus, da ja aus einer falschen Aussage allesgefolgert werden kann. Mit anderen Worten: Ein Satz mit falschen Voraussetzungen ist immer wahr.In Zukunft werden wir also immer von der Gültigkeit der Voraussetzungen eines Satzes ausgehen.Die Behauptung des Satzes ist

n gerade , n2 gerade.

Nach Satz 1 können wir diese Äquivalenz in zwei Implikationen zerlegen.

„)“: Wir zeigen (n gerade ) n2 gerade). Dies ist eine Implikation der Struktur A ) B. Um dieGültigkeit einer solchen Implikation nachzuweisen, nehmen wir A als wahr an und zeigen, dassdann auch B gilt.Sei n gerade. Dann existiert eine natürliche Zahl k mit n = 2k. Damit folgt n2

= 4k2

= 2 · 2k2.Somit ist n2 durch 2 teilbar, also gerade.

„(“: Wir wollen als nächstes (n2 gerade ) n gerade) zeigen, verwenden aber die dazu äquivalenteAussage (n ungerade ) n2 ungerade), die Kontraposition (vgl. Satz 1).Sei nun n ungerade. Dann existiert eine natürliche Zahl k mit n = 2k � 1. Damit folgt für dasQuadrat n2

= 4k2 �4k +1 = 2(2k2 �2k)+1. Somit ist n2 nicht durch 2 teilbar, also ungerade.

Ein Beweis, wie Sie ihn in einem Buch finden könnten, der nicht mehr die Strukturen genau aufdeckt,könnte folgendermaßen lauten:

Beweis. Sei n 2 N. Ist n gerade, also n = 2k für ein k 2 N, so ist n2

= 4k2 offensichtlich durch 2teilbar. Ist andererseits n ungerade, also n = 2k � 1 für ein k 2 N, so ist n2

= 4k2 � 4k + 1 nichtdurch 2 teilbar.

Satz 3. Die Wurzelp

2 ist irrational, d. h. es gibt keine natürlichen Zahlen n, m mitp

2 =

nm .

Zunächst scheint der Satz keine Voraussetzungen zu haben, also nicht der Struktur A ) B zuentsprechen. Sie werden aber im Beweis unten sehen, dass wir einerseits Rechenregeln aus der Schulebenutzen und andererseits die Gültigkeit von Satz 2 (zu recht, da schon bewiesen) voraussetzen.Somit könnte man A :, „Es gelten die Rechenregeln rationaler Zahlen und Satz 2“ setzen.

Beweis. Wir führen den Beweis des Satzes durch einen Widerspruchsbeweis. Dabei wird angenom-men, dass die Behauptung falsch ist und daraus ein Widerspruch hergeleitet. Als Folgerung erhältman, dass die Behauptung wahr sein muss.Sei

p2 nicht irrational, also rational. Dann existieren teilerfremde natürliche Zahlen n und m mitp

2 =

nm . Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden.

Durch Quadrieren folgt 2m2

= n2. Somit ist mit n2 nach Satz 2 auch n gerade. Es existiert daherein k 2 N mit n = 2k. Einsetzen in 2m2

= n2 liefert nach Division mit 2 die Gleichung m2

= 2k2.Daher ist mit m2 auch m nach Satz 2 gerade. Insgesamt sind also m und n gerade, was einen Wi-derspruch zur Teilerfremdheit darstellt. Damit ist die Annahme der Rationalität von

p2 falsch;

p2

ist irrational.

Page 6: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 1. AUSSAGENLOGIK 6

Es gelten die Regeln von de Morgan:

¬(A ^ B) , (¬A _ ¬B),

¬(A _ B) , (¬A ^ ¬B).

Mit Satz 1 und den Regeln von de Morgan lassen sich auch die Verneinungen der Implikation undder Äquivalenz konkretisieren:

¬(A ) B) , (A ^ ¬B),

¬(A , B) , (¬A , B).

1.3 Aussageformen, Quantoren und Logikgesetze

Definition 2 (Aussageform). Aussageformen gleichen Aussagen, die von Variablen abhängen.Sie haben selbst keinen Wahrheitswert; erst durch Einsetzen der Variablen lässt sich der Wahr-heitswert bestimmen. Durch die oben kennengelernten Verknüpfungen von Aussagen (¬, ^, _, ), ,) lassen sich auch Aussageformen zu neuen Aussageformen verknüpfen.

Beispiele 5.

(a) A(x) :, 5x = 10

Offenbar ist A(3) falsch und A(2) wahr.

(b) A(x, y) :, x2

+ y2 1

Hier ist A(2, 1) falsch und A(

1

2

, 0) wahr.

(c) Mit A(x) aus (a) und B(x) :, x > 0 lassen sich neue Aussageformen bilden: A(x) ^ B(x),A(x) _ B(x), A(x) ) B(x), B(x) ) A(x), A(x) , B(x) und ¬A(x).

Viele Aussagen der Mathematik beginnen mit „Für alle ... “ oder „Es gibt ein ...“. AbkürzendeSchreibweisen, welche oft benutzt werden, sind die sogenannten Quantoren:

Definition 3 (Quantoren). Mithilfe von Quantoren 8, 9 und 9! werden aus AussageformenAussagen gebildet:

(i) 8x 2 M : A(x)

Für alle x 2 M ist A(x) wahr.

(ii) 9x 2 M : A(x)

Es existiert (mindestens) ein x 2 M, für das A(x) wahr ist.

(iii) 9!x 2 M : A(x)

Es existiert genau ein x 2 M, für das A(x) wahr ist.

Bemerkung 2. Quantoren sind hilfreich, um die Struktur eine mathematischen Aussage besserzu erfassen. Dennoch wird in mathematischen Texten, wie Bücher und Artikel, möglichst auf dieVerwendung der Quantoren verzichtet.

Page 7: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 1. AUSSAGENLOGIK 7

Beispiele 6.

(a) Wir betrachten die Aussageform A(n) :, (n gerade , n2 gerade ) und die damit gebildeteAussage (vgl. Satz 2)

8n 2 N : A(n).

(b) Wie betrachten die Aussageform A(x, y) aus Beispiel 5 und die Aussage

8x 2 [0, 1] 9y 2 [0, 1] : A(x, y),

die durch Verwendung von zwei Quantoren gebildet wird.

Offensichtlich gilt (A^B) , (B^A) und (A^B) , (B^A), d. h. die Verknüpfungen „und“ und „oder“sind kommutativ. Zudem lässt sich die Äquivalenz (A ^ B) ^ C , A ^ (B ^ C) (Assoziativgesetzt)leicht mit einer Wahrheitstafel nachweisen und damit

A ^ B ^ C :, (A ^ B) ^ C

definieren. Rekursiv lassen sich so endlich viele Aussagen mit ^ verknüpfen. Analog geht man beider Verknüpfung _ vor. Etwas Vorsicht ist bei der Verwendung von ^ und _ in einem Ausdruckgeboten. Es gelten die folgenden zwei Distributivgesetze:

A ^ (B _ C) , (A ^ B) _ (A ^ C),

A _ (B ^ C) , (A _ B) ^ (A _ C).

Page 8: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

Kapitel 2

Mengen

Mengen spielen in der Mathematik eine entscheidende Rolle. Um mit Mengen umgehen zu können,müssen wir zunächst klären, was wir unter einer Menge genau verstehen wollen:

Definition 4. (Menge, Georg Cantor(1845-1918))Eine Menge ist eine Zusammenfassung von bestimmten, wohlunterschiedenen Objekten unsererAnschauung oder unseres Denkens zu einem Ganzen. Die Objekte heißen Elemente der Menge.Zu jedem Objekt x und jeder Menge M lässt sich eindeutig entscheiden, ob x in der Menge Mliegt, x 2 M, oder nicht, x /2 M :, ¬(x 2 M).

Die Definition ist sehr abstrakt. So können wir nicht nur Mengen von Zahlen zulassen, sondern Men-gen mit weitaus allgemeineren Elementen. Wir werden Mengen von Vektoren, von Matrizen undsogar Mengen von Funktionen kennenlernen.

Mengen lassen sich durch explizite Aufzählung definieren, z. B.

M :

= {Berlin, Hamburg, München, Köln},

wobei die Reihenfolge keine Rolle spielt, aber auch durch Angabe einer verbindenden Eigenschaft,einer Aussageform, die auf alle Elemente zutrifft:

N :

= {x : x ist eine deutsche Stadt mit mehr als einer Million Einwohner}.

Der Doppelpunkt vor dem Gleichheitszeichen signalisiert, dass etwas definiert wird. Hier folgt jedochnicht das Äquivalenzzeichen wie im vorherigen Kapitel, sondern das Gleichheitszeichen. Insgesamtheißt „:=“ definierende Gleichheit. Merke: Aussagen können äquivalent, Mengen gleich sein. Hiergilt M = N .

Beispiele 7.

(a) Die Menge der natürlichen Zahlen mit der Null: N0

:

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

(b) Die Menge der natürliche Zahlen: N :

= {n 2 N0

: n > 0} = {1, 2, 3, . . .}.

Eine ausgezeichnete Menge ist die sogenannte leere Menge ;. Sie ist die einzige Menge ohne Ele-ment, d. h. ; = {}. Es scheint zunächst nicht unbedingt sinnvoll, eine leere Menge zu definieren. Sie

8

Page 9: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 2. MENGEN 9

entspricht der 0 in der Menge der natürlichen Zahlen, welche auch erst spät in der westlichen Weltals eigene Zahl akzeptiert wurde.Teilmengen einer Menge M lassen sich folgendermaßen bilden:

N := {x 2 M : x hat eine gewisse Eigenschaft}.

Im obigen Beispiel der Städte könnte die geforderte Eigenschaft zum Beispiel lauten: „Ist Hauptstadtvon Deutschland“ oder „Hat sogar mehr als 1.5 Millionen Einwohner“. Im ersten Fall wäre N =

{Berlin} im zweiten N = {Berlin, Hamburg}. Im Allgemeinen nennt man N eine Teilmenge von M,wenn jedes Element von N auch in M liegt. Wir schreiben dann N ✓ M (N ist Teilmenge von M).Mit den Mitteln des vorangegangenen Kapitels lautet die formale Definiton

N ✓ M :, 8x : (x 2 N ) x 2 M) .

Dies bedeutet: Für jedes Element von N ist es notwendig ein Element von M zu sein. Gibt es einElement in M, welches nicht in N ✓ M zu finden ist, so bezeichnen wir N als echte Teilmengevon M. Die formale Definition:

N ⇢ M :, (N ✓ M ^ N 6= M) .

Vorsicht: In der Literatur wird auch durch ⇢ eine Teilmenge und durch ( eine echte Teilmengegekennzeichnet.

Offenbar sind zwei Mengen genau dann gleich, wenn die eine Teilmenge der anderen ist und diesumgekehrt ebenfalls gilt:

M = N , M ✓ N ^ N ✓ M.

Dies ist gleichbedeutend zu8x : (x 2 M , x 2 N ).

Für eine endliche Menge M, also für eine Menge mit nur endlich vielen Elementen, wird mit #Moder auch |M| die Anzahl der Elemente bezeichnet.

Aus zwei Mengen M und N lassen sich auf verschiedene Weise neue Mengen bilden. Wir definierendie Vereinigung der beiden Mengen

M [ N :

= {x : x 2 M _ x 2 N},

den Schnitt der beiden Mengen

M \ N :

= {x : x 2 M ^ x 2 N}und die Differenz

M\N :

= {x : x 2 M ^ x /2 N}.

Offenbar gelten für die Vereinigung und den Schnitt die Kommutativ- und Assoziativgesetze:

M [ N = N [ M, (M [ N ) [ O = M [ (N [ O),

M \ N = N \ M, (M \ N ) \ O = M \ (N \ O).

Zwei Mengen M und N heißen disjunkt, falls M \ N = ;.

Page 10: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 2. MENGEN 10

Beispiel 8. Für die Mengen

M :

= {x 2 R : x > 4}, N :

= {x 2 R : x 5}

sind die Mengen M [ N , M \ N , M\N und N\M gegeben durch:

M [ N = {x 2 R : x > 4 _ x 5} = ]4, 1[ [ ] � 1, 5] = ] � 1, 1[ = RM \ N = {x 2 R : x > 4 ^ x 5} = ]4, 1[ \ ] � 1, 5] = ]4, 5]

M\N = {x 2 R : x > 4 ^ ¬(x 5)} = {x 2 R : x > 4 ^ x > 5} = {x 2 R : x > 5} = ]5, 1[

N\M = {x 2 R : ¬(x > 4) ^ x 5} = {x 2 R : x 4 ^ x 5} = {x 2 R : x 4} = ] � 1, 4]

An den neugebildeten Mengen wird sehr schön deutlich, welche Rolle Aussagen, und somit auch dieVerknüpfung von Aussagen, bei der Definition und Beschreibung von Mengen spielen. Entsprechendden Regeln der Aussagenlogik finden wir die Regeln von de Morgan und die Distributivgesetze derMengenlehre

M\(N [ O) = (M\N ) \ (M\O),

M\(N \ O) = (M\N ) [ (M\O),

M \ (N [ O) = (M \ N ) [ (M \ O),

M [ (N \ O) = (M [ N ) \ (M [ O)

für drei Mengen M, N und O. Wir zeigen beispielhaft die erste Regel von de Morgan:Wir prüfen zuerst M\(N [ O) ✓ (M\N ) \ (M\O). Dazu wählen wir ein beliebiges Elementx 2 M\(N [ O) und zeigen, dass es dann auch in (M\N ) \ (M\O) liegt. Offenbar liegt x inM, aber weder in N noch in O (sonst wäre es in der Vereinigung und würde von M „abgezogen“werden). Also liegt x sowohl in M\N als auch in M\O und somit im Schnitt dieser beiden Men-gen. Um nun auch (M\N ) \ (M\O) ✓ M\(N [ O) zu zeigen, wählen wir ein x aus dem Schnitt(M\N ) \ (M\O). Es liegt somit in beiden Mengen M\N und M\O. Insbesondere liegt x in M,aber weder in N noch in O, also auch nicht in der Vereinigung N [O. Folglich gilt x 2 M\(N [O).

Eine weitere Menge, das sogenannte kartesische Produkt, wird aus zwei Mengen M, N gebildet,indem wir die Menge aller geordneten Paare bilden:

M ⇥ N :

= {(x, y) : x 2 M ^ y 2 N}.

Man beachte, dass zum Beispiel (y, x) mit y 2 N und x 2 M im Allgemeinen nicht in M ⇥ N liegt,also M ⇥ N 6= N ⇥ M. Es ist auch möglich, das kartesische Produkt einer Menge mit sich selbst zubilden. Dies tritt insbesondere bei Verknüpfungen auf einer Menge auf, z. B. bei der Addition reellerZahlen: + : R ⇥ R ! R, (x, y) 7! x + y. Wir schreiben auch R2

:

= R ⇥ R.

Die Potenzmenge einer Menge M ist definiert als die Menge aller Teilmengen:

P(M)

:

= {N : N ✓ M}.

Abschließend führen wir abkürzende Schreibweisen für die Vereinigung, Schnitt und Produkt von

Page 11: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 2. MENGEN 11

insgesamt N Mengen ein:

N[

n=1

Mn :

= M1

[ M2

[ · · · [ MN = {x : 9n 2 {1, . . . , N} : x 2 Mn},

N\

n=1

Mn :

= M1

\ M2

\ · · · \ MN = {x : 8n 2 {1, . . . , N} : x 2 Mn},

NY

n=1

Mn :

= M1

⇥ M2

⇥ · · · ⇥ MN = {(x1

, . . . , xN ) : 8n 2 {1, . . . , N} : xn 2 Mn}

Da es nicht auf die Reihenfolge ankommt, in welcher man vereinigt bzw. den Schnitt bildet, sinddie jeweiligen rechten Seiten, also zum einen die Vereinigung und zum anderen der Schnitt mehrererMengen, wohldefiniert. Diese Eigenschaft der Assoziativität wird aus der Assoziativität der „oder“-bzw. „und“-Verknüpfung von Aussagen abgeleitet (siehe Kapitel 1 über die Aussagenlogik). Definierenwir die Indexmenge I :

= {1, . . . , N}, so lässt sich äquivalent schreiben

[

n2IMn :

=

N[

n=1

Mn,\

n2IMn :

=

N\

n=1

Mn.

Tatsächlich ist auch die Vereinigung bzw. der Schnitt von unendlich vielen Mengen definiert. In die-sem Fall hat die Indexmenge I unendlich viele Elemente.

Beispiel 9.[

k2Z]k, k + 1[ = R\Z,

\

k2Z]k, k + 1[ = ;,

[

n2N[0, 1

n ] = [0, 1],\

n2N[0, 1

n ] = {0},

1[

n=1

{x 2 R : xn 2 N} = {x 2 Q | x � 0},

1\

n=1

{x 2 R : xn 2 N} = N.

Erklärungen für die beiden unteren Mengengleichheiten:Sei p

q eine positive rationale Zahl, also p, q 2 N. Dann gilt mit n = q offenbar pqn = p 2 N. Ist

andererseits x in der Vereinigung, so existiert ein n 2 N mit x 2 {y 2 R : yn 2 N}, d. h. xn = p 2 N.Offenbar ist dann x =

pn eine nicht negative rationale Zahl.

Für n = 1 erhalten wir {x 2 R : x 2 N} = N. Wir zeigen nun für n > 1, dass N ✓ {x 2 R : xn 2 N}.Sei dazu p 2 N. Dann gilt für n > 1 auch pn 2 N, also p 2 {x 2 R : xn 2 N}.

Beispiele 10.

(a) Euklidische Ebene R2

= R ⇥ R =

⇢✓

xy

: x, y 2 R�

.

(b) Euklidischer Raum R3

= R ⇥ R ⇥ R =

8

<

:

0

@

xyz

1

A

: x, y, z 2 R

9

=

;

.

Page 12: Aussagenlogik - KIT...2=n m. Die Teilerfremdheit kann nach entsprechendem Kürzen des Bruches garantiert werden. Durch Quadrieren folgt 2m2 = n2.Somitistmitn2 nach Satz 2 auch n gerade

KAPITEL 2. MENGEN 12

• RN:= R ⇥ RN�1

= R ⇥ R ⇥ · · · ⇥ R =

8

>

<

>

:

x =

0

B

@

x1

...xN

1

C

A

: xn 2 R für alle n = 1, . . . , N

9

>

=

>

;

.

(c) Kreis vom Radius 1 in der euklidischen Ebene

B1

=

⇢✓

xy

2 R2

: x2

+ y2 1

(d) M =

⇢✓

xy

2 R2

: 5 x2

+ 1 17

.

Es gilt

5 x2

+ 1 17 , 4 x2 16

, 2 |x| 4

, �4 x �2 _ 2 x 4

(e) Seien a, b 2 R mit a < b.

– abgeschlossenes Intervall [a, b] := {x 2 R : a x b}.– offenes Intervall ]a, b[ := {x 2 R : a < x < b}. Oft auch (a, b).– halboffene Intervalle [a, b[ := {x 2 R : a x < b} und ]a, b] := {x 2 R : a < x b}. Oft

auch [a, b) bzw. (a, b].