Computersysteme I - 1608
Boolesche Ausdrücke / Schaltungen, Grundlagen für Technische Informatik und Computersysteme, Kurs an der Fernuni Hagen
Boolesche Ausdrücke / Schaltungen, Grundlagen für Technische Informatik und Computersysteme, Kurs an der Fernuni Hagen
-
- 1 / 20
-
Cartes-fiches
Primimplikant
Ein Implikant einer Booleschen
Funktion, der in keinem anderen Implikanten
vollständig enthalten ist.
Implikant
Fasst Min- oder Maxterme zusammen, die eine Funktion erfüllen
Konjunktion und Disjunktion
Konjunktion (Und Verknüpfung) ^ Minterm x1^x2^x3 Monom x1^x3 1
Disjunktion (Oder Verknüpfung) v Maxterm x1vx2vx3 Klausel x1vx3 0
Kernimplikant
Ist ein wesentlicher Implikant, der von keinen anderen Monom (Implikant) überdeckt wird.
Primterm
anderes Wort für Primimplikant
Was ist der Unterschied zwischen einem Minterm und einem Monom bzw. Maxterm und Klausel?
Ein Minterm ist so definiert, dass er X i oder ~X i für alle i von 1 bis n enthält. Sprich, ein Minterm enthält alle Variablen auf denen die Funktion definiert ist in negierter oder nicht negierter Form.
Dem gegenüber ist ein Monom einfach eine Konjunktion von Literalen, ohne dass über für die Literale Vorschriften festgelegt werden. Die einzige Vorschrift ist, dass es endlich viele sind (siehe Definition 1.19).
Das gleiche gilt für Maxterme und Klauseln.
Was ist die Kanonische disjunktive Normalform?
Die KDNF ist die Disjunktion aller Monome, die zu Elementen des Trägers gehören. Der Träger ist die Menge der Belegungen, an denen die Funktion den Wert 1 annimmt. Da der Träger eindeutig definiert ist, ist es - bis auf die Reihenfolge - auch die KDNF. KDNF ist meist relativ lang und damit teuer, andere DNF sind kürzer.
Wie viele n-stellige Schaltfunktionen gibt es? Eine n-stellige Schaltfunktion ist eine Abbildung f:{0,1}n->{0,1}.
Es gibt 22n n-stellige Schaltfunktionen. (In Worten: Zwei hoch Zwei hoch n).
Wie sind die Kosten L(e) eines Boole'schen Ausdrucks definiert?
Sei e ∈ B ein Boole’scher Ausdruck. Die Kosten L(e) von e sind definiert als die Anzahl von Vorkommen der Zeichen ∧, ∨ und ∼ in e. Beispiel: L(X1 ∧ ∼X2∧ X3) = 3.
Decoder
wandelt eine t-stellige binäre Zahlendarstellung in eine unäre Zahlendarstellung um
{0,1}n -> {0,1}2^n
dc(st-1,...,s0)=(a2t-1,...,a0)
Coder
er wandelt ein unäre Zahlendarstellung in eine binäre Zahlendarstellung um
{0,1}2^t -> {0,1}t+2
warum t+2, 0 für den Fehlerfall alles null,1 für den Fehlerfall mehr als eine 1
Kosten C und Tiefe T eine Halbaddierers
Kosten C(HA) = 2
Tiefe T(HA) = 1
Kosten C und Tiefe T eines Volladdierers
Kosten C(FA)=5
Tiefe T(FA)=3
da eine Volladdierer aus zwei Halbaddierer und einem OR-Gatter besteht C(FA) = C(HA) + C(HA) + C(OR) = 2 + 2 + 1
Ein Minimalpolynom besteht niemals ausschließlich aus Kernimplikanten.
Eine kanonische konjunktive Normalform ist eine Konjunktion von Disjunktionstermen, wobei in jedem Disjunktionsterm jede Variable in einem Literal vorkommen muss.
Die kanonische konjunktive Normalform einer Funktion ist eindeutig bis auf die Reihenfolge der Minterme und die Reihenfolgen der Literale in den Mintermen.
Die Formelgröße einer Schaltfunktion kann nicht kleiner sein als die Kosten ihrer kürzesten disjunktiven Normalform.
Die Trägermenge einer Schaltfunktion enthält stets mehr als ein Element.
Eine Schaltfunktion gegebener Variablenzahl ist durch die Menge ihrer Primimplikanten eindeutig bestimmt.
Eine Schaltfunktion gegebener Variablenzahl ist durch die Menge ihrer Implikanten eindeutig bestimmt.
