Flashcards
Normalformen
Flashcards do conjunto (12)
- 1Definition einschlägiger IndexZeile (beginnend bei Null), in welcher der Funktionswert für die gegebene Variablenkombination eine Eins als Output hat.
Anmerkung: Wir gehen dabei von einer "normal" geordneten Wertetabelle aus. - 2i-ter MintermDer i-te Minterm von f ist das Produkt der Variablen in der i-ten Zeile der Wertetabelle. Dabei sind die Variablen im Minterm auf die gleiche Art und Weise verknüpft wie in der Wertetabelle
(z.B.: x=0 => NOT x) - 3Disjunktive NormalformDie disjunktive Normalform ist die Summe der Minterme ihrer einschlägigen Indizes.
Es handelt sich also um die Summe (OR) derjenigen Produkte von Variablen, für welche die Funktion eine Eins als Output liefert. - 4Funktionale Vollständigkeit einer Menge von Booleschen FunktionenEine Menge S von Booleschen Funktionen heisst funktional vollständig, wenn sich jede beliebige boolesche Funktion als Komposition von Funktionen aus S darstellen lässt.
- 5Beispiele für Mengen, die funktional vollständig sind.
- 6i-ter MaxtermDer i-te Maxterm von f ist ist die Negation des i-ten Minterms von f.
- 7Konjunktive NormalformDie Konjunktive Normalform von f bildet sich aus dem Produkt (AND) der Maxterme der nicht-einschlägigen Indizes von f. Es handelt sich also um das Produkt der negierten Variablen in den Zeilen der Wertetabelle, für welche die Funktion Eins liefert.
- 8Wann ist DNF besser? Wann KNF?DNF besser wenn mehr einschlägige Indizes (Einsen) als nicht-einschlägigie Indizes (Nullen). Ansonsten KNF.
- 9Gerichteter Azyklische Graph (DAG)Ein DAG ist ein gerichteter Graph, in dem es keinen Weg gibt, bei dem Anfangs- und Endpunkt übereinstimmen (azyklisch).
- 10Fan-InBei dem Fan-In handelt es sich um die Anzahl der Inputs eines Gatters.
- 11Fan-OutBei dem Fan-Out handelt es sich um die Anzahl der Inputs, mit denen der Output eines Gatters verbunden ist.
- 12Entwurfsprinzipien für Schaltungen- Geschwindigkeit (wenige Stufen)
- Grösse (kleine Schaltungen)
- Kleiner Fan-In und Fan-Out