Gibt es einen Trick, um boolesche Formeln umzuformen, für den NAchweis, dass zwei boolesche Funktionen gleich sind?

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet

Um Äquivalenz von zwei Logikfunktionen zu zeigen, gibt es viele Möglichkeiten. Natürlich kannst du versuchen, eine Funktion so umzuformen, dass sie wie die andere aussieht. Dazu kannst du die üblichen Logikregeln verwenden: https://de.wikipedia.org/wiki/Boolesche_Algebra#Definition

Tricks vom Umformen lassen sich so auf die Schnelle schlecht vermitteln, da ist viel Übungssache dabei und der geeignete Blick. Aber als Hinweis: Disjunktive Minterm-Form und Konjungtive Maxtermform sind zum Beispiel immer eindeutig.

Möchtest du die Funktionen f und g auf Gleichheit prüfen, kannst du aber auch prüfen, ob: (f und g) oder ((nicht f) und (nicht g)) = 1 ist. (Äquivalenzoperator)
Automatisiert wird dieser Zusammenhang in invertierter Form verwendet, um einen Erfüllbarkeitstest (SAT-Checker) zu machen. Das sind die mächtigsten Tools für große Funktionen mit vielen Variablen.

Du könntest aber auch den OBDD beider Funktionen erstellen (ordered binary decision diagram). Wird der OBDD nach gleichen Variablen entwickelt, muss er gleich aussehen.

Für kleinere Funktionen lässt sich natürlich auch Funktionstabelle auf Übereinstimmung prüfen.

PS: Ich habe mir damals fürs Studium einen kleinen Logikrechner programmiert: https://kmkcl.de/logikrechner.html
Das hat mir damals manchmal geholfen. ;)