Technische Informatik
Umwandlung in NAND und NOR

Thorsten Thormählen
15. November 2022
Teil 5, Kapitel 1

Dies ist die Druck-Ansicht.

Weiterschalten der Folien durch die → Taste oder
durch das Klicken auf den rechten Folienrand.

Steuerungstasten

→ nächste Folie (auch Enter oder Spacebar).
← vorherige Folie
d schaltet das Zeichnen auf Folien ein/aus
p wechselt zwischen Druck- und Präsentationsansicht
CTRL + vergrößert die Folien
CTRL - verkleinert die Folien
CTRL 0 setzt die Größenänderung zurück

Das Weiterschalten der Folien kann ebenfalls durch das Klicken auf den rechten bzw. linken Folienrand erfolgen.

Notation

Typ	Schriftart	Beispiele
Variablen (Skalare)	kursiv	$a, b, x, y$
Funktionen	aufrecht	$\mathrm{f}, \mathrm{g}(x), \mathrm{max}(x)$
Vektoren	fett, Elemente zeilenweise	$\mathbf{a}, \mathbf{b}= \begin{pmatrix}x\\y\end{pmatrix} = (x, y)^\top,$ $\mathbf{B}=(x, y, z)^\top$
Matrizen	Schreibmaschine	$\mathtt{A}, \mathtt{B}= \begin{bmatrix}a & b\\c & d\end{bmatrix}$
Mengen	kalligrafisch	$\mathcal{A}, B=\{a, b\}, b \in \mathcal{B}$
Zahlenbereiche, Koordinatenräume	doppelt gestrichen	$\mathbb{N}, \mathbb{Z}, \mathbb{R}^2, \mathbb{R}^3$

Inhalt

Umwandlung zweistufiger Logik in
- NAND-Gatter-Schaltungen
- NOR-Gatter-Schaltungen
Umwandlung mehrstufiger Logik

Realisierung zweistufiger Logik

Disjunktive Normalform (DNF)
- AND-Gatter für die Minterme
- OR-Gatter für die Erweiterung
Konjuktive Normalform (KNF)
- OR-Gatter für die Maxterme
- AND-Gatter für die Erweiterung

Zweistufige Logik mit NAND-Gattern

1. Schritt
- Ersetzen der AND-Gatter der Minterme mit NAND-Gattern
- Kompensation durch Invertieren der Eingänge des OR-Gatters
2. Schritt
- Laut De Morgan kann ein OR-Gatter mit invertierten Eingängen durch ein NAND-Gatter ersetzt werden
  $\lnot x_0 \lor \lnot x_1 \lor \lnot x_2= \lnot (x_0 \land x_1 \land x_2)$
- Fertige Schaltung besteht nur noch aus NAND-Gattern

Zweistufige Logik mit NOR-Gattern

1. Schritt
- Ersetzen der OR-Gatter der Maxterme mit NOR-Gattern
- Kompensation durch Invertieren der Eingänge des AND-Gatters
2. Schritt
- Laut de Morgan kann ein AND-Gatter mit invertierten Eingängen durch ein NOR-Gatter ersetzt werden
  $\lnot x_0 \land \lnot x_1 \land \lnot x_2= \lnot (x_0 \lor x_1 \lor x_2)$
- Fertige Schaltung besteht nur noch aus NOR-Gattern

Äquivalente Gatter

Mit De Morgans Gesetzen lassen sich vier Gleichungen aufstellen:
- $\lnot(a \land b) = \lnot a \lor \lnot b \Leftrightarrow (a \land b) = \lnot (\lnot a \lor \lnot b)$
- $\lnot(a \lor b) = \lnot a \land \lnot b \Leftrightarrow (a \lor b) = \lnot (\lnot a \land \lnot b)$
Damit erhalten wir vier austauschbare Gattertypen
- OR ist ein NAND mit invertierten Eingängen: $=$
- AND ist ein NOR mit invertierten Eingängen: $=$
- NAND ist ein OR mit invertierten Eingängen: $=$
- NOR ist ein AND mit invertierten Eingängen: $=$

Mehrstufige Logik

Wieso überhaupt mehrstufige Logik? Zwei Stufen reichen doch eigentlich.
Motivierendes Beispiel:
$y = adf \lor aef \lor bdf \lor bef \lor cdf \lor cef \lor g$
- Dies ist eine reduzierte (vereinfachte) DNF
- Für die Realisierung werden 6 AND-Gatter mit 3 Eingängen und ein OR-Gatter mit 7 Eingängen benötigt (vielleicht nicht realisierbar)
- 25 Verbindungen (19 Literale plus 6 interne Verbindungen)
Faktorisierte Form, die nicht als zweistufige DNF realisierbar ist

$y = (a \lor b \lor c) (d \lor e) f \lor g$
- Für die Realisierung werden 1 OR-Gatter mit 3 Eingängen und 2 OR-Gatter mit 2 Eingängen und 1 AND-Gatter mit 3 Eingängen benötigt
- 10 Verbindungen (7 Literale plus 3 interne Verbindungen)