--- title: "Kapitel 02 - Darstellung Boolescher Funktionen" source: "ti-2-deck.html" generated-by: uni-vault/sync.py --- # Kapitel 02 - Darstellung Boolescher Funktionen ## 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: - 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 - **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? - Ja - Nein - Ja, nach geschickter Vereinfachung ## 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. - 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 - 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}\] - 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 ## Grundbausteine zur Realisierung Boolescher Funktionen ## 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 ## Beispiel Alternative Schaltung: ## DAG-Darstellung DAG = Directed Acyclic Graph (gerichteter azyklischer Graph) ## Beispiel für zyklischen Graph: Flimmerschaltung ## Beispiel für zyklischen Graph: Flimmerschaltung ## Beispiel für zyklischen Graph: Flimmerschaltung ## 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 ## 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 ## 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 ## Beispielbaum nach Zusammenlegen der Blätter ## Beispiel 2 \[f=\ ?\] ## 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 ## Beispiel: OBDD für die „Schwellenwert-Funktion“ \(f(x_4,x_3,x_2,x_1,x_0)=T_2^5\) ## Beispiel: OBDD für die „Ungerade-Paritäts-Funktion“ ## OBDD zur Variablenordnung \(V_1 = x_5 \leq x_2 \leq x_4 \leq x_1 \leq x_3 \leq x_0\) ## OBDD zur Variablenordnung \(V_2 = x_5 \leq x_4 \leq x_3 \leq x_2 \leq x_1 \leq x_0\) ## 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: Zahl im Binärcode darstellen: \(x_1=(11)_2\) - Links-Shift um 1 Bit: \(x_2=x_1\ll 1=(110)_2\) - XOR-Verknüpfung: \(x_3=x_1\oplus x_2=(101)_2\) - 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 ## 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 ## Karnaugh-Diagramme für n = 3, 4 - Spalten und Zeilen sind im **Gray-Code** angeordnet: Benachbarte Felder unterscheiden sich in genau einer Variablen. ## Beispiel: Vom Wertevektor zum Karnaugh-Diagramm ## Beispiel: Vom Wertevektor zum Karnaugh-Diagramm ## 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