Galileo Computing < openbook >
Galileo Computing - Professionelle Buecher. Auch fuer Einsteiger.
Galileo Computing - Professionelle Buecher. Auch fuer Einsteiger.


Kompendium der Informationstechnik
 von Sascha Kersken
EDV-Grundlagen, Programmierung, Mediengestaltung
Buch: Kompendium der Informationstechnik
gp Kapitel 2 Mathematische und technische Grundlagen
  gp 2.1 Einführung in die Logik
    gp 2.1.1 Aussagen
    gp 2.1.2 Aussageformen
    gp 2.1.3 Logische Verknüpfungen
    gp 2.1.4 Mengenoperationen
  gp 2.2 Informationsspeicherung im Computer
    gp 2.2.1 Bits und Bytes
  gp 2.3 Elektronische Grundlagen
    gp 2.3.1 Einfache Schaltungen
    gp 2.3.2 Zusammengesetzte Schaltungen
  gp 2.4 Automatentheorien und -simulationen
    gp 2.4.1 Algorithmen
    gp 2.4.2 Die Turing-Maschine
    gp 2.4.3 Der virtuelle Prozessor
  gp 2.5 Zusammenfassung

gp

Prüfungsfragen zu diesem Kapitel (extern)

Kapitel 2 Mathematische und technische Grundlagen

Die Logik ist keine Lehre, sondern ein Spiegelbild der Welt.
– Ludwig Wittgenstein

Dieses Kapitel bildet die Grundlage für das Verständnis von Computerprogrammen. Wer die Logik versteht, die den einzelnen Vorgängen in Computersystemen zugrunde liegt, wird geringere Schwierigkeiten haben, mit Software umzugehen. Die konkrete Verwirklichung maßgeblicher logischer Funktionen durch elektronische Bauteile wird hier ebenfalls behandelt. Das Kapitel wird durch eine einfache Prozessorsimulation abgerundet, die sowohl auf dem Papier als auch als Programm auf einem gewöhnlichen PC mit einer einfachen Sprache programmiert werden kann.

Die grundlegenden Arbeitsschritte, die ein Computer ausführt, sind mathematische und logische Operationen: Der Mikroprozessor verknüpft Werte, die ihm ein Programm übergibt oder die er auf Anweisung aus dem Speicher oder von einem Eingabegerät liest, nach verschiedenen Vorschriften. Dazu gehören Grundrechenarten, Vergleiche und Wenn-dann-Beziehungen.


Galileo Computing

2.1 Einführung in die Logik  downtop

Der Begriff Logik ist von dem griechischen Wort logos (Logos) abgeleitet. Die Bedeutung dieses Wortes hat eine lange Geschichte und ist nicht ganz eindeutig. Die Wurzel des Wortes stammt von dem altgriechischen Verb legein (legechte obermengein), das für zunächst für »sammeln« oder »auflesen« steht; es ist verwandt mit lateinisch »legere« und deutsch »lesen«.

Der Logos

Der Beginn des Johannes-Evangeliums wird beispielsweise in den meisten Bibel-Übersetzungen folgendermaßen wiedergegeben: »Im Anfang war das Wort.« Im Original steht »en archi in o logos« – sinngemäß »Im Anfang war der Logos.« Einen aufschlussreichen Überblick über die Übersetzungsversuche für dieses Wort liefert Goethe, der seinen Helden Faust folgendermaßen darüber nachsinnen lässt:

Geschrieben steht: »Im Anfang war das Wort!«
Hier stock ich schon! Wer hilft mir weiter fort?
Ich kann das Wort so hoch unmöglich schätzen,
Ich muß es anders übersetzen,
Wenn ich vom Geiste recht erleuchtet bin.
Geschrieben steht: Im Anfang war der Sinn.
Bedenke wohl die erste Zeile,
Daß deine Feder sich nicht übereile!
Ist es der Sinn, der alles wirkt und schafft?
Es sollte stehn: Im Anfang war die Kraft!
Doch, auch indem ich dieses niederschreibe,
Schon warnt mich was, daß ich dabei nicht bleibe.
Mir hilft der Geist! Auf einmal seh ich Rat
Und schreibe getrost: Im Anfang war die Tat!
– Goethe, Faust 1; Szene 3, Studierzimmer

Von dem Wort logos (Logos) wurde später die Bezeichnung logiki (Logike) abgeleitet – es handelt sich um ein substantiviertes Adjektiv und steht demnach für »etwas, das den Logos betrifft«.

Philosophische Logik

Im Sinne der Philosophie von der Antike bis heute ist Logik allgemein die Lehre von der Richtigkeit des Denkens. Es geht also grob gesprochen um die wahre Erkenntnis. Als Begründer der philosophischen Logik gilt Aristoteles; seither wurden zahlreiche unterschiedliche Wahrheits- und Erkenntnistheorien entwickelt. Sie alle kreisen um existentielle Fragen wie die folgenden: Was wissen wir? Woher wissen wir, dass das, was wir wissen, wahr ist? Was ist Wahrheit? Es würde zu weit führen, an dieser Stelle näher darauf einzugehen; äußerst interessant ist das Thema aber allemal.

Aus der Sicht der Informatik ist die wichtigste Form der Logik die formale Logik. Ihre klassische Form ist die Aussagelogik, die Wissenschaft von der Verknüpfung und Wechselwirkung von Aussagen. Eine Aussage ist dabei ein beliebiger Satz, der eindeutig wahr oder eindeutig falsch ist, dessen Wahrheit also überprüft werden kann. Für die Mathematik wurde die Aussagelogik erst nutzbar, als Gottlob Frege 1879 die Prädikatenlogik entwickelte, eine mathematisch-formale Schreibweise für Aussagen, auf der einige der weiter unten verwendeten mathematischen Sätze basieren. Typische Formulierungen der Prädikatenlogik sind die bekannten Satzanfänge »Für alle x gilt: ...« (fuer alle x gilt x) oder »Es gibt (mindestens) ein x, für das gilt: ...« (es gibt mindestens ein x).


Galileo Computing

2.1.1 Aussagen  downtop

Aussagen sind beispielsweise die folgenden Sätze:

gp  »Der Kölner Dom ist 157 Meter hoch.«
gp  »Der Kölner Dom ist 17 Meter hoch.«
gp  »Ich bin 17 Meter groß.«

Die folgenden Sätze sind dagegen aus verschiedenen Gründen keine Aussagen:

gp  »Der Kölner Dom ist schön.« – eine subjektive Meinungsäußerung, die für den einen wahr und für den anderen falsch sein kann.
gp  »Ist heute Freitag?« – eine Frage ist keine Aussage; in diesem Fall kann die Antwort eine Aussage sein.
gp  »Wie geht es dir?« – ebenfalls eine Frage, allerdings ist hier auch die Antwort keinesfalls eine Aussage (sie ergibt wieder eine subjektive Meinungsäußerung).

Mathematische Aussagen

Die Art von Aussagen, die im Zusammenhang mit Informatik und Computern besonders interessant ist, sind die mathematischen Aussagen. Eine mathematische Aussage ist ein System, das aus Termen (mathematischen Ausdrücken) besteht. Ein Term ist im einfachsten Fall eine numerische Konstante wie beispielsweise 100 oder –3,25, in komplexeren Fällen eine arithmetische Verknüpfung wie etwa 3 + 5, die sich in einen konkreten Wert auflösen lassen muss. Eine vollständige mathematische Aussage ist ein Vergleich zwischen Termen, der zwei mögliche Formen annehmen kann:

gp  Die Gleichung ist eine wahre Aussage, wenn die beiden verknüpften Terme den gleichen Wert haben.
gp  Die Ungleichung ist dagegen dann eine wahre Aussage, wenn die Werte der beiden verknüpften Terme auf eine vorgegebene Weise unterschiedlich sind.

Beispiele für mathematische Aussagen sind folgende:

gp  5 + 6 = 6 + 5 – eine Gleichung.
gp  5 + 6 < 6 + 5 – eine Ungleichung; die Beziehung lautet in diesem Fall »ist kleiner als«.

Sowohl sprachliche als auch mathematische Aussagen können, wie bereits erwähnt, wahr oder falsch sein. Hier sehen Sie einige Beispiele für wahre und falsche Aussagen:

gp  »Der Kölner Dom ist 17 Meter hoch.« – falsche sprachliche Aussage.
gp  »Ein Tag hat 24 Stunden.« – wahre sprachliche Aussage.
gp  5 > 7 – falsche mathematische Aussage (Ungleichung).
gp  7 > 5 – wahre mathematische Aussage (Ungleichung).
gp  3 + 4 = 34 – falsche mathematische Aussage (Gleichung).
gp  3 + 4 = 7 – wahre mathematische Aussage (Gleichung).

Galileo Computing

2.1.2 Aussageformen  downtop

Die in der Mathematik weit verbreiteten Formeln und verallgemeinerten Gleichungen mit Platzhaltern (Variablen oder Unbekannten) sind keine Aussagen. Schließlich gilt für sie die Bedingung nicht, dass sie eindeutig wahr oder falsch sein müssen. Beispielsweise lässt sich die allgemeine Gleichung a + b = 3 mit unendlich vielen Werten zur wahren oder auch zur falschen Aussage machen:

gp  a = 2; b = 1 oder a = 3,5; b = -0,5 ergeben eine wahre Aussage.
gp  a = 3; b = 5 oder a = 0,75; b = 0,2 ergeben eine falsche Aussage.

Ein Wert, der in eine Aussageform eingesetzt wird und diese zu einer wahren Aussage macht, wird als Lösung dieser Aussageform beziehungsweise genauer als Teil ihrer Lösungsmenge bezeichnet.

Gleichungen und Ungleichungen lösen

Das folgende Beispiel zeigt, wie die Lösungsmenge einer linearen Gleichung mit einer Unbekannten bestimmt wird:

2x + 7 = 21 | –7
2x = 14 | :2
x = 7

Lineare Gleichungen besitzen in der Regel genau eine Lösung. Komplexere Gleichungssysteme können dagegen auch Lösungsmengen besitzen, die aus keiner, aus mehreren oder aus unendlich vielen Lösungen bestehen.

Das Lösen von Ungleichungen ist der Versuch, eine Menge von Werten zu bestimmen, die in die Aussageform einer Ungleichung eingesetzt werden können, um eine wahre Aussage zu erhalten:

2x + 7 < 21 | –7
2x < 14 | :2
x < 7

Die Lösungsmenge der Ungleichung ist die Menge aller x, für die gilt, dass x kleiner als 7 ist. Mathematisch wird dies folgendermaßen ausgedrückt:

L = {x | x < 7}
Galileo Computing

2.1.3 Logische Verknüpfungen  downtop

Nicht immer werden nur einzelne Aussagen betrachtet. Es ist üblich und oft notwendig, mehrere Aussagen mit Hilfe verschiedener logischer Verknüpfungen zu verbinden. Dazu gehören sowohl logische Schlussfolgerungen (Wenn-dann-Beziehungen) als auch einfache Und- sowie Oder-Verknüpfungen.

Boolesche Algebra

Das gesamte Fachgebiet der logischen Verknüpfungen wird auch als boolesche Algebra bezeichnet, benannt nach dem britischen Mathematiker George Boole, der bereits im 19. Jahrhundert eine Algebra der binären logischen Verknüpfungen entwickelte.

Logische Schlussfolgerungen

Die Schlussfolgerung, das Lieblingsspielzeug der philosophischen Logik, ist eine Wenn-dann-Beziehung zwischen Aussagen. Auch Computerprogramme arbeiten mit dieser Art der Logik, weil sie oft anhand bestimmter Bedingungen Entscheidungen treffen müssen.

In der sprachlichen Aussagelogik sieht eine Schlussfolgerung beispielsweise folgendermaßen aus:

1. Es regnet.
       
2. Die Straße wird nass.
       

Schlussfolgerung: Wenn es regnet, dann wird die Straße nass.

Oder in formaler Schreibweise: Es regnet. daraus folgt Die Straße wird nass. Das Zeichen daraus folgt wird als »daraus folgt« aufgelöst.

Die direkte Umkehrung einer solchen Schlussfolgerung ist unzulässig: Eine Aussage wie

    A daraus folgt B (aus A folgt B)
       

bedingt nicht den folgenden Schluss:

    B daraus folgt A (aus B folgt A)
       

Sprachlich formuliert gilt also nicht die folgende Schlussfolgerung: Wenn die Straße nass wird, regnet es. Schließlich kann es zahlreiche Gründe dafür geben, warum eine Straße nass wird.

Umkehrschluss

Den korrekten, zulässigen Umkehrschluss bildet dagegen die verneinte Umkehrung:

    nichtB daraus folgt nichtA (aus nicht-B folgt nicht-A)
       

Auf das Sprachbeispiel übertragen: Wenn die Straße nicht nass wird, dann regnet es nicht. Dieser Satz ist intuitiv einleuchtend und richtig.

Zur Verdeutlichung sehen Sie hier alle erlaubten Umkehrschlüsse im Überblick:

1. A daraus folgt B; Umkehrung: nichtB daraus folgt nichtA Beispiel: Wenn es regnet, dann wird die Straße nass. Umkehrung: Wenn die Straße nicht nass wird, dann regnet es nicht.
       
2. A daraus folgt nichtB; Umkehrung: B daraus folgt nichtA Beispiel: Wenn die Sonne scheint, dann ist nicht Nacht. Umkehrung: Wenn es Nacht ist, dann scheint nicht die Sonne.1
       
3. nichtA daraus folgt B; Umkehrung: nichtB daraus folgt A Beispiel: Wenn nicht Wochenende, Feiertag oder Urlaub ist, dann muss ich arbeiten. Umkehrung: Wenn ich nicht arbeiten muss, dann ist Wochenende, Feiertag oder Urlaub.
       
4. nichtA daraus folgt nichtB; Umkehrung: B daraus folgt A Beispiel: Wenn ich nicht den Führerschein habe, dann darf ich nicht Auto fahren. Umkehrung: Wenn ich Auto fahren darf, dann habe ich den Führerschein.
       

Und- und Oder-Verknüpfungen

Die beiden Verknüpfungen Und und Oder (AND und OR) sind die wichtigsten Mittel zur Verbindung mehrerer Aussagen oder Bedingungen.

Und-Verknüpfung

Werden mehrere Aussagen durch Und verknüpft (Konjunktion), ergibt sich nur dann eine wahre Aussage, wenn alle Teilaussagen wahr sind.

Die Verknüpfung A und B ist also nur dann wahr, wenn sowohl A als auch B wahre Aussagen sind.

Sprachlich kann dies sehr gut durch zusammengesetzte Wenn-Bedingungen bei der Schlussfolgerung gezeigt werden. Zum Beispiel:

Wenn die Glühbirne funktioniert und der Lichtschalter eingeschaltet wird, dann leuchtet das Licht. Oder als einzelne Aussagen:

1. Die Glühbirne funktioniert.
       
2. Der Lichtschalter ist eingeschaltet.
       
3. Das Licht leuchtet.
       

Die erste und die zweite Aussage werden hier durch Und verknüpft und ergeben so die dritte Aussage:

Die Glühbirne funktioniert und der Lichtschalter wird eingeschaltet daraus folgt das Licht leuchtet.

Schematisch lassen sich solche Verknüpfungen am einfachsten durch eine so genannte Wahrheitstabelle darstellen. In einer solchen Tabelle (wie übrigens auch bei den Abläufen innerhalb eines Computers) wird eine wahre Aussage durch den Wert 1 und eine falsche Aussage durch die 0 dargestellt. Die Wahrheitstabelle für Und sieht also folgendermaßen aus:


Tabelle 2.1   Wahrheitstabelle für die Und-Verknüpfung

und 0 1
0 0 0
1 0 1

Oder-Verknüpfung

Werden dagegen mehrere Aussagen durch Oder verknüpft (Disjunktion), dann ist die Gesamtaussage wahr, wenn mindestens eine der Teilaussagen zutrifft.

Die Beziehung A oder B ist also wahr, wenn A wahr ist, wenn B wahr ist, oder auch, wenn A und B wahr sind. Hier sehen Sie zunächst wieder ein sprachliches Beispiel:

Wenn ich sechs Richtige im Lotto habe oder bei einer Quiz-Sendung gewinne, dann bin ich Millionär. Die einzelnen Aussagen sind folgende:

1. Ich habe sechs Richtige im Lotto.
       
2. Ich gewinne bei einer Quiz-Sendung.
       
3. Ich bin Millionär.
       

Formal sieht diese Oder-Verknüpfung der beiden ersten Aussagen so aus:

Ich habe sechs Richtige im Lotto oder ich gewinne bei einer Quiz-Sendung daraus folgt ich bin Millionär. Es ist egal, ob nur eine der beiden Voraussetzungen zutrifft oder ob beide wahr sind – in beiden Fällen stimmt die Schlussfolgerung.

Hier wieder die entsprechende schematische Darstellung als Wahrheitstabelle.


Tabelle 2.2   Wahrheitstabelle für die Oder-Verknüpfung

oder 0 1
0 0 1
1 1 1

Die folgende Tabelle zeigt eine Übersicht der Und- und Oder-Verknüpfungen aller vier möglichen logischen Belegungen zweier Wahrheitswerte A und B sowie all ihrer Verneinungen.


Tabelle 2.3   Wahrheitstabelle aller normalen und verneinten Und- beziehungsweise Oder-Verknüpfungen

Verknüpfung A=0, B=0 A=0, B=1 A=1, B=0 A=1, B=1
A und B 0 0 0 1
A oder B 0 1 1 1
nichtA und B 0 1 0 0
nichtA oder B 1 1 0 1
A und nichtB 0 0 1 0
A oder nichtB 1 0 1 1
nicht (A und B) 1 1 1 0
nicht (A oder B) 1 0 0 0

 

Aus den Verhältnissen in Tabelle 2.3 ergeben sich die beiden folgenden wichtigen Äquivalenzen, die als DeMorgan-Theorem bezeichnet werden:

    nichtA und nichtB aequivalent nicht (A oder B)
       
    nichtA oder nichtB aequivalent nicht (A und B)
       

Diese Beziehungen müssen Sie direkt beim Programmieren beachten, wenn Sie Wenn-dann-Beziehungen formulieren.

XOR-Verknüpfung

Zu guter Letzt gibt es eine dritte wichtige logische Verknüpfung, die als Exklusiv-Oder bezeichnet wird. Da sie in der Mathematik nicht verwendet wird, besitzt sie kein traditionelles Zeichen, sondern wird in der Regel durch den abgekürzten englischen Namen XOR bezeichnet. Auch in den meisten Programmiersprachen existiert kein XOR-Operator.

Eine XOR-Verknüpfung zweier Aussagen ist nur dann wahr, wenn genau eine Teilaussage wahr ist. Es ist recht schwierig, ein anschauliches sprachliches Beispiel für diese Verknüpfung zu finden. Das XOR steht im Grunde für ein »Entweder-Oder«: Wenn ich entweder mit dem Bus oder mit dem Auto fahre, gelange ich zur Arbeit (ich kann auf keinen Fall mit Bus und Auto gleichzeitig fahren).

Tabelle 2.4 zeigt die möglichen Ergebnisse der XOR-Verknüpfung.


Tabelle 2.4   Wahrheitstabelle für die XOR-Verknüpfung

XOR 0 1
0 0 1
1 1 0

Vergleichsoperationen

Diese Art logischer Verknüpfungen erzeugt Aussagen durch die Überprüfung von Termen auf Gleichheit oder Ungleichheit. Die resultierenden Aussagen können also wahr oder falsch sein.

gp  Gleichheit:
    A = B (A gleich B) ist wahr, wenn A den gleichen Wert hat wie B.
       
gp  Ungleichheit:
    A ungleich B (A ungleich B) ist wahr, wenn A einen anderen Wert hat als B.
       
gp  Ungleichheit mit Richtungsangabe:
    A < B (A ist kleiner als B) ist wahr, wenn A einen geringeren Wert hat als B.
       
    A > B (A ist größer als B) ist wahr, wenn A einen höheren Wert hat als B.
       
    A kleiner oder gleich B (A ist kleiner oder gleich B) ist wahr, wenn A entweder einen geringeren Wert als B oder den gleichen Wert wie B hat.
       
    A groesser oder gleich B (A ist größer oder gleich B) ist wahr, wenn A entweder einen höheren Wert als B oder den gleichen Wert wie B hat.
       
    A kleiner oder gleich B ist eine Kurzfassung für: A < B oder A = B
       
    A kleiner oder gleich B ist entsprechend eine Kurzfassung für: A > B oder A = B
       

Umgekehrte Vergleichsoperationen

Interessant sind einige Umkehrungen (gegenteilige Aussagen) der Vergleichsoperationen:

gp  Die Umkehraussage von A = B ist A ungleich B.
gp  A < B besitzt die Umkehraussage A kleiner oder gleich B.
gp  A > B hat schließlich die Umkehraussage A kleiner oder gleich B.

Tabelle 2.5 verdeutlicht dies an Beispielen für den Vergleich verschiedener ganzzahliger Werte. Beachten Sie, dass die verknüpften Werte ganze Zahlen, die Ergebnisse (1 oder 0) aber Wahrheitswerte sind.


Tabelle 2.5   Beispiele für Vergleichsoperationen

Verknüpfung A=2, B=2 A=2, B=3 A=3, B=2
A = B

1

0

0

A ungleich B

0

1

1

A < B

0

1

0

A > B

0

0

1

A kleiner oder gleich B

1

1

0

A kleiner oder gleich B

1

0

1


Logische Verknüpfungen in Computerprogrammen

Da Zeichen wie ungleich, kleiner oder gleich oder oder nicht zum ASCII-Zeichensatz (dem ursprünglichen Standard-Computerzeichensatz) gehören, haben sich die Entwickler der verschiedenen Programmiersprachen andere Zeichen beziehungsweise Zeichenkombinationen ausgedacht. Ärgerlicherweise sind diese Bezeichnungen in den verschiedenen Sprachen nicht einheitlich. Tabelle 2.6 zeigt die Schreibweisen der Programmiersprachen C und Pascal im Vergleich. Beachten Sie, dass die C-Schreibweise in einer ganzen Reihe von Sprachen verwendet wird, beispielsweise C++, Java, JavaScript, Perl, PHP und so weiter. Die Pascal-Schreibweise verwenden dagegen auch einige BASIC-Dialekte.


Tabelle 2.6   Schreibweise logischer Operationen in verschiedenen Programmiersprachen

Mathematik C-Schreibweise Pascal-Schreibweise
a = b (Vergleich) a == b a = b
a = b (Wertzuweisung) a = b a := b
a ungleich b a != b a <> b
a < b a < b a < b
a > b a > b a > b
a kleiner oder gleich b a <= b a <= b
a kleiner oder gleich b a >= b a >= b
a und b a && b a AND b
a oder b a || b a OR b

Die in der Tabelle aufgeführte Wertzuweisung betrifft eine Besonderheit von Variablen in Programmiersprachen: Während eine Variable in der Mathematik lediglich ein Platzhalter ist, der für beliebige Werte stehen kann, ist sie in einer Programmiersprache ein Speicherplatz, der jederzeit einen bestimmten, wohl definierten Wert enthält. Die Wertzuweisungsoperation dient dazu, ihr einen solchen Wert zuzuteilen.


Galileo Computing

2.1.4 Mengenoperationen  toptop

Eine spezielle Form der logischen Verknüpfung beschäftigt sich mit den Beziehungen zwischen einem einzelnen Element und einer Menge beziehungsweise zwischen zwei Mengen. Eine Menge ist eine Gruppe mehrerer Werte, die entweder als Abfolge einzelner Zahlen oder durch bestimmte Regeln definiert wird.

Beachten Sie für die Umsetzung im Computer, dass Mengenoperationen nicht in jeder Programmiersprache eingebaut sind. In Kapitel 6, Konzepte der Programmierung, werden allerdings einige Strategien vorgestellt, wie man Listen oder Mengen in verschiedenen Sprachen erzeugen und damit arbeiten kann.

Beziehungen zwischen Mengen und einzelnen Werten

Ein Wert ist Element einer Menge, wenn dieser Wert in der Menge vorkommt. Ein Wert ist nicht Element einer Menge, wenn dieser Wert nicht in der Menge vorkommt.

Betrachten Sie zum Beispiel die Menge M, für die die folgende Definition gilt:

M := {3; 4; 5}

Es gelten die folgenden Elementbeziehungen:

gp  3 ist Element von M. Formale Schreibweise: 3 ist element von M
gp  2 ist nicht Element von M. Formale Schreibweise: 2 ist nicht element von M.

Eine weitere Menge P sei folgendermaßen definiert:

P := {x|x < 5 und x ist element von R}

P ist also die Menge aller x, für die gilt: x ist kleiner als 5 und x ist Element der Menge der reellen Zahlen. Für diese Menge gelten die folgenden Elementbeziehungen:

4 ist element von P, aber 5 ist nicht element von P.

Beziehungen zwischen zwei Mengen

Eine Menge M heißt Teilmenge einer Menge N, wenn jedes Element von M auch Element von N ist, wenn also für jedes x ist element von M auch x ist element von N gilt.

Eine Menge M ist nicht Teilmenge einer Menge N, wenn es in M mindestens ein Element gibt, das nicht auch Element von N ist. Es gibt also mindestens ein x ist element von M, für das gilt: x ist nicht element von N.

Betrachten Sie beispielsweise die folgenden Mengendefinitionen:

M := {3; 4; 5; 6} N := {2; 4; 5; 6} P := {3; 4; 5; 6; 7}

Es gelten die folgenden Mengenbeziehungen:

    M echte teilmenge P (M ist Teilmenge von P)
       
    N nicht teilmenge P (N ist nicht Teilmenge von P)
       

Echte Teilmengen

Übrigens ist die angegebene Teilmengendefinition ungenau: Die oben beschriebene Beziehung könnte ebenso gut bedeuten, dass zwei identische Mengen beschrieben werden. Deshalb heißt eine Menge M echte Teilmenge einer Menge N, wenn folgende Bedingungen gelten:

gp  Für jedes x ist element von M gilt auch x ist element von N.
gp  Es existiert mindestens ein x ist element von N, für das x ist nicht element von M gilt.

Wenn man es genau nimmt, wird nur für diese echte Teilmenge die Schreibweise M echte teilmenge N verwendet. Für die weiter oben definierte allgemeine Teilmenge, bei der M = N als Variante zulässig ist, wird stattdessen die Formulierung M teilmenge oder gleich N (Teilmenge oder gleich) verwendet.

Wenn M teilmenge oder gleich N gilt, wird N übrigens umgekehrt als Obermenge von M bezeichnet. Geschrieben wird dies als N obermenge oder gleich M (N ist Obermenge von oder gleich M). Die strengere Form M echte teilmenge N (echte Teilmenge) bedeutet entsprechend, dass N echte Obermenge von M ist: N echte obermenge M.

Eine Abfolge von Beziehungen echter Teilmengen beziehungsweise Obermengen lässt sich hervorragend an den offiziellen Zahlenmengen der Mathematik demonstrieren. Dies sind im Einzelnen (von der speziellsten bis zur allgemeinsten) folgende:

1. Die Menge der natürlichen Zahlen. Natürliche Zahlen sind alle Zahlen, mit denen sich Anzahlen ausdrücken lassen. Intuitiv ist diese Menge folgendermaßen definiert:
       
natürliche Zahlen = {1; 2; 3; 4; ...}
    Die 0 gehört übrigens nicht zur Menge der natürlichen Zahlen, allerdings gibt es die spezielle Menge natürliche Zahlen0, die zusätzlich die 0 enthält.
       
2. Die Menge der ganzen Zahlen. Ebenso wie die natürlichen Zahlen sind auch die ganzen Zahlen intuitiv betrachtet Zahlen ohne Nachkommastellen, allerdings mitsamt 0 und negativen Zahlen. Es handelt sich um die folgende Menge:
       
ganze Zahlen = {...; -3; -2; -1; 0; 1; 2; 3; ...}
3. Die Menge der rationalen Zahlen. Es handelt sich um sämtliche Zahlen, die durch die Division zweier ganzer Zahlen gebildet werden können. Dies sind neben den ganzen Zahlen selbst alle abbrechenden und alle periodischen Dezimalbrüche. Formal lautet die Definition dieser Menge folgendermaßen:
       
rationale Zahlen = {x | x = /q und p ist element von ganze Zahlen und q ist element von ganze Zahlen und q ungleich 0}
    Bemerkenswert an dieser Menge ist, dass zwischen zwei rationalen Zahlen immer unendlich viele weitere rationale Zahlen liegen. Bei den natürlichen und ganzen Zahlen ist das anders: Da zwei Elemente dieser Mengen jeweils einen festgelegten numerischen Abstand voneinander haben (1), ist die Anzahl der Elemente zwischen zweien von ihnen jeweils endlich und steht fest.
       
4. Die Menge der reellen Zahlen. Neben den abbrechenden und den periodischen Dezimalbrüchen gibt es auch unendlich viele nichtabbrechende, nichtperiodische. Es handelt sich also um Zahlen mit unendlich vielen Nachkommastellen ohne Wiederholung (Periode). Beispiele sind etwa die Kreiszahl Pi (3,1415926…), die Eulersche Zahl e (2,718281828…) – die Basis des natürlichen Logarithmus – oder Wurzel2 (1,41421356…).
       
    Formal haben diese Zahlen miteinander gemeinsam, dass ihr Quadrat eine positive Zahl oder 0 ist:
       
reelle Zahlen := { x | x kleiner oder gleich 0 }
    Beachten Sie, dass reelle Zahlen im Computer nicht dargestellt werden können, übrigens ebenso wenig wie periodische Dezimalbrüche. Wie weiter unten ausgeführt, verwenden Rechner eine bestimmte Anzahl von Bits und können Fließkommazahlen auf diese Weise mit einer bestimmten Genauigkeit, also nur mit einer endlichen Anzahl von Stellen, speichern.
       
5. Die Menge der komplexen Zahlen. Eine Zahl mit negativem Quadrat ist intuitiv nicht vorstellbar (da sowohl positive als auch negative Zahlen, wenn man sie mit sich selbst multipliziert, zu einem positiven Ergebnis führen). Dennoch ist es zum Beispiel für mathematische Gedankenexperimente oder bestimmte Berechnungen aus der theoretischen Physik erforderlich, die Wurzeln negativer Zahlen zu berechnen.
       
    Zu diesem Zweck werden die imaginären (oder irreellen) Zahlen eingeführt. Sie reduzieren das Problem der Wurzel aus negativen Zahlen auf die irrationale Komponente i, die als Wurzel-1 definiert ist (und natürlich nicht durch eine normale Berechnung aufgelöst werden kann). Jede irreelle Zahl ist deshalb als Vielfaches von i definiert.
       
    Die reellen und die irreellen Zahlen werden zusammengenommen als komplexe Zahlen (komplexe Zahlen) bezeichnet und bilden die vollständigste Zahlenmenge der allgemeinen Mathematik.
       

Jede der fünf hier genannten Mengen enthält die vorige. Die verkettete Beziehung von Teil- beziehungsweise Obermengen lautet also:

natürliche Zahlen echte teilmenge ganze Zahlen echte teilmenge rationale Zahlen echte teilmenge reelle Zahlen echte teilmenge komplexe Zahlen
komplexe Zahlen echte obermenge reelle Zahlen echte obermenge rationale Zahlen echte obermenge ganze Zahlen echte obermenge natürliche Zahlen

Verknüpfungen von Mengen

Ähnlich, wie Sie einzelne Werte durch arithmetische Operatoren oder durch logische Verknüpfungen miteinander verbinden können, existieren spezielle Mengenoperationen, deren Ergebnis eine Verknüpfung der ursprünglichen Mengen ist.

gp  Die Schnittmenge. Eine Schnittmenge M SchnittmengeSchnittmenge N zweier Mengen M und N enthält alle diejenigen Elemente x, für die x ist element von M und x ist element von N gilt. Hier sehen Sie ein Beispiel:
M := {1; 2; 3; 4}
N := {4; 5; 6; 7}
M Schnittmenge N = {4}
    Beachten Sie, dass das Ergebnis nicht 4 lautet, sondern »die Menge, in der nur die 4 enthalten ist«. Eine Schnittmenge ist also auch dann eine Menge, wenn sie nur ein Element enthält. Wenn die beiden verknüpften Mengen keine gemeinsamen Elemente besitzen, geschieht sogar Folgendes:
       
M := {1; 2; 3}
N := {4; 5; 6}
M Schnittmenge N = { } = Æ
    { } beziehungsweise leere menge wird dabei als leere Menge bezeichnet.
       
gp  Die Vereinigungsmenge. Eine Vereinigungsmenge M Vereinigungsmenge N zweier Mengen M und N ist die verbundene Menge aller x ist element von M und aller y ist element von N. Hier ein Beispiel:
M := {1; 2; 3; 4}
N := {4; 5; 6; 7}
M Vereinigungsmenge N = {1; 2; 3; 4; 5; 6; 7}
gp  Die Restmenge. Wenn aus der Menge M alle Elemente einer Menge N entfernt werden (M \ N, gesprochen »M ohne N«), dann ist das Ergebnis eine Restmenge. Beispiel:
M := {1; 2; 3; 4} N := {3; 4; 5} M \ N = {1; 2}




  

Einstieg in PHP 5

Einstieg in Java

C von A bis Z

Einstieg in C++

Einstieg in Linux

Einstieg in XML

Apache 2




Copyright © Galileo Press GmbH 2004
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das <openbook> denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.


[Galileo Computing]

Galileo Press GmbH, Gartenstraße 24, 53229 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de