Boolesche Funktion

... komplette Frage anzeigen

1 Antwort

Eine Boolesche Funktion ist eigentlich nur ein aussagenlogischer Ausdruck in Abhängigkeit einer oder mehrerer Variablen. Ich erläutere es dir am besten an einem Beispiel:

f(a, b, c, d) = abc + ad * (b + c * not(d)).

So, die Variablen sind hier offensichtlich a, b, c, d. Eine boolesche Funktion muss diese 4 Variablen nun auf einen Wahrheitswert abbilden, also true oder false. Hierzu ist es natürlich notwendig, dass auch die Variablen nur die Werte true oder false annehmen dürfen. Der Einfachheit halber nennt man true = 1 und false = 0.

Das "+", das ich oben benutzt habe, steht für das aussagenlogische oder. D.h. a + b ist gleichbedeutend mit "a oder b". Das * steht analog für das aussagenlogische und. In der booleschen Algebra gilt übrigens wieder Punkt vor Strich ;)

Das not, das ich oben verwendet habe ist selbsterklärend, normalerweise schreibt man allerdings nicht "not(d)" sondern macht stattdessen einfach einen Querstrich über das d.

Zusammenfassung: Eine boolesche Funktion ist eine Abbildung von {0,1}^n nach {0,1} und verwendet die logischen Operatoren +, * und not.

Nun hast du einen booleschen Funktionsterm gegeben und willst ihn in eine konjunktive Normalform bringen. Das ist eine besonders einfache Form, die endlich viele Disjunktionsterme miteinander "undet". D.h. statt meinem Funktionsterm da oben hättest du gerne so etwas wie

(a + b + c) * (not(a) + c + not(d)) * (a + b + c + d) * ... Und in den Klammern sollen immer nur Summen von einzelnen Variablen stehen.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Kungfukuh
18.11.2012, 13:03

Danke für die Erklärung. Mich verwirrt folgender Umstand:

Eine Boolesche Variable nimmt den Wert entweder "wahr" oder "falsch" an. Bei der Erklärung auf wiki http://de.wikipedia.org/wiki/Boolesche_Variable steht allerdings, dass eine solche Variable endlich viele (also auch zb 3 Werte) annehmen darf. Nun, wenn man davon ausgeht, dass sie 3 Werte annimmt, wie soll man das überhaupt mit einer Boolschen Algebra in Verbindung bringen, da diese lediglich als ein n-dimensionaler {0,1}-Gitter definiert wird? Denn 3 ist keine Potenz von 2.

Zur KNF:

ich blicke nicht ganz durch, warum die letzte Form besser sein soll, als die erste. Wann stellt man fest, dass eine KNF vorliegt?

0

Was möchtest Du wissen?