Direkt zum Inhalt

Lexikon der Mathematik: Baummethode

Methode zur Berechnung der vollständigen Summe einer vollständig spezifizierten Booleschen Funktion. Sie beruht auf dem folgenden Lemma:

Gegeben seien die vollständigen Summen p1und p2der Booleschen Funktionen g : {0, 1}n → {0, 1} und h : {0, 1}n → {0, 1}.

Dann ist das Boolesche Polynom p, das durch Ausmultiplizieren von p1und p2unter Verwendung des Distributivgesetzes (Boolesche Algebra) und der Regeln l ∧ l = l, \(l\wedge \overline{l}=0\), l ∧ 1 = l, l ∧ 0 = 0 für alle Booleschen Literale l, und durch anschließendes Entfernen der 0-Summan- den und der Booleschen Monome, für die es eine echte Verkürzung im so entstandenen Booleschen Polynom gibt, entsteht, eine vollständige Summe der Konjunktion g ∧ h der Booleschen Funktionen g und h.

Die vollständige Summe einer über den Booleschen Variablen x1, …, xn definierten Booleschen Funktion f : {0, 1}n → {0, 1} wird bei diesem Verfahren berechnet, indem rekursiv die vollständige Summe p1 der Booleschen Funktion \({x}_{i}\vee {f}_{\overline{{x}_{i}}}\) und die vollständige Summe p2 der Booleschen Funktion \(\bar{{x}_{i}}\vee {f}_{{x}_{i}}\) für eine beliebige Boolesche Variable xi, von der f abhängt, berechnet werden. Hierbei bezeichnet \({f}_{{x}_{i}}\) den positiven Kofaktor und \({f}_{\overline{{x}_{i}}}\) den negativen Kofaktor von f nach xi. Die Konjunktion von \({x}_{i}\vee {f}_{\overline{{x}_{i}}}\) und \(\overline{{x}_{i}}\vee {f}_{{x}_{i}}\) ist gleich der Booleschen Funktion f.

Die vollständige Summe von f kann somit aus den vollständigen Summen p1 und p2 von \({x}_{i}\vee {f}_{\overline{{x}_{i}}}\) und \(\overline{{x}_{i}}\vee {f}_{{x}_{i}}\) durch Anwendung des obigen Satzes berechnet werden.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos