Logik und Algebra - Homepage von Andreas Zeh-Marschkezeh-marschke.de/LogikUndAlgebra.pdf · Skript Logik und Algebra Mathematische Grundlagen Andreas Zeh-Marschke Version 8.1

Skript

Logik und Algebra

Mathematische Grundlagen

Andreas Zeh-Marschke

Version 8.1

Dipl.-Mathematiker Andreas Zeh-Marschke M.Sc. Praktische InformatikTauberring 16 b, 76344 Eggenstein-LeopoldshafenE-Mail Andreas(at)Zeh-Marschke.deHomepage http://www.Zeh-Marschke.de

ImpressumCopyright: c2001 - 2017(Version: 8.1 - 18.02.2017)Layout und Satz: Andreas Zeh-Marschke

Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen und so wei-ter in diesemWerk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,dass solche Namen im Sinne der Warenzeichen- und Markenschutz- Gesetzgebung als freizu betrachten wren und daher von jedermann benutzt werden drfen.

2 Version 8.1 18.02.2017

Inhaltsverzeichnis

Vorwort 9

1 Aussagen 11

1.1 Aussagen und Aussageformen . . . . . . . . . . . . . . . . . . . . . . . . . 121.2 Verknpfung von Aussagen . . . . . . . . . . . . . . . . . . . . . . . . . . 151.3 Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.4 Prdikatenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291.5 Beweisverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321.7 Lsungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2 Mengen 41

2.1 Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.2 Teilmengen und Potenzmenge . . . . . . . . . . . . . . . . . . . . . . . . . 452.3 Operationen von Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . 492.4 Klasseneinteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552.5 Kartesisches Produkt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602.7 Lsungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3 Relationen 69

3.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693.2 Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.3 quivalenzrelationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773.4 Ordnungsrelationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803.5 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863.6 Lsungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4 Abbildungen 95

4.1 Denition von Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . 954.2 Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.3 Mengen von Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . . 1074.4 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1084.5 Lsungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

Version 8.1 18.02.2017 3

Inhaltsverzeichnis

5 Strukturen 113

5.1 Verknpfungen und Operationen . . . . . . . . . . . . . . . . . . . . . . . 1135.2 Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185.3 Ringe und Krper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1195.4 Moduln und Vektorrume . . . . . . . . . . . . . . . . . . . . . . . . . . . 1215.5 Verbnde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1215.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1225.7 Lsungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

6 Boolesche Algebren 123

6.1 Boolesche Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1236.2 Normalformen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1266.3 Konstruktion der Normalformen . . . . . . . . . . . . . . . . . . . . . . . . 1286.4 KV-Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1376.5 Schaltnetze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1416.6 Aufgaben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1456.7 Lsungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

Namensliste 149

Abkrzungen 151

Literatur 153

Index 155

4 Version 8.1 18.02.2017

Abbildungsverzeichnis

2.1 Teilmenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.2 Transitive Teilmengen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472.3 Durchschnitt von Mengen . . . . . . . . . . . . . . . . . . . . . . . . . . . 502.4 Mengendiagramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512.5 Klasseneinteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.1 Darstellung Relation als Grak . . . . . . . . . . . . . . . . . . . . . . . . 703.2 Beispiel: Ortsverbindungen . . . . . . . . . . . . . . . . . . . . . . . . . . 713.3 Beispiel: Ordnungsrelation . . . . . . . . . . . . . . . . . . . . . . . . . . . 823.4 Beispiel: maximale und minimale Elemente . . . . . . . . . . . . . . . . . 823.5 Ordnungsrelation Teiler von 36 . . . . . . . . . . . . . . . . . . . . . . . . 86

4.1 Abbildung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964.2 Bild . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 984.3 Urbild . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.1 disjunkte Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1276.2 KV-Diagramm n = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.3 KV-Diagramm n = 2 a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.4 KV-Diagramm n = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1396.5 KV-Diagramm n = 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1396.6 KV-Diagramm n = 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1396.7 KV-Diagramm n = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1406.8 KV-Diagramm n = 4, Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . 1416.9 NOT-Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1416.10 AND-Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1426.11 OR-Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1426.12 NOR-Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1426.13 NAND-Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1436.14 XOR-Gatter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1436.15 Halbaddierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1446.16 Halbaddierer (Symbol) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1446.17 Volladdierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1446.18 Volladdierer (Symbol) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

Version 8.1 18.02.2017 5

Tabellenverzeichnis

1.1 Beispiel Wahrheitstafel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.2 Wahrheitstafel Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.3 Wahrheitstafel Konjunktion . . . . . . . . . . . . . . . . . . . . . . . . . . 171.4 Wahrheitstafel Disjunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.5 Wahrheitstafel Implikation . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.6 Wahrheitstafel quivalenz . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.7 Beispiel Auswertung Wahrheitstafel . . . . . . . . . . . . . . . . . . . . . . 201.8 Liste 1-stellige Verknpfungen . . . . . . . . . . . . . . . . . . . . . . . . . 201.9 Liste 2-stellige Verknpfungen, Teil 1 . . . . . . . . . . . . . . . . . . . . . 211.10 Liste 2-stellige Verknpfungen, Teil 2 . . . . . . . . . . . . . . . . . . . . . 211.11 Beweis A = AA = AA . . . . . . . . . . . . . . . . . . . . . . . . . . 231.12 Beweis Satz vom ausgeschlossenen Dritten . . . . . . . . . . . . . . . . . . 241.13 Beweis Regel von de Morgan . . . . . . . . . . . . . . . . . . . . . . . . . 261.14 Beweis Satz zum modus tollens . . . . . . . . . . . . . . . . . . . . . . . . 28

3.1 Darstellung Relation in Tabellenform . . . . . . . . . . . . . . . . . . . . . 70

4.1 Abbildungsvorschrift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

6.1 Boolesche Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1286.2 Beispiel 3-stellige boolesche Funktion . . . . . . . . . . . . . . . . . . . . . 1296.3 Beispiel: Min-Terme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1296.4 Quine-McCluskey Boolesche Funktion . . . . . . . . . . . . . . . . . . . . 1316.5 Quine-McCluskey Stufe 0, disjunktive Normalform . . . . . . . . . . . . . 1326.6 Quine-McCluskey Stufe 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1326.7 Quine-McCluskey Stufe 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1326.8 Beispiel Max-Terme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1336.9 Beispiel mit vier Aussagen . . . . . . . . . . . . . . . . . . . . . . . . . . . 1346.10 Beispiel mit vier Aussagen, Klassen, Stufe 0 . . . . . . . . . . . . . . . . . 1346.11 Beispiel mit vier Aussagen, Klassen, Stufe 1 . . . . . . . . . . . . . . . . . 1346.12 Beispiel mit vier Aussagen, Tabelle Min-Terme und Primimplikanten . . . 1366.13 Boolesche Funktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.14 Schalttabelle Halbaddierer . . . . . . . . . . . . . . . . . . . . . . . . . . . 1436.15 Schalttabelle Volladdierer . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

Version 8.1 18.02.2017 7

Vorwort

Vorwort zur Version 8.1

Dieses Skript entstand aus Vorlesungen, die ich an der Dualen Hochschule Baden-Wrttemberg - Karlsruhe (ehemalige Berufsakademie Karlsruhe), erstmals im Frhjahr2001 im Studiengang Wirtschaftsinformatik im Fachbereich Wirtschaft, gehalten habe.Im zweiten Semester wird das Thema Logik und Algebra im Umfang von etwa 30Stunden inklusive bungen behandelt. Daher knnen in der Vorlesung und damit auchin diesem Skript die Themen Logik und Algebra nur angerissen werden. Fr die weiteReise ins Innere der Mathematik und fr die Frage des Einsatzes mathematischer Theoriein die Praxis der Anwendung kann dies nur ein erster Startpunkt sein.

Was soll im Rahmen einer solchen Vorlesung gelehrt werden? Was ist wichtig? Dies istkeine leichte Frage, denn die Mathematik und auch das Thema Logik und Algebra istreichhaltig und bietet viele interessante Aspekte. Fr die Auswahl kann man sich danndie Frage stellen, was ist fr einen Wirtschaftsinformatiker wichtig? Wichtig ist zu denkenund zwar systematisch, logisch, abstrakt und strukturiert! Ich werde versuchen neben derTheorie auch praktische Beispiele zu bringen, um damit (hoentlich) das Verstndnis zufrdern.

Des weiteren mchte ich Peter Hartmann beipichten, der im Vorwort zu seinem BuchMathematik fr Informatiker (Hartmann 2002) geschrieben hat: Genauso wie Sieeine Programmiersprache nicht durch das Lesen der Syntax lernen knnen, ist es unmg-lich Mathematik zu verstehen ohne mit Papier und Bleistift zu arbeiten. Das heit, dassman sich intensiv mit der Mathematik beschftigen muss, um sie zu verstehen und dassman viel ben muss. Das ist mit Arbeit verbunden, aber ohne dies geht es nicht.

Anforderungen wandeln sich schnell und werden sich wohl auch immer schneller wandeln.Daher muss man sich schnell in neue Themen einarbeiten. Dafr ist eine stabile und so-lide Basis ntig. Dazu ist es notwendig, dass man denkt, um das vorhandene Wissenrichtig einzusetzen. Daher werde ich in diesem Skript Logik und Algebra auf Bewei-se nicht ganz verzichten, denn Beweise sind eine Mglichkeit, um das Denken zu ben.Das Denken darf sich jedoch nicht allein auf die Mathematik konzentrieren. Wichtig istein bergreifendes Denken. Wobei dies ein langer Entwicklungsprozess sein wird, der imRahmen nur einer Vorlesung nicht erreicht werden kann. Dieses Skript stellt eine Einfh-rung dar, um eine Basis fr die Arbeit zu schaen. Ich hoe, dass mir dies einigermaen

Version 8.1 18.02.2017 9

Tabellenverzeichnis

gelungen ist, obwohl ich wei, dass es schwierig ist, das mathematische Verstndnis zuvermitteln.

In den bungsaufgaben versuche ich neben den theoretischen Aspekten auch immerwieder praktische Anwendungen mit einzubringen. In der praktischen Anwendung bestehtmeistens die Schwierigkeit, aus den Problemen den mathematischen Kern zu erarbeiten,um eine klare mathematische Aufgabe zu erhalten.

Im Literaturverzeichnis sind einige grundlegende und weiterfhrende Bcher aufgefhrt.Bcher, welche das Thema Logik und Algebra behandeln, oder Teilaspekte dieses Skriptsbeleuchten. Diese Literatur kann daher als Vertiefung aufgefasst werden, die jedoch in derRegel weit mehr beinhalten als dieses Skript. Manchmal haben die Bcher auch andereHerangehensweisen an die Thematik, was sehr spannend sein kann, denn es gibt vieleWege, sich die Mathematik zu erschlieen.

Am nchsten zu den Inhalten der Vorlesung passt das Buch von Staab 2007. Die Inhaltewerden auch gut von Hartmann 2002, Lehmann und Schulz 2004, Meinel und Mundhenk2002, Schichl und Steinbauer 2009 und Struckmann und Wtjen 2007 dargestellt. Dieanderen Referenzen in der Literaturliste beziehen sich auf Bcher, die teilweise deutlichber den Sto der Vorlesung gehen: Beutelspacher und Zschiegner 2002, Henze 2005,Knauer 2001, Lau 2004b, Lau 2004a, Schmidt 2000, Steger und Schickinger 2002, G.Teschl und S. Teschl 2006 und Witt 2001. Die Bcher Arens 2008 und Eichholz undVilkner 2002 sind eher Nachschlagewerke.

Die erste Version des Skripts entstand 2001. Im Laufe der Jahre wurden Anpassungenund Ergnzungen, sowohl auf fachlicher, als auch auf technischer Art umgesetzt. Vondaher wird das Skript stndig Vernderungen unterzogen. Das Skript wurde mit TEX,genauer mit LATEX erstellt.

Ein Skript ist niemals fertig. Durch neue Erkenntnisse gibt es immer wieder neue in-teressante Sachverhalte, die eingearbeitet werden knnen. Vernderungen in den Schwer-punkten bedingen ebenso Vernderungen. Daher werde ich von Zeit zu Zeit immer wiedereinzelne Kapitel anpassen.

Ich habe versucht Fehler herauszunehmen, ohne neue Fehler zu machen - nicht immerganz einfach. Wenn Fehler entdeckt werden, so bitte ich, dass mir diese Fehler gemeldetwerden, damit ich diese Fehler in einer neuen Version korrigieren kann. Auch Anregungenund weitere Anmerkungen sind gerne willkommen.

Andreas Zeh-MarschkeEggenstein-Leopoldshafen, 18.02.2017

10 Version 8.1 18.02.2017

Kapitel 1

Aussagen

1.0.1 . In diesem Kapitel werden grundlegende Begrie der mathematischen Logik ein-gefhrt. Es werden dabei einige Themen behandelt, die fr das mathematische Denken,die mathematische Sprechweise und das Beweisen bentigt werden. Es kann und solldamit im Rahmen dieser Einfhrung die mathematische Logik nur insoweit eingefhrtwerden, wie dies fr das weitere Verstndnis bentigt wird. Als Ziel kann hier die Ein-fhrung in das logische Denken und die Durchfhrung von logischen Schlussfolgerungengenannt werden. Logische Schlussfolgerungen, die gelernt und spter auch angewendetwerden. Ein weiteres Ziel ist es, mathematische Formulierungen kennen zu lernen, ma-thematische Formulierungen, die nicht nur in der Mathematik, sondern auch in anderenBereichen (zum Beispiel Wirtschaftswissenschaften, Ingenieurwesen, Informatik . . . ) ein-gesetzt werden. Die Einfhrung in diesem Kapitel ist damit nur sehr knapp und gehtsomit nicht bis zu den philosophischen Fragen der Logik. Das wrde den Rahmen ganzund gar sprengen.

Die klare Formulierung von Aussagen ist in allen Bereichen notwendig, nicht nur inder Mathematik. Beispielsweise ist die Spezikation einer Software ohne klare Aussa-gen, Aussagen, die vollstndig und widerspruchsfrei sind, nicht denkbar. Auch andereWissenschaften erfordern klare Aussagen und Folgerungen aus Aussagen.

Auch in Programmiersprachen sind logische Konzepte implementiert. Um diese Konzeptezu verstehen, ist die Kenntnis von Aussagen eine unabdingbare Basis.

Zuerst werden Aussagen und Aussageformen (Abschnitt 1.1) und Verknpfungenvon Aussagen (Abschnitt 1.2) betrachtet, um das Grundgerst zu erhalten. Danachwerden Stze der Aussagenlogik (Abschnitt 1.3) untersucht und bewiesen. Im anschlie-enden Abschnitt 1.4 wird die Prdikatenlogik angerissen, die den Sprachumfang er-weitert. Der abschlieende Abschnitt 1.5 beschftigt sich mit Beweisverfahren, die imweiteren Verlauf angewendet werden.

Version 8.1 18.02.2017 11

1.1 Aussagen und Aussageformen


1.1.1 Beispiel. Bevor der Begri Aussage przisiert wird, einige Beispiele von Aussa-gen. Zur przisen mndlichen oder schriftlichen Formulierung von Sachverhalten ist dieMathematik, aber nicht allein die Mathematik, dazu bergegangen, Aussagen zu treen,die teilweise in natrlicher Sprache und teilweise in einer knstlichen und formalisiertenSprache wiedergegeben werden. Daher einige Beispiele von Aussagen, wobei erst danachder Begri Aussage prziser gefasst wird.

1. 2 + 3 = 5.Dies ist eine wahre Aussage.

2. 4 ist eine Primzahl.Dies ist eine falsche Aussage. Das bedeutet, dass Aussagen nicht immer wahr sind,sie knnen auch falsch sein!

3. Es gibt unendlich viele Primzahlen.Dies ist eine wahre Aussage, die bereits vom griechischen Mathematiker Euklid (um300 v.Chr.) vor etwa 2.300 Jahren bewiesen wurde.

4. Die Gleichung xn + yn = zn hat, auer der trivialen Lsung, keine ganz-zahligen Lsungen fr n grer als 2Dies ist eine Aussage, die von franzsischen Mathematiker Pierre de Fermat (1601- 1665)1 etwa 1637 aufgestellt wurde. Die Aussage ist als groer Fermat'scher Satzoder Fermats letzter Satz bekannt. Sie wurde erst 1993 / 1995 vom britischen Ma-thematiker Andrew Wiles (*1953) bewiesen2.

5. Jede gerade Zahl, die grer als 2 ist, ist Summe zweier Primzahlen.Die Aussage ist die Goldbach'sche Vermutung, benannt nach dem deutschen Ma-thematiker Christian Goldbach (1690 - 1764).

(Beispiele: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5 = 3 + 7) Dies ist eineAussage, von der noch nicht bekannt ist, ob sie wahr oder falsch ist.

6. Es ist Vollmond.Dies ist eine Aussage, die manchmal wahr ist, manchmal jedoch falsch. Der Wahr-heitsgehalt hngt von der Zeit ab. Hier erreicht man dann die temporale Logik,welche zeitliche Zusammenhnge einbezieht.

7. Brasilia ist die Hauptstadt von Brasilien.Dies ist eine wahre Aussage, nicht aus der Mathematik. Der Wahrheitswert einersolchen Aussage kann sich im Laufe der Zeit verndern. Die Aussage Rio de Janeiro

1Eine Kurzbiographie ber Pierre de Fermat: Klaus Barner; Das Leben Fermats; in Mitteilungen derDeutschen Mathematiker-Vereinigung, Heft 3/2001

2Eine interessante und lesenswerte Beschreibung der Geschichte des Satzes von Fermat, von den Grund-lagen bis zu seiner Lsung, mit vielen historischen Anmerkungen steht in Simon Singh; Fermats letzterSatz; dtv, 2000

12 Version 8.1 18.02.2017

Kapitel 1 Aussagen

ist die Hauptstadt von Brasilien war bis 1960 eine wahre Aussage, seit 1960 nichtmehr, denn dann wurde Brasilia die Hauptstadt von Brasilien.

8. Guten Morgen!Dies ist keine Aussage, sondern ein Ausruf.

9. Dieser Satz ist falsch.Diesen Satz wird spter, wenn der Begri Aussage prziser deniert ist noch ge-nauer betrachtet.

10. Diese Person ist gro.Auch diesen Satz wird nach der Denition des Begries Aussage noch genauerbetrachtet.

1.1.2 Denition (Aussage). Auf der Basis dieser Beispiele wird nun der Begri Aus-sage genauer deniert.

Denition. Ein sprachliches Gebilde A heit Aussage, wenn man eindeutig entschei-den kann, ob es wahr oder falsch ist.

Einer Aussage kann somit eindeutig der Wahrheitswert wahr oder falsch zuge-ordnet werden. Ist A eine Aussage, dann sei w(A) der zugehrige Wahrheitswert derAussage.

Dies ist keine klare Denition, da auf Begrie zurckgegrien wird, die selber nicht exaktdeniert sind.

Statt der Begri wahr und falsch werden oftmals auch andere Begrie oder Kurzzei-chen verwendet. Es werden oftmals statt wahr auch der englische Begri true oderdie Krzel W , w, T , t oder 1 verwendet. Fr falsch wird auch der englische Begrifalse oder die Krzel F , f oder 0 verwendet.

Diese Denition von Aussagen basiert auf dem Prinzip der Zweiwertigkeit, das heit aufder Tatsache, dass eine Aussage entweder wahr oder falsch ist. Daher spricht man hier vonzweiwertiger Logik. Es gibt Kulturkreise, in denen das Prinzip der zweiwertigen Logiknicht gilt, in denen es neben wahr und falsch auch noch andere Wahrheitswerte gibt,zum Beispiel vielleicht oder unbestimmt oder sogar noch andere Abstufungen.3

1.1.3 Anmerkung (Diskussion Dieser Satz ist falsch.). Nun wird der Satz Die-ser Satz ist falsch. untersucht. Auf den ersten Blick ist es eine Aussage. Wenn es eineAussage ist, dann ist zu klren, welchen Wahrheitswert die Aussage hat, denn einer Aus-sage muss nach der Denition eindeutig ein Wahrheitswert zugeordnet werden knnen.

3siehe hierzu John D. Barrow; Ein Himmel voller Zahlen - Auf den Spuren mathematischer Wahrheit;rororo, 1999

Version 8.1 18.02.2017 13


Wenn es eine wahre Aussage ist, dann besagt der Satz, dass die Aussage des Satzes falschist, dass es also eine falsche Aussage ist. Also kann es keine wahre Aussage sein. Ist esdann eine falsche Aussage? Wenn die Aussage des Satzes falsch ist, dann besagt dies, dassdie Aussage des Satzes wahr ist!? Auch das fhrt zu einem Widerspruch. Es kann nichtentschieden werden, ob der Satz wahr oder falsch ist. Somit ist es keine Aussage (nachder Denition)! Es ist eine Paradoxie, die zu tiefer gehenden, philosophischen Problemender Logik fhrt, die hier nicht nher beleuchtet werden.

1.1.4 Anmerkung (Diskussion Diese Person ist gro.). Beim Satz Diese Per-son ist gro. ist es ebenfalls schwer zu bestimmen, ob dieser Satz wahr oder falsch ist.Die Gre bezieht sich hierbei auf die Krpergre. Fr Pygmen ist eine Person mit 1,70m Krperlnge eine groe Person, fr Basketballspieler ist dies jedoch nicht gro. Diesfhrt in die moderne Entwicklung der Fuzzy Logik, die bewusst mit Unschrfen arbeitet.Die Fuzzy Logik wird hier nicht weiterverfolgt. Die Fuzzy Logik wird beispielsweise inder regelungstechni fr die Steuerung in Technik aber auch in der Medizin eingesetzt.

1.1.5 Beispiel. Es gibt andere Formulierungen, fr die man direkt keinenWahrheitswertzuordnen kann. Die nachfolgenden Stze sind keine Aussage.

P (x) := x ist eine Primzahl.

T (x, y) := x ist ein Teiler von y.

S(x, y, z) := x ist die Summe von y und z

Wenn man jedoch fr die Platzhalter x, y oder z konkrete Werte aus einem Grundbereichvon Werten einsetzt, dann ergeben sich hieraus Aussagen, denen man einen Wahrheits-wert zuordnen kann.

1.1.6 Denition (Variable, Aussageform). Die Beispiele fhren zur nachfolgendenDenition.

Denition. Eine Variable ber einem Grundbereich ist ein Symbol, fr das spezielleObjekte eines Grundbereichs eingesetzt werden knnen. Eine mit Hilfe mindestens einerVariablen ausgedrckte Formulierung heit Aussageform oder Prdikat, wenn beimEinsetzen von bestimmten Objekten des Grundbereichs fr die Variable(n) eine Aussageentsteht.

Auch diese Denition agiert mit schwammigen Begrien.

1.1.7 Beispiel. Fr die Aussageformen in Beispiel 1.1.5 gelten:

w(P (3)) = w; w(P (4)) = f ; w(P (5)) = w

14 Version 8.1 18.02.2017

Kapitel 1 Aussagen

w(T (2, 3)) = f ; w(T (2, 4)) = w

w(S(5, 2, 3)) = w

Durch die Einsetzung von konkreten Werten aus dem Grundbereich in die Aussageformenwerden konkrete Aussagen gebildet, fr die jeweils ein Wahrheitswert bestimmbar ist.

1.1.8 Beispiel. In Java, aber auch in anderen Programmiersprachen, gibt es den pri-mitiven Datentyp boolean mit den beiden mglichen Werte true und false. Diesist eine Darstellung der Wahrheitswerte. Eine Aussage ist dann einfach eine BoolescheVariable. Bei der Programmierung gibt es viele Aussageformen. Jede Methode mit einemRckgabewert vom Typ boolean ist eine Aussageform

public boolean istPrimzahl ();

public boolean istTeilerVon (long zahl);

public boolean istSummeVon (double x, double y);

1.2 Verknpfung von Aussagen

1.2.1 . Im Nachfolgenden werden Verknpfungen von Aussagen betrachtet, das heitmit Verbindungen von mehreren Aussagen und wie ausgehend von Aussagen andereAussagen gebildet werden knnen. Diese Verknpfungen sind aus dem Alltag bekannt,allerdings vielleicht ein klein bisschen anders als die nachfolgenden Denitionen. Es sinddies die Verknpfungen nicht, und, oder, wenn, dann und genau dann, wenn. Inder Aussagenlogik werden diese Verknpfungen so festgelegt, dass sich der Wahrheitswertder Verknpfung eindeutig aus den Wahrheitswerten der Teilaussagen ergibt, unabhngigdavon, ob zwischen den Teilaussagen ein inhaltlicher Zusammenhang besteht oder jedochkein Zusammenhang besteht. Auch wenn die Verknpfungen teilweise aus dem Alltagsle-ben bekannt sind, so ist deren mathematische Denition und Deutung manchmal etwasanders als in der Umgangssprache.

1.2.2 Denition (Wahrheitstafel, Verknpfungstafel). Zur Darstellung der Aus-sagen wird eine Wahrheitstafel oder Verknpfungstafel verwendet. In der Tabellesind fr alle mglichen Belegungen der Variablen mit Wahrheitswerten der daraus resul-tierende Wahrheitswert der Verknpfung dargestellt. Die Wahrheitstafel in Tabelle 1.1zeigt als Beispiel die Wahrheitstafel fr die und-Verbindung.

Mit Hilfe von Wahrheitstafeln knnen nun die einzelnen Verknpfungen przise darge-stellt werden.

1.2.3 Denition (Negation). Zuerst wird die nicht-Verknpfung przisiert.

Version 8.1 18.02.2017 15


A B A Bw w ww f ff w ff f f

Tabelle 1.1: Beispiel Wahrheitstafel

Denition. Es sei A eine beliebige Aussage. Eine Aussage C heit Negation derAussage A, falls C genau dann wahr ist, wenn A falsch ist und falsch, wenn A wahrist.

Die Negation von A wird mit C = A oder mit C = not(A) oder mit C = A bezeichnet.Die Negation von A wird auch durch die Wahrheitstafel in Tabelle 1.2 dargestellt.

A Aw ff w

Tabelle 1.2: Wahrheitstafel Negation

Auch wenn hier nur eine Aussage verwendet wird, wird hier von einer Verknpfunggesprochen, einer 1-stelligen Verknpfung. Diese Verknpfung entspricht auch dem um-gangssprachlichen Umgang nicht.

1.2.4 Beispiel. Ist A die Aussage, dass eine Kugel ist rot ist, dann ist A die Aussage,dass die Kugel nicht rot ist.

1.2.5 Denition (Konjunktion). Jetzt kommt die und-Verknpfung.

Denition. Es seien A und B beliebige Aussagen. Eine Aussage C heit Konjunktionoder und-Verknpfung oder and-Verknpfung der Aussagen A und B, falls C genaudann wahr ist, wenn A wahr ist und B wahr ist. Die Konjunktion von A und B wirdmit C = A B oder mit C = A and B bezeichnet.

Die Konjunktion von A und B wird durch die Wahrheitstafel in Tabelle 1.3 dargestellt.Die Konjunktion entspricht dem umgangssprachlichen und.

16 Version 8.1 18.02.2017

Kapitel 1 Aussagen

A B A Bw w ww f ff w ff f f

Tabelle 1.3: Wahrheitstafel Konjunktion

Alle mglichen Kombinationen der Wahrheitswerte fr A und B sind mit dem Ergebnisder Verknpfung dargestellt.

1.2.6 Beispiel. Ist A die Aussage, dass eine Kugel rot ist und B die Aussage, dass aufeiner Kugel eine gerade Zahl ist, dann ist die Aussage C = AB die Aussage, dass eineKugel rot ist und eine gerade Nummer hat.

1.2.7 Beispiel. Ist A die wahre Aussage, 2 ist gerade und B die falsche Aussage 3 istgerade, so ist die Aussage A B (2 ist gerade und 3 ist gerade) eine falsche Aussage.

1.2.8 Denition (Disjunktion). Jetzt kommt die oder-Verknpfung.

Denition. Es seien A und B beliebige Aussagen. Eine Aussage C heit Disjunktionoder Adjunktion oder oder-Verknpfung oder or-Verknpfung der Aussagen A undB, falls C genau dann wahr ist, wenn A wahr ist oder B wahr ist (oder A wahr ist undB wahr ist). Die Disjunktion von A und B wird mit C = A B oder C = A or Bbezeichnet.

Die Verwendung von oder im mathematischen Sinne ist ein nicht ausschlieendes oder.In der Umgangssprache verwendet man das oder oftmals als exklusives oder, alsoals entweder . . . oder. Dies ist zu beachten. Hier wird mit der oder-Verknpfung stetsdas nicht-ausschlieende oder verwendet. Ein ausschlieendes oder wird spter nocheingefhrt.

Die Disjunktion von A und B wird durch die Wahrheitstafel in Tabelle 1.4 dargestellt.

1.2.9 Beispiel. Ist A die Aussage, dass eine Kugel rot ist und B die Aussage, dass aufeiner Kugel eine gerade Zahl ist, dann ist die Aussage C = A B die Aussage, dassdie Kugel rot ist oder eine gerade Nummer hat. Die Kugel kann auch rot sein und einegerade Nummer haben.

1.2.10 Beispiel. Ist A die wahre Aussage, 2 ist gerade und B die falsche Aussage 3ist gerade, so ist die Aussage AB (2 ist gerade oder 3 ist gerade) eine wahre Aussage.

Version 8.1 18.02.2017 17


A B A Bw w ww f wf w wf f f

Tabelle 1.4: Wahrheitstafel Disjunktion

1.2.11 Denition (Implikation). Bei der wenn-dann-Verknpfung wird der Ver-gleich zum umgangssprachlichen noch etwas schwieriger.

Denition. Es seien A und B beliebige Aussagen. Eine Aussage C heit Implikationoder Subjunktion oder Folgerung von A nach B, falls C genau dann wahr ist, wennA und B wahr sind oder aber A falsch ist. Die Implikation von A nach B wird mitC = A B bezeichnet.

Die Implikation von A und B wird durch die Wahrheitstafel in der Tabelle 1.5 dargestellt.

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

Tabelle 1.5: Wahrheitstafel Implikation

Mit dieser Denition haben viele Personen, die vom normalen Sprachgebrauch ausgehenSchwierigkeiten, denn in der vorletzten Zeile steht, dass man von etwas Falschem etwasRichtiges folgern kann. Das ist auf den ersten Blick merkwrdig, aber es wurde obenbereits erwhnt, dass die mathematische Denition manchmal etwas anderes ist. Eineinfachen Beispiel ist in Beispiel 1.2.13 zu nden.

1.2.12 Beispiel. Es sei A die wahre Aussage 2 ist gerade und B die wahre Aussage4 ist gerade. Die Aussage A B ist ebenfalls wahr.

1.2.13 Beispiel. Es sei A die falsche Aussage 1 = -1 und B die wahre Aussage 12 =(1)2. Auch die Aussage A B ist wahr.

Aus etwas Falschem kann alles gefolgert werden!

18 Version 8.1 18.02.2017

Kapitel 1 Aussagen

1.2.14 Denition (quivalenz). Nun wird die genau dann - wenn-Verknpfung vor-gestellt.

Denition. Eine Aussage C heit quivalenz oder Bijunktion von A und B, fallsC genau dann wahr ist, wenn A wahr ist und B wahr ist oder aber A falsch ist und Bfalsch ist. Die quivalenz von A und B wird mit C = A B bezeichnet.

Die quivalenz von A und B wird durch die Wahrheitstafel in Tabelle 1.6 dargestellt.

A B A Bw w ww f ff w ff f w

Tabelle 1.6: Wahrheitstafel quivalenz

1.2.15 Beispiel. Es sei A die Aussage, dass der Schalter (im Stromkreis) geschlossenist und B die Aussage, dass der Strom im Stromkreis iet. Dann sind die Aussagen Aund B quivalent.

1.2.16 Anmerkung. Damit sind die fnf wichtigsten Verknpfungen (Negation, Kon-junktion, Disjunktion, Implikation und quivalenz) eingefhrt. Sie werden auch Junk-toren genannt.

Bei der Darstellung von Ausdrcken kann es zu Problemen kommen, wenn man keineKlammern setzt oder wenn man keine Vereinbarung ber die Reihenfolge der Verknp-fungen festlegt. Beispiel: A B C.

Es wird daher vereinbart: Die Junktoren , , , und binden jeweils strker als dieNachfolger in dieser Liste. Daher kann man den Ausdruck ABC auch als (AB)Cschreiben, whrend A (B C) etwas anderes darstellt.

Im Zweifelsfall sollten eher etwas mehr Klammern geschrieben werden als zu wenige, ummgliche Fehlerquellen oder genauer Interpretationsfehler zu vermeiden.

1.2.17 Beispiel. Mit Hilfe einer Wahrheitstafel knnen auch zusammengesetzte Aus-sagen schrittweise gelst werden. Dazu wird die zusammengesetzte Aussage (A B) (A C) betrachtet. Wie sieht der Wahrheitswert der Aussage in Abhngigkeitvon den Wahrheitswerten der elementaren Aussagen A, B und C aus. (siehe Tabelle 1.7)

Version 8.1 18.02.2017 19


A B C (A B) (A C)w w w w w w w w w ww w f w w w w w f fw f w w f f w w w ww f f w f f f w f ff w w f w w w f f wf w f f w w w f f ff f w f w f w f f wf f f f w f w f f f

0. 1. 0. 2. 0. 1. 0.

Tabelle 1.7: Beispiel Auswertung Wahrheitstafel

1.2.18 Anmerkung. Die zusammengesetzte Aussage wurde schrittweise gelst. In deruntersten Zeile steht, in welcher Reihenfolge die Teilaussagen gelst wurden. Dabei steht0. fr die einfache bertragung der Basiswerte. Gleiche Zahlenwerte in der letzten Zeilebedeuten, dass die Ergebnisse auf dieser Ebene in beliebiger Reihenfolge gebildet werdenknnen.

Die Erstellung von Wahrheitstafeln fr Aussagen kann auch mit Hilfe eines Tabellenkal-kulationsprogramms erstellt werden. Diese Programme bieten logische Funktionen undAusdrcke. Auch moderne Programmiersprachen bieten Konstrukte fr die Bearbeitungvon logischen Ausdrcken.

1.2.19 Denition (1-stellige Verknpfungen). Es sei A eine Aussage, dann gibt esvier 1-stelligen Verknpfungen. Das heit, es gibt vier Mglichkeiten, wie die Wahrheits-werte in Abhngigkeit des Wahrheitswertes von A verteilt sein knnen. In der Tabelle1.8 werden die mglichen 1-stelligen Verknpfungen dargestellt:

V1 V2 V3 V4A true id(A) A falsew w w f ff w f w f

Tabelle 1.8: Liste 1-stellige Verknpfungen

In dieser Wahrheitstafel sind in der ersten beiden Zeilen die Aussagen oder einstelligenVerknpfungen aufgefhrt, in den beiden nachfolgenden Zeilen die mglichen Verteilun-gen der Wahrheitswerte von Vi(A), fr i = 1, 2, 3, 4 bei gegebenem Wahrheitswert derAussage A. In der zweiten Zeile stehen die kurzen Bezeichnungen der Verknpfung. DieBezeichnungen dieser Verknpfungen sind in der Literatur allerdings nicht einheitlich.

Die Verknpfungen true(A) und false(A) sind unabhngig vom Wahrheitswert von A

20 Version 8.1 18.02.2017

Kapitel 1 Aussagen

stets wahr beziehungsweise falsch. Die Verknpfung id(A) ist die Identitt von A, sodass als einzige nicht-triviale 1-stellige Verknpfung die Negation A, not(A) oder Ableibt.

1.2.20 Anmerkung. Nun werden die 2-stelligen Verknpfungen untersucht. Einige die-ser Verknpfungen haben besondere Namen und sind (insbesondere in der Informatik)bedeutend. Vier Verknpfungen wurden oben bereits deniert: Konjunktion, Disjunktion,Implikation und quivalenz. Jetzt werden alle Mglichkeiten untersucht.

1.2.21 Denition (2-stellige Verknpfungen). Zweistellige Verknpfungen gibt esinsgesamt 16, die in den Tabellen 1.9 und 1.10 vollstndig aufgefhrt sind. In der Ta-belle stehen die Wahrheitswerte von Vi(A,B) fr i = 1, 2, . . . , 16 in Abhngigkeit derWahrheitswerte von A und B.

V1 V2 V3 V4 V5 V6 V7 V8A B true id(A) id(B) w w w w w w w w w ww f w w w w f f f ff w w w f f w w f ff f w f w f w f w f

Tabelle 1.9: Liste 2-stellige Verknpfungen, Teil 1

V9 V10 V11 V12 V13 V14 V15 V16A B B A falsew w f f f f f f f fw f w w w w f f f ff w w w f f w w f ff f w f w f w f w f

Tabelle 1.10: Liste 2-stellige Verknpfungen, Teil 2

Aus der Wahrheitstafel kann man erkennen, dass die Verknpfungen aus dem zweiten Teilaus der Negation der Verknpfungen aus dem ersten Teil entstehen. Es gilt Vi(A,B) =(V17i(A,B)) fr i = 1, . . . , 16.

1.2.22 Bemerkung. Die Verknpfung V3 setzt sich zusammen aus A B oder aberB A, die Verknpfungen V1, V4 und V6 sind trivial, so dass sich alle 2-stelligen Ver-knpfungen auf die fnf Verknpfungen , , , und zurckfhren lassen. Darausergibt sich die

Version 8.1 18.02.2017 21


Bemerkung. Die 2-stelligen Verknpfungen lassen sich alle allein mit Hilfe der Junk-toren darstellen.

1.2.23 Bemerkung. Darber hinaus lassen sich die Verknpfungen und alleinmit Hilfe der Verknpfungen , und darstellen lassen:

Bemerkung. Es seien A und B beliebige Aussagen dann gelten

(A B) (A B) (B A) (1.1)(A B) A B . (1.2)

1.2.24 Bemerkung. Damit ergibt sich sogar die

Bemerkung. Die 2-stelligen Verknpfungen lassen sich alle allein mit Hilfe der Ver-knpfungen , und darstellen.

Dies ist auch der Grund, wieso in einigen Programmiersprachen, zum Beispiel in Java,und in Tabellenkalkulationsprogrammen oftmals nur die logischen Operatoren , und realisiert sind.

1.2.25 Denition (nand, nor, xor). Einige Verknpfungen aus der obigen Tabellehaben einen besonderen Namen, die in der Tabelle auch bereits eingetragen sind.

= (nicht und; nicht zugleich; nand),

= (nicht oder; weder noch; nor)

= exclusive or (exklusives oder; entweder oder; xor)

1.2.26 Bemerkung. Die Verknpfungen haben ihre besondere Bedeutung in der Schal-talgebra, die auf der nachfolgenden Bemerkung beruht.

Bemerkung. Die 2-stelligen Verknpfungen lassen sich alle allein mit den Verknp-fung beziehungsweise darstellen.

22 Version 8.1 18.02.2017

Kapitel 1 Aussagen

Beweis: Es gelten die nachfolgenden quivalenzen, die leicht nachgerechnet werden kn-nen.

A (AA) (AA) (1.3)

A B (AB)(AB) (AA)(B B) (1.4)

A B (AA)(B B) (AB)(AB) (1.5)

A B A(AB) (B (AB))(B (AB)) (1.6)

Diese quivalenzen knnen beispielsweise mittels Wahrheitstafeln bewiesen werden. Dieswird anhand der erste quivalenz ausgefhrt, siehe Tabelle 1.11.

A A AA AAw f f ff w w w

Tabelle 1.11: Beweis A = AA = AA

Es kann aber auch ohne Wahrheitstafeln bewiesen werden, durch quivalente Umformun-gen.

(AB)(AB) (AB) ((A B)) A B

Die Ausfhrung des Beweises der restlichen quivalenzen kann als einfache bung durch-gefhrt werden.

1.3 Aussagenlogik

1.3.1 Denition (Tautologie, Kontradiktion). Der Wahrheitswert einer zusam-mengesetzten Aussage lsst sich eindeutig aus den Wahrheitswerten der Teilaussagenermitteln. Wenn A eine beliebige Aussage ist, dann ist die Verknpfung A A stetswahr, whrend die Verknpfung AA stets falsch ist, unabhngig vom Wahrheitswertvon A. Dies fhrt zur nachfolgenden Denition.

Version 8.1 18.02.2017 23

1.3 Aussagenlogik

Denition. Eine Aussage heit eine Tautologie, wenn sie stets eine wahre Aussageist. Eine Aussage heit eine Kontradiktion, wenn sie stets eine falsche Aussage ist.

Allgemein gltige Aussage (Tautologien) heien auch Stze der Aussagenlogik. Sie bildendie Basis fr die mathematische Logik und das Beweisen. Im nachfolgenden werden einigeTautologien aufgestellt und beweisen.

1.3.2 Satz (vom ausgeschlossenen Dritten). Es kann nur eine Aussage A oder dieNegation von A gelten, nichts anderes.

Satz. Es sei A eine Aussage, dann gilt der Satz vom ausgeschlossenen Dritten.Es ist

A A (1.7)

eine Tautologie.

Beweis:

A A Aw w w ff f w w

0. 2. 1.

Tabelle 1.12: Beweis Satz vom ausgeschlossenen Dritten

Der Beweis kann mit Hilfe einer Wahrheitstafel (siehe Tabelle 1.12) erbracht werden.

1.3.3 Satz (vom Widerspruch). Es kann nicht gleichzeitig eine Aussage A und dieNegation davon wahr sein.

Satz (Satz vom Widerspruch). Es sei A eine Aussage, dann gilt der Satz vomWiderspruch. Es ist

(A A) (1.8)

eine Tautologie.

24 Version 8.1 18.02.2017

Kapitel 1 Aussagen

Die Aussage (A A) ist eine Kontradiktion. Dies bedeutet, dass eine Aussage nichtgleichzeitig wahr und falsch sein kann.

1.3.4 Satz (Assoziativ-, Kommutativ- und Distributivgesetz). Aus dem Rech-nen mit Zahlen sind die Assoziativ-, Kommutativ- und Distributivgesetze bekannt. Ent-sprechende Regeln git es auch fr Aussagen.

Satz. Es seien A, B und C Aussagen. Es gelten das Assoziativgesetz

(A B) C A (B C) (1.9)(A B) C A (B C) (1.10)

, das Kommutativgesetz

A B B A (1.11)A B B A (1.12)

und das Distributivgesetz

A (B C) (A B) (A C) (1.13)A (B C) (A B) (A C). (1.14)

Das Assoziativgesetz ermglicht es, einfach A B C beziehungsweise A B C zuschreiben, ohne dass man Klammern setzen muss. Dies erleichtert oftmals die Schreib-arbeit. Das Assoziativgesetz gilt auch fr mehr als drei Aussagen. Diese drei Gesetzeerinnern stark an die entsprechenden Gesetze bei der Arithmetik mit + und , dochbeim Distributivgesetz ist zu sehen, dass es Unterschiede gibt.

1.3.5 Satz (von der doppelte Verneinung). Die Negation der Negation ist wiederdie ursprngliche Aussage.

Satz. Es sei A eine Aussage, dann gilt der Satz von der doppelten Verneinung.Es ist

((A)) A (1.15)

eine Tautologie.

Die doppelte Verneinung einer Aussage hebt sich also gegenseitig auf.

Version 8.1 18.02.2017 25

1.3 Aussagenlogik

1.3.6 Satz (Regeln von de Morgan). Wie verhalten sich die Negation mit der Kon-junktion und Disjunktion.

Satz. Es seien A und B Aussagen, dann gelten die Regeln von de Morgan

(a) (A B) A B (1.16)(b) (A B) A B (1.17)

Die Negation einer and-Verknpfung ist die or-Verknpfung der Negationen der Aussa-gen. Ebenso ist die Negation einer or-Verknpfung die and-Verknpfung der Negationen.Die Regeln von de Morgan sind nach dem britischen Mathematiker Augustus de Morgan(1806 - 1871) benannt.

Beweis: Es wird (A B) ((A) (B)) mit Hilfe einer Wahrheitstafel (siehe 1.13)bewiesen.

A B (A B) A Bw w f w w f f fw f w f w f w wf w w f w w w ff f w f w w w w

2. 1. 3. 1. 2. 1.

Tabelle 1.13: Beweis Regel von de Morgan

Durch ersetzen von A durch A und B durch B in der obigen quivalenz, ergibt sich,dabei hilft auch der Satz von der doppelten Verneinung,

(A B) ((A) (B)) A B . (1.18)

Negation auf beiden Seiten und nochmalige Anwendung des Satzes der doppelten Ver-neinung ergibt die zweite Regel von de Morgan.

(A B) (doppelte Verneinung)

((A) (B)) (Regel von de Morgan, a)

((A B)) (doppelte Verneinung)

A B

26 Version 8.1 18.02.2017

Kapitel 1 Aussagen

1.3.7 Anmerkung (Stze fr Beweisverfahren). Im nachfolgenden werde einigeStze der Aussagenlogik vorgestellt, die bei den Beweisverfahren immer wieder die Grund-lage bilden.

1.3.8 Satz (Kontrapositionssatz). Wenn aus einer Aussage A die Aussage B folgt,dann ist das quivalent zu der Folgerung von nicht B (also Aussage B gilt nicht) zu nichtA.

Satz. Es seien A und B beliebige Aussagen, dann gilt der Kontrapositionssatz

(A B) (B A) . (1.19)

Wenn die Folgerung aus A folgt B bewiesen werden soll, dann kann dafr auch dieFolgerung aus nicht B folgt nicht A bewiesen werden.

1.3.9 Satz (Abtrennungsregel). Es wir der Zusammenhang zwischen der FolgerungA B und der Aussage A betrachtet.

Satz. Es seien A und B beliebige Aussagen, dann gilt der Satz zum modus ponensoder die Abtrennungsregel

((A B) A) B . (1.20)

Wenn die Folgerung aus A folgt B wahr ist und die Aussage A wahr ist, dann ist auchdie Aussage B wahr.

1.3.10 Satz (Satz zum modus tollens). Es wir der Zusammenhang zwischen derFolgerung A B und der Aussage B betrachtet.

Satz. Es seien A und B beliebige Aussagen, dann gilt der Satz zum modus tollens

(A B) B A . (1.21)

Wenn die Folgerung aus A folgt B wahr ist und die Aussage B nicht wahr ist, dannist auch die Aussage A nicht wahr. Wre die Aussage A wahr, dann wre nach derAbtrennungsregel die Aussage B wahr.

Version 8.1 18.02.2017 27

1.3 Aussagenlogik

A B (A B) B Aw w w f f w fw f f f w w ff w w f f w wf f w w w w w

1. 2. 1. 3. 1.

Tabelle 1.14: Beweis Satz zum modus tollens

Beweis: Der Beweis ist als Wahrheitstabelle in der Tabelle 1.14 zu sehen.

Der Beweis kann jedoch auch ohne Wahrheitstafel, durch quivalente Umformungen er-folgen.

(A B) B (siehe Bemerkung 1.2.23)

(A B) B Distributivgesetz

(A B) (B B) (Satz 1.3.3 vom Widerspruch)

(A B) false (siehe Bemerkung 1.2.23)

A B

A

1.3.11 Satz (Kettenschlussregel). Was ist, wenn man mehrere Folgerungen hat.

Satz. Es seien A, B und C beliebige Aussagen, dann gilt der Satz zum modus bar-bara oder die Kettenschlussregel

[(A B) (B C)] (A C) . (1.22)

Wenn die Folgerung aus A folgt B wahr ist und auch die Folgerung aus B folgt Cwahr ist, dann ist auch die Folgerung aus A folgt C eine wahre Aussage.

28 Version 8.1 18.02.2017

Kapitel 1 Aussagen

1.4 Prdikatenlogik

1.4.1 Anmerkung. Fr die Formulierung mathematischer Theorien reicht die Aussa-genlogik noch nicht aus. In der Aussagenlogik werden Aussagen betrachtet. In der Pr-dikatenlogik werden Prdikate oder Aussageformen betrachtet.

Bei der weiteren Analyse von Aussagen stt man auf Subjekte, Prdikate und sogenann-te quantizierbare Redeteile wie fr alle und es gibt. Subjekte sind Namen fr Dingeaus einer bestimmten vorgegebenen Individualmenge, Prdikate sind Namen fr Relatio-nen4 auf dieser Individualmenge. 1-stellige Prdikate heien Eigenschaften. Weiter fhrtman die Quantoren (fr alle oder Generalisator) und (es gibt oder Partikulari-sator) ein. Darber hinaus gibt es noch das Gleichheitszeichen = und Vergleichsoptionen, um Identitten darstellen zu knnen. Fhrt man noch Funktionen5 (in nVariablen) ein, die jedoch genau genommen nur ((n+ 1)-stellige) Relationen sind. Damitsind Elemente der Prdikatenlogik der 1. Stufe mit Identitt eingefhrt. Damit knnenmathematische Aussagen formulieren werden. Dies und die Erweiterung in hhere Stufenwird hier nicht weiter ausgefhrt.

Damit hilft die Prdikatenlogik bei klaren Beschreibung mathematischer Aussagen. DiePrdikatenlogik wird an dieser Stelle nicht weiter detailliert. Sie wird immer wieder an-gewendet.

1.4.2 Beispiel. Gegeben sei die Aussage Es existiert (mindestens) eine Primzahl grer5 und kleiner 9.Sei P das 1-stellige Prdikat (Eigenschaft) ist Primzahl, dann lsst sich die Aussagekurz in mathematischer Schreibweise darstellen als

n N : P (n) (5 < n < 9) . (1.23)

1.4.3 Beispiel. Die Aussage Fr alle reelle Zahlen x grer 0 existiert (mindestens)eine natrliche Zahl n, so dass 1/n kleiner x ist lsst sich in mathematischer Formdarstellen als:

(x R+) : (n N) : 1/n < x . (1.24)

1.5 Beweisverfahren

1.5.1 . Unter einem Beweis versteht man die Ableitung einer Aussage aus anderen Aus-sagen nach bestimmten, logischen Schlussregeln. Es werden hier einige der Beweisverfah-ren an konkreten Beispielen betrachtet. Ziel eines Beweises ist es immer, aus einer Mengevon wahren Aussagen durch logische Schlussfolgerungen eine Behauptung zu besttigen.

4Relationen werden erst spter genauer betrachtet5Funktionen werden erst spter genauer betrachtet

Version 8.1 18.02.2017 29

1.5 Beweisverfahren

In den nachfolgenden Kapiteln wird es noch oft die Gelegenheit geben, die verschiedenenBeweisverfahren einzusetzen.

1.5.2 (Gegenbeispiel). Nicht jede Behauptung ist wahr. Die Anfhrung eines einzigenGegenbeispieles ist eine Mglichkeit, eine Behauptung zu widerlegen. Eine Mglichkeit,die man immer in Erwgung ziehen sollte. Fr die Widerlegung einer Aussage gengt eineinziges Gegenbeispiel. Fr einen Beweis einer Aussage reichen auch viele Beispiele nicht.

1.5.3 (Vollstndiges Durchrechnen). Ebenfalls eine einfache Mglichkeit ist dasvollstndige Durchrechnen aller Flle. Dies ist jedoch nur dann mglich, wenn esendlich viele Flle gibt. Es ist nur dann wirklich einfach, wenn die Anzahl der mglichenFlle klein ist. In den ersten Abschnitten wurden einige Beweise dadurch gefhrt. Mitdem Aufkommen der Computer sind derartige Beweise verstrkt aufgekommen. Ein be-rhmtes Beispiel ist der Beweis des Vierfarbenproblem6, das mit Hilfe der Reduzierungauf endliche viele Untersuchungsflle und dem anschlieenden Durchrechnen mittels einesComputerprogramms gelst wurde.

1.5.4 (Direkter Beweis). Beim direkten Beweis wird eine Aussage aus einer wah-ren Aussage durch direkte logische Schlussregeln hergeleitet. Als Basis dient hierbei derSatz zum modus ponens.

((A B) A) B (1.25)

1.5.5 Beispiel (direkter Beweis). Beispiel fr einen direkten Beweis:

Behauptung: Es sei n eine ungerade natrliche Zahl, dann ist auch n2 eine ungeradeZahl. Hierbei sei n ist ungerade die Aussage A und n2 ist ungerade die Aussage B.

Beweis: Da n eine ungerade natrliche Zahl ist, existiert eine Zahl k( N0), mit n =2k + 1. Damit gilt

n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 . (1.26)

Somit ist auch n2 eine ungerade Zahl.

Damit wurde die Aussage direkt bewiesen.

1.5.6 (Indirekter Beweis). Der indirekten Beweis basiert auf dem Kontrapositi-onssatz, der folgenden quivalenz:

(A B) (B A) (1.27)

Es wird somit von der Negation der Aussage B ausgegangen und daraus die Negationder Aussage A bewiesen. Auf Grund der quivalenz wird die Aussage damit indirektbewiesen.

6Wie viele Farben reichen aus, um eine beliebige Karte so einzufrben, dass je zwei aneinander gren-zende Lnder unterschiedliche Farben haben? Diese Problem wurde von Francis Guthrie (englischerMathematiker) 1852 formuliert. Erst 1977 gelangen Kenneth Appel und Wolfgang Haken mit Hilfeeines Computerprogrammes der Beweis.

30 Version 8.1 18.02.2017

Kapitel 1 Aussagen

1.5.7 Beispiel (indirekter Beweis). Beispiel fr einen indirekten Beweis:

Behauptung: Ist n2 eine gerade Zahl, dann ist auch n eine gerade Zahl.

Beweis: A sei die Aussage n2 ist gerade, B sei die Aussage n ist eine gerade Zahl.Die Negation zu B ist die Aussage n ist ungerade. Beim Beispiel 1.5.5 zum direktenBeweis wurde gezeigt, dass dann n2 eine ungerade Zahl ist, dies ist die Negation von A.Aus der Negation von B folgt die Negation von A, damit folgt aus A die Aussage B.

Damit wurde die Aussage indirekt bewiesen.

1.5.8 (Beweis durch Widerspruch). Der Beweis durch Widerspruch basiert aufdem Satz zum modus tollens.

(A B) B A (1.28)

Wenn aus der Aussage A die Aussage B folgt, jedoch die Negation von B wahr ist, dannkann die Aussage A nicht wahr sein, denn ansonsten wrde auch die Aussage B wahrsein, was ein Widerspruch darstellt. Somit ist die Negation von A wahr.

1.5.9 Beispiel (Beweis durch Widerspruch). Ein schon ber 2000 Jahrer alter Be-weis durch Widerspruch.

Behauptung:

2 ist irrational.Beweis: Wenn

2 rational ist, dann gibt es teilerfremde, natrliche Zahlen p und q, so

dass

2 = pq gilt. Damit ergibt sich 2q2 = p2. Damit ist p2 gerade und damit auch p

(siehe Beispiel 1.5.7 zum indirekten Beweis). Somit gibt es eine Zahl k, so dass p = 2kgilt. Eingesetzt in die Gleichung ergibt sich 2q2 = 4k2. Hier kann man durch 2 krzenund man erhlt q2 = 2k2. Damit ist q2 gerade und somit auch q. Dies widerspricht jedochder Annahme, dass p und q teilerfremd sind, also ist die Annahme, dass

2 rational ist

falsch!

Damit wurde die Aussage, dass

2 irrational ist, durch Widerspruch bewiesen.

1.5.10 (Vollstndige Induktion). Beim Beweis durch vollstndige Induktion be-weist man eine Aussage der Form n N : A(n), indem zuerst die Aussage fr n = 1bewiesen wird (Induktionsbeginn oder Induktionsverankerung). In der Induktionsannah-me wird angenommen, dass A(n) gilt. Im Induktionsschritt von n auf n + 1 wird dieAussage A(n + 1), basierend auf der Aussage A(n) (manchmal auch auf den AussagenA(n 1), . . .) bewiesen: (A(n) A(n + 1)). Durch wiederholte Anwendung des Satzesdes modus ponens gilt A(n) fr alle n N.

1.5.11 Beispiel (Vollstndige Induktion).

Behauptung:

n N :ni=1

i =n(n+ 1)

2(1.29)

Version 8.1 18.02.2017 31

1.6 Aufgaben

Beweis: Die Aussage A(n) ist fr n N

A(n) :

ni=1

i =n(n+ 1)

2(1.30)

Induktionsbeginn: Es gilt A(1), denn1

i=1 i = 1 =1(1+1)

2 .

Induktionsannahme: A(n) gilt.

Induktionsschritt von n auf n+ 1:

n+1i=1

i =

ni=1

i + (n+ 1) =n(n+ 1)

2+ (n+ 1) =

(n+ 1)(n+ 2)

2(1.31)

Beim ersten Gleichheitszeichen wurde der Term fr n + 1 so umgeformt, dass ein Termentsteht, fr den die Induktionsannahme verwendbar ist. Beim mittleren Gleichheitszei-chen wurde die Induktionsannahme verwendet.

1.6 Aufgaben

1.6.1 Aufgabe. Es seien A, B und C Aussagen. Erstellen Sie die Wahrheitstafeln frdie nachfolgenden logischen Aussagen

(a) (A B) (A C)(b) (A (B C)) (A B)(c) (A B) (B C)(d) (A B) (B C)

1.6.2 Aufgabe. Es seien A, B und C Aussagen. Bestimmen Sie die Wahrheitstafeln dernachfolgen Aussageformen

(a) (A B) C(b) A (B C)(c) (A B) C(d) A (B C)

1.6.3 Aufgabe. Erstellen Sie Wahrheitstafeln mit Hilfe eines Tabellenkalkulationspro-gramms ihrer Wahl.

1.6.4 Aufgabe. Erstellen Sie Wahrheitstafeln mit Hilfe eines Programms in einer belie-bigen Programmiersprache Ihrer Wahl.

1.6.5 Aufgabe. Zeigen Sie, dass die logischen Verknpfungen , , und alleindurch den logischen Operator darstellbar sind.

32 Version 8.1 18.02.2017

Kapitel 1 Aussagen

1.6.6 Aufgabe. Zeigen Sie, dass die logischen Verknpfungen , , und alleindurch den logischen Operator darstellbar sind.

1.6.7 Aufgabe. Es seien A und B zwei beliebige Aussagen. Zeigen Sie, dass

(A B) (B A)

eine Tautologie ist. (Kontrapositionssatz)

1.6.8 Aufgabe. Beweisen Sie den Satz zum modus ponens.

1.6.9 Aufgabe. Zeigen Sie, dass die nachfolgenden Aussagen Tautologien sind:(a) (A B) (A B)(b) (A B) ((A B) (A B))(c) (A B) (AB)(d) (AB) (A B)(e) (A B) (A B)

1.6.10 Aufgabe. Es seien A, B und C Aussagen. Zeigen Sie, dass folgende AussagenTautologien (Stze der Aussagenlogik) sind.

1. (splitten) [(A B) C] [(A C) (B C)]

2. (verschieben) [(A B) C)] [A B C]

3. (tauschen) [(A B) C)] [(A C) B]

4. (aggregieren) [(A B) (A C)] [A (B C)]

1.6.11 Aufgabe. Beweisen Sie durch vollstndige Induktion:

n N :ni=1

i2 =n(n+ 1)(2n+ 1)

6

1.7 Lsungen

1.7.1 Lsung. zu Aufgabe 1.6.1

Es werden die Wahrheitstabellen erstellt.

(a) (A B) (A C)

Version 8.1 18.02.2017 33

1.7 Lsungen

D = E =A B C A B D E A Cw w w f f fw w f f f fw f w w w fw f f w w ff w w f w wf w f f f ff f w f w wf f f f f f

1. 2. 1.

(b) (A (B C)) (A B)

E = D = F =A B C A D B C E F A Bw w w w w w ww w f w w w ww f w w w w ww f f f f f wf w w w w w wf w f w w w wf f w w w f ff f f w f f f

2. 1. 3. 1.

(c) (A B) (B C)

D = E =A B C A B D E B Cw w w w w ww w f w w ww f w f f ww f f f w ff w w f f wf w f f f wf f w f f wf f f f w f

1. 2. 1.

(d) (A B) (B C)

34 Version 8.1 18.02.2017

Kapitel 1 Aussagen

E = D = F =A B C D A B E F B Cw w w f w w ww w f f w f fw f w w f w fw f f w f w ff w w f w w wf w f f w f ff f w f w f ff f f f w f f

2. 1. 3. 1.


Es wird die Wahrheitstabelle erstellt.

A B C (A B) C A (B C) (A B) C A (B C)w w w w w w ww w f w w f ww f w w w w ww f f f f f wf w w w f w wf w f f f f ff f w w f f ff f f f f f f


bung


bung


Es werden quivalente Umformungen durchgefhrt.

A A (A A) A

(AB)(AB) ((A B) (A B)) (A B) (A B) Regel von de Morgan A B

Version 8.1 18.02.2017 35

1.7 Lsungen

(AA)(B B) ((A A) (B B)) (A B) A B Regel von de Morgan

Wegen (A B) = (A B) und den oben aufgefhrten Nachweisen, ist auch dieImplikation allein mit darstellbar.



AA (A A) A

(AA)(B B) ((A A) (B B)) (A B) (A B) Regel von de Morgan

(AB)(AB) ((AB)(AB)) ((A B) (A B)) Regel von de Morgan A B

Wegen (A B) = (A B) und den oben aufgefhrten Nachweisen, ist auch dieImplikation allein mit darstellbar.


Es werden Umformungen durchgefhrt.

A B

A B doppelte Verneinung

A (B) kommutativ

(B) A

B A

36 Version 8.1 18.02.2017

Kapitel 1 Aussagen



(A B) A (A B) A (A A) (B A)) false (B A) (B A) B


(a) Beweis mittels einer Wahrheitstafel.

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

(b) Beweis durch quivalente Umformungen.

A B

(A B) (B A) (a)

(A B) (B A) Distributivgesetz

[A (B A)][B (B A)]

Distributivgesetz[A B] [A A][B B] [A B]

Satz vom ausgeschlos-senen Dritten

[A B] [A B]

(c) Beweis durch Wahrheitstafel.

A B A B (AB)w w w w fw f f f wf w f f wf f w w f

1. 2. 1.

Version 8.1 18.02.2017 37

1.7 Lsungen

(d) Beweis durch Wahrheitstafel.

A B AB (A B)w w f f ww f f f wf w f f wf f w w f

1. 2. 1.

(e) Beweis durch Wahrheitstafel.

A B AB (A B)w w f f ww f w w ff w w w ff f w w f

1. 2. 1.


(splitten)[(A B) C] [(A C) (B C)]

(A B) C

(A B) C Regel von de Morgan

(A B) C Distributivgesetz

(A C) (B C)

(A C) (B C)

(verschieben)

38 Version 8.1 18.02.2017

Kapitel 1 Aussagen

[(A B) C)] [A (B C)]

(A B) C

(AB) C Regel von de Morgan

(A B) C Assoziativgesetz

A (B C)

A (B C)

(tauschen)[(A B) C)] [(A C) B]

(A B) C verschieben von B von links nach rechts

A (B C) verschieben von C von rechts nach links

(A C) B

(aggregieren)[(A B) (A C)] [A (B C)]

(A B) (A C)

(A B) (A C) Distributivgesetz

A (B C)

A (B C)


Induktionsbeginn: Fr n = 1 ist die Aussage wahr:

1i=1

i2 = 1 =1(1 + 1)(2 1 + 1)

6

Induktionsannahme: die Aussage gilt fr n

Version 8.1 18.02.2017 39

1.7 Lsungen

Induktionsschritt von n auf n+ 1:

n+1i=1

i2 =

ni=1

i2 + (n+ 1)2

=n(n+ 1)(2n+ 1)

6+ (n+ 1)2

=(n+ 1)(n+ 2)(2n+ 3)

6

Beim mittleren Gleichheitszeichen wurde die Induktionsannahme verwendet.

40 Version 8.1 18.02.2017

Kapitel 2

Mengen

2.0.1 . In diesem Kapitel werden die wichtigsten Grundbegrie und Notationen der Men-genlehre eingefhrt. Begrie und Symbolik der Mengenlehre und der formalen Logikzusammen gestatten eine przise Formulierung mathematischer Aussagen.

Zuerst werdenMengen eingefhrt (Abschnitt 2.1), bevor dannTeilmengen und diePo-tenzmenge deniert werden (Abschnitt 2.2). Im Abschnitt 2.3 werden Operationenvon Mengen betrachtet und die Mengenarithmetik untersucht. Im anschlieenden Ab-schnitt 2.4 werden Klasseneinteilungen das heit Zerlegungen von Mengen betrachtet,die eine Verbindung zu quivalenzrelationen haben, die erst im nchsten Kapitel be-trachtet werden, beschrieben. Ein wichtiges Beispiel von Mengen, die ebenfalls im nach-folgenden Kapitel eine weiter gehende Bedeutung haben, ist das kartesische Produkt,welches im abschlieenden Abschnitt 2.5 deniert wird.

2.1 Mengen

2.1.1 Denition (Menge). Die grundlegende Denition einer Menge geht zurck aufden deutschen Mathematiker Georg Cantor (1845 - 1918).

Denition. Eine Menge ist die Zusammenfassung bestimmter, wohlunterschiedenerObjekte unserer Anschauung oder unseres Denkens zu einem Ganzen. Die Objekte, diezu einer Menge zusammengefasst werden heien Elemente der Menge.Ist M eine Menge und x ein Objekt, so schreibt man x M , wenn x ein Element vonM ist und x /M , wenn x nicht Element von M ist.

Mengen knnen entweder durch die Aufzhlung ihrer Elemente oder die Angabe derEigenschaften der Elemente der Menge beschrieben werden. Die Elemente werden ingeschweifter Klammer geschrieben.

2.1.2 Beispiel. Einige Beispiele von Beschreibungen von Mengen:

Version 8.1 18.02.2017 41

2.1 Mengen

1. A sei die Menge aller Farben einer Verkehrsampel.A := {rot, gelb, grn}

2. B sei die Menge aller mglichen Farbzustnde einer Verkehrsampel.B := {rot, rot-gelb, grn, gelb, gelb-blinkend, aus}

3. C sei die Menge aller geraden Zahlen.

4. D sei die Menge aller Quadratzahlen kleiner als 100.D := {1, 4, 9, 16, 25, 36, 49, 64, 81}

5. E sei die Menge der Studentinnen und Studenten einer Vorlesung.

2.1.3 Beispiel. Die Beschreibung von Mengen kann auch mit Hilfe von Prdikaten er-folgen.

1. Es sei P3 das Prdikat ist gerade, also P3(x) die Aussageform x ist gerade.Weiter sei C := {x | P3(x)} die Menge, deren Elemente diejenigen Objekte sind,fr welche die Aussage P3(x) wahr ist.

2. Es seien P4 das Prdikat ist Quadratzahl und P4(x) die Aussageform x ist Qua-dratzahl. Weiter seien Q4 das Prdikat ist kleiner als 100 und Q4(x) die Aussa-geform x ist kleiner als 100. Die Menge der Quadratzahlen kleiner als 100 kanndurch D := {x | P4(x) Q4(x)} beschrieben werden.

2.1.4 Anmerkung. Die obige Denition der Menge kann zu Widersprchen fhren. DieBildung der Menge M aller Mengen X, die nicht Element von sich selbst sind, fhrtzu einem Widerspruch. Gehrt M selbst zu dieser Menge oder nicht? Dies ist unter demNamen Antinomie von Russell bekannt, benannt nach dem britischen Mathematiker undPhilosoph Bertrand Russell (1872 - 1970, Nobelpreis fr Literatur 1950). Diese Problema-tik wird hier nicht weiter verfolgt. Daher beschftigen wir uns nur mit der sogenanntennaiven Mengenlehre.

2.1.5 Beispiel (Wichtige grundlegende Mengen). Beispiele wichtiger Mengen ausder Mathematik:

1. Menge der natrlichen Zahlen1: N

N = {n | n ist naturlicheZahl} = {1, 2, 3, . . .} (2.1)

2. Menge der natrlichen Zahlen mit der 0: N0

N0 = {n | n ist naturliche Zahl oder (n = 0)} = {0, 1, 2, . . .} (2.2)

3. Menge der Primzahlen: P

P = {p | p ist Primzahl} = {2, 3, 5, 7, 11, . . .} (2.3)1Die 0 zhlt bei mir nicht zu den natrlichen Zahlen!

42 Version 8.1 18.02.2017

Kapitel 2 Mengen

4. Menge der ganzen Zahlen: Z

Z = {z | z ist ganze Zahl} = {0,1,2,3, . . .} (2.4)

5. Menge der rationalen Zahlen: Q

Q = {x | x ist rationale Zahl} = {x = pq| p Z und q Z\{0}} (2.5)

6. Menge der reellen Zahlen: R

R = {x | x ist reelle Zahl} (2.6)

2.1.6 Beispiel. Fr die nachfolgenden Beispiel sei stets die Grundmenge X einer derMengen Z, Q oder R.

1. Menge der positiven Zahlen: X+

X+ = {x | x X und (x > 0)} (2.7)

2. Menge der negativen Zahlen: X

X = {x | x X und (x < 0)} (2.8)

3. Menge der positiven Zahlen inklusive der 0: X+0

X+0 = {x | x X und (x 0)} (2.9)

4. Menge der negativen Zahlen inklusive der 0: X0

X0 = {x | x X und (x 0)} (2.10)

5. X> Menge der Zahlen, grer (x > )

X> = {x | x X mit (x > )} (2.11)

6. X Menge der Zahlen, grer oder gleich (x )

X = {x | x X mit (x )} (2.12)

7. X

2.1 Mengen

8. X Menge der Zahlen, kleiner oder gleich (x )

X = {x | x X mit (x )} (2.14)

2.1.7 Beispiel (Intervalle). Auch fr die nachfolgenden Beispiel sei stets die Grund-menge X einer der Mengen Z, Q oder R.

1. oenes Intervall

(, ) = {x X | < x < } (2.15)

2. halboene Intervalle

(, ] = {x X | < x } (2.16)[, ) = {x X | x < }

3. abgeschlossenes Intervall

[, ] = {x X | x } (2.17)

Statt ( beziehungsweise ) wird manchmal auch ] beziehungsweise [ geschrieben.Damit gelten dann (, ) =], [, (, ] =], ] und [, [.

2.1.8 Beispiel. Anbei einige weitere Mengen.

1. Menge der komplexen Zahlen: C

C = {x | x ist komplexe Zahl} (2.18)

2. Fr n N sei

Zn = {0, 1, 2, . . . , n 1} (2.19)

2.1.9 Denition (Mengengleichheit). Wichtig ist immer die Frage, wann zwei Men-gen gleich sind.

Denition. Zwei Mengen M und N heien gleich (M = N), wenn sie dieselbenElemente enthalten.

M = N : x : (x M) (x N) (2.20)

Die Reihenfolge, mit der die Elemente in einer Menge aufgefhrt werden ist nicht vonBedeutung. Genauso knnen Elemente mehrmals aufgefhrt werden, ohne dass sich dieMenge ndert. Daher sind folgende Mengen identisch: {1, 2, 3} = {2, 1, 3} = {2, 3, 2, 1}.

44 Version 8.1 18.02.2017

Kapitel 2 Mengen

2.1.10 Anmerkung. Wenn Elemente in einer Menge mehrmals vorkommen drfen,dann ist dies eine Multimenge, die jedoch hier nicht weiter behandelt wird.

2.1.11 Denition (endliche Menge, leere Menge). Fr die Anzahl der Elementeeiner Menge gilt:

Denition. Es sei M eine Menge, dann ist |M | die Anzahl der Elemente von M .Eine Menge M heit endliche Menge, wenn |M | < gilt, ansonsten heit sie eineunendliche Menge .Die Menge , die keine Elemente enthlt heit leere Menge.

Fr eine unendliche Menge kann man die Elemente nicht einzeln auhren. Fr eine end-liche Menge ist dies machbar, jedoch nicht immer praktikabel. Dann werden die Elementeber ihre Eigenschaften aufgefhrt.

2.2 Teilmengen und Potenzmenge

2.2.1 Denition (Teilmenge). Teilobjekten einer Menge werden nachfolgend de-niert.

Denition. Es seien M und N zwei Mengen. Die Menge N heit Teilmenge von M(N M), wenn jedes Element von N auch Element von M ist. Die Menge M heitdann auch Obermenge von N .

N M : x : (x N) (x M) (2.21)

Die Menge N heit echte Teilmenge von M (N M), wenn N eine Teilmenge vonM ist, jedoch N ungleich M ist.

N M : (N M) (N 6= M) . (2.22)

Ist N keine Teilmenge von M , so schreibt man N 6M .

Fr alle Mengen M gelten M M und M . Die leere Menge und die Menge selbstsind also stets Teilmengen einer Menge, dies sind die trivialen Teilmengen einer Menge.Ist N eine echte Teilmenge von M , dann gibt es Elemente in M , die nicht Elemente vonN sind.

Version 8.1 18.02.2017 45


Fr wichtige Mengen aus der Mathematik gilt:

N Z Q R C . (2.23)

2.2.2 Anmerkung. Zur Veranschaulichung und leichteren Erfassung mengentheoreti-scher Zusammenhnge bedient man sich hug Punktmengen in der Ebene (siehe Abbil-dung 2.1).

M N

Abbildung 2.1: Teilmenge

Diese Abbildungen heien Mengendiagramme oder auch Euler-Diagramme oderVenn-Diagramme. Sie sind benannt nach dem schweizer Mathematiker Leonhard Euler(1707 - 1783) und dem britischen Logiker John Venn (1834 - 1923). Die Mengendiagram-me dienen nur der Veranschaulichung! Sie knnen einem beim Beweisen als Anschauunghelfen, sie ersetzen jedoch keinen Beweis!

2.2.3 Bemerkung. Aus der Denition der Gleichheit fr Mengen und der Denitionfr Teilmengen ergibt sich

Bemerkung. Es seien M und N Mengen, dann gilt:

(M = N) (M N) (N M) . (2.24)

Beweis:M = N

(Denition der Gleichheit)x : (x N) (x M)

(Aussagenlogik)x : (x N) (x M))x : (x M) (x N))

(Denition der Teilmenge)(N M) (M N) .

46 Version 8.1 18.02.2017

Kapitel 2 Mengen

Fr den Beweis einer Mengengleichheit wird oftmals nachgewiesen, dass sich die beidenMengen gegenseitig als Teilmengen enthalten.

2.2.4 Bemerkung. Die Teilmengenbeziehung ist transitiv.

Bemerkung. Es seien L, M und N Mengen, dann gilt (Transitivitt):

(N M) (M L) (N L) . (2.25)

Ist N eine Teilmenge von M und M eine Teilmenge von L, dann ist N auch eineTeilmenge von L.

L M N

Abbildung 2.2: Transitive Teilmengen

Beweis: Die Grak (siehe Abbildung 2.2) dient nur der Veranschaulichung. Der formaleBeweis ist kurz. Fr jedes x N gilt:

(x N) N ist Teilmenge von M (N M)

(x M) M ist Teilmenge von L (M L)

(x L)

2.2.5 bung. Es seienM = {1, 2} und N = {2, 3, 4}. Welche der folgenden Aussagensind richtig?

M N?Nein, da 1 M , aber 1 / N .

N M?Nein, da 4 N , aber 4 /M .

Version 8.1 18.02.2017 47


M = N?Nein, da 4 N , aber 4 /M .

M 6= N?Ja.

{2, 4} N?Ja.

2 M?Ja.

2 M?Nein, dies ist nicht einmal ein gltiger Ausdruck, da 2 keine Menge ist, so dasskeine Teilmengenbeziehung bestehen kann. Gltig wren die Aussagen 2 Moder {2} M .

{2, {3, 4}} N?Nein, die Menge auf der linken Seite besteht aus zwei Elementen, aus der 2 undaus der Menge mit den Elementen 3 und 4. Das zweite Element ({3, 4}) ist jedochkein Element von N (sondern eine Teilmenge von N). Fr die Teilmengenbeziehungmsste es jedoch Element von N sein.

2.2.6 Denition (Potenzmenge). Die Teilmengen einer Menge lassen sich selber wie-derum zu einer Menge zusammenfassen.

Denition. Die Mengen aller Teilmengen einer Menge M heit Potenzmenge vonM : P(M).

P(M) := {T | T M} (2.26)

2.2.7 Beispiel. 1. Es sei M = , also die leere Menge, dann ist P(M) = {}, alsodie Menge, die nur ein Element hat, nmlich die leere Menge. Man beachte somit,dass P(M) nicht die leere Menge ist, sondern die Menge, die nur aus der leerenMenge besteht!

2. Es sei M = {a} eine Menge, die aus einem Element besteht. Damit ist die Potenz-menge die Menge, die aus der leeren Menge und der Menge selbst besteht, denndas sind die einzigen Teilmengen der Menge M , also P(M) = {,M}.

3. Es sei M = {a, b} eine Menge mit genau zwei Elementen, dann ist P(M) ={, {a}, {b},M}.

2.2.8 Bemerkung. Fr endliche Mengen kann die Elementanzahl der Potenzmenge ein-fach angegeben werden.

48 Version 8.1 18.02.2017

Kapitel 2 Mengen

Bemerkung. Es sei M eine endliche Menge mit n = |M | Elementen, dann hat diePotenzmenge von M genau 2n Elemente.

(|M | = n) (|P(M)| = 2n) (2.27)

Der Beweis kann durch vollstndige Induktion gefhrt werden, was hier jedoch nichtausgefhrt wird.

2.2.9 Bemerkung. Eine Teilmengenbeziehung bertrgt sich auch auf die Potenzmen-gen.

Bemerkung. Es seien M und N zwei beliebige Mengen. Ist M eine Teilmenge von N ,dann ist die Potenzmenge von M eine Teilmenge der Potenzmenge von N .

M N P(M) P(N) (2.28)

Beweis: als bung

2.3 Operationen von Mengen

2.3.1 . Wie kann mit Mengen gerechnet werden, welche Operationen gibt es und welcheRegeln gibt es fr die Operationen gibt.

2.3.2 Denition (Durchschnitt). Eine wichtige Verknpfung von Mengen ist derDurchschnitt.

Denition. Es seien M und N beliebige Mengen. Die Menge der Elemente, die sowohlin der Menge M , als auch in der Menge N sind, heit der Durchschnitt (M N) vonM und N .

M N := {x | (x M) (x N)} (2.29)

Die Abbildung (siehe 2.3) veranschaulicht den Durchschnitt. Der Durchschnitt der Men-gen M und N beinhaltet nur die kleine innere Flche, die mit M N bezeichnet ist.

Version 8.1 18.02.2017 49


N

M

M N

Abbildung 2.3: Durchschnitt von Mengen

2.3.3 Denition (Vereinigung). Eine weitere wichtige Verknpfung von Mengen istdie Vereinigung.

Denition. Es seien M und N beliebige Mengen. Die Menge der Elemente, die in derMenge M oder in der Menge N sind, heit die Vereinigung (M N) von M und N .

M N := {x | (x M) (x N)} (2.30)

2.3.4 Denition (disjunkt). Die Eigenschaft, dass der Durchschnitt zweier Mengendie leere Menge ist, ist eine besondere Eigenschaft.

Denition. Sind M und N zwei beliebige Mengen, mit leerem Durchschnitt (M N =), dann heienM und N disjunkt, und man kann stattMN auchM+N schreiben.

2.3.5 Anmerkung. Durchschnitt und Vereinigung lassen sich nicht nur fr zwei Mengendenieren. Ist I eine beliebige (endliche oder unendliche) Indexmenge und ist jedem i Ieine MengeMi zugeordnet, so deniert man den verallgemeinerten Durchschnitt derMengen Mi mittels

iIMi := {x | i I : x Mi} . (2.31)

Es ist die Menge der Elemente, die in jeder der Mengen Mi enthalten ist.

Weiter deniert man mittelsiI

Mi := {x | i I : x Mi} (2.32)

50 Version 8.1 18.02.2017

Kapitel 2 Mengen

die verallgemeinerte Vereinigung der Mengen Mi. Es ist die Menge der Elemente,die in mindestens einer der Mengen Mi enthalten ist.

Ist die Indexmenge gleich der leeren Menge, so ist der Durchschnitt die Grundmenge (!)und die Vereinigung die leere Menge (!), da die Bedingung i I nicht erfllt ist.

2.3.6 Satz. Fr das Rechnen mit Mengen gelten folgende Aussagen:

Satz (Assoziativ-, Kommutativ- und Distributionsgesetz). Es seien M , N undL beliebige Mengen. Dann gelten die Assoziativgesetze

M (N L) = (M N) L (2.33)M (N L) = (M N) L , (2.34)

die Kommutativgesetze

M N = N M (2.35)M N = N M (2.36)

und die Distibutivgesetze

M (N L) = (M N) (M L) (2.37)M (N L) = (M N) (M L) . (2.38)

Mit Hilfe der Mengendiagramme (siehe Abbildung 2.4) lassen sich diese Stze leichtveranschaulichen.

M

N

L

Abbildung 2.4: Mengendiagramm

Formal wird das Distributivgesetz bewiesen.

Version 8.1 18.02.2017 51


x M (N L) (Denition Durchschnitt)

(x M) (x (N L)) (Denition Vereinigung)

(x M) ((x N) (x L)) (Distributivgesetz - Aussagen)

((x M) (x N))((x M) (x L))

(Denition Durchschnitt)(x M N) (x M L)

(Denition Vereinigung)x (M N) (M L)

Somit wurde gezeigt, dass jedes Element x M (N L) auch Element von (M N)(M L), also M (N L) (M N) (M L) und umgekehrt. Wir haben damit diebeidseitige Teilmengenbeziehung gezeigt, und somit die Idenditt der beiden Mengen.

Das Assoziativgesetz gilt nicht nur fr drei Mengen, sondern auch fr mehre Mengen.Daher kann hierbei auf die Klammersetzung verzichtet werden.

2.3.7 Bemerkung. Fr das Rechnen mit Mengen sind folgende Regeln oftmals ntzlich:

Bemerkung. Es seien M und N beliebige Mengen, dann gelten

M (M N) = M (2.39)M (M N) = M (2.40)

M M = M (2.41)M M = M (2.42)

2.3.8 Bemerkung. Fr die leere Menge und die Grundmenge gelten folgende Aussagen:

Bemerkung. Es sei M eine beliebige Teilmenge der Grundmenge G, dann gelten

M = (2.43)M = M (2.44)M G = M (2.45)M G = G (2.46)

52 Version 8.1 18.02.2017

Kapitel 2 Mengen

2.3.9 Bemerkung. Wie wirken sich der Durchschnitt und die Vereinigung von zweiMengen auf die Potenzmengen aus, welchen Beziehungen gibt es?

Bemerkung. Es seien M und N zwei beliebige Mengen. Dann gelten(a) Die Potenzmenge des Durchschnitts der Mengen M und N ist gleich dem Durch-schnitt der Potenzmengen der Mengen M und N .

P(M N) = P(M) P(N) (2.47)

(b) Die Vereinigung der Potenzmengen der Mengen M und N ist eine Teilmenge derPotenzmenge der Vereinigung der Mengen M und N .

P(M) P(N) P(M N) (2.48)

Beweis: bung. Bei (a) ist die gegenseitige Teilmengenbeziehung zu zeigen. Bei (b) istnur die eine Richtung nachzuweisen. Wieso gilt die Gegenrichtung nicht? Finden Sie dazuein Gegenbeispiel.

2.3.10 Denition (Dierenz, Komplement). Im nachfolgenden seien M , N und Lstets beliebige Mengen, die Teilmenge einer festen Grundmenge G sind.

Denition. (a) Es seien M und N beliebige Mengen, dann heit

M\N := {x | (x M) (x / N)} (2.49)

die Dierenz der Mengen M und N . In der Dierenz sind die Elemente von M , dienicht in N sind.(b) Es sei M eine beliebige Teilmenge von G, dann heit die Menge

{G(M) := {x G | x /M} = G\M (2.50)

das Komplement von M bezglich G. Es enthlt die Elemente der Grundmenge, dienicht in M sind.

Ist die Grundmenge G allgemein bekannt, so kann man das Komplement einer MengeMkurz als M schreiben. Durch die Umformulierung {G(M) := {x G | (x M)} wirdder Zusammenhang zwischen Komplementbildung und der aussagenlogischen Negationdeutlich.

Es ergibt sich sofort, dass M und {G(M) disjunkt sind und dass M + {G(M) = G ist.

Version 8.1 18.02.2017 53


2.3.11 Bemerkung. Wie bildet man die Dierenzmenge, mit Hilfe der Komplement-menge.

Bemerkung. Es seien M und N beliebige Teilmengen einer Grundmenge G, dann gilt

M\N = M {G(N) . (2.51)

Beweis: bung

2.3.12 Denition (symmetrische Dierenz). Wie wird die symmetrische Dierenzmit Hilfe der Dierenzen gebildet.

Denition. Es seien M und N Mengen, dann heit

M4N := (M\N) + (N\M) (2.52)

die symmetrische Dierenz von M und N .

Veranschaulichen Sie sich die Dierenz.

2.3.13 Bemerkung. Nochmals eine andere Mglichkeit, die symmetrische Dierenzdarzustellen.

Bemerkung. Es seien M und N beliebige Teilmengen, dann gilt

M4N = (M N)\(M N) . (2.53)

Beweis: bung

2.3.14 Satz (Regel von de Morgan). Wie bei den Aussagen gibt es auch hier Regelnvon de Morgan.

Satz. Es seien M und N beliebige Teilmengen der Grundmenge G, dann gelten dieStze von de Morgan

{G(M N) = {G(M) {G(N) (2.54){G(M N) = {G(M) {G(N) . (2.55)

54 Version 8.1 18.02.2017

Kapitel 2 Mengen

Ist die Grundmenge G bekannt, so schreibt man kurz

(M N) = M N und (2.56)(M N) = M N . (2.57)

Beweis der ersten Aussage:x {G(M N)

(Denition Komplement)(x G) (x / (M N))

(Negation)(x G) (x (M N))

(Denition Vereinigung)(x G)((x M) (x N))

(Satz von de Morgan - Aussagen)(x G)(((x M)) ((x N)))

(Assoziativgesetz)((x G) ((x M)))((x G) ((x N)))

(Negation)((x G) (x /M))((x G) (x / N))

(Denition Komplement)(x {G(M) (x {G(N))

(Denition Durchschnitt)x {G(M) {G(N)

Auf Grund der Denition der Mengengleichheit gilt damit die behauptete Aussage. Derandere Teil kann analog bewiesen werden.

2.3.15 Anmerkung. Auch fr Familien von Mengen gelten die verallgemeinerter Stzevon de Morgan .

{G(iI

Mi) =iI

{G(Mi) (2.58)

{G(iI

Mi) =iI

{G(Mi) (2.59)

2.4 Klasseneinteilung

2.4.1 Denition (Klasseneinteilung). Im folgenden sei I stets eine beliebige Index-menge.

Version 8.1 18.02.2017 55

2.4 Klasseneinteilung

Denition. Es sei {Mi | i I)} eine Familie von beliebigen nicht leeren Teilmengeneiner Grundmenge. Die Familie von Mengen heit (paarweise) disjunkt, wenn fralle i, j I die Mengen Mi und Mj disjunkt sind:

{Mi | i I} paarweise disjunkt : i, j I, i 6= j : Mi Mj = . (2.60)

Eine Familie von Mengen heit Klasseneinteilung oder disjunkte Zerlegung oderPartition von G, wenn sie paarweise disjunkt ist und die verallgemeinerte Vereinigungder Mengen gleich der Grundmenge ist.

M1

M2

M3

M4

M5

M6

Abbildung 2.5: Klasseneinteilung

Klasseneinteilung treen wir an vielen Stellen an.

2.4.2 Beispiel. Es sei G die Menge aller derzeit lebenden Menschen, M die Mengeder Menschen mnnlichen Geschlechts und F die Menge der Menschen weiblichen Ge-schlechts, dann gilt M F = und M F = G, so dass dies eine Klasseneinteilung ist.Wir haben zwei disjunkte Klassen.

2.4.3 Beispiel. Die natrlichen Zahlen lassen sich in die disjunkten Mengen der geradenund der ungeraden Zahlen zerlegen.

2.4.4 Beispiel. Ist P die Menge der Produktion der Automobile eines Werkes an einemTag. Es werden die verschiedenen Baumuster B1, . . . , Bn produziert und seien T1, . . . , Tndie Menge der Autos der Tagesproduktion mit diesen Baumustern, dann ist {Ti ; i =1, . . . , n} die Klasseneinteilung der Tagesproduktion P .

2.4.5 Denition (quivalenzklassen). Durch die Klasseneinteilung einer Menge Gist jedes Element von G genau in einer Teilmenge der Klasseneinteilung enthalten.

56 Version 8.1 18.02.2017

Kapitel 2 Mengen

Denition. Sind zwei Elemente x, y in der gleichen Teilmenge einer Klasseneintei-lung, so heien sie quivalent (x y). Die Teilmengen der Klasseneinteilung heienauch quivalenzklassen. Ein Element einer quivalenzklasse heit Reprsentantder quivalenzklasse.

2.4.6 Bemerkung. Fr quivalenzklassen gibt es einige Eigenschaften, die bei der Be-handlung von Relationen noch genauer betrachtet werden.

Bemerkung. Es seien x, y und z Elemente aus einer Menge G mit einer Klassenein-teilung. Fr die quivalenz der Klasseneinteilung gelten:(a) Fr jedes x G ist x x, das heit, dass die Klasseneinteilung reexiv ist.(b) Ist x y, sind also x und y in derselben quivalenzklasse, dann gilt auch y x,das heit, dass die Klasseneinteilung symmetrisch ist.(c) Ist x y und y z, dann ist auch x z, das heit, dass die Klasseneinteilungtransitiv ist.

2.4.7 Beispiel. Die Menge der ganzen Zahlen Z wird bezglich des Rests bei der Di-vision durch 6 in sechs verschiedene quivalenzklassen aufgeteilt. Fr i = 0, 1, 2, 3, 4, 5seien Ti die Menge der ganzen Zahlen, die bei der Division durch 6 den Rest i haben.

Ti = {x Z | n Z : x = 6n+ i} (2.61)

Dies deniert eine Klasseneinteilung: Z = T0 + T1 + T2 + T3 + T4 + T5.Fr einen Reprsentanten und jeden Vertreter einer der Klassen T2, T4 oder T6 gilt, dasser durch zwei teilbar ist. Die Reprsentanten der Klassen T3 und T6 sind jeweils durch 3teilbar. Daher knnen in den Klassen T2, T3, T4 und T6 keine Primzahlen enthalten sein.(Ausnahme: 2 und 3 selbst). Durch die gemeinsame Eigenschaft der Zahlen der Klassenkann dies fr jedes Element der Klasse bewiesen werden.

2.4.8 Anmerkung. Ist n eine beliebige natrliche Zahl, so kann die Menge Z in ndisjunkte Teilmengen bezglich der Division durch n zerlegt werden. Die Teilmengen Tifr i = 0, 1, . . . , n 1, werden folgendermaen gebildet:

Ti := {x Z | k Z : x = kn+ i} (2.62)

Diese Teilmengen bilden eine Klasseneinteilung der ganzen Zahlen. Die Menge Zn ={0, 1, . . . , n 1} bildet ein Reprsentantensystem. Dieses Reprsentantensysten werdenim Folgenden noch vorkommen. Es hat eine wichtige Bedeutung in der Informatik.

Version 8.1 18.02.2017 57

2.5 Kartesisches Produkt

2.4.9 Anmerkung. Die Klassenaufteilung ist ein hug verwendetes Verfahren, um dieProblemlsung oder andere Aufgaben auf eine begrenzte Zahl von Fllen zu reduzieren.Bei Meinungsumfragen werden die Befragten in bestimmte Klassen eingeteilt, um dannAussagen ber die Vertreter dieser Klassen im allgemeinen zu erhalten.

Auch die Fallunterscheidungen ist eine Klasseneinteilung. Auch Fallunterscheidungenkommen an vielen Stellen vor, zum Beispiel bei der Denition von mathematischen Funk-tionen, bei der Berechnung der privaten Steuerlast, in Programmvorgaben, um nur einigewenige Beispiele zu nennen.

2.5 Kartesisches Produkt

2.5.1 Anmerkung. In vielen Fllen ist es sinnvoll, geordnete Paare (x, y) von Elemen-ten x X und y Y zweier Mengen X und Y zu betrachten. Dabei heit x die ersteKomponente und y die zweite Komponente. Ein Beispiel hierfr ist das 2-dimensionaleKoordinatensytem, bei dem X = R und Y = R gilt. Die Gleichheit zweier geordneterPaare wird durch

(x1, y1) = (x2, y2) : (x1 = x2) (y1 = y2) (2.63)

deniert. Die Mengen X und Y knnen jedoch auch beliebige Mengen sein.

2.5.2 Denition (Kartesisches Produkt). Zuerst die Denition eines kartesischenProduktes bei zwei Mengen.

Denition. Es seien X und Y zwei beliebige Mengen, dann heit die Menge

X Y := {(x, y) | x X y Y } , (2.64)

also die Menge der geordneten Paare (x, y) mit x X und y Y das kartesischeProdukt der Mengen X und Y . Die Elemente dieses kartesischen Produktes heienauch geordnete 2-Tupel .

Das kartesische Produkt ist nach dem franzsischen Philosophen und Mathematiker RenDescartes (1596 - 1650) benannt. Das kartesische Produkt ist selber wieder eine Menge,deren Elemente die geordneten 2-Tupel sind.

2.5.3 Beispiel. In der Regel ist X Y ungleich Y X. Die Gleichheit ist hier dieMengengleichheit. Diese Aussage kann anhand des ersten Beispiel sofort gesehen werden.

Es seien X = {1, 2, 3} und Y = {a, b}, dann ist

X Y = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)} (2.65)

58 Version 8.1 18.02.2017

Kapitel 2 Mengen

und

Y X = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)} . (2.66)

Die beiden kartesischen Produkte sind ungleich.

2.5.4 Beispiel. Es seien P = {p1, p2, p3, p4} eine Menge von Produkten und L ={l1, l2, l3} eine Menge von Lieferanten. Dann ist P L das kartesische Produkt derProdukte und Lieferanten.

2.5.5 Beispiel. Es seien X = Y = N, dann ist N N die Menge der geordneten Paarevon natrlichen Zahlen.

2.5.6 Beispiel. Es seien X = Y = R, dann ist R R die Menge der geordneten Paarevon reellen Zahlen, der 2-dimensionale Anschaungsraum.

2.5.7 Denition (Kartesisches Produkt). Die Denition des kartesischen Produkteskann verallgemeinert werden. Das Produkt kann auch fr drei oder mehr Mengen gebildetwerden.

Denition. Es sei n N. Des weiteren seien beliebige nicht leere MengenX1, X2, . . . , Xn gegeben. Dann heit die Menge

ni=1

Xi := {(x1, x2, . . . , xn) | ni=1xi Xi} , (2.67)

die Menge aller (geordneten) n-Tupel (x1, x2, . . . , xn) mit xi Xi fr alle i {1, 2, . . . , n}, das kartesische Produkt von X1, X2, . . . , Xn.

Stattni=1Xi schreibt man auch X1X2 Xn. Die Denition kann auch auf Folgen

von Mengen {Xn}nN verallgemeinert werden.

Ist n = 2, so nennt man X1 X2 auch Paarmenge. Fr n = 1 ist das kartesischeProdukt gleich der Menge X1. Sind X1 = X2 = = Xn = X, so schreibt man frni=1Xi auch kurz X

n. Beispiele fr spezielle kartesische Produkte sind R2 und R3, die2- und 3-dimensionalen Anschungsrume.

2.5.8 Bemerkung. Bei einem (endlichen) kartesisches Produkt von endlichen Mengen,kann die Elementanzahl des kartesichen Produktes berechnet werden.

Bemerkung. Es seien fr n N die Mengen X1, X2, . . . , Xn endlich mit den Elemen-tanzahlen |Xi| = mi. Dann gilt |

ni=1Xi| =

ni=1mi.

Version 8.1 18.02.2017 59

2.6 Aufgaben

2.6 Aufgaben

2.6.1 Aufgabe. Geben Sie die folgenden Mengen reeller Zahlen in der aufzhlendenSchreibweise an:(a) A := {x | x+ 2 = 5}(b) B := {x | x2 1 = 3}(c) C := {x | x3 = 8}(d) D := {x | (x 3)2 = 36}(e) E := {x | x2 = 1}

2.6.2 Aufgabe. Bestimmen Sie alle Teilmengen von A = {a}, B = {a, b} und C ={a, b, c}.

2.6.3 Aufgabe. Es seien M und N zwei beliebige Mengen. Beweisen Sie: Ist M eineTeilmenge von N , dann ist P(N) eine Teilmenge von (N) ist:

M N P(M) P(N) . (2.68)

2.6.4 Aufgabe. Es seien M und N zwei beliebige Mengen. Beweisen Sie, dass die Po-tenzmenge vom Durchschnitt gleich dem Durchschnitt der Potenzmengen ist:

P(M) P(N) = P(M N) (2.69)

2.6.5 Aufgabe. Es seien M und N zwei beliebige Mengen. Beweisen Sie, dass die Ver-einigung der Potenzmengen eine Teilmenge der Potenzmenge der Vereinigung ist:

P(M) P(N) P(M N) (2.70)

Gilt auch die Umkehrung? Beweisen Sie dies oder widerlegen Sie die Umkehrung.

2.6.6 Aufgabe. Es seien A und B beliebige Mengen und G eine Grundmenge. BeweisenSie, dass A\B = A{G(B) gilt, dass also die Dierenz A ohne B gleich dem Durchschnittvon A mit dem Komplement von B ist.

2.6.7 Aufgabe. Es seien A und B beliebige Mengen. Beweisen Sie

A4B = (A B)\(A B) , (2.71)

dass also die symmetrische Dierenz gleich der Dierenz der Vereinigung vom Durch-schnitt ist.

2.6.8 Aufgabe. Es seienM und N beliebige Mengen mit der Grundmenge G. BeweisenSie, die Regel von de Morgan, dass also

{G(M N) = {G(M) {G(N) (2.72)

gilt.

60 Version 8.1 18.02.2017

Kapitel 2 Mengen

2.6.9 Aufgabe. Es seien G = {1, 2, 3, 4, 5, 6, 7, 8, 9} eine Grundmenge, M ={2, 3, 4, 7, 9} und N = {1, 4, 5, 9}. Bestimmen Sie:

(a) M N

(b) M N

(c) M\N

(d) N\M

(e) {G(M)

(f) {G(N)

(g) MN

2.6.10 Aufgabe. Es sei G = {n N | n < 12}, A = {1, 2, 4, 8, 9} und B ={2, 3, 5, 7, 11} Bestimmen Sie

(a) A B

(b) A B

(c) A\CG(B)

(d) B\A

(e) Geben Sie eine Menge C mit so wenig wie mglich Elemente an, so dass ABC = Gist.

2.6.11 Aufgabe. Es seien Ti := {n N | i teilt n} die Menge der Vielfachen von i fri N. Bestimmen Sie fr beliebige i, j N Ti Tj .

2.6.12 Aufgabe. Es seien X, Y und Z beliebige Mengen. Zeigen Sie(a) X (Y Z) = (X Y ) (X Z)(b) X (Y Z) = (X Y ) (X Z)

Veranschaulichen Sie sich die Mengen mit Hilfe einer Skizze im 2-dimensionalen An-schaungsraum.

2.6.13 Aufgabe. Es seien X1, X2, Y1 und Y2 beliebige Mengen. Zeigen Sie

(a) (X1 X2) (Y1 Y2) = (X1 Y1) (X2 Y2)

(b) (X1 X2) (Y1 Y2) (X1 Y1) (X2 Y2)

(c) Gilt auch die Umkehrung von (b)? Beweisen Sie entweder die Umkehrung oder zeigenSie an Hand eines Gegenbeispiels, dass die Umkehrung nicht gilt.

Veranschaulichen Sie sich die Mengen mit Hilfe einer Skizze im 2-dimensionalen Anschau-ungsraum.

Version 8.1 18.02.2017 61

2.7 Lsungen

2.6.14 Aufgabe. Es seien X1, X2, Y1 und Y2 beliebige Mengen. Zeigen Sie

(X1 X2) (Y1 Y2) (X1 Y1) (X2 Y2) . (2.73)

2.7 Lsunge

Logik und Algebra - Homepage von Andreas Zeh-Marschkezeh-marschke.de/LogikUndAlgebra.pdf · Skript Logik und Algebra Mathematische Grundlagen Andreas Zeh-Marschke Version 8.1

Text of Logik und Algebra - Homepage von Andreas Zeh-Marschkezeh-marschke.de/LogikUndAlgebra.pdf · Skript...

Arithmetik & Algebra Aritmetica & Algebra max. punti: 45

Menschliche Logik AND Boolsche Logik = NOT Logisch

Modulhandbuch Wir tsc haftsinformatik · 2020. 9. 24. · X-5 Fr e ie Wahl 1 uniweit diverse Angebote ... Mathematische Grundlagen 1: Logik und Algebra Mathematics 1 Modulnummer:

Wissenschaftsmagazin Mathematische Logik

JULI ZEH Neujahr - Bayern

Arithmetik & Algebra Aritmetica & Algebra...Einheitsprüfung / esame uniformato 2018 Fach / Materia: Arithmetik & Algebra / Aritmetica & Algebra Seite 4 von 14 pagina 4 di 14 Punkte

Höhere Algebra: Darstellungstheorie und homologische Algebra · Höhere Algebra: Darstellungstheorie und homologische Algebra Wintersemester 2014/15 Christoph Schweigert Universität

Lineare Algebra, Teil I - mathematik.tu-dortmund.de · Lineare Algebra, Teil I 11. Oktober 2010 0. Kapitel I. Grundbegriﬀe Inhalt: 1. Logik 2. Mengen und Abbildungen 3. Primfaktorzerlegung

Logik - ein Rätsel von Raymond Smullyan ... - emath.deemath.de/Referate/Smullyan.pdf · Mathe-Board Logik - ein Rätsel von Raymond Smullyan Mathe-Board: Knobelecke: Logik - ein

Vorlesung Logik, Diskrete Mathematik und Lineare Algebra · 5 Lineare Algebra 51 5.1 Einfuhrung: Anschauliche Vektorrechnung . . . . . . . . . . . . . . . 51 ... Die Grundlagen der

Logik und Argumentation - Leibniz Universität Hannover · 2019-08-27 · Logik und Argumentation Materialien zu einführenden Vorlesungen über formale Logik und Argumentationstheorie

Grundlagen der linearen Algebra und analytischen Geometrie · 1. Grundlagen der Aussagenlogik Wir wollen uns zunächst mit den Grundlagen der Logik beschäftigen. Hierbei benötigen

Übungsaufgaben mit Computer-Algebra-Software Mathematik ... · I Maxima, SymPy, NumPy, SciPy, R, Mengen, Logik, Graphentheorie, graphische Darstellung Anbindung an Programmiersprache

Logik & Argumentation

Logik für Informatiker - KITformal.iti.kit.edu/~beckert/teaching/Logik-SS06/01Einfuehrung.pdf · Vorlesung Logik für Informatiker 1. Einführung Bernhard Beckert Universität Koblenz-Landau

Schmitz Hegels Logik

Jedem seine Logik!

Einführung in die Mathematische Logik - math.uni-bonn.de logik... · Einführung in die Mathematische Logik by Peter Koepke Bonn, Sommersemester 2015 Vorläuﬁges Skript zur Vorlesung

Georges Bataille Der große Zeh - blauwerke-berlin.deblauwerke-berlin.de/bilder/Zeh-Inhaltsverzeichnis.pdf · Inhaltsverzeichnis Georges Bataille Le gros orteil / Der große Zeh 6

Nota Fce3102 Logik

Jedem seine Logik! - Conrad Electronic · Jedem seine Logik! Die dritte Generation von Logik-Controllern für Ihre branchenspezifischen Anwendungen. Größerer Speicher für Ihre

Logik - ein Rätsel von Raymond Smullyan Knobelecke: Logik - ein … · 2017-03-26 · Mathe-Board Logik - ein Rätsel von Raymond Smullyan Mathe-Board: Knobelecke: Logik - ein Rätsel

Mathematische Logik - Website of Alexander Bors · 2017. 3. 7. · Mathematische Logik kann als Teilgebiet der Mathematik angesehen werden, wie z.B. auch Algebra oder Analysis. Untersuchungsobjekt

Georg Wilhelm Friedrich Hegel - Die Wissenschaft der Logik. Die subjektive Logik (1834)

Mathematische Grundlagen 1: Logik und Algebra · Bruckner, Emanuele Delucchi, Martin Dlugosch, Eva-Maria Feichtner, Di- mitryFeichtner-Kozlov,TimHaga,DamienImbs,Jan-PhilippLitza,Lennart

Einführung in die Logik - Homepage von Joachim Stillerjoachimstiller.de/download/philosophie_einfuehrung_in_die_logik.pdf · Einführung in die Logik: Einleitung Was heißt "Logik"?

Vorlesung Logik und Datenbanken - hu-berlin.de · Relationale Algebra Relationale Algebra 3.1 Deﬁnition und Beispiele 3.2 Anfrageauswertung und Heuristische Optimierung NICOLE SCHWEIKARDT

Logik für Informatiker - KITbeckert/teaching/Logik-SS06/01... · Einführung: Zusammenfassung Ziel und Rolle der Formalen Logik in der Informatik Modellierung, Adäquatheit der Modellierung

Logik f¨ur Informatiker 1. Grundlegende Beweisstrategiensofronie/logik-ss-2012/slides/... · Logik f¨ur Informatiker 1. Grundlegende Beweisstrategien Viorica Sofronie-Stokkermans

Lineare Algebra I - minet.uni-jena.de · PDF fileInhaltsverzeichnis 1 Grundbegriffe der Logik 3 2 Grundbegriffe der Mengenlehre 4 3 Relationen und Funktionen 8 4 Algebraische Grundbegriffe

Documents

Logik und Algebra - Homepage von Andreas Zeh-Marschkezeh-marschke.de/LogikUndAlgebra.pdf · Skript Logik und Algebra Mathematische Grundlagen Andreas Zeh-Marschke Version 8.1

Text of Logik und Algebra - Homepage von Andreas Zeh-Marschkezeh-marschke.de/LogikUndAlgebra.pdf · Skript...