Worauf baut die zweiwertige Boole'sche Algebra auf?
Auf der Menge B = {0, 1}, wobei 0 = „falsch" und 1 = „wahr" interpretiert wird. — Grundlage der Aussagenlogik (Aussagen mit eindeutigem Wahrheitswert). Begründer: George Boole.
Was ist eine logische Variable und was eine Belegung?
Logische Variable a ∈ {0,1}: kann nur die Werte 0 (falsch) oder 1 (wahr) annehmen. Belegung = Zuweisung eines konkreten Wertes an die Variable. — Beispiel: Aussage „11 ist Primzahl" → a = 1.
UND-Verknüpfung (Konjunktion): Wertetabelle und Schreibweisen?
c = a∧b ist nur 1, wenn BEIDE Eingänge 1 sind (0/0→0, 0/1→0, 1/0→0, 1/1→1). — Schreibweisen: a∧b = a UND b = a·b. Gatter: & (UND-Gatter).
ODER-Verknüpfung (Disjunktion): Wertetabelle und Schreibweisen?
c = a∨b ist 1, wenn MINDESTENS ein Eingang 1 ist (nur 0/0→0). — Schreibweisen: a∨b = a ODER b = a+b. Gatter: ≥1 (ODER-Gatter).
NICHT-Verknüpfung (Negation): Wertetabelle und Schreibweisen?
b = ¬a kehrt den Wert um (0→1, 1→0). — Schreibweisen: ¬a = NICHT a = ā. Gatter: 1 mit Negationskreis.
Rechenregeln für die UND-Verknüpfung (a∧0, a∧1, a∧a)?
a∧0 = 0, a∧1 = a, a∧a = a. — Merke: 0 ist „absorbierend" (macht alles 0), 1 ist neutral.
Rechenregeln für die ODER-Verknüpfung (a∨0, a∨1, a∨a)?
a∨0 = a, a∨1 = 1, a∨a = a. — Merke: 1 ist „absorbierend" (macht alles 1), 0 ist neutral.
Welche Vorrangregeln gelten in Boole'schen Ausdrücken?
¬ (NICHT) bindet am stärksten, dann ∧ (UND), dann ∨ (ODER) → „UND vor ODER" (analog Punkt vor Strich). — Beispiel: a∧¬b∨c = (a∧(¬b))∨c. Klammern überschreiben die Reihenfolge.
Was ist die Disjunktive Normalform (DNF)?
Eine ODER-Verknüpfung (Disjunktion) der UND-Terme (Minterme) aller Zeilen, in denen die Ausgangsvariable 1 ist. — Standardform zur Beschreibung jeder Booleschen Funktion aus ihrer Wahrheitstabelle.
Verfahren: Wie ermittelt man die DNF aus einer Wahrheitstabelle?
1) Alle Zeilen mit Ausgang = 1 suchen. 2) Pro Zeile UND-Term aller Eingangsvariablen bilden: Variable normal, wenn dort 1, negiert (ā), wenn dort 0. 3) Alle UND-Terme mit ODER verknüpfen. — Knackpunkt: pro 1-Zeile genau ein Produktterm.
Aufgabe: DNF einer Funktion, die nur für (a,b,c) = (0,1,1) und (1,0,1) gleich 1 ist?
Zeile (0,1,1): ā∧b∧c. Zeile (1,0,1): a∧b̄∧c. DNF: y = (ā∧b∧c) ∨ (a∧b̄∧c). — Knackpunkt: 0 → negierte Variable, 1 → normale Variable.
Wie lauten Kommutativ- und Assoziativgesetz?
Kommutativ: a∧b = b∧a; a∨b = b∨a. Assoziativ: (a∧b)∧c = a∧(b∧c); (a∨b)∨c = a∨(b∨c). — Reihenfolge bzw. Klammerung von gleichartigen Operatoren ist beliebig.
Wie lautet das Distributivgesetz der Boole'schen Algebra?
a∧(b∨c) = (a∧b)∨(a∧c) UND a∨(b∧c) = (a∨b)∧(a∨c). — Knackpunkt: Anders als in der normalen Algebra gilt BEIDE Richtungen (auch ∨ distribuiert über ∧).
Wie lautet das Negations-/Komplementärgesetz?
a∨ā = 1 und a∧ā = 0. — Eine Variable ODER ihre Negation ist immer wahr; UND ihre Negation immer falsch. Doppelte Negation: ¬(¬a) = a.
Wie lautet das Idempotenzgesetz und die Null-/Einsgesetze?
Idempotenz: a∨a = a, a∧a = a. Null-/Einsgesetze: a∨0=a, a∨1=1, a∧0=0, a∧1=a. — Mehrfaches gleiches Glied kann zusammengefasst werden.
Wie lautet das DeMorgan-Gesetz?
¬(a∨b) = ā∧b̄ und ¬(a∧b) = ā∨b̄. — Merksatz: Negation „umgedreht" – aus ∨ wird ∧ und umgekehrt, jede Variable wird negiert. Sehr wichtig zum Auflösen von Gesamtnegationen.
Wie lauten die Absorptionsgesetze?
a∨(a∧b) = a und a∧(a∨b) = a. Außerdem: (a∧b)∨(ā∧b) = b und a∨(ā∧b) = a∨b. — Knackpunkt: ein „eingeschlossener" Term wird vom äußeren absorbiert.
Aufgabe: Vereinfache (a∧b) ∨ (a∧b̄).
= a∧(b∨b̄) [Distributiv] = a∧1 [Komplementär] = a. — Knackpunkt: a ausklammern, dann b∨b̄ = 1.
Aufgabe: Vereinfache ¬(a∨b) ∨ (a∧b̄).
= (ā∧b̄) ∨ (a∧b̄) [DeMorgan] = b̄∧(ā∨a) [Distributiv] = b̄∧1 [Komplementär] = b̄. — Ergebnis: ¬b.
Aufgabe: Vereinfache (a∨b) ∧ (a∨b̄) ∧ (ā∨b).
(a∨b)∧(a∨b̄) = a∨(b∧b̄) = a∨0 = a. Dann a∧(ā∨b) = (a∧ā)∨(a∧b) = 0∨(a∧b) = a∧b. — Ergebnis: a∧b.
Aufgabe: Vereinfache a ∨ (b̄ ∧ (ā ∨ b)).
= a∨[(b̄∧ā)∨(b̄∧b)] [Distributiv] = a∨[(b̄∧ā)∨0] = a∨(b̄∧ā) = (a∨b̄)∧(a∨ā) [Distributiv] = (a∨b̄)∧1 = a∨b̄. — Ergebnis: a∨¬b.
Was ist die NAND-Verknüpfung?
NAND = „Nicht UND" = ¬(a∧b). Wertetabelle: 1,1,1,0 (nur 0, wenn beide Eingänge 1). — NAND ist universell: jede Boolesche Funktion lässt sich allein mit NAND aufbauen.
Was ist die NOR-Verknüpfung?
NOR = „Nicht ODER" = ¬(a∨b). Wertetabelle: 1,0,0,0 (nur 1, wenn beide Eingänge 0). — Auch NOR ist universell.
Was ist die XOR-Verknüpfung (Exklusiv-Oder) und wie drückt man sie mit Grundoperationen aus?
a⊕b = 1, wenn die Eingänge UNGLEICH sind (0/0→0, 0/1→1, 1/0→1, 1/1→0). Mit Grundoperationen: a⊕b = (a∧b̄)∨(ā∧b). — XOR entspricht der dualen Addition ohne Übertrag.
Was ist die Äquivalenz („genau dann wenn") und wie drückt man sie aus?
a↔b = 1, wenn die Eingänge GLEICH sind (0/0→1, 1/1→1, sonst 0). Mit Grundoperationen: a↔b = (a∧b)∨(ā∧b̄). — Äquivalenz = ¬XOR (XNOR).
Aufgabe: 3-er-Jury entscheidet per Mehrheit (Ausgang y=1 bei ≥ 2 Ja-Stimmen). Boole'scher Ausdruck?
y = (a∧b) ∨ (a∧c) ∨ (b∧c). — Jeder UND-Term steht für eine mögliche Zweier-Mehrheit; trifft mindestens eine zu, ist y = 1.
Wofür stehen die Gattersymbole &, ≥1 und =1?
& = UND-Gatter (Konjunktion), ≥1 = ODER-Gatter (Disjunktion), =1 = XOR-Gatter (Exklusiv-Oder). — Ein Negationskreis am Ausgang macht daraus NAND bzw. NOR.
Warum sind DNF und Wahrheitstabelle äquivalent zum logischen Ausdruck?
Weil sie dasselbe Ein-/Ausgangsverhalten beschreiben: jede Wahrheitstabelle liefert genau eine DNF, die sich per Rechenregeln zum minimierten Ausdruck vereinfachen lässt. — Knackpunkt: erst DNF aufstellen, dann mit den Gesetzen minimieren.
Zuletzt geändertvor 9 Tagen