Veroderung UND-verknüpfter boolscher Ausdrücke
01.07.2008 15:40:18
zacharias
ich habe ein kniffeliges Problem für das meine Kenntnisse in boolscher Algebra, bzw. Algorithmenprogrammierung nicht ausreichen.
Folgende UND-verknüpfte boolsche Ausdrücke (+: UND-Verknüfung; /: ODER-Verknüpfung)
sollen durch Veroderung mit Hilfe möglichst weniger boolscher Ausdrücke dargestellt werden:
+A1+B1+C1
+A1+B2+C1
+A2+B1+C1
+A1+B1+C2
+A1+B2+C2
Gesucht ist also ein Algorithmus, der durch Veroderung zu möglichst wenig Varianten führt, die in Summe die gleiche logische Verknüpfung abbilden, wie die oben dargestellten ODER-freien Ausdrücke.
Ein Beispiel habe ich in dieser Arbeitsmappe untergebracht:
https://www.herber.de/bbs/user/53497.xls
Der Algorithmus sollte also die kürzeste Lösung liefern
+A1+B1/B2+C1/C2
+A2+B1+C1
und nicht etwa eine zwar ebenfalls richtige, aber längere wie diese hier
+A1/A2+B1+C1
+A1+B2+C1/C2
+A1+B1+C2
Optimale wäre, wenn Eure Lösung so flexibel ist, daß sie auch mit anderen UND-verknüpften boolschen Ausdrücken funktioniert.
Danke an Alle, die sich mit dem Problem befassen
und Grüße aus WOB
Zacharias