Sie sind hier
E-Book

Kompendium der diskreten Mathematik

AutorBernd Baumgarten
VerlagDe Gruyter Oldenbourg
Erscheinungsjahr2014
ReiheDe Gruyter Studium 
Seitenanzahl388 Seiten
ISBN9783486781328
FormatePUB/PDF
KopierschutzWasserzeichen
GerätePC/MAC/eReader/Tablet
Preis34,95 EUR
Das Kompendium präsentiert die für ein Mathematik- oder Informatikstudium benötigten Grundlagen der diskreten Mathematik in kompakter Form. Alle wichtigen Themen wie Mengen, Relationen und Funktionen, Logik, Graphen, abstrakte und lineare Algebra sowie diskrete Wahrscheinlichkeitstheorie werden abgedeckt. Damit erweist sich das Buch als nützlicher Begleiter für viele Vorlesungen im Studium.


Bernd Baumgarten, Hochschule Darmstadt.

Kaufen Sie hier:

Horizontale Tabs

Blick ins Buch
Inhaltsverzeichnis
Inhaltsverzeichnis??????????????????????????????????????????????????5
1 Einleitung??????????????????????????????????????11
1.1 Überblick????????????????????????????????????????11
1.2 Methodische Schwerpunkte??????????????????????????????????????????????????????????????????????12
1.3 Notation??????????????????????????????????????13
1.4 Formalismus und Sicherheit??????????????????????????????????????????????????????????????????????????14
1.5 Minimalismus??????????????????????????????????????????????16
1.6 Danksagungen??????????????????????????????????????????????16
2 Mengen??????????????????????????????17
2.1 Mengen und Elemente????????????????????????????????????????????????????????????17
2.1.1 Mengen, Elemente, Objekte????????????????????????????????????????????????????????????????????????????17
2.1.2 Mengendefinition – Möglichkeiten und Fallstricke??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????18
2.2 Mengenrelationen und -operationen????????????????????????????????????????????????????????????????????????????????????????22
2.3 Das Auswahlaxiom *??????????????????????????????????????????????????????????27
2.4 Axiomatische Mengenlehre??????????????????????????????????????????????????????????????????????28
2.4.1 Hauptrichtungen????????????????????????????????????????????????????????28
2.4.2 ZFU als Beispiel einer Axiomatik *??????????????????????????????????????????????????????????????????????????????????????????????29
2.4.3 Abseits der Axiomatik????????????????????????????????????????????????????????????????????31
2.5 Übungsaufgaben??????????????????????????????????????????????????31
3 Relationen und Funktionen????????????????????????????????????????????????????????????????????35
3.1 Paare und Tupel????????????????????????????????????????????????????35
3.2 Relationen??????????????????????????????????????????36
3.3 Abbildungen (Funktionen)??????????????????????????????????????????????????????????????????????39
3.4 Äquivalenzrelationen??????????????????????????????????????????????????????????????43
3.5 Kongruenzrelationen????????????????????????????????????????????????????????????45
3.6 Ordnungsrelationen??????????????????????????????????????????????????????????46
3.6.1 Halb- und Totalordnungen??????????????????????????????????????????????????????????????????????????46
3.6.2 Extremale und begrenzende Elemente??????????????????????????????????????????????????????????????????????????????????????????????48
3.6.3 Ordnungen und das Auswahlaxiom *??????????????????????????????????????????????????????????????????????????????????????????50
3.6.4 Verbände als spezielle Ordnungen *??????????????????????????????????????????????????????????????????????????????????????????????51
3.7 Operationen auf Relationen??????????????????????????????????????????????????????????????????????????52
3.8 Permutationen????????????????????????????????????????????????54
3.9 Abbildungen von Relationen *??????????????????????????????????????????????????????????????????????????????56
3.10 Induktion und Rekursion??????????????????????????????????????????????????????????????????????57
3.10.1 Induktive Mengendefinitionen????????????????????????????????????????????????????????????????????????????????????57
3.10.2 Induktionshistorie????????????????????????????????????????????????????????????????60
3.10.3 Induktionsvarianten??????????????????????????????????????????????????????????????????61
3.10.4 Induktionsbeweise??????????????????????????????????????????????????????????????62
3.10.5 Rekursive Funktionsdefinitionen??????????????????????????????????????????????????????????????????????????????????????????63
3.11 Hüllen und Erzeugendensysteme??????????????????????????????????????????????????????????????????????????????????69
3.11.1 Transitive Hülle????????????????????????????????????????????????????????????69
3.11.2 Andere Hüllen??????????????????????????????????????????????????????70
3.12 Übungsaufgaben????????????????????????????????????????????????????72
4 Logik????????????????????????????77
4.1 Aussagenlogik????????????????????????????????????????????????77
4.1.1 Die Syntax der Aussagenlogik??????????????????????????????????????????????????????????????????????????????????77
4.1.2 Zwei wichtige Eigenschaften der Syntax der Aussagenlogik *??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????80
4.1.3 Die elementare Semantik der Aussagenlogik????????????????????????????????????????????????????????????????????????????????????????????????????????????82
4.1.4 Semantische Begriffe rund ums Modell??????????????????????????????????????????????????????????????????????????????????????????????????86
4.1.5 Substitution und Ersetzung??????????????????????????????????????????????????????????????????????????????91
4.1.6 Assoziativitätsaspekte??????????????????????????????????????????????????????????????????????95
4.1.7 Mehr über Junktoren *????????????????????????????????????????????????????????????????????97
4.1.8 Reduzierbarkeit und Dualität *??????????????????????????????????????????????????????????????????????????????????????100
4.1.9 Normalformen??????????????????????????????????????????????????102
4.1.10 Beweisverfahren und Algorithmen??????????????????????????????????????????????????????????????????????????????????????????106
4.2 Prädikatenlogik????????????????????????????????????????????????????116
4.2.1 Die Syntax der Prädikatenlogik??????????????????????????????????????????????????????????????????????????????????????117
4.2.2 Weitere syntaktische Begriffe????????????????????????????????????????????????????????????????????????????????????118
4.2.3 Die elementare Semantik der Prädikatenlogik????????????????????????????????????????????????????????????????????????????????????????????????????????????????120
4.2.4 Semantische Begriffe und Sätze der Prädikatenlogik??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????123
4.2.5 Substitution und Ersetzung in PL1????????????????????????????????????????????????????????????????????????????????????????????125
4.2.6 Entscheidungsprobleme *????????????????????????????????????????????????????????????????????????127
4.2.7 PL1-Beweisverfahren und -Algorithmen *??????????????????????????????????????????????????????????????????????????????????????????????????????129
4.2.8 Prädikatenlogik mit Identität????????????????????????????????????????????????????????????????????????????????????135
4.3 Übungsaufgaben??????????????????????????????????????????????????137
5 Zahlen und Anzahlen????????????????????????????????????????????????????????147
5.1 Zahlen??????????????????????????????????148
5.1.1 Natürliche Zahlen und ihre Operationen??????????????????????????????????????????????????????????????????????????????????????????????????????148
5.1.2 Ganze Zahlen??????????????????????????????????????????????????152
5.1.3 Rationale Zahlen??????????????????????????????????????????????????????????154
5.1.4 Reelle und komplexe Zahlen *??????????????????????????????????????????????????????????????????????????????????157
5.2 Anzahlen??????????????????????????????????????163
5.2.1 Mächtigkeit und endliche Anzahlen????????????????????????????????????????????????????????????????????????????????????????????163
5.2.2 Abzählende Kombinatorik????????????????????????????????????????????????????????????????????????166
5.2.3 Unendliche Anzahlen????????????????????????????????????????????????????????????????174
5.3 Elementare Zahlentheorie *??????????????????????????????????????????????????????????????????????????184
5.3.1 Teiler und Restklassenarithmetik??????????????????????????????????????????????????????????????????????????????????????????184
5.3.2 Primzahlen, ggT und Restklassengleichungen??????????????????????????????????????????????????????????????????????????????????????????????????????????????186
5.4 Übungsaufgaben??????????????????????????????????????????????????194
6 Graphen????????????????????????????????201
6.1 Einführende Beispiele????????????????????????????????????????????????????????????????202
6.2 Definition, Grundbegriffe????????????????????????????????????????????????????????????????????????204
6.3 Darstellungsfragen??????????????????????????????????????????????????????????206
6.3.1 Zeichnerische Darstellung in der Ebene??????????????????????????????????????????????????????????????????????????????????????????????????????206
6.3.2 Andere Darstellungen von Graphen??????????????????????????????????????????????????????????????????????????????????????????208
6.4 Isomorphie??????????????????????????????????????????209
6.5 Nachbarschaft, Wege????????????????????????????????????????????????????????????210
6.5.1 … in ungerichteten Graphen??????????????????????????????????????????????????????????????????????????????211
6.5.2 … in gerichteten Graphen??????????????????????????????????????????????????????????????????????????211
6.5.3 … und in beiden????????????????????????????????????????????????????????212
6.5.4 Zwei Hilfssätze für die theoretische Informatik????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????212
6.5.5 Weglängen????????????????????????????????????????????214
6.5.6 Zusammenhang??????????????????????????????????????????????????216
6.5.7 Spezielle Wege??????????????????????????????????????????????????????217
6.6 Bäume????????????????????????????????219
6.6.1 Bäume – ein Thema mit Variationen????????????????????????????????????????????????????????????????????????????????????????????219
6.6.2 Gerichtete ungeordnete Bäume??????????????????????????????????????????????????????????????????????????????????221
6.6.3 Ungerichtete ungeordnete Bäume??????????????????????????????????????????????????????????????????????????????????????222
6.6.4 Parallelen zwischen gerichteten und ungerichteten Bäumen??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????224
6.6.5 Geordnete Bäume????????????????????????????????????????????????????????225
6.6.6 Spannbäume??????????????????????????????????????????????226
6.6.7 Baumbezogene Graphenalgorithmen????????????????????????????????????????????????????????????????????????????????????????227
6.6.8 Unendliche Bäume??????????????????????????????????????????????????????????229
6.7 Beschriftete Graphen??????????????????????????????????????????????????????????????230
6.7.1 Endliche Automaten??????????????????????????????????????????????????????????????230
6.7.2 Termsyntax??????????????????????????????????????????????232
6.7.3 Färbungen????????????????????????????????????????????232
6.8 Einfache Algorithmen für endliche Graphen????????????????????????????????????????????????????????????????????????????????????????????????????????233
6.8.1 Graphendurchläufe, Zusammenhang, Spannbäume????????????????????????????????????????????????????????????????????????????????????????????????????????????????233
6.8.2 Besondere Wege: kürzeste, längste, Euler’sche und Hamilton’sche????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????235
6.9 Übungsaufgaben??????????????????????????????????????????????????238
7 Algebra????????????????????????????????243
7.1 Gruppen????????????????????????????????????243
7.1.1 Definition, Beispiele, Grundeigenschaften????????????????????????????????????????????????????????????????????????????????????????????????????????????243
7.1.2 Gruppenhomomorphismen????????????????????????????????????????????????????????????????????247
7.1.3 Untergruppen??????????????????????????????????????????????????248
7.2 Ringe und Körper??????????????????????????????????????????????????????253
7.2.1 Ringe????????????????????????????????????253
7.2.2 Körper??????????????????????????????????????258
7.3 Verbände *??????????????????????????????????????????260
7.4 Vektorräume????????????????????????????????????????????263
7.4.1 Definition und Beispiele??????????????????????????????????????????????????????????????????????????263
7.4.2 Lineare Abhängigkeit, Basis und Dimension????????????????????????????????????????????????????????????????????????????????????????????????????????????264
7.4.3 Untervektorräume??????????????????????????????????????????????????????????270
7.4.4 Lineare Abbildungen und Matrizen??????????????????????????????????????????????????????????????????????????????????????????272
7.4.5 Lineare Gleichungssysteme????????????????????????????????????????????????????????????????????????????279
7.4.6 Räume linearer Abbildungen??????????????????????????????????????????????????????????????????????????????283
7.4.7 Basistransformationen????????????????????????????????????????????????????????????????????288
7.4.8 Determinanten????????????????????????????????????????????????????290
7.4.9 Eigenwerte und Eigenvektoren??????????????????????????????????????????????????????????????????????????????????296
7.5 Quotienten *??????????????????????????????????????????????299
7.5.1 Normalteiler und Faktorgruppen??????????????????????????????????????????????????????????????????????????????????????299
7.5.2 Ideale und Restklassenringe????????????????????????????????????????????????????????????????????????????????302
7.5.3 Quotientenräume von Vektorräumen??????????????????????????????????????????????????????????????????????????????????????????303
7.5.4 Isomorphiesätze bezüglich Produkten und Quotienten??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????304
7.6 Allgemeine Algebra *??????????????????????????????????????????????????????????????305
7.6.1 Zwei Beispiele??????????????????????????????????????????????????????305
7.6.2 Signaturen, Terme und Spezifikationen????????????????????????????????????????????????????????????????????????????????????????????????????306
7.6.3 Algebren und Modelle??????????????????????????????????????????????????????????????????307
7.6.4 Initiale Semantik????????????????????????????????????????????????????????????308
7.7 Übungsaufgaben??????????????????????????????????????????????????311
8 Diskrete Wahrscheinlichkeitstheorie????????????????????????????????????????????????????????????????????????????????????????323
8.1 Markante Beispiele??????????????????????????????????????????????????????????323
8.1.1 Die Verdoppelungsstrategie??????????????????????????????????????????????????????????????????????????????323
8.1.2 Das Aufteilungsproblem??????????????????????????????????????????????????????????????????????324
8.1.3 Das False-Positive-Problem??????????????????????????????????????????????????????????????????????????????324
8.1.4 Das Geburtstagsphänomen????????????????????????????????????????????????????????????????????????325
8.1.5 Das Ziegenproblem????????????????????????????????????????????????????????????325
8.1.6 Serien beim Glücksspiel – der Spielerfehlschluss??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????326
8.2 Wahrscheinlichkeit und Wahrscheinlichkeitsmodelle????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????326
8.2.1 Zufallsergebnisse????????????????????????????????????????????????????????????326
8.2.2 Wahrscheinlichkeit und Ereignisse????????????????????????????????????????????????????????????????????????????????????????????327
8.2.3 Wahrscheinlichkeitsräume??????????????????????????????????????????????????????????????????????????328
8.2.4 Reiner Zufall????????????????????????????????????????????????????332
8.3 Abgeleitete Begriffe??????????????????????????????????????????????????????????????333
8.3.1 Unabhängigkeit und bedingte Wahrscheinlichkeit??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????333
8.3.2 Mehrstufige Zufallsexperimente??????????????????????????????????????????????????????????????????????????????????????335
8.3.3 Zufallsvariablen, Verteilungsfunktionen, Erwartungswerte??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????339
8.3.4 Erwartungswerte als Entscheidungsgrundlage??????????????????????????????????????????????????????????????????????????????????????????????????????????????342
8.3.5 Streuungsmaße????????????????????????????????????????????????????343
8.4 Anwendungsbeispiele????????????????????????????????????????????????????????????347
8.4.1 Wahrscheinlichkeitstheoretische Begriffe und Ergebnisse an einem Demonstrationsbeispiel????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????347
8.4.2 Ernüchterung bei der Verdopplungsstrategie??????????????????????????????????????????????????????????????????????????????????????????????????????????????349
8.4.3 Gerechtigkeit beim Aufteilungsproblem????????????????????????????????????????????????????????????????????????????????????????????????????350
8.4.4 Erleichterung beim False Positive????????????????????????????????????????????????????????????????????????????????????????????351
8.5 Prozesse??????????????????????????????????????352
8.5.1 Definition und Beispiele??????????????????????????????????????????????????????????????????????????352
8.5.2 Spezielle Bernoulli-Prozesse??????????????????????????????????????????????????????????????????????????????????352
8.5.3 Die hypergeometrische Verteilung??????????????????????????????????????????????????????????????????????????????????????????356
8.5.4 Markow-Ketten *????????????????????????????????????????????????????????358
8.5.5 Zufallsbewegungen *????????????????????????????????????????????????????????????????362
8.6 Übungsaufgaben??????????????????????????????????????????????????364
Literatur????????????????????????????????371
Stichwortverzeichnis??????????????????????????????????????????????????????377

Weitere E-Books zum Thema: Mathematik - Algorithmik - Arithmetik

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Gewöhnliche Differenzialgleichungen

E-Book Gewöhnliche Differenzialgleichungen
Differenzialgleichungen in Theorie und Praxis Format: PDF

Im Anschluss an Vorlesungen in Analysis und Linearer Algebra folgen an nahezu allen technischen und wirtschaftswissenschaftlich orientierten Studiengängen an Hochschulen und Universitäten als eine…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Weitere Zeitschriften

AUTOCAD Magazin

AUTOCAD Magazin

Die herstellerunabhängige Fachzeitschrift wendet sich an alle Anwender und Entscheider, die mit Softwarelösungen von Autodesk arbeiten. Das Magazin gibt praktische ...

BIELEFELD GEHT AUS

BIELEFELD GEHT AUS

Freizeit- und Gastronomieführer mit umfangreichem Serviceteil, mehr als 700 Tipps und Adressen für Tag- und Nachtschwärmer Bielefeld genießen Westfälisch und weltoffen – das zeichnet nicht ...

Burgen und Schlösser

Burgen und Schlösser

aktuelle Berichte zum Thema Burgen, Schlösser, Wehrbauten, Forschungsergebnisse zur Bau- und Kunstgeschichte, Denkmalpflege und Denkmalschutz Seit ihrer Gründung 1899 gibt die Deutsche ...

Das Hauseigentum

Das Hauseigentum

Das Hauseigentum. Organ des Landesverbandes Haus & Grund Brandenburg. Speziell für die neuen Bundesländer, mit regionalem Schwerpunkt Brandenburg. Systematische Grundlagenvermittlung, viele ...

Der Steuerzahler

Der Steuerzahler

Der Steuerzahler ist das monatliche Wirtschafts- und Mitgliedermagazin des Bundes der Steuerzahler und erreicht mit fast 230.000 Abonnenten einen weitesten Leserkreis von 1 ...

EineWelt

EineWelt

Lebendige Reportagen, spannende Interviews, interessante Meldungen, informative Hintergrundberichte. Lesen Sie in der Zeitschrift „EineWelt“, was Menschen in Mission und Kirche bewegt Man kann ...

FileMaker Magazin

FileMaker Magazin

Das unabhängige Magazin für Anwender und Entwickler, die mit dem Datenbankprogramm Claris FileMaker Pro arbeiten. In jeder Ausgabe finden Sie von kompletten Lösungsschritten bis zu ...