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.

2.1 Einführung in die Logik 

Der Begriff Logik ist von dem griechischen Wort (Logos) abgeleitet. Die Bedeutung dieses Wortes hat eine lange Geschichte und ist nicht ganz eindeutig. Die Wurzel des Wortes stammt von dem altgriechischen Verb (legin), 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 »« – 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:

Von dem Wort (Logos) wurde später die Bezeichnung (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: ...« ( x) oder »Es gibt (mindestens) ein x, für das gilt: ...« ( x).

2.1.1 Aussagen 

Aussagen sind beispielsweise die folgenden Sätze:

»Der Kölner Dom ist 157 Meter hoch.«

»Der Kölner Dom ist 17 Meter hoch.«

»Ich bin 17 Meter groß.«

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

»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.

»Ist heute Freitag?« – eine Frage ist keine Aussage; in diesem Fall kann die Antwort eine Aussage sein.

»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:

Die Gleichung ist eine wahre Aussage, wenn die beiden verknüpften Terme den gleichen Wert haben.

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:

5 + 6 = 6 + 5 – eine Gleichung.

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:

»Der Kölner Dom ist 17 Meter hoch.« – falsche sprachliche Aussage.

»Ein Tag hat 24 Stunden.« – wahre sprachliche Aussage.

5 > 7 – falsche mathematische Aussage (Ungleichung).

7 > 5 – wahre mathematische Aussage (Ungleichung).

3 + 4 = 34 – falsche mathematische Aussage (Gleichung).

3 + 4 = 7 – wahre mathematische Aussage (Gleichung).

2.1.2 Aussageformen 

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:

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

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:

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:

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:

2.1.3 Logische Verknüpfungen 

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:

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

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

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

	A B (aus A folgt B)

bedingt nicht den folgenden Schluss:

	B 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:

	B A (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 B; Umkehrung: B A Beispiel: Wenn es regnet, dann wird die Straße nass. Umkehrung: Wenn die Straße nicht nass wird, dann regnet es nicht.

2.	A B; Umkehrung: B A Beispiel: Wenn die Sonne scheint, dann ist nicht Nacht. Umkehrung: Wenn es Nacht ist, dann scheint nicht die Sonne.1

3.	A B; Umkehrung: B 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.	A B; Umkehrung: B 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 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:

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

Die Glühbirne funktioniert der Lichtschalter wird eingeschaltet 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

	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 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:

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

Ich habe sechs Richtige im Lotto ich gewinne bei einer Quiz-Sendung 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

	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 B	0	0	0	1
A B	0	1	1	1
A B	0	1	0	0
A B	1	1	0	1
A B	0	0	1	0
A B	1	0	1	1
(A B)	1	1	1	0
(A 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:

	A B (A B)

	A B (A 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.

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.

Gleichheit:

Ungleichheit:

	A B (A ungleich B) ist wahr, wenn A einen anderen Wert hat als B.

Ungleichheit mit Richtungsangabe:

	A 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 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 B ist eine Kurzfassung für: A < B A = B

	A B ist entsprechend eine Kurzfassung für: A > B A = B

Umgekehrte Vergleichsoperationen

Interessant sind einige Umkehrungen (gegenteilige Aussagen) der Vergleichsoperationen:

Die Umkehraussage von A = B ist A B.

A < B besitzt die Umkehraussage A B.

A > B hat schließlich die Umkehraussage A 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 B	0	1	1
A < B	0	1	0
A > B	0	0	1
A B	1	1	0
A B	1	0	1

Logische Verknüpfungen in Computerprogrammen

Da Zeichen wie , 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 b	a != b	a <> b
a < b	a < b	a < b
a > b	a > b	a > b
a b	a <= b	a <= b
a b	a >= b	a >= b
a b	a && b	a AND b
a 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.

2.1.4 Mengenoperationen 

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:

Es gelten die folgenden Elementbeziehungen:

3 ist Element von M. Formale Schreibweise: 3 M

2 ist nicht Element von M. Formale Schreibweise: 2 M.

Eine weitere Menge P sei folgendermaßen definiert:

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:

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 M auch x 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 M, für das gilt: x N.

Betrachten Sie beispielsweise die folgenden Mengendefinitionen:

Es gelten die folgenden Mengenbeziehungen:

	M P (M ist Teilmenge von P)

	N 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:

Für jedes x M gilt auch x N.

Es existiert mindestens ein x N, für das x M gilt.

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

Wenn M N gilt, wird N übrigens umgekehrt als Obermenge von M bezeichnet. Geschrieben wird dies als N M (N ist Obermenge von oder gleich M). Die strengere Form M N (echte Teilmenge) bedeutet entsprechend, dass N echte Obermenge von M ist: N 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:

	Die 0 gehört übrigens nicht zur Menge der natürlichen Zahlen, allerdings gibt es die spezielle Menge 0, die zusätzlich die 0 enthält.

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 (3,1415926…), die Eulersche Zahl e (2,718281828…) – die Basis des natürlichen Logarithmus – oder 2 (1,41421356…).

	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 -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 () 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:

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.

Die Schnittmenge. Eine Schnittmenge M N zweier Mengen M und N enthält alle diejenigen Elemente x, für die x M und x N gilt. Hier sehen Sie ein Beispiel:

	{ } beziehungsweise wird dabei als leere Menge bezeichnet.

Die Vereinigungsmenge. Eine Vereinigungsmenge M N zweier Mengen M und N ist die verbundene Menge aller x M und aller y N. Hier ein Beispiel:

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: