Beweismethode für Boolesche Funktionen

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Beweismethode für Boolesche Funktionen
Gibt es eine Beweismethode für Boolesche Funktionen, wie z.B. die vollständige Induktion in der Mathmatik?
Wenn ja, welches?


Spontan würde ich es bei einfachen Funktionen mit Wahrheitstabellen probieren (wenn alle Fälle abgedeckt sind, müsste das als Beweis gelten). Ansonsten müsste man die Funktion mal durch einen SAT-Solver jagen. Vielleicht meldet sich aber noch jemand, der etwas mehr Ahnung hat :wink:


Das ist gar nicht so einfach. Falls du BFS noch nicht gehört hast, dann ist das Erfüllbarkeitsproblem das richtige Stichwort für dich.


Ein weiteres wichtiges Stichwort dazu ist die Resolution. Näheres dazu lernt man in Grundlagen der Logik in der Informatik (ehemals Grundlagen der Logik und Logikprogrammierung) und weiteren Vertiefungsvorlesungen. Wahrheitstabellen sind aber auch als Beweismethode geeignet, sind jedoch meist sehr aufwändig.


Ich danke euch! Ich werde mir mal die Stichworte näher anschauen.