Frage von Kungfukuh,

Boolesche Funktion

Hallo,

könnte mir jemand vielleicht kurz erklären, was eine Boolesche Funktion (insbesondere was eine Boolesche Funktion in KNF (=Kojunktive Normalform)) sein soll?

Grüße

Hilfreichste Antwort von Melvissimo,
1 Mitglied fand diese Antwort hilfreich

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.

Kommentar von Kungfukuh,

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?

Kommentar von Kungfukuh,

Verstehe ich richtig, dass eine KNF nicht eindeutig ist, und immer dann vorliegt, wenn verschiedene Terme, die sich lediglich aus "oder" und "not" Operatoren zusammensetzen, durch "und" Operatoren verbunden werden?

Kommentar von Melvissimo,

Verstehe ich richtig, dass eine KNF nicht eindeutig ist

Nicht eindeutig stimmt insofern, dass sowohl + als auch * kommutativ wirken. Und selbstverständlich kann man auch immer wieder einen booleschen Ausdruck dranmultiplizieren, der "1" ergibt, denn das ändert den Wahrheitswert nicht ab, also ist eine KNF in der Tat keineswegs eindeutig.

und immer dann vorliegt, wenn verschiedene Terme, die sich lediglich aus "oder" und "not" Operatoren zusammensetzen, durch "und" Operatoren verbunden werden?

Ja, so könnte man das ausdrücken. Allerdings muss dazu gesagt werden, dass ein not-Operator nur auf eine einzelne Variable angewendet werden darf. So ist z.B. not(a) + not(b) in einem Disjunktionsterm erlaubt, aber not(a+b) nicht, da es nach de Morgan äquivalent zu not(a) * not(b) wäre, was keine Disjunktion mehr ist.

Kommentar von Kungfukuh,

Vielen vielen Dank für die guten Erklärungen!!! :-)

Kommentar von Melvissimo,

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

Wie man das feststellt, haben wir unten ja schon geklärt. Sie ist insofern besser, dass man die Schaltung durch eine einfachere Konstruktion von Gattern darstellen kann (vor allem eine durchsichtigere Konstruktion). Ich bin aber kein Informatiker, vllt kann dir ein anderer noch eine bessere Begründung nennen :D

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.

Das stimmt natürlich. Ich bin aber davon ausgegangen, dass du hier nur zwischen true und false unterscheiden willst, da mir die konjunktive Normalform nur für diesen Spezialfall bekannt ist ^^

Antwort von burn3r,
1 Mitglied fand diese Antwort hilfreich

z.b.

bool A; bool B; bool C;

if (A == B ) { tuWas(); }

Das ist z.b. eine boolesche Funktion. für KNF schauste hier: http://de.wikipedia.org/wiki/Konjunktive_Normalform

Kommentar von burn3r,

Vielleicht brauchst du auch für bool eine Erklärung. Bool liefert immer true oder false. D.h. bei der obigen Funktion würde die Schleife tuWas() nur dann betreten, wenn A und B entweder beide false oder true sind, andernfalls wird dieser Schritt nicht ausgeführt.

Kommentar von Kungfukuh,

Def:

Eine Formel der Aussagenlogik ist in konjunktiver Normalform, wenn sie eine Konjunktion von Disjunktionstermen ist. Disjunktionsterme sind dabei Disjunktionen von Literalen. Literale sind nichtnegierte oder negierte Variablen. Eine Formel in KNF hat also die Form... blablabla

also schlau werde daraus nicht. Ich vermute, eine KNF liegt vor, wenn die Funktion lediglich auf drei Operatoren "und", "oder" und "not" gebildet wird. Stimmt das?

Keine passende Antwort gefunden?

Fragen Sie die Community