Resolventenmethode
Die Resolventenmethode (engl. resolvent method, resolution method) ist ein von John Alan Robinson um 1963 beschriebenes Verfahren zur Berechnung aller Primterme, um Boolesche Funktionen zu minimieren. Im Unterschied zum Verfahren nach Quine und McCluskey benötigt die Resolventenmethode keine kanonische Disjunktive Normalform.
Für die Durchführung benötigt man die zwei folgenden Gesetze:
- Allgemeines Resolutionsgesetz:
- Absorptionsgesetz:
Ein mögliches Schema zum Durchführen der Resolventenmethode ist der Schichtenalgorithmus. Es wird die gegebene Disjunktive Normalform als Schicht 0 in die erste Zeile geschrieben. Nun wird jeder Term mit jedem anderen verglichen und geprüft, ob das allgemeine Resolutionsgesetz angewendet werden kann. Falls dies der Fall ist, wird die Resolvente ( in obiger Formel) in die nächste Zeile geschrieben. Diese Zeile wird dann mit Schicht 1 benannt. Als Nächstes wird überprüft, ob zwischen der hinzugefügten Resolvente und einem Term der oberen Schicht das Absorptionsgesetz angewendet werden kann. Der entsprechende Term in Schicht 0 wird gestrichen.
Nachdem alle Terme in Schicht 0 miteinander verglichen wurden, geht man genauso mit den Termen der Schicht 1 vor, wobei zu beachten ist, dass die Terme auch mit den Termen der oberen Schichten verglichen werden müssen. Terme, welche wegen Absorption gestrichen wurden, werden nicht weiter betrachtet.
Das wird so lange wiederholt, bis keine neuen Terme mehr erzeugt werden können. Die übrigen Terme sind alle Primterme der Funktion. Nun müssen einige Primterme ausgewählt werden, so dass eine minimale Funktion entsteht. Die Auswahl ist identisch wie beim Verfahren nach Quine und McCluskey.
Beispiel:
Literatur
- Friedrich L. Bauer, Martin Wirsing: Elementare Aussagenlogik. Reihe Mathematik für Informatiker, Springer Verlag, 1991, Kapitel 15: Die Resolventenmethode, ISBN 978-3-540-52974-3.
Auf dieser Seite verwendete Medien
Beispiel eines Schichtenalgorithmus (ein Schema zum Durchführen der Resolventenmethode)