Schaltfunktionen

Eine Schaltfunktion (Boolesche Funktion oder logische Funktion) ist eine Funktion der Form

F\colon B^n \to B^1

, wobei

B

eine zweielementige Boolesche Algebra ist. Typischerweise wird

B=\{0,1\}

mit den logischen Operatoren

\and

\or

und

\not

gewählt.

Aufzählung nach Stelligkeit

Die Anzahl der möglichen Schaltfunktionen der Form

F\colon B^n \to B^1

, wobei

B

ist

2^{(2^n)}

und daher stets endlich. Beispielsweise existieren

2^{2^4} = 2^{16} = 65536

verschiedene vierstellige Boolesche Funktionen. Es bietet sich eine Unterscheidung nach der Stelligkeit an.

Nullstellige Funktion

n=0

: Anzahl der Funktionen:

2^{2^0}=2^{1} = 2

Diese beiden "Funktionen" sind aber eigentlich Konstanten, da man bei Funktionen ohne Argumente nicht wirklich von Funktionen sprechen kann. Sie entsprechen genau

1\in B

und

0\in B

werden aber auch wahr und falsch, verum und falsum, true und false genannt.

Einstellige Funktion

n=1

; Anzahl der Funktionen:

2^{2^1}= 2^{2} = 4

Die vier möglichen unären Booleschen Funktionen

y

f_{0} (x)

…

f_{3} (x)

mit einer Variablen sind:

$x$	0	1	Funktion ( $y$ =)	Name
$f_{0}$	0	0	0	Kontradiktion
$f_{1}$	0	1	$x$	Identität
$f_{2}$	1	0	$\not x$ $=\ovl x$ $=1 - x$	Negation
$f_{3}$	1	1	1	Tautologie

Zweistellige Funktion

n=2

; Anzahl der Funktionen:

2^{2^2}= 2^{4} = 16

$x _{1},\, x_{2}$	0, 0	0, 1	1, 0	1, 1	Funktion			Name
$f_{0}$	0	0	0	0	$0=x _{1}+{x _{1}}$	0	$x _{1}\cdot \not x _{1}$	Kontradiktion, Nullfunktion
$f_{1}$	0	0	0	1	$x _{1}$ · $x _{2}$	$\min( x _{1},\, x_{2})$	$x _{1}\and x _{2}$	Konjunktion, AND $(x _{1},\, x_{2})$
$f_{2}$	0	0	1	0	$x _{1}+ {x_1 x _{2}}$	$x _{1}$ > $x _{2}$	$\not(x _{1}\ra x _{2})$	Inhibition von $x _{1}$
$f_{3}$	0	0	1	1	$x _{1}$	$x _{1}$	$x _{1}$	Identität von $x _{1}$
$f_{4}$	0	1	0	0	$x _{2}+ {x_1 x _{2}}$	$x _{1}$ < $x _{2}$	$\not(x _{1}\leftarrow x _{2})$	Inhibition von $x _{2}$
$f_{5}$	0	1	0	1	$x _{2}$	$x _{2}$	$x _{2}$	Identität von $x _{2}$
$f_{6}$	0	1	1	0	$x _{1} + x _{2}$	$x _{1} \neq x_{2}$	$x _{1}$ ↮ $x _{2}$	Antivalenz, Alternative, XOR $(x _{1},\, x_{2})$
$f_{7}$	0	1	1	1	$x_1+x_2+x_1 \cdot x_2$	$\max(x _{1},\, x_{2})$	$x _{1}$ ∨ $x _{2}$	Disjunktion, OR $(x _{1},\, x_{2})$
$f_{8}$	1	0	0	0	$1+x_1+x_2+x_1 \cdot x_2$	$1-\max(x _{1},\, x_{2})$	$x _{1}$ ↓ $x _{2}$	Nihilition, Peirce-Funktion, NOR $(x _{1},\, x_{2})$
$f_{9}$	1	0	0	1	$1+x_1+x_2$	$x _{1}$ = $x _{2}$	$x _{1}$ ↔ $x _{2}$	Äquivalenz
$f_{10}$	1	0	1	0	$1+{x _{2}}$	1 - $x _{2}$	¬ $x _{2}$	Negation von $x _{2}$ , NOT $(x _{2})$
$f_{11}$	1	0	1	1	$1+ x _{2}+ {x_1 x _{2}}$	$x _{1} \geq x_{2}$	$x _{1}$ ← $x _{2}$	Replikation
$f_{12}$	1	1	0	0	$1+x_1$	1 - $x _{1}$	¬ $x _{1}$	Negation von $x _{1}$ , NOT $(x _{1})$
$f_{13}$	1	1	0	1	$1+ x _{1}+ {x_1 x _{2}}$	$x _{1} \leq x_{2}$	$x _{1} \to x_{2}$	Implikation
$f_{14}$	1	1	1	0	$1+x_1\cdot x_2$	$1-\min( x _{1},\, x_{2})$	$x _{1}$ ↑ $x _{2}$	Exklusion, Sheffer-Funktion, NAND $(x _{1},\, x_{2})$
$f_{15}$	1	1	1	1	1	1	$x _{1}$ ∨ ¬ $x _{1}$	Tautologie, Einsfunktion

Mehr als zwei Variablen

n>2

Bei drei Variablen gibt es bereits

2^{8}

= 256 Boolesche Funktionen, bei vier Variablen

2^{16}

= 65.536, bei fünf Variablen

2^{32}

= 4.294.966.416, bei sechs Variablen sind es

2^{64}

= über 18 Trillionen.

Normalformen (DNF, KNF, RSNF)

Jede Boolesche Funktion lässt sich in einer Normalform darstellen. Eine Überführung von einer Normalform in eine andere ist möglich. Normalformen sind nützlich für bestimmte Algorithmen, Schaltungen oder Beweise. Beispiele von Normalformen sind:

Disjunktive Normalform (DNF)
Konjunktive Normalform (KNF)
Ringsummennormalform (RSNF)

Jede Wissenschaft bedarf der Mathematik, die Mathematik bedarf keiner.

Jakob I. Bernoulli

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Boolesche Funktion aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!

Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld • Dοrfplatz 25 • 17237 Blankеnsее • Tel.: 01734332309 (Vodafone/D2) • Email: cο@maτhepedιa.dе

Datenschutzerklärung

Informatik

Theoretische Informatik
- Schaltfunktionen
  - Disjunktive Normalform
  - Konjunktive Normalform
- Formale Sprachen
Algorithmen