Kombinatorik
Datum: 24.8.2011 | Kommentare: 0Allgemeines
Bei einer kombinatorischen Schaltung handelt es sich um eine Digital-Schaltung deren Ausgänge eindeutig durch die Eingänge bestimmt sind. Um dies zu erreichen darf die Schaltung keine speichernden Elemente aufweisen, d.h. die Schaltung ist Zustandslos.
Ein solches Schaltnetz kann durch die elementaren logischen Schaltglieder (Gatter) dargestellt werden: AND, OR, XOR und NOT. Darstellungsformen sind unter anderem Boolesche Funktionen, Wahrheitstabellen oder zeichnerische Verknüpfungen von logischen Schaltglieder.
Bei den Schaltnetzen im folgenden Kapitel werden die Schaltverzögerungen durch Gatterlaufzeiten bzw. Signallaufzeiten nicht betrachtet.
Logische Gatter
Zu den gebräuchlichsten Logikgattern zählen AND, OR, NOT und XOR. Die Gatter NAND, NOR und XNOR können durch Kombination von AND, OR bzw. XOR mit einem NOT Gatter gebildet werden. Eine vollständige Übersicht findet man unter Wikipedia:Logikgatter.
AND-Gatter
Ein AND- bzw. zu deutsch UND-Gatter hat zwei oder mehr Eingänge und einen Ausgang. Dieser Ausgang ist nur dann logisch 1 wenn alle Eingänge auf logisch 1 sind. Die AND-Verknüpfung kann in booleschen Funktionen als "•" (Mal), "&" oder mittels "∧" dargestellt werden. In der klassischen Logik wird eine Aussage, die nur dann wahr ist, wenn zwei oder mehr Aussagen wahr sind als Konjunktion bezeichnet.
Wahrheitstabelle:
| A | B | A∧B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR-Gatter
Ein OR- bzw. ODER-Gatter hat zwei oder mehr Eingänge und einen Ausgang. Dieser Ausgang ist dann logisch 1 sobald mindestens ein Eingang auf logisch 1 ist. In booleschen Funktionen wird die OR-Verknüpfung als "+" oder als "∨" dargestellt. Eine Disjunktion ist in der klassischen Logik eine Aussage, die dann wahr ist, wenn mindestens eine Teil-Aussage wahr ist.
Wahrheitstabelle:
| A | B | A∨B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
OR-Gatter bedient sich der nicht-ausschließenden Disjunktion.NOT-Gatter
Das NOT-Gatter hat einen Eingang und einen Ausgang. Der Ausgang stellt die Invertierung (auch Komplement genannt) des Einganges dar. In booleschen Funktionen wird es mittels "¬". In der klassischen Logik stellt es eine Verneinung einer Aussage dar.
Oft sieht man auch die Darstellung mittels Überstrich (z.B. A∧B)
Wahrheitstabelle:
| A | ¬A |
| 0 | 1 |
| 1 | 0 |
XOR-Gatter
Das XOR-Gatter (von engl. eXclusive OR) hat meist zwei (oder auch mehr) Eingänge und einem Ausgang. Bei einem XOR-Gatter mit zwei Eingängen ist der Ausgang auf logisch 1, wenn einer der beiden Eingänge auf logisch 1 ist, aber nicht beide gleichzeitig. Dies entspricht der ausschließenden Disjunktion. Für zwei oder mehr Eingänge ist der Ausgang auf logisch 1, wenn an einer ungerade Anzahl von Eingängen eine logische 1 anliegt.
In booleschen Funktionen wird die XOR Verknüpfung mittels "⊕" oder "⊻" dargestellt.
Wahrheitstabelle:
| A | B | A⊕B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Darstellungsformen
Im europäischen Raum wird für die Darstellung von Schaltsymbolen die Norm IEC 60617 verwendet. In Schaltplänen findet man auch recht häufig die im amerikanischen Raum verbreitete Darstellungsform nach der Norm US ANSI 91-1984. Die Darstellung nach DIN 40700 ist veraltet.
Rechengesetze
Für die Operatoren der booleschen Algebra gilt die folgende Rangfolge (in absteigender Wertigkeit):
- Negation (¬)
- Konjunktion (∧)
- Disjunktion (∨)
Der Ausdruck a ∨ ¬ b ∧ c entspricht dem Ausdruck (a ∨ ( (¬b) ∧ c ) ). Bei den Rechengesetzen sieht man auch Analogien von der booleschen Konjunktion (∧) zur arithmetischen Multiplikation (•) und von der booleschen Disjunktion (∨) zur arithmetischen Addition (+).
Für die boolesche Algebra gelten folgende Rechengesetze:
| Kommutativgesetz | a∧b = b∧a | a∨b = b∨a |
| Assoziativgesetz | (a∧b)∧c = a∧(b∧c) | (a∨b)∨c = a∨(b∨c) |
| Idempotenzgesetz | a∧a=a | a∨a=a |
| Distributivgesetz | a∧(b∨c) = (a∧b)∨(a∧c) | a∨(b∧c) = (a∨b)∧(a∨c) |
| Neutralitätsgesetz | a∧1 = a | a∨0 = a |
| Extremalgesetz | a∧0=0 | a∨1=1 |
| Doppelnegationsgesetz (Involution) | ¬(¬a)=a | |
| De Morgansche Gesetz | ¬(a∧b)=¬a ∨ ¬b | ¬(a∨b)=¬a ∧ ¬b |
| Komplementärgesetz | a ∧ ¬a=0 | a ∨ ¬a=1 |
| Dualitätsgesetz | ¬0 = 1 | ¬1 = 0 |
| Absorptionsgesetz | a ∨ (a∧b)=a | a ∧ (a∨b)=a |
| a | b | c | b∨c | a∧(b∨c) | a∧b | a∧c | (a∧b)∨(a∧c) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |