Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Boolesche Funktion aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Boolesche Funktion

Eine Boolesche Funktion (man spricht auch von logischen Funktionen) ist eine mathematische Funktion der Form F: Bⁿ -> B¹ (teilweise auch allgemeiner F: Bⁿ -> B^m). B ist dabei eine Boolesche Algebra. Der Funktionsbezeichner, hier F, wird für Boolesche Funktionen im Allgemeinen groß gewählt, da in einer Booleschen Algebra die verwendeten Größen bevorzugt mit Großbuchstaben bezeichnet werden. Boolesche Funktionen sind dann in Ausdrücke der Booleschen Algebra einsetzbar und können wie Variablen behandelt werden. Die Verknüpfungen einer Booleschen Algebra wie ?, ? oder ¬ sehen aus wie spezielle ein- und zweistellige Boolesche Funktionen, sie sind jedoch nicht mit den entsprechenden Booleschen Funktionen zu verwechseln. Es handelt sich lediglich um Verknüpfungen auf einer Menge, über die noch nichts weiter bekannt ist, während für die Definitions- und Wertebereiche einer Booleschen Funktion bereits alle Axiome einer Booleschen Algebra als gegeben vorausgesetzt werden können.

Unterscheidung nach Stelligkeit

Wie bei der Untersuchung anderer Funktionstypen auch unterscheidet man Boolesche Funktionen gerne nach ihrer Stelligkeit. Aufgrund der auf die Binärzahlen eingeschränkten Definitions- und Wertebereiche sind niederstellige Boolesche Funktionen verhältnismäßig einfach zu handhaben. So gibt es überhaupt nur 4 verschiedene einstellige Boolesche Funktionen, die man als Identität, Negation, konstante 1 und konstante 0 bezeichnen kann. Für die Boolesche Algebra ist hier insbesondere die Negation von Bedeutung. Die Anzahl der zweistelligen Booleschen Funktionen beträgt bereits 16. Zu den wichtigsten zählen dabei _Konjunktion, Disjunktion, Äquivalenz, Antivalenz, NAND und NOR. Es existieren allgemein $2^\{2^n\}$ n-stellige Boolesche Funktionen. Beispielsweise existieren $2^\{2^4\}\; =\; 2^\{16\}\; =\; 65536$ verschiedene vierstellige Boolesche Funktionen. Im folgenden werden Boolesche Funktionen verschiedener Stelligkeit etwas näher beschrieben.

n=0

$2^\{2^0\}=2^1=2$

Das sind die zwei Konstanten 1 und 0, auch wahr und falsch, verum und falsum, true und false genannt.

n=1

$2^\{2^1\}=2^2=4.$

Die vier möglichen Booleschen Funktionen y=f₀(x) ... f₃(x) mit einer Variablen sind:

n=2

Für zwei Variable y=f(x₁,x₂) gibt es

$2^\{2^2\}=2^4=16$

verschiedene Boolesche Funktionen. Diese Funktionen y=f₀(x₁,x₂) ... f₁₅(x₁,x₂) sind:
In der disjunktiven_Normalform geschrieben:
: $y=\backslash bar\{x\_1\}x\_2\; \backslash vee\; x\_1\backslash bar\{x\_2\}$

Beispiel: Die Mehrheits-Funktion

Angenommen man hat drei Personen, die jeweils einen Schalter vor sich haben. Eine Lampe l soll nur aufleuchten, wenn die Mehrheit, also zwei der Personen oder alle drei, ihren Schalter betätigen:

: $l=\backslash bar\{s\_1\}s\_2s\_3\backslash vee\; s\_1\backslash bar\{s\_2\}s\_3\backslash vee\; s\_1s\_2\backslash bar\{s\_3\}\backslash vee\; s\_1s\_2s\_3$

Da sich $\backslash bar\{s\_1\}s\_2s\_3$ und $s\_1s\_2s\_3$ nur in einem Zustand unterscheiden, kann man den sich unterscheidenden Teil wegfallen lassen: $s\_2s\_3$. Das gleiche gilt für $s\_1\backslash bar\{s\_2\}s\_3$ und $s\_1s\_2s\_3$, sowie für $s\_1s\_2\backslash bar\{s\_3\}$ und $s\_1s\_2s\_3$, so das am Ende folgende optimierte Funktion übrig bleibt:
: $l=s\_2s\_3\backslash vee\; s\_1s\_3\backslash vee\; s\_1s\_2$


----

Vollständige Logiksysteme

Mit den Grundverknüpfungen AND, OR und NOT können alle anderen Verknüpfungen dargestellt werden. Man bezeichnet daher diese Verknüpfungen als vollständiges System oder auch Verknüpfungsbasis.

Für einen Schaltungsentwurf hat dieser Umstand einen Vorteil: Es werden lediglich drei Grundschaltungen benötigt die dieses vollständige System (AND, OR, NOT) realisieren. Durch eine entsprechende Kombination der Grundoperatoren können dann alle anderen Operatoren gebildet werden.

Die NAND-Verknüpfung stellt bereits ein solches vollständiges System dar. Beweisen kann man diesen Sachverhalt sehr einfach indem man mit einem NAND die Grundverknüpfungen AND, OR und NOT nachbildet.
Das gleiche gilt auch für die NOR-Verknüpfung.

Disjunktive Normalform (DNF) und konjunktive Normalform (KNF)

Jede Boolesche Funktion lässt sich in der disjunktiven_Normalform und in der konjunktiven_Normalform darstellen. Ebenso kann man eine Funktion von der disjunktiven Normalform in die konjunktive Normalform überführen und umgekehrt.

Besondere Boolesche Funktionen

*Die immer wahr berechnende Funktion heißt Tautologie.
*Die immer falsch berechnende Funktion heißt Kontradiktion.
*Einstellige Boolesche Funktionen, die immer genau den Eingangswert zurückliefern, nennt man Identität.
*Einstellige Boolesche Funktionen, die immer genau die Umkehrung des Eingangswertes zurückliefern, nennt man Negation.
*Symmetrische Boolesche Funktionen, die invariant gegenüber Permutationen der Eingabevariablen sind, d.h. der Funktionswert ist nur von der Anzahl der Einsen im Argument, nicht aber von deren Position abhängig.

Boolesche Funktionen in Kombination

Man kann komplexere Strukturen erhalten, wenn man mehrere Boolesche Funktionen zusammenfasst. So erhält man beispielsweise einen Halbaddierer, wenn man die gleichen Eingänge x und y für die UND- und die XOR-Funktion verwendet, um am Ausgang der UND-Funktion den Carry-Zustand c, und am Ausgang der XOR-Funktion den Summen-Zustand s zu bekommen.

       VIDEO-NEWS UND ANGEBOTE