digitale Logik - Für Fachfremde und Gäste

Mich haben die Erkenntnisse aus dem Uni-Kurs so fasziniert, dass ich hier versuchen möchte einen kleinen spannenden Teil daraus in einer sehr einfachen Form zu vermitteln.

Computer sind heutzutage kaum noch wegzudenken und fast überall begegnen uns elektronische Schaltungen, die irgend etwas steuern. Doch was ist des Pudels Kern von all diesen Dingen?

Die Antwort ist: Logik. Um genau zu sein ist es die mathematische Logik. Diese Logik besteht aus den zwei Zuständen wahr und falsch und ein paar Operatoren (sowas wie Plus und Mal). Dieses wahr und falsch wird auch gerne mit den Werten 1 und 0 bezeichnet und in der Realität durch Strom an und Strom aus realisiert. Anders als in der üblichen Mathematik gibt es in der Logik verschiedene Operatoren, mit denen man jeweils das gleiche ausdrücken kann.

So sind zum Beispiel beide Aussagen richtig, da man beides ineinander umwandeln kann:

“Ein Computer kann nur Addieren und Multiplizieren”
“Ein Computer kennt nur und, oder und nicht.”

Warum dieses Beispiel? Weil mir schon als kleines Kind erklärt wurde, dass ein Computer nur die Zahlen 0 und 1 entweder addieren oder multiplizieren kann. Später habe ich dann mal gehört, dass der Computer nur und und oder beherrscht...

Doch wie genau macht der Computer jetzt was daraus? Man muss diese Frage in mehrere Teile zerlegen.

Wie bekommt es der Computer hin unterschiedliche Aufgaben zu erledigen?

Dafür kann man sich zum Beispiel eine Bahnhofsanlage mit Schienen, Weichen und Zügen vorstellen. An einigen Stellen sind Signale aufgestellt um Züge stoppen zu können. Auf den Zügen befinden sich dann die Daten, zum Beispiel Zahlen.

Der Bahnhof ist so gebaut, das auf Gleis 1 addiert, auf Gleis 2 multipliziert und auf Gleis 3 die Wurzel gezogen wird.

Möchte man also zwei Zahlen addieren, schickt man auf einen extra-Gleis einen Zug zum Bahnhof, der dem Weichensteller sagt, wie er die Weichen zu stellen hat. In diesem fall also so, dass ein Zug mit Zahlen zu Gleis 1 fährt.

Jetzt bekommt der Zug das Signal, dass er losfahren darf. Er fährt zu dem Gleis, lässt sich dort die Zahlen addieren und fährt dann weiter zum Ziel.

Wofür braucht man nun einen Takt?

Bei diesen Vorgängen muss sichergestellt sein, dass die Weichen so lange gestellt bleiben, bis der Zug am Ziel angekommen ist. Aber es muss auch sichergestellt sein, dass die Weichen rechtzeitig für den nächsten Zug eingestellt werden, der vielleicht woanders hin will. Idealerweise weiß man, wie lange ein Zug braucht und mit ein wenig Sicherheitstoleranz lässt sich gefahrlos eine Zeitspanne bestimmen. In diesem Rythmus schaltet dann das Signal vor der Weichen-Anlage auf „Freie Fahrt” und lässt immer genau einen Zug durch. Genau so funktioniert ein Computer im Prinzip auch. Wie die weichen gestellt werden müssen, entscheidet das Computer-Programm und der Rythmus in dem die Daten „durchgelassen” werden ist der Takt. Ohne ihn würde man nie sicher sagen können, wann welcher Zug wo ist und ob man gerade gefahrlos die Weiche umstellen kann.

Was ist Übertakten?

Beim Übertakten werden die Sicherheitstoleranzen eingeschränkt und/oder der Zug dazu gebracht schneller zu fahren.

Wie löst der Computer nun eine Teilaufgabe?

Die Frage ist also, wie nun ein Gleis bzw. Bahnsteig aussieht.
Wie am Anfang erwähnt, würden zwei Gleise ausreichen, eines zum Addieren und eines zum Multiplizieren. Um aber schneller zu sein, hat ein Computer wesentlich mehr Gleise. Dabei gibt es eine Unterscheidung zwischen Computern mit wenigen kurzen Bahnsteigen und Computern mit vielen langen. Die einen sind schneller in der Abfertigung (schnellerer Takt), die anderen können mehr auf einmal erledigen.

Wie sieht nun das Gleis des addierens aus?

Eine Zahl besteht für den Computer nur aus 0en und 1en. Eine 11 wird zu 010011, eine 3 zu 000011. Das Addieren ist so definiert, dass 1+0=1 ist und 1+1=0, aber 1 gemerkt wird (wie bei „9+1=0, 1 gemerkt” in der Grundschule)

Betrachtet werden nur die markierten Ziffern!

  1. 01011+00011   =00000 1 gemerkt
  2. 01011+00011 +1=00010 1 gemerkt
  3. 01011+00011 +1=00100
  4. 01011+00011   =01000
  5. 00011+00011   =00000
  6.                =01110
01110 ist umgerechnet 14.
Auch wenn man die genaue Rechnung nicht verstanden hat, erkennt man, dass der Computer hier schon 5 Schritte dafür gebraucht hat.

Wie sieht ein Gleis aus, dass den Sinus einer Zahl berechnet?

kompliziert? Nein, da das schwierig auszurechnen ist (und somit lange dauern würde), gibt es einfach eine große Tabelle, in der nachgeschaut wird.
Etwas zum schmunzeln: im Jahr 1994 hat Intel einen Prozessor hergestellt, bei dem Fehler in so einer Tabelle waren (allerdings in einer Divisionstabelle).

Wie sieht ein Gleis aus, dass ... macht?

Mit sowas beschäftigt man sich dann in Digitaler Logik.

Was ist für mich Logik?

Zunächst eine komische Frage, aber der Logik-Begriff hat sich für mich ganz neu geprägt. Bevor ich studiert habe, dachte ich bei Logik immer an etwas kompliziertes. Etwas, wo man intelligent sein muss, sich vielleicht auch viel merken muss und das dann im Kopf zu kombinieren. Doch zumindest bei der boolschen Logik, bei der es nur die Werte Wahr und Falsch gibt, ist das ganz und gar nicht der Fall. Man muss eigentlich nur ein paar Regeln kennen und wissen, wie man das Ganze aufschreiben kann. Und das geht auch mit ganz normalen Zeichen wie + und *.

Beispiel: ein Rätsel

Es gilt herauszufinden, wie mein Frühstück aussehen kann. Alle Aussagen sollen wahr sein.

  • Ich esse immer Müsli oder Toast.
  • Wenn ich Müsli esse, esse ich kein Toast.
  • Wenn ich Müsli und Nutella esse, esse ich kein Ei
  • Wenn ich Nutella esse, esse ich Toast.
  • Wenn ich kein Ei habe und Toast esse, esse ich Nutella oder Müsli
Ohne die Methoden der boolschen Logik scheint das Ziel aussichtslos. Doch Mithilfe der boolschen Algebra ist die Lösung kein Problem:

Lösung

Hinweis: Die Schreibweise weicht von der mathematischen ab. Es gelten die Konventionen auf meiner Seite.

Im Folgenden werden nur die Anfangsbuchstaben von Müsli, Toast, Nutella und Ei genommen.

Eine Wenn... dann Konstruktion entspricht der Mathematischen Implikation (=daraus folgt, mathematisches Zeichen: →). Das Besondere dabei: Die Aussage ist auch wahr, wenn die Annahme falsch ist. Desweiteren gibt es eine spezielle Regel (Satz von De-Morgan), wie man eine negierte Klammer auflöst.

  1. M + T (Müsli oder Toast)
  2. M → !T= !M + !T (Implikation)
  3. M * N → !E = !(M*N)+!E = !M + !N + !E (Satz von De-Morgan)
  4. N → T = !N + T
  5. !E * T → N + M= E+ !T + N + M
Da alle Bedingungen wahr sein sollen, werden sie mit und verknüpft:
	(M+T)*(!M+!T)*(!M+!N+!E)*(!N+T)*(E+!T+N+M)
	
Dieser Ausdruck lässt sich quasi ausmultiplizieren, allerdings sind einige spezielle Rechenregeln zu beachten:
  1. x*!x=0
  2. x*x=x (bei und spielt die Häufigkeit keine Rolle)
  3. x+x=x (bei oder spielt die Häufigkeit keine Rolle)
Als Beispiel mal die ersten 3 Klammern:

rote Ausdrücke fallen unter die 1. Regel

M*!M*!M + M*!M*!N + M*!M*!E + M*!T*!M + M*!T*!N + M*!T*!E +
T*!M*!M + T*!M*!N + T*!M*!E + T*!T*!M + T*!T*!N + T*!T*!E

Nach der zweiten und dritten Regel bleibt:
M*!T*!N + M*!T*!E + T*!M + T*!M*!N + T*!M*!E Wendet man die Regeln Nun nutzt man entweder die Rechenregeln oder den Logikrechner und man kommt auf das Ergebnis, dass mein Frühstück aus folgenden Kombinationen bestehen kann:
  • Nur Müsli
  • Müsli und Ei
  • Toast und Ei
  • Toast und Nutella
  • Toast, Ei und Nutella