Title

Einführung in die Technische Informatik
Prof. Jian-Jia Chen | Dr.-Ing. Christian Hakert | Dr. rer. nat. Marcus Völker
RWTH Aachen University

Kapitel 2: Darstellung Boolescher Funktionen

Abschnitt 2.1

Boolesche Algebra

  • Gesetze einer Booleschen Algebra
  • Anwendung einer Booleschen Algebra

Motivation

  • 2 Zustände reichen aus, um Informationen zu speichern
  • Beispiel:
images/Kapitel 02 - Boolesche Funktionen/s002_seg17_snap.png
  • Aufgabe des Systems:
    • „Da nur eine Leitung genutzt wird, darf nur eines der beiden Telefone zu einem Zeitpunkt verwendet werden.“
  • Formal ausgedrückt:

Boolesche Algebra

  • Boolesche Algebra als formale Grundlage in der Schaltungstechnik und der Computerhardware
  • In der Booleschen Algebra gibt es genau 2 Werte: 0 (false) und 1 (true)
  • Unäre Verknüpfung: \(\neg\)
  • Binäre Verknüpfungen: \(\lor\), \(\land\)
\(x\) \(\neg x\)
0 1
1 0
\(x\) \(y\) \(x\lor y\)
0 0 0
0 1 1
1 0 1
1 1 1
\(x\) \(y\) \(x\land y\)
0 0 0
0 1 0
1 0 0
1 1 1

Beispiel: XOR, XNOR und NAND

Weitere Verknüpfungen, zusammengesetzt aus \(\neg\), \(\lor\), \(\land\):

  • XOR: \(x\oplus y=(x\land\neg y)\lor(\neg x\land y)\)
  • XNOR: \(\overline{x\oplus y}=(x\land y)\lor(\neg x\land\neg y)\)
  • NAND: \(x\uparrow y=\overline{x\land y}=\neg x\lor\neg y\)
\(x\) \(y\) \(x\oplus y\) \(\overline{x\oplus y}\) \(x\uparrow y\)
0 0 0 1 1
0 1 1 0 1
1 0 1 0 1
1 1 0 1 0

Gesetze in der Booleschen Algebra

  • (a) Kommutativgesetze:
    \(x\land y=y\land x \qquad\qquad x\lor y=y\lor x\)
  • (b) Assoziativgesetze:
    \((x\land y)\land z=x\land(y\land z) \qquad\qquad (x\lor y)\lor z=x\lor(y\lor z)\)
  • (c) Distributivgesetze:
    \(x\land(y\lor z)=(x\land y)\lor(x\land z) \qquad\qquad x\lor(y\land z)=(x\lor y)\land(x\lor z)\)
  • (d) Absorption:
    \(x\land(x\lor y)=x \qquad\qquad x\lor(x\land y)=x\)
  • (e) Idempotenz:
    \(x\land x=x \qquad\qquad x\lor x=x\)
  • (f) Nullelement / Einselement:
    \(x\land 0=0 \qquad\qquad x\lor 1=1\)

Gesetze in der Booleschen Algebra

  • (g) Eindeutiges Komplement:
    \((x\lor y=1 \text{ und } x\land y=0)\Leftrightarrow(x=\neg y)\)
  • (h) Involution:
    \(\neg(\neg x)=x\)
  • (i) Konstanten:
    \(\neg 0=1 \qquad\qquad \neg 1=0\)
  • (j) De Morgansche Regeln:
    \(\neg(x\lor y)=\neg x\land\neg y \qquad\qquad \neg(x\land y)=\neg x\lor\neg y\)

Abschnitt 2.2

Boolesche Funktionen

  • Schaltfunktionen
  • 1-stellige Boolesche Funktionen
  • 2-stellige Boolesche Funktionen
  • Darstellung Boolescher Funktionen

Schaltfunktionen

ti-2-deck-code-b8571c99.tex.svg
  • Definition: Seien \(n,m\in\mathbb{N}\), \(n,m\geq 1\). Dann heißt eine Funktion \(F:B^n\to B^m\) Schaltfunktion.
  • Beispiele:
    • Addition von zwei 16-stelligen Dualzahlen
    • Multiplikation von zwei 16-stelligen Dualzahlen
    • Sortieren von 30 16-stelligen Dualzahlen
    • Primzahltest einer 16-stelligen Dualzahl

Boolesche Funktionen

Eine Schaltfunktion \(f:B^n\to B^1\) heißt (\(n\)-stellige) Boolesche Funktion.

Zusammenhang zu Schaltfunktionen:

Sei \(F:B^n\to B^m\) mit \(F(x_{n-1},\ldots,x_1,x_0)=(y_{m-1},\ldots,y_1,y_0)\).
Setzt man für jedes \(i\in\{m-1,\ldots,0\}\)

\[ f_i:B^n\to B \quad\text{definiert durch}\quad f_i(x_{n-1},\ldots,x_1,x_0)=y_i, \]

so ist \(F\) wie folgt darstellbar:

\[ F(x_{n-1},\ldots,x_0)=\big(f_{m-1}(x_{n-1},\ldots,x_0),\ f_{m-2}(x_{n-1},\ldots,x_0),\ \ldots,\ f_0(x_{n-1},\ldots,x_0)\big) \]

für alle \(x_{n-1},\ldots,x_0\in B\).

Beispiel für Zusammenhang Schaltfunktion – Boolesche Funktion

  • Schaltfunktion \(F:B^2\to B^2\): Addition zweier 1-Bit-Zahlen (Halbaddierer)
  • \(F(x_1,x_0)=(y_1,y_0)\) mit Übertrag \(y_1\) und Summenbit \(y_0\)
  • Zerlegung in zwei Boolesche Funktionen \(f_1,f_0:B^2\to B\):
    • \(f_1(x_1,x_0)=x_1x_0\) (AND)
    • \(f_0(x_1,x_0)=x_1\oplus x_0\) (XOR)
  • Damit: \(F(x_1,x_0)=\big(f_1(x_1,x_0),\ f_0(x_1,x_0)\big)\)
\(x_1\) \(x_0\) \(y_1\) \(y_0\)
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

1-stellige Boolesche Funktion

  • Alle Funktionen \(f: B\to{}B\):
\(x\) \(f_0(x)\) \(f_1(x)\) \(f_2(x)\) \(f_3(x)\)
0 0 0 1 1
1 0 1 0 1
  • Es gilt: \(f_0(x)=0,\quad f_1(x)=x,\quad f_2(x)=\overline{x},\quad f_3(x)=1\)

2-stellige Boolesche Funktion

  • Alle Funktionen \(f: B^2\to{}B\) (Teil 1):
\(x\) \(y\) \(f_0\) \(f_1\) \(f_2\) \(f_3\) \(f_4\) \(f_5\) \(f_6\) \(f_7\)
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
(1) \(x\land\overline{x}\) \(x\land{}y\) \(x\land\overline{y}\) \(x\) \(\overline{x}\land{}y\) \(y\) \(x\oplus{}y\) \(x\lor y\)
(2) \(\equiv 0\) Min \(>\) \(x\) \(<\) \(y\) \(\neq\) Max
(3) \(\wedge\) \(\nrightarrow\) \(x\) \(\nleftarrow\) \(y\) \(\nleftrightarrow\) \(\vee\)
(4) AND XOR OR
  • Legende: (1) Boolescher Ausdruck, (2) arithmetische Deutung, (3) logischer Operator, (4) Gatter
  • Sind das alle 2-stelligen Booleschen Funktionen?

2-stellige Boolesche Funktion

  • Alle Funktionen \(f: B^2\to{}B\) (Teil 2):
\(x\) \(y\) \(f_8\) \(f_9\) \(f_{10}\) \(f_{11}\) \(f_{12}\) \(f_{13}\) \(f_{14}\) \(f_{15}\)
0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
(1) \(\overline{x\lor y}\) \(\overline{x\oplus{}y}\) \(\overline{y}\) \(x\lor \overline{y}\) \(\overline{x}\) \(\overline{x}\lor y\) \(\overline{x\land{}y}\) \(x\lor \overline{x}\)
(2) 1-Max \(=\) 1-\(y\) \(\geq\) 1-\(x\) \(\leq\) 1-Min \(\equiv 1\)
(3) \(\downarrow\) \(\leftrightarrow\) \(\neg{}y\) \(\leftarrow\) \(\neg{}x\) \(\rightarrow\) \(\uparrow\)
(4) NOR XNOR NAND
  • Legende: (1) Boolescher Ausdruck, (2) arithmetische Deutung, (3) logischer Operator, (4) Gatter

Beispiel für eine 3-stellige Funktion

\(i\) \(x_2\) \(x_1\) \(x_0\) \(f(x_2,x_1,x_0)\)
0 0 0 0 0
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 0
5 1 0 1 1
6 1 1 0 0
7 1 1 1 1
  • Einschlägige Indizes: die Zeilen mit \(f=1\), hier \(i\in\{3,5,7\}\)
  • Wie viele 3-stellige Boolesche Funktionen gibt es?
  • Müssen wir die alle in Funktionstabellen definieren, bevor wir sie benutzen können?

Darstellung Boolescher Funktionen

Folgende Darstellungen werden vorgestellt:

  • Disjunktive und Konjunktive Normalform (DNF, KNF)
  • Directed Acyclic Graph (DAG)
  • Ordered Binary Decision Diagram (OBDD)
  • Karnaugh-Diagramme

Abschnitt 2.3

Disjunktive und Konjunktive Normalform

  • Minterme
  • Darstellungssatz für Boolesche Funktionen
  • Folgerung aus dem Darstellungssatz
  • Maxterme
  • Grundbausteine zur Realisierung Boolescher Funktionen

Minterme

Gegeben: \(B^3\) in dieser Darstellung.

Minterm: eine Anzahl von Literalen (booleschen Variablen wie z.B. \(x_2\)), die alle durch ein UND (\(\land\)) verknüpft sind.

Beispiele für Minterme:

\[ \begin{aligned} m_3(x_2,x_1,x_0) &= \overline{x_2}x_1x_0\\ m_4(x_2,x_1,x_0) &= x_2\overline{x_1}\,\overline{x_0} \end{aligned} \]

\(i\) \(x_2\) \(x_1\) \(x_0\)
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1

Darstellungssatz für Boolesche Funktionen

Jede Boolesche Funktion \(f:B^n\to B\) ist eindeutig darstellbar als Summe der Minterme ihrer einschlägigen Indizes.

D.h.: Ist \(I\subseteq\{0,\ldots,2^n-1\}\) die Menge der einschlägigen Indizes von \(f\), so gilt

\[ f=\bigvee_{i\in I}m_i \]

und keine andere Minterm-Summe stellt \(f\) dar.

Die Summe der Minterme der einschlägigen Indizes wird als Disjunktive Normalform (DNF) bezeichnet.

Quiz: Minterme

Gegeben seien die beiden Minterme \(m_3=\overline{x_2}x_1x_0\) und \(m_4=x_2\overline{x_1}\,\overline{x_0}\). Ist \(f(x_2,x_1,x_0)=m_3\lor m_4=\overline{x_2}x_1x_0\lor x_2\overline{x_1}\,\overline{x_0}\) wieder ein Minterm?

DNF Beispiel

Sei \(f:B^3\to B\) gegeben durch die Tabelle.

DNF:

\[ \begin{aligned} f(x_2,x_1,x_0) &= m_3\lor m_5\lor m_7\\ &= \overline{x_2}x_1x_0\lor x_2\overline{x_1}x_0\lor x_2x_1x_0 \end{aligned} \]

\(i\) \(x_2\) \(x_1\) \(x_0\) \(f(x_2,x_1,x_0)\)
0 0 0 0 0
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 0
5 1 0 1 1
6 1 1 0 0
7 1 1 1 1

Folgerung aus dem Darstellungssatz

  • Alle \(n\)-stelligen Booleschen Funktionen lassen sich mit den 2-stelligen Funktionen UND und ODER und der 1-stelligen Funktion NICHT darstellen.
  • Man sagt:
    Das System \(\{\land,\lor,\neg\}\) ist funktional vollständig.

Maxterme

Gegeben: \(B^3\) in dieser Darstellung.

Maxterm: eine Anzahl von Literalen (booleschen Variablen wie z.B. \(x_2\)), die alle durch ein ODER (\(\lor\)) verknüpft sind.

Beispiele für Maxterme:

\[ \begin{aligned} M_3(x_2,x_1,x_0) &= x_2\lor \overline{x_1}\lor \overline{x_0}\\ M_4(x_2,x_1,x_0) &= \overline{x_2}\lor x_1\lor x_0 \end{aligned} \]

\(i\) \(x_2\) \(x_1\) \(x_0\)
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1

Konjunktive Normalform (KNF)

  • Analog zu DNF: jede Boolesche Funktion ist eindeutig darstellbar als das Produkt der Maxterme ihrer NICHT-einschlägigen Indizes.
  • Es gilt:
    • Sei \(m_i\) \(i\)-ter Minterm von \(f\)
    • Dann heißt \(M_i=\overline{m_i}\) \(i\)-ter Maxterm von \(f\)

KNF Beispiel

Sei \(f:B^3\to B\) gegeben durch die Tabelle.

KNF:

\[ f(x_2,x_1,x_0) = M_0\land M_1\land M_2\land M_4\land M_6 \]

\(i\) \(x_2\) \(x_1\) \(x_0\) \(f(x_2,x_1,x_0)\)
0 0 0 0 0
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 0
5 1 0 1 1
6 1 1 0 0
7 1 1 1 1

\[ \begin{aligned} f(x_2,x_1,x_0) &= (x_2\lor x_1\lor x_0)\land(x_2\lor x_1\lor \overline{x_0})\land(x_2\lor \overline{x_1}\lor x_0)\\ &\quad\land(\overline{x_2}\lor x_1\lor x_0)\land(\overline{x_2}\lor \overline{x_1}\lor x_0) \end{aligned} \]

Abschnitt 2.4

Funktionale Vollständigkeit

  • Funktionale Vollständigkeit von NAND
  • Funktionale Nicht-Vollständigkeit von \(\{\to,1\}\)

Funktionale Vollständigkeit von NAND

  • Bekannt: \(\{\land,\lor,\neg\}\) ist funktional vollständig
  • Frage: Ist \(\{\uparrow\}\) funktional vollständig?
  • Vorgehen: Stelle ein bekanntes fkt. vollst. System mit \(\{\uparrow\}\) dar.
  1. Nicht \(\{\neg\}\):
    \(\overline{x}=\overline{x}\lor\overline{x}=\overline{\overline{\overline{x}\lor\overline{x}}}=\overline{x\land x}=x\uparrow x\)
\(x\) \(y\) \(f_{14}\)
0 0 1
0 1 1
1 0 1
1 1 0

\(f_{14}=x\uparrow y\) (NAND, 1-Min)

Funktionale Vollständigkeit von NAND

  1. Oder \(\{\lor\}\): \[ \begin{aligned} x\lor y &= \overline{\overline{x\lor y}} = \overline{\overline{x}\land\overline{y}}\\ &= \overline{x}\uparrow\overline{y} = (x\uparrow x)\uparrow(y\uparrow y) \end{aligned} \]
  2. Und \(\{\land\}\): \[ \begin{aligned} x\land y &= \overline{\overline{x\land y}} = \overline{x\uparrow y}\\ &= (x\uparrow y)\uparrow(x\uparrow y) \end{aligned} \]

\(\Rightarrow\) Funktional vollständig

\(x\) \(y\) \(f_{14}\)
0 0 1
0 1 1
1 0 1
1 1 0

\(f_{14}=x\uparrow y\) (NAND, 1-Min)

Funktionale Nicht-Vollständigkeit von \(\{\to,1\}\)

  • Bekannt: \(\{\land,\lor,\neg\}\) ist funktional vollständig
  • Frage: Ist \(\{\to,1\}\) nicht funktional vollständig?
  • Vorgehen: Versuche ein bekanntes fkt. vollst. System mit \(\{\to,1\}\) darzustellen.
  • Zeige, dass sich eine der Funktionen mit keiner Kombination darstellen lässt.
\(x\) \(y\) \(f_{13}\)
0 0 1
0 1 1
1 0 0
1 1 1

\(f_{13}=x\to y\)

Funktionale Nicht-Vollständigkeit von \(\{\to,1\}\)

  • Nicht \(\{\neg\}\): \(\overline{x}=\ ?\)
  • Mögliche Kombinationen von \(x\) mit \(\{\to,1\}\):

\[ \begin{aligned} 1\to 1 &= 1\\ 1\to x &= x\\ x\to 1 &= 1\\ x\to x &= 1 \end{aligned} \]

  • Es lassen sich keine neuen Funktionen und insbesondere kein Nicht \(\{\neg\}\) darstellen.

\(\Rightarrow\) Nicht funktional vollständig

\(x\) \(y\) \(f_{13}\)
0 0 1
0 1 1
1 0 0
1 1 1

\(f_{13}=x\to y\)

Abschnitt 2.5

Schaltnetze

  • DAG-Darstellung
  • Anwendung: Schaltungsabhängige Fehlerdiagnose

Grundbausteine zur Realisierung Boolescher Funktionen

ti-2-deck-code-9ec35582.tex.svg

Grundbausteine zur Realisierung Boolescher Funktionen

ti-2-deck-code-2b233303.tex.svg

Beispiel

Sei \(f:B^3\to B\) gegeben durch die Tabelle.

DNF:

\[ \begin{aligned} f(x_2,x_1,x_0) &= m_3\lor m_5\lor m_7\\ &= \overline{x_2}x_1x_0\lor x_2\overline{x_1}x_0\lor x_2x_1x_0 \end{aligned} \]

\(i\) \(x_2\) \(x_1\) \(x_0\) \(f(x_2,x_1,x_0)\)
0 0 0 0 0
1 0 0 1 0
2 0 1 0 0
3 0 1 1 1
4 1 0 0 0
5 1 0 1 1
6 1 1 0 0
7 1 1 1 1

Beispiel

ti-2-deck-code-74e74dc3.tex.svg

Beispiel

Alternative Schaltung:

ti-2-deck-code-f9f8a444.tex.svg

DAG-Darstellung

DAG = Directed Acyclic Graph (gerichteter azyklischer Graph)

ti-2-deck-code-892ecd83.tex.svg

Beispiel für zyklischen Graph: Flimmerschaltung

ti-2-deck-code-98f88bb9.tex.svg

Beispiel für zyklischen Graph: Flimmerschaltung

ti-2-deck-code-bcfb076d.tex.svg

Beispiel für zyklischen Graph: Flimmerschaltung

ti-2-deck-code-77666e69.tex.svg

Anwendung: Schaltungsabhängige Fehlerdiagnose

Beispiel:

\[ f(x_2,x_1,x_0)=\overline{x_2}x_1x_0\lor x_2\overline{x_1}x_0\lor x_2x_1x_0 \]

Annahmen:

  • Es tritt im gegebenen Schaltnetz höchstens ein Fehler auf
  • Der Defekt, welcher den Fehler verursacht, ist ein gerissener Verbindungsdraht

Hier: 0-Verklemmung bzw. Stuck-at-Zero-Fault

DAG mit Drahtnummern

ti-2-deck-code-fc45f8be.tex.svg

Darstellung von f

\(f_i\): die von der Schaltung berechnete Funktion, wenn Draht \(i\) gerissen ist (Wert 0).

\[ \begin{aligned} f_1 &= \overline{0}\land x_1x_0\lor x_2\overline{x_1}x_0\lor x_2x_1x_0 = x_1x_0\lor x_2x_0\\ f_2 &= 0\land x_1x_0\lor x_2\overline{x_1}x_0\lor x_2x_1x_0 = x_2x_0\\ f_3 &= \overline{x_2}x_1x_0\lor x_2x_1x_0 = x_1x_0\\ f_4 &= \overline{x_2}x_1x_0\lor x_2\overline{x_1}x_0\\ f_5 &= x_2\overline{x_1}x_0\lor x_2x_1x_0 = x_2x_0\\ f_6 &= \overline{x_2}x_1x_0\lor x_2x_0\\ f_7 &= x_1x_0\\ f_8 &= \overline{x_2}x_1x_0\lor x_2\overline{x_1}x_0\\ f_9 &= x_2x_0 \end{aligned} \]

\[ \begin{aligned} f_{10} &= x_1x_0\\ f_{11} &= \overline{x_2}x_1x_0\lor x_2\overline{x_1}x_0\\ f_{12} &= 0\land x_0\lor x_2\overline{x_1}x_0\lor x_2x_1x_0 = x_2x_0\\ f_{13} &= x_1x_0\\ f_{14} &= \overline{x_2}x_1x_0\lor x_2\overline{x_1}x_0\\ f_{15} &= x_2x_0\\ f_{16} &= x_1x_0\\ f_{17} &= x_2x_1x_0\\ f_{18} &= \overline{x_2}x_1x_0\lor x_2\overline{x_1}x_0 \end{aligned} \]

Hinweis: \(xyz\lor x\overline{y}z=xz\)

Fehlermöglichkeiten (Ausfalltafel/-matrix)

\(x_2\) \(x_1\) \(x_0\) \(f_1\) \(f_2\) \(f_3\) \(f_4\) \(f_5\) \(f_6\) \(f_7\) \(f_8\) \(f_9\) \(f_{10}\) \(f_{11}\) \(f_{12}\) \(f_{13}\) \(f_{14}\) \(f_{15}\) \(f_{16}\) \(f_{17}\) \(f_{18}\)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 1
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0

Reduzierte Ausfallmatrix

Es gilt:

\[ \begin{aligned} f_1 &= f_6\\ f_2 &= f_5 = f_9 = f_{12} = f_{15}\\ f_3 &= f_7 = f_{10} = f_{13} = f_{16}\\ f_4 &= f_8 = f_{11} = f_{14} = f_{18} \end{aligned} \]

\(x_2\) \(x_1\) \(x_0\) \(f\) \(f_1\) \(f_2\) \(f_3\) \(f_4\) \(f_{17}\)
0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 1 1 1 1 0 1 1 0
1 0 0 0 0 0 0 0 0
1 0 1 1 1 1 0 1 0
1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 1

Fehlermatrix

Zeilen-Nr. \(x_2\) \(x_1\) \(x_0\) \(f\) \(f\oplus f_1\) \(f\oplus f_2\) \(f\oplus f_3\) \(f\oplus f_4\) \(f\oplus f_{17}\)
0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0 0
3 0 1 1 1 0 1 0 0 1
4 1 0 0 0 0 0 0 0 0
5 1 0 1 1 0 0 1 0 1
6 1 1 0 0 0 0 0 0 0
7 1 1 1 1 0 0 0 1 0
  • Eine 1 in Spalte \(f\oplus f_i\): Mit dieser Eingabe ist der Fehler \(f_i\) erkennbar (\(f\neq f_i\)).

Abschnitt 2.6

Alternative Darstellungen

  • Kofaktoren
  • Geordnete Binäre Entscheidungs-Diagramme (OBDD)
  • Gray-Code
  • Karnaugh-Diagramme

Kofaktoren

\[ f(x_i/a)=f(x_{n-1},\ldots,x_{i+1},a,x_{i-1},\ldots,x_0) \]

Dabei sei \(a\) ein fester Wert:

  • Positiver Kofaktor: \(f(x_i/1)=f(x_{n-1},\ldots,x_{i+1},1,x_{i-1},\ldots,x_0)\)
  • Negativer Kofaktor: \(f(x_i/0)=f(x_{n-1},\ldots,x_{i+1},0,x_{i-1},\ldots,x_0)\)

Baumdarstellung einer Booleschen Funktion anhand der Kofaktoren

ti-2-deck-code-16f11e57.tex.svg

Beispiel: Funktion als Entscheidungsbaum

\(x_2\) \(x_1\) \(x_0\) \(f\)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
ti-2-deck-code-7441145a.tex.svg

Beispielbaum nach Zusammenlegen der Blätter

ti-2-deck-code-78290365.tex.svg

Beispiel 2

\[ f=\ ? \]

ti-2-deck-code-0d300bc2.tex.svg

OBDD: Ordered Binary Decision Diagram

  • BDD (Binary Decision Diagram):
    • Jeder innere Knoten prüft genau eine Variable auf 0 (gestrichelte Kante) oder 1 (durchgezogene Kante)
    • Auf keinem Pfad wird eine Variable doppelt geprüft
    • Keine Kreise: Jeder Pfad von der Wurzel endet in einem Blatt 0 oder 1
  • O (ordered): Es gibt eine feste Variablenordnung (z.B. \(x_2<x_1<x_0\)), die auf allen Pfaden eingehalten wird
    • Variablen dürfen übersprungen werden: Nicht auf jedem Pfad muss jede Variable geprüft werden
ti-2-deck-code-dfab993b.tex.svg

Gültig: Ordnung \(x_2<x_1<x_0\); die 1-Kante von \(x_2\) überspringt \(x_1\) und \(x_0\)

ti-2-deck-code-95161d96.tex.svg

Ungültig: Kreis \(x_2\to x_1\to x_2\)

ti-2-deck-code-45303aff.tex.svg

Ungültig: keine feste Variablenordnung (\(x_1\) vor \(x_0\) links, \(x_0\) vor \(x_1\) rechts)

Beispiel: OBDD für die „Schwellenwert-Funktion“ \(f(x_4,x_3,x_2,x_1,x_0)=T_2^5\)

ti-2-deck-code-1a90958e.tex.svg

Beispiel: OBDD für die „Ungerade-Paritäts-Funktion“

ti-2-deck-code-d863316f.tex.svg

OBDD zur Variablenordnung \(V_1 = x_5 \leq x_2 \leq x_4 \leq x_1 \leq x_3 \leq x_0\)

ti-2-deck-code-d9df6eae.tex.svg

OBDD zur Variablenordnung \(V_2 = x_5 \leq x_4 \leq x_3 \leq x_2 \leq x_1 \leq x_0\)

ti-2-deck-code-5243d640.tex.svg

Gray-Code

  • Generierungsverfahren zur robusten Übertragung
  • Eigenschaft:
    Die Darstellung zweier benachbarter Zahlen unterscheidet sich nur durch 1 Bit
  • Generierung (eine Möglichkeit), Beispiel für die Zahl 3:
    1. Zahl im Binärcode darstellen: \(x_1=(11)_2\)
    2. Links-Shift um 1 Bit: \(x_2=x_1\ll 1=(110)_2\)
    3. XOR-Verknüpfung: \(x_3=x_1\oplus x_2=(101)_2\)
    4. Rechts-Shift um 1 Bit: \(x_4=x_3\gg 1=(10)_2\)

Beispiel: 2-Bit Gray-Code

Dualzahl Gray-Code
00 00
01 01
10 11
11 10
images/Kapitel 02 - Boolesche Funktionen/s055_seg03_snap.png
images/Kapitel 02 - Boolesche Funktionen/s055_seg04_snap.png

Beispiel: 3-Bit Gray-Code

\(c_2\) \(c_1\) \(c_0\) \(C_2\) \(C_1\) \(C_0\)
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 1
0 1 1 0 1 0
1 0 0 1 1 0
1 0 1 1 1 1
1 1 0 1 0 1
1 1 1 1 0 0
  • \(c_2c_1c_0\): Dualzahl, \(C_2C_1C_0\): zugehöriger Gray-Code

Beispiel: 3-Bit Gray-Code

\[ \begin{aligned} C_2 &= f(c_2,c_1,c_0) = c_2\overline{c_1}\,\overline{c_0}\lor c_2\overline{c_1}c_0\lor c_2c_1\overline{c_0}\lor c_2c_1c_0\\[1.5em] C_1 &= g(c_2,c_1,c_0) = \overline{c_2}c_1\overline{c_0}\lor \overline{c_2}c_1c_0\lor c_2\overline{c_1}\,\overline{c_0}\lor c_2\overline{c_1}c_0\\[1.5em] C_0 &= h(c_2,c_1,c_0) = \overline{c_2}\,\overline{c_1}c_0\lor \overline{c_2}c_1\overline{c_0}\lor c_2\overline{c_1}c_0\lor c_2c_1\overline{c_0} \end{aligned} \]

Karnaugh-Diagramme für n = 2

ti-2-deck-code-1b4b43d0.tex.svg

Karnaugh-Diagramme für n = 3, 4

ti-2-deck-code-9b41d08a.tex.svg
  • Spalten und Zeilen sind im Gray-Code angeordnet: Benachbarte Felder unterscheiden sich in genau einer Variablen.

Beispiel: Vom Wertevektor zum Karnaugh-Diagramm

ti-2-deck-code-840610db.tex.svg

Beispiel: Vom Wertevektor zum Karnaugh-Diagramm

ti-2-deck-code-16626def.tex.svg

Zusammenfassung

  • Boolesche Algebra als formale Grundlage in der Schaltungstechnik und der Computerhardware
  • Mehrere Möglichkeiten Boolesche Funktionen darzustellen: KNF, DNF, DAGs, OBDDs, Karnaugh-Diagramme
  • Gray-Code: Generierungsverfahren zur robusten Übertragung