Computerlogik

Ein Sonderfall: Die Computerlogik. Computer können nicht rechnen, sie tun nur so! Das Innenleben eines Prozessors besteht nur aus Speichern und logischen Gattern. Rechenoperationen müssen auf logische Operationen zurückgeführt werden.

Die Computerlogik ist auch eine zweiwertige Logik. Statt der Wahrheitswerte wahr und falsch, werden in einem Computerchip Ströme oder Spannungen ein- oder ausgeschaltet. In der englischsprachigen Literatur werden die beiden Zustände High (H) für ein, bzw. Low (L) für aus abgekürzt. Alle logischen Operationen, wie oben ausgeführt, werden mittels elektronischer Schaltungen (Gatter) ausgeführt.

Wie kann aber eine Berechnung, z.B. eine Addition, durch logische Funktionen ausgeführt werden? Zunächst sei angemerkt, dass im Computer nicht im Dezimal-, sondern im → Binärsystem gerechnet wird. Das heißt zum Beispiel, dass die dezimale 5 wird durch die binäre Zahl 101 (entspricht in logischen Termini H, L, H) ausgedrückt wird. Die Addition einer 3 (011) erfolgt so:

4. Stelle 3. Stelle 2. Stelle 1. Stelle
Wert 23 22 21 20
OP1: 5 0 1 0 1
OP2: 3 0 0 1 1
Übertrag 1 1 1
Summe 1 0 0 0

also gleich 8.

In logischer Schreibweise für die n-te Stelle:

\( \begin{aligned} Ü_n & = (OP1_{n-1} ∧ OP2_{n-1}) ∨ (OP1_{n-1} ∧ Ü_{n-1}) ∨ (OP2_{n-1} ∧ Ü_{n-1}); \quad Ü_1 = 0 \quad n ∈ \mathbb{N} \\ & = (OP1_{n-1} ∧ OP2_{n-1}) ∨ (OP1_{n-1} ∨ OP2_{n-1}) ∧ Ü_{n-1} \end{aligned} \)

\( S_n = ¬(¬(OP1_n ⇔ OP2_n) ⇔ Ü_{n-1}) \)

Wahrheitstafeln für

- Übertrag

OP1n-1 OP2n-1 Ün-1 (OP1n-1 ∧ OP2n-1) (OP1n-1 ∨ OP2n-1) ∧ Ün-1 Ün
L L L L L L
L (H) H (L) L L L L
H H L H L H
L L H L L L
L (H) H (L) H L H H
H H H H H H

- Summe

OP1n-1 OP2n-1 Ün-1 (OP1n-1 ⇔ OP2n-1) ¬ ¬(OP1n-1 ⇔ OP2n-1) ⇔ Ün-1 Sn
L L L H L H L
L (H) H (L) L L H L H
H H L H L H L
L L H H L L H
L (H) H (L) H L H H L
H H H H L L H

Eine logische Schaltung, die beide Operation ausführt, wird ADDER genannt.

Für fast jede logische Operation gibt es äquivalente elektronische Schaltungen:

Logische Funktion Operation Elektronisches Äquivalent
Negation ¬A Negator
Konjunktion A ∧ B AND
Disjunktion A ∨ B OR
Antivalenz ¬(A ⇔ B) XOR
Sheffer-Symbol A|B NAND
Peirce-Symbol A↓B NOR

Aus technologischer Sicht sind viele unterschiedliche Gatter-Typen nicht erwünscht, weil jeder Typ besondere Prozessschritte bei der Herstellung logischer Schaltkreise erfordert. Darum steht die Aufgabe, die Zahl der unterschiedlichen Gatter-Typen auf das absolut notwendige zu beschränken. In der Praxis genügen zwei Typen: den Negator und das NAND (bzw. Negator und NOR). Dank der Regeln von De Morgan können alle anderen Operationen auf diese beiden Grundschaltungen zurückgeführt werden.