Logische Operationen und Schaltnetze

Einordnung des Artikels

• Einführung in die Informatik
  • Rechnerarchitektur
    • Logische Operationen und Schaltnetze

Logisches UND und logisches ODER

Die beiden logischen Operationen UND und ODER (AND und OR) können leicht mit elektrischen Schaltungen mit zwei Schaltern und einer Glühbirne realisiert werden (siehe Abbildung 1). Dabei sind die Schalterstellungen x und y die Eingabewerte und der Zustand der Glühbirne z die Ausgabe. Klar ist, dass

• x = 1 für Schalter ist eingeschaltet steht und
• x = 0 für Schalter ist ausgeschaltet steht.

Und ebenso für die Glühbirne:

• z = 1 steht für die Glühbirne brennt und
• z = 0 steht für die Glühbirne brennt nicht.

Abbildung 1: Elektrische Schaltungen zur Realisierung von logischen Operationen. Eingaben sind die beiden Schalterstellungen x und y, Ausgabe ist der Zustand der Glühbirne z (leuchten oder nicht leuchten). Die Schaltung links realisiert das logische UND, rechts das logische ODER.

Achtung:

In der Umgangssprache werden die logischen Operationen UND und ODER anders verwendet als sie mit Hilfe der Schaltungen definiert werden. Die folgenden Beispiele zeigen den Unterschied:

• "Was möchten Sie trinken, Kaffee oder Tee?" "Ja gerne, aber dann brauche ich eine zweite Tasse!"
• "Hier, nehmen Sie doch Milch und Zucker!" "Nein danke! Aber ich hätte gerne Milch."
• Bei einer Datenbankabfrage des Einwohnermeldeamtes soll die Zahl der Einwohner von München und Augsburg bestimmt wird. Schätzen Sie, wieviele es etwa gibt!
• "Frauen und Kinder zuerst!"

Aufgaben:

1. Versuchen Sie zu formulieren, wie in der Umgangssprache UND und ODER meist gebraucht werden und wie sie in der Logik definiert sind (nämlich gemäß den Schaltungen aus Abbildung 1).

2. Welcher der folgenden Sätze aus der Analysis ist richtig:

• Eine Funktion f hat bei x eine waagrechte Tangente und die zweite Ableitung ist dort positiv. Dann hat f bei x ein Minimum.
• Eine Funktion f hat bei x eine waagrechte Tangente oder die zweite Ableitung ist dort positiv. Dann hat f bei x ein Minimum.

Warum ist eine Version falsch?

3. Welche der folgenden Aussagen ist richtig:

• Ein Produkt ab ist genau dann null, wenn a und b gleich null sind.
• Ein Produkt ab ist genau dann null, wenn a oder b gleich null ist.
• Ein Produkt ab ist genau dann null, wenn entweder a oder b gleich null ist.

Warum sind die anderen beiden Aussagen falsch?

Lösungshinweise zu den Aufgaben:

1. UND und ODER in der Umgangssprache:

In der Umgangssprache wird oder meist als entweder oder verwendet. Wer sagt Was möchten Sie trinken, Kaffee oder Tee? meint damit, dass er entweder Kaffee oder Tee kocht, aber nicht beides gleichzeitig. Der Gast wird mit der Frage aufgefordert sich genau eines von beiden auszusuchen.

Dagegen verwenden wir und gerne in der Bedeutung des logischen ODER: Bieten wir Milch und Zucker an, so beinhaltet es drei Möglichkeiten, entweder Milch oder Zucker oder Milch und zugleich Zucker.

Um diese Verwirrung der Begriffe zu vermeiden:

• Denken Sie sich bei und immer und zugleich.
• Denken Sie sich bei oder: das ist kein entweder oder.

2. Minimum einer Funktion:

Damit eine Funktion f in x ein Minimum hat, müssen beide Bedingungen gleichzeitig erfüllt sein; eine allein reicht nicht aus. Daher ist die Aussage nur mit und richtig.

3. Produkt ab = 0:

In den Behauptungen steht immer: genau dann, wenn, das heißt also dass die beiden Aussagen gleichwertig sind (also sowohl Hin- als auch Rückrichtung der Behauptung sind richtig). Dann trifft aber nur zu:

Ein Produkt ab ist genau dann null, wenn a oder b gleich null ist.

Für die beiden anderen Aussagen gilt nur die Rückrichtung: Wenn a = 0 und zugleich b = 0, dann ist sicher auch ab = 0; aber aus ab = 0 folgt nicht, dass a = 0 und zugleich b = 0.

Ebenso: Wenn entweder a = 0 oder b = 0, dann ist sicher auch ab = 0; aber wenn ab = 0, dann könnte auch a = 0 und zugleich b = 0.

Boolsche Funktionen

Neben UND und ODER gibt es noch weitere logische Funktionen, die sogenannten Booleschen Funktionen, mit zwei Eingabewerten und einem Ausgabewert. Zu ihrer Definition wird noch eine weitere Funktion, nämlich eine einstellige Funktion benötigt: Die Negation, die 0 und 1 vertauscht. Sie wird auch als NICHT-Verknüpfung (im Englischen NOT) oder Inverter bezeichnet.

Es gibt mehrere Darstellungsmöglichkeiten für Boolsche Funktionen, die eigentlich äquivalent sind; aber je nach Anwendung wird die treffendste Darstellung ausgewählt. Es gibt:

Schaltzeichen

Dies sind abstrahierte Symbole, die für die Funktion stehen und die wie eine black box in einer Schaltung eingesetzt werden können. Die Schaltzeichen sind für den Laien manchmal nicht sehr intuitiv gewählt.

Logik-Tabelle

Sie ist zwar aufwendig, definiert die logische Funktion aber am klarsten. In ihr werden die möglichen Kombinationen der Eingabewerte (oben waren es die Schalterstellungen) zusammen mir den zugehörigen Ausgabewerten dargestellt.

Schaltung

Man kann eine elektrische Schaltung (wie in Abbildung 1) angeben, die das Verhalten der Funktion wiedergibt (genau so gut könnte man sich auch eine mechanische Realisierung überlegen).

Schalt-Funktion

Für jede Funktion gibt es ein Symbol, das wie in mathematischen Formeln verwendet wird.

Funktionsdiagramm

Man kann die Ein- und Ausgabewerte durch eine zeitlichen Verlauf einer Funktion wiedergeben, was hier nicht geschehen soll.

Am Beispiel der NICHT-Verknüpfung sollen die ersten vier Darstellungsmöglichkeiten demonstriert werden:

Abbildung 2: Links: Das Schaltzeichen für die Negation. Halblinks: die zugehörige logische Tabelle mit Ein- und Ausgabewerten. Halbrechts: Eine elektrische Schaltung, die das Verhalten der Negation besitzt (schließt man den Schaltern, fließt der Strom durch den Zweig mit dem Schalter und nicht durch den Zweig mit der Glühbirne, die einen deutlich höheren Widerstand besitzt. Rechts: Die Schalt-Funktion der Negation.

Das Schaltzeichen der Negation bedarf einer Erklärung:

• Der Kasten soll die black box andeuten.
• Die 1 im Kasten steht für die Identität, also die identische Abbildung (der Ausgabewert stimmt mit dem Eingabewert überein).
• Der kleine Kreis rechts steht für die eigentliche Negation.

Die elektrische Schaltung sollte auch klar sein: Ist der Schalter geöffnet (Eingabe 0), fließt Strom durch die Glühbirne (Ausgabe 1); bei geschlossenem Schalter hat die Glühbirne einen sehr viel höheren Widerstand als der Zweig mit dem Schalter und es fließt kein Strom.

Die Schalt-Funktion für die Negation ist entweder der Oberstrich über der Eingabe oder ausführlich A = NOT E.

Nach der Erklärung, wie Funktionen dargestellt werden, endlich die wichtigsten Booleschen Funktionen:

• UND (= AND)
• ODER (= OR)
• XOR (auch exklusiv oder beziehungsweise entweder oder oder auch Antivalenz)
• NAND ( = NOT AND, das heißt, man bildet zuerst AND und anschließend die Negation NOT = NICHT)
• NOR (= NOT OR).
• Äquivalenz (XNOR = NOT XOR, siehe unten)

Die folgende Tabelle fasst die Logik-Tabellen dieser Booleschen Funktionen zusammen. In den ersten beiden Spalten stehen die Eingabewerte x und y; es gibt vier Kombinationen für die Eingabewerte, für die anschließend die Booleschen Funktionen berechnet werden.

Abbildung 3: Logik-Tabelle und Schaltzeichen für die wichtigsten Booleschen Funktionen; genauere Erklärung im Text

Die Schaltzeichen sind zum Teil erklärungsbedürftig:

1. AND: Das kaufmännische UND wird oft für das logische UND eingesetzt.
2. OR: Das Symbol größer gleich 1 soll bedeuten, dass ein oder mehr Eingabewerte gleich 1 sein müssen, damit auch der Ausgabewert gleich 1 ist (ansonsten ergibt sich 0).
3. XOR: Sollte damit auch klar sein, denn jetzt muss genau 1 Eingabewert gleich 1 sein sein, um 1 zu erhalten. Die Boolesche Funktion XOR wird manchmal auch als anti-valent bezeichnet — dies wird klarer, nachdem unten bei XNOR gesagt wird, dass XNOR treffender mit äquivalent bezeichnet wird.
4. NAND: Es wird zuerst AND gebildet und anschließend verneint (kleiner Kreis am Ausgang).
5. NOR: Ganz ähnlich, man bildet zuerst OR und dann die Negation.
6. XNOR: Betrachtet man die logische Tabelle von XNOR, so sieht man, dass die Ausgabe genau dann 1 ist, wenn die beiden Eingaben identisch sind; daher ist der treffendere Name äquivalent. Genau dies soll das = im Schaltzeichen ausdrücken.

Aufgaben:

1. Wieviele Boolesche Funktionen (mit zwei Eingabewerten und einem Ausgabewert) gibt es?
2. Die Funktionen AND und OR sind monoton. Was versteht man darunter?

Maschinensprache

Die Maschinensprache stellt die Befehle bereit, die auf der ALU (Arithmetic and Logic Unit) ausgeführt werden können; unter anderem die meisten Booleschen Operationen.

Die Befehle der Maschinensprache werden in folgende Gruppen unterteilt:

1. Logische Operationen:

Hierunter fallen die bereits gesprochenen Booleschen Funktionen.

2. Elementare Rechenoperationen:

Addition, Multiplikation und so weiter.

3. Bitoperationen:

Mit der Negation wurde schon die wichtigste Bitoperation genannt. Eine andere wichtige Gruppe von Bitoperationen sind die shift-Operatoren. Bei einem shift um n Stellen nach links beziehungsweise rechts werden alle Bits eines Bytes um n Stellen nach links beziehungsweise rechts verschoben; die frei werdende Stelle (oder Stellen) wird mit 0 aufgefüllt.

Bei einem Rotationsbefehl werden die herausfallenden Bits am anderen Ende wieder eingefügt.

4. Kopierbefehle (oder Datentransferbefehle):

Hier werden nur die Inhalte zwischen den Speicherzellen verschoben.

5. Sprungbefehle:

Die Befehle eines Maschinensprache-Programms sind mit Befehlszeilen versehen. Üblicherweise wird ein Programm sequentiell abgearbeitet. Durch die Sprungbefehle können die Befehlszeilen in beliebiger Reihenfolge ausgeführt werden.

Meist können die Befehle der Maschinensprache nicht eindeutig einer der fünf genannten Gruppen zugeordnet werden, da auch Kombinationen möglich sind.

Es gibt natürlich nicht die Maschinensprache, ihre konkrete Realisierung hängt immer von ihrem Einsatz ab. (Genauer: von der Prozessorarchitektur; unter einem Prozessor stellen Sie sich zunächst eine ALU vor, die zusätzlich mit Speicherzellen, den Registern, ausgestattet ist.). Mit konkreter Realisierung einer Maschinensprache ist gemeint, welche Befehle eine Maschinensprache anbietet und wie komplex sie sind.

Um einige Beispiele für Maschinensprachebefehle zu nennen:

mov RA, 17;

Schreibe 17 in das Register mit der Adresse RA (reiner Kopierbefehl).

add RA, RB;

Addiere die Inhalte der Register mit den Adressen RA und RB (das Ergebnis wird dann in die Speicherzelle RA geschrieben) (Rechenoperationen und anschließender Kopierbefehl).

sub RA, RB;
mult RA, RB;
div RA, RB;

Subtraktion, Multiplikation, Division.

NOT RA, RB;
OR RA, RB;
AND RA, RB;
XOR RA, RB;

Logische Operationen.

dec RB;

Erniedrige den Inhalt der Adresse RB um 1 (Rechenoperationen und anschließender Kopierbefehl).

inc RB;

Erhöhe den Inhalt der Adresse RB um 1 (Rechenoperationen und anschließender Kopierbefehl).

jnz LABEL1;

Falls das Ergebnis der letzten Berechnung ungleich null ist, springe zur Befehlszeile LABEL1 (jnz = jump not zero; logische Operation und anschließender Sprungbefehl).

Alle Befehle, die in der Maschinensprache vorkommen, können im Prozessor des Computers ausgeführt werden. Dazu stehen in der ALU (= Arithmetic and Logic Unit) elektrische Schaltungen (mit Transistoren statt Schaltern) und im Register Speicherzellen bereit.

Aufgabe:

Versuchen Sie herauszufinden, welche Berechnung das folgende Programm ausführt. Am Ende wird der Inhalt der Speicherzelle RA in die Speicherzelle mit der Adresse FA70h (Adresse als Hexadezimalzahl) verschoben. Welchen Inhalt hat RA dabei? Welche mathematische Funktion wurde hier berechnet?

mov RA, 1;
mov RB, 5;
ITERATE:
mult RA, RB;
dec RB;
jnz ITERATE;
mov [FA70h], RA;

Liefert das Programm noch das identische Ergebnis, wenn der Multiplikationsbefehl in der vierten Zeile lautet:

mult RB, RA;