Was ist die zweiwertige Boole'sche Algebra?
Eine Algebra über der Menge B={0,1}, wobei 0 als „falsch" und 1 als „wahr" interpretiert wird (nach George Boole). — Grundlage der Aussagenlogik und der digitalen Schaltungstechnik.
Was ist eine logische Variable und eine Belegung?
Eine logische Variable a ∈ {0,1} kann nur die Werte 0 (falsch) oder 1 (wahr) annehmen. Die Zuweisung eines Wertes heißt Belegung. — Beispiel: Aussage „11 ist Primzahl" → a=1.
Definiere die UND-Verknüpfung (Konjunktion).
c = a ∧ b = a·b ist nur dann 1, wenn BEIDE Variablen 1 sind.
Schreibweisen: logisch a∧b = a UND b; arithmetisch a·b (logisches Produkt). Entspricht einer Reihenschaltung.
Definiere die ODER-Verknüpfung (Disjunktion).
c = a ∨ b = a+b ist 1, wenn MINDESTENS EINE Variable 1 ist.
Schreibweisen: logisch a∨b = a ODER b; arithmetisch a+b (logische Summe).
Achtung: „+" ist die Boole'sche Summe, daher 1+1=1 (nicht 2). Entspricht einer Parallelschaltung.
Definiere die NICHT-Verknüpfung (Negation).
b = ¬a = a̅ hat immer den gegenteiligen Wert von a (0↔1).
Schreibweisen: logisch ¬a = NOT a; arithmetisch a̅
Zusammengesetzte Negationen werden hier als (…)' geschrieben, z. B. ¬(a∨b) = (a+b)'.
Rechenregeln für die UND-Verknüpfung mit Konstanten?
Logisch:
a∧0 = 0;
a∧1 = a;
a∧a = a.
Arithmetisch:
a·0 = 0;
a·1 = a;
a·a = a.
Eine einzige 0 in einer UND-/Produkt-Kette macht das Ganze 0; 1 ist neutrales Element.
Rechenregeln für die ODER-Verknüpfung mit Konstanten?
a∨0 = a;
a∨1 = 1;
a∨a = a.
a+0 = a;
a+1 = 1;
a+a = a.
Eine einzige 1 in einer ODER-/Summen-Kette macht das Ganze 1; 0 ist neutrales Element („+" ist die logische Summe).
Definiere NAND und NOR.
NAND(a,b) = ¬(a∧b) = (a·b)' -> nur 0, wenn beide 1.
NOR(a,b) = ¬(a∨b) = (a+b)': nur 1, wenn beide 0.
NAND und NOR sind je für sich funktional vollständig (alle Logik nur damit baubar).
Definiere XOR (Exklusiv-Oder) und Äquivalenz.
XOR a⊕b = 1, wenn a und b VERSCHIEDEN sind; arithmetisch a⊕b = a·b̅ + a̅·b .
Äquivalenz a⇔b = ¬(a⊕b) = a·b + a̅·b̅ = 1, wenn a und b GLEICH sind.
XOR entspricht der stellenweisen Dualaddition ohne Übertrag.
Welche Vorrangregeln gelten in logischen Ausdrücken?
¬ (NICHT) bindet am stärksten,
dann ∧ // • (UND),
dann ∨ // + (ODER)
Beispiel:
a ∧ ¬b ∨ c = (a ∧ (¬b)) ∨ c
a·b̅ + c = (a·(b̅)) + c.
Nenne Kommutativ-, Assoziativ- und Distributivgesetz der Boole'schen Algebra.
Kommutativ: a∧b=b∧a (a·b=b·a), a∨b=b∨a (a+b=b+a).
Assoziativ: (a∧b)∧c=a∧(b∧c) ((a·b)·c=a·(b·c)), analog für ∨/+.
Distributiv: a∨(b∧c)=(a∨b)∧(a∨c) → a+(b·c)=(a+b)·(a+c) UND a∧(b∨c)=(a∧b)∨(a∧c) → a·(b+c)=(a·b)+(a·c).
Beachte: in der Boole'schen Algebra ist auch ∨ über ∧ distributiv, also a+(b·c)=(a+b)·(a+c) – anders als in der gewöhnlichen Arithmetik!
Wie lauten Negations-, Idempotenz- und Null/Eins-Gesetz?
Negation (Komplement):
a∨¬a=1 (a+a̅=1),
a∧¬a=0 (a·a̅=0);
doppelte Negation:
¬¬a=a
(a̅)'=a.
Idempotenz:
a∨a=a (a+a=a),
a∧a=a (a·a=a).
Null/Eins:
∨0=a (a+0=a),
a∨1=1 (a+1=1),
a∧0=0 (a·0=0),
a∧1=a (a·1=a).
Wie lauten die DeMorgan-Gesetze?
¬(a∨b) = ¬a ∧ ¬b
(a+b)' = a̅·b̅
¬(a∧b) = ¬a ∨ ¬b
(a·b)' = a̅+b̅.
Merke: Negation „nach innen ziehen" kehrt jede Variable um UND tauscht ∧↔∨ (bzw. ·↔+). Sehr wichtig zum Auflösen von Über-/Negationsstrichen.
Wie lauten die Absorptionsgesetze?
a∨(a∧b)=a (a+a·b=a)
a∧(a∨b)=a (a·(a+b)=a).
Außerdem:
a∨(¬a∧b)=a∨b (a+a̅·b=a+b)
a∧(¬a∨b)=a∧b (a·(a̅+b)=a·b)
Verfahren: Aufstellen der Disjunktiven Normalform (DNF) aus einer Wertetabelle?
1) Alle Zeilen mit Ausgang = 1 suchen.
2) Je Zeile einen Minterm (UND-Verknüpfung / Produkt aller Eingänge) bilden: Variable normal, wenn sie 1 ist, negiert, wenn sie 0 ist.
3) Alle Minterme mit ODER (Summe) verknüpfen.
Aufgabe (DNF): d=1 bei (a,b,c) = 001, 011, 111 – wie lautet die DNF?
Logisch: (¬a∧¬b∧c) ∨ (¬a∧b∧c) ∨ (a∧b∧c).
Arithmetisch: a̅·b̅·c + a̅·b·c + a·b·c.
Jede 1-Zeile liefert genau einen UND-/Produkt-Term; 0-Eingänge werden negiert eingesetzt.
Aufgabe: Vereinfache (a∧b) ∨ (a∧¬b).
Logisch: (a∧b)∨(a∧¬b) = a∧(b∨¬b) [Distributiv] = a∧1 [Komplement] = a [Eins-Gesetz].
Arithmetisch: a·b + a·b̅ = a·(b+b̅) = a·1 = a.
Klassisches Ausklammern: a ist in beiden Termen, b und b̅ ergänzen sich zu 1.
Aufgabe: Vereinfache a ∨ (¬b ∧ (¬a ∨ b)).
Logisch: a ∨ ((¬b∧¬a) ∨ (¬b∧b)) [Distributiv] = a ∨ (¬b∧¬a) [Neg./Neutral] = (a∨¬b) ∧ (a∨¬a) [Distributiv] = (a∨¬b)∧1 = a ∨ ¬b.
Arithmetisch: a + b̅·(a̅+b) = a + (a̅·b̅ + b·b̅) = a + a̅·b̅ = (a+b̅)·(a+a̅) = (a+b̅)·1 = a + b̅. — Ergebnis: a ∨ ¬b = a + b̅.
Aufgabe: Vereinfache (A∨B) ∧ (A∨¬B) ∧ (¬A∨B).
Logisch: erst (A∨B)∧(A∨¬B) = A∨(B∧¬B) = A∨0 = A; dann A∧(¬A∨B) = (A∧¬A)∨(A∧B) = 0∨(A∧B) = A∧B.
Arithmetisch: (A+B)·(A+B̅) = A+(B·B̅) = A+0 = A; dann A·(A̅+B) = (A·A̅)+(A·B) = 0+(A·B) = A·B.
Aufgabe: Vereinfache ¬(¬(a∨b) ∧ ¬(a∨b)).
Logisch: innen Idempotenz ¬(a∨b)∧¬(a∨b) = ¬(a∨b); dann doppelte Negation ¬(¬(a∨b)) = a∨b.
Arithmetisch: (a+b)'·(a+b)' = (a+b)' [Idempotenz]; dann ((a+b)')' = a+b.
Verfahren: Wie wendet man DeMorgan zum Vereinfachen eines negierten Ausdrucks an?
Negationsstrich über einem Ausdruck mit DeMorgan auflösen:
¬(a∧b)→¬a∨¬b ((a·b)'→a̅+b̅)
¬(a∨b)→¬a∧¬b ((a+b)'→a̅·b̅);
¬¬a=a ((a̅)'=a)
Bei mehrfach geschachtelten Strichen von außen nach innen arbeiten und Operatoren ∧↔∨ (·↔+) tauschen.
Aufgabe: Stelle für die DSDS-3er-Jury (Mehrheitsentscheid) den Ausdruck auf.
y = 1, wenn mindestens 2 von 3 zustimmen:
logisch y = (a∧b) ∨ (a∧c) ∨ (b∧c);
arithmetisch y = a·b + a·c + b·c.
Aufgabe (Zufahrtsschranke): Öffnet, wenn (A ODER B) UND C. Logischer Ausdruck?
Logisch D = (A ∨ B) ∧ C;
arithmetisch D = (A+B)·C.
Als DNF aus der Wertetabelle: (¬A∧B∧C)∨(A∧¬B∧C)∨(A∧B∧C) = A̅·B·C + A·B̅·C + A·B·C;
minimiert zu (A∨B)∧C = (A+B)·C.
Wozu dient die Minimierung Boole'scher Ausdrücke?
Möglichst wenige Variablen/Terme → einfachere, billigere und schnellere Schaltung mit weniger Gattern.
Wie übersetzt man einen Boole'schen Ausdruck in eine Gatterschaltung (und umgekehrt)?
Jede Operation wird durch ihr Gatter ersetzt; Klammerung bestimmt die Verschachtelung. ¬ / a̅ = NICHT-Gatter, ∧ / · = UND (&), ∨ / + = ODER (≥1). — Aus einer Schaltung liest man rückwärts den Ausdruck ab (logisch oder arithmetisch) und kann die Wertetabelle ausfüllen.
Aufgabe: Vereinfache ¬(A∨B) ∨ (A∧¬B).
Logisch: ¬(A∨B) = ¬A∧¬B (DeMorgan); (¬A∧¬B) ∨ (A∧¬B) = ¬B∧(¬A∨A) = ¬B∧1 = ¬B.
Arithmetisch: (A+B)' = A̅·B̅; (A̅·B̅) + (A·B̅) = B̅·(A̅+A) = B̅·1 = B̅.
Aufgabe: Vereinfache (a∨b) ∧ (a∨¬b).
Logisch (Distributiv rückwärts): a ∨ (b∧¬b) = a ∨ 0 = a.
Arithmetisch: (a+b)·(a+b̅) = a + (b·b̅) = a + 0 = a.
Aufgabe: Vereinfache a ∨ (b ∧ a ∧ ¬b ∧ c).
Logisch: im Klammerterm steht b∧¬b = 0, also ist die ganze Klammer 0; a ∨ 0 = a.
Arithmetisch: b·b̅ = 0 ⇒ a + (b·a·b̅·c) = a + 0 = a.
Warum sind NAND bzw. NOR funktional vollständig?
Mit NAND allein (oder NOR allein) lassen sich NICHT, UND und ODER nachbilden, also jede Boole'sche Funktion.
Beispiel: ¬a = a NAND a, a̅ = (a·a)'; daher baut man Schaltwerke oft nur aus NAND-Gattern.
Verfahren: logische Äquivalenz zweier Ausdrücke über Wertetabellen zeigen?
Für beide Ausdrücke die vollständige Wertetabelle (alle 2^n Belegungen) aufstellen; sind die Ausgangsspalten identisch, sind sie äquivalent.
Knackpunkt: ALLE Belegungen prüfen; eine Abweichung widerlegt die Äquivalenz.
Welche Klammern darf man wegen UND-vor-ODER weglassen?
Klammern um UND-/Produkt-Terme innerhalb einer ODER-/Summen-Verknüpfung sind überflüssig:
(a∧b) ∨ (c∧d) = a∧b ∨ c∧d (a·b)+(c·d) = a·b + c·d.
Nicht weglassen darf man Klammern, die ODER vor UND erzwingen: a ∧ (b∨c) = a·(b+c).
Zuletzt geändertvor 9 Tagen