Logische Operationen und Schaltnetze

F├╝r den Computer werden komplexe Operationen auf elementare Rechenoperationen heruntergebrochen. Deren wichtigste Gruppe sind logische Operationen, die hier ausf├╝hrlich vorgestellt werden.
Noch keine Stimmen abgegeben
Noch keine Kommentare

Einordnung des Artikels

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.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.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 TextAbbildung 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;