imported>Liberatus: /* Unterscheidung nach Stelligkeit */ Was sind Funktionstypen?

2026-04-08T00:11:59Z

Unterscheidung nach Stelligkeit: Was sind Funktionstypen?

Neue Seite

{{Belege fehlen}}
Eine '''Boolesche Funktion''' (auch '''logische Funktion''') ist eine [[Mathematik|mathematische]] [[Funktion (Mathematik)|Funktion]] der Form <math>F\colon B^n \to B^1</math> (teilweise auch allgemeiner <math>F\colon B^n \to B^m</math>). <math>B</math> ist dabei eine [[Boolesche Algebra]].

Der Funktionsbezeichner, hier <math>F</math>, 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 [[Funktionstyp|Funktionstypen]] auch, unterscheidet man Boolesche Funktionen gerne nach ihrer [[Stelligkeit]]. Aufgrund der auf die Binärzahlen eingeschränkten [[Definitionsbereich|Definitions-]] und [[Bild (Mathematik)|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 (Logik)|Konjunktion]]'', ''[[Disjunktion]]'', ''[[Logische Äquivalenz|Äquivalenz]]'', ''[[Antivalenz]]'', ''[[Shefferscher Strich|NAND]]'' und ''[[Peirce-Funktion|NOR]]''. Es existieren allgemein <math>2^{2^n}</math> <math>n</math>-stellige Boolesche Funktionen. Beispielsweise existieren <math>2^{2^4} = 2^{16} = 65536</math> verschiedene vierstellige Boolesche Funktionen. Im Folgenden werden Boolesche Funktionen verschiedener Stelligkeit näher beschrieben.

=== Nullstellige Funktion ===
<math>n=0</math>
: 220 = 21 = 2

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

=== Einstellige Funktion ===
<math>n=1</math>
: 221 = 22 = 4

Die vier möglichen Booleschen Funktionen <math>y = f_0(x),\ldots,f_3(x)</math> mit einer Variablen sind:

{| border="1" cellpadding="4" style="border-collapse:collapse"
|- class="hintergrundfarbe8"
!''x''||0||1
! Funktion (''y'' =)
! Name
|- class="hintergrundfarbe5"
|f0||0||0
| 0
| [[Kontradiktion]]
|-
|f1||0||1
| ''x''
| [[Identische Abbildung|Identität]]
|-
|f2||1||0
| ¬''x'' = ''x'' = 1 − ''x''
| [[Negation]]
|- class="hintergrundfarbe5"
|f3||1||1
| 1
| [[Tautologie (Logik)|Tautologie]]
|}

=== Zweistellige Funktion ===
<math>n=2</math> 
Für zwei Variablen <math>y = f(x_1,x_2)</math> gibt es
: 222 = 24 = 16
verschiedene Boolesche Funktionen. Diese Funktionen <math>y = f_0(x_1,x_2) ,\ldots, f_{15}(x_1,x_2)</math> sind:

{| border="1" cellpadding="4" style="border-collapse:collapse"
|+ Zweistellige Boolesche Funktionen
|- class="hintergrundfarbe8"
! ''x''1, ''x''2
! 0, 0
! 0, 1
! 1, 0
! 1, 1
!colspan="3"| Funktion
! Name
|- class="hintergrundfarbe5"
|f0||0||0||0||0
| ''x''1 · ''x''1
| 0
| ''x''1 ∧ ¬''x''1
| [[Kontradiktion]], [[Nullfunktion]]
|- class="hintergrundfarbe1"
|f1||0||0||0||1
| ''x''1 · ''x''2
| ⌊''x''1, ''x''2⌋
| ''x''1 ∧ ''x''2
| [[Konjunktion (Logik)|Konjunktion]], [[Und-Gatter|AND]](''x''1, ''x''2)
|- class="hintergrundfarbe1"
|f2||0||0||1||0
| ''x''1 · ''x''2
| ''x''1 > ''x''2
| ''x''1 ↛ ''x''2
| [[Inhibition (Digitaltechnik)|Inhibition]] von ''x''1
|-
|f3||0||0||1||1
| ''x''1
| ''x''1
| ''x''1
| [[Identische Abbildung|Identität]] von ''x''1
|- class="hintergrundfarbe1"
|f4||0||1||0||0
| ''x''1 · ''x''2
| ''x''1 < ''x''2
| ''x''1 ↚ ''x''2
| [[Inhibition (Digitaltechnik)|Inhibition]] von ''x''2
|-
|f5||0||1||0||1
| ''x''2
| ''x''2
| ''x''2
| [[Identische Abbildung|Identität]] von ''x''2
|- class="hintergrundfarbe1"
|f6||0||1||1||0
| (''x''1 · ''x''2) + (''x''1 · ''x''2)
| ''x''1 ≠ ''x''2
| ''x''1 ↮ ''x''2
| [[Kontravalenz|Antivalenz]], [[Alternative]], [[XOR-Verknüpfung|XOR]](''x''1, ''x''2)
|- class="hintergrundfarbe1"
|f7||0||1||1||1
| ''x''1 + ''x''2
| ⌈''x''1, ''x''2⌉ 
| ''x''1 ∨ ''x''2
| [[Disjunktion]], OR(''x''1, ''x''2)
|- class="hintergrundfarbe1"
|f8||1||0||0||0
| ''x''1 + ''x''2 = ''x''1 · ''x''2
| 1 − ⌈''x''1, ''x''2⌉ 
| ''x''1 ↓ ''x''2
| [[Nihilition]], [[Peirce-Funktion]], [[NOR-Gatter|NOR]](''x''1, ''x''2)
|- class="hintergrundfarbe1"
|f9||1||0||0||1
| (''x''1 · ''x''2) + (''x''1 · ''x''2)
| ''x''1 = ''x''2
| ''x''1 ↔ ''x''2
| [[Bikonditional|Äquivalenz]], [[XNOR-Gatter|XNOR]] (''x''1,''x''2)
|-
|f10||1||0||1||0
| ''x''2
| 1 − ''x''2
| ¬''x''2
| [[Negation]] von ''x''2, NOT(''x''2)
|- class="hintergrundfarbe1"
|f11||1||0||1||1
| ''x''1 + ''x''2
| ''x''1 ≥ ''x''2
| ''x''1 ← ''x''2
| [[Replikation (Logik)|Replikation]]
|-
|f12||1||1||0||0
| ''x''1
| 1 − ''x''1
| ¬''x''1
| [[Negation]] von ''x''1, NOT(''x''1)
|- class="hintergrundfarbe1"
|f13||1||1||0||1
| ''x''1 + ''x''2
| ''x''1 ≤ ''x''2
| ''x''1 → ''x''2
| [[Implikation]]
|- class="hintergrundfarbe1"
|f14||1||1||1||0
| ''x''1 · ''x''2 = ''x''1 + ''x''2
| 1 − ⌊''x''1, ''x''2⌋ 
| ''x''1 ↑ ''x''2
| [[Exklusion (Begriffsklärung)|Exklusion]], [[Sheffer-Funktion]], [[NAND-Gatter|NAND]](''x''1, ''x''2)
|- class="hintergrundfarbe5"
|f15||1||1||1||1
| ''x''1 + ''x''1
| 1
| ''x''1 ∨ ¬''x''1
| [[Tautologie (Logik)|Tautologie]], [[Einsfunktion]]
|}

=== Mehr als zwei Variablen ===
Bei drei Variablen gibt es bereits 28 = 256 Boolesche Funktionen, bei vier Variablen 216 = 65.536, bei fünf Variablen 232 = 4.294.967.296, bei sechs Variablen sind es 264 = über 18 Trillionen, also zu viele, um sie hier alle darzustellen.

== Grafische Veranschaulichung ==
Die grafische Veranschaulichung Boolescher Funktionen kann zumindest für niedrigstellige Funktionen durch Auftragen von [[Punkt (Geometrie)|Punkten]] in einem [[Koordinatensystem]] erfolgen. Einstellige Funktionen lassen sich in einem [[Kartesisches Koordinatensystem|kartesischen Koordinatensystem]] als Eckpunkte eines [[Einheitsquadrat]]s auftragen. Für zweistellige Funktionen gelingt dies noch einigermaßen anschaulich mittels der Eckpunkte eines [[Würfel (Geometrie)|Einheitswürfels]] in einem dreidimensionalen Koordinatensystem. n-stellige Funktionen lassen sich allgemein in einem n+1-dimensionalen Koordinatensystem als ein n+1-dimensionaler [[Hyperwürfel|Einheitshyperwürfel]] darstellen.

== Algebraische Darstellbarkeit ==
Diese Darstellung wird jedoch spätestens ab vier Variablen zu komplex, um noch anschaulich zu sein. Daher ist für höhere Dimensionen unbedingt ein algebraischer Zugang erforderlich. Tatsächlich ist es möglich, jede beliebige (etwa mittels einer Funktionstafel willkürlich festgelegte) Boolesche Funktion rein algebraisch auszudrücken. Ein System von Booleschen Funktionen, welches dies ermöglicht, bezeichnet man auch als ''vollständiges Operatorensystem'' oder ''Verknüpfungsbasis''. Vollständige Operatorensysteme sind etwa das UND-ODER-NICHT-System, das UND-[[XOR-Verknüpfung|Antivalenz]]-System, das NAND- und das NOR-System. Man beachte, dass es sich bei diesen Funktionen ''nicht'' um die Verknüpfungen der zugrundeliegenden [[Boolesche Algebra|Booleschen Algebra]] handelt, sondern um definierte Funktionen.

Jede Boolesche Funktion kann in die [[Disjunktive Normalform]] (siehe [[Disjunktive Normalform#Beispiel für die Bildung der DNF|Beispiel für die Bildung der DNF]]) und die [[Konjunktive Normalform]] (siehe [[Konjunktive Normalform#Beispiel für die Bildung der KNF|Beispiel für die Bildung der KNF]]) umgeformt werden.

== Boolesche Grundfunktionen ==
Jede Boolesche Funktion mit zwei oder mehr Eingängen lässt sich mit den Funktionen ''UND'' (Konjunktion), ''ODER'' (Disjunktion) und ''NICHT'' (Negation) realisieren. In der Praxis wird das auch so gehandhabt. Wegen der [[De Morgansche Gesetze|De Morganschen Regel]] reichen grundsätzlich auch zwei dieser drei Grundfunktionen aus (''NICHT'' zusammen mit ''ODER'' oder ''NICHT'' zusammen mit ''UND''). Alternativ lassen sich auch alle Booleschen Funktionen mittels ''NAND'' realisieren (dasselbe gilt für ''NOR'') oder mittels (''AND'', ''XOR'' und ''T'').

=== Beispiel XOR-Funktion ===
Bei der [[XOR-Verknüpfung]] ist der Ausgangszustand 1 (wahr), wenn die beiden Eingangszustände x1 und x2 unterschiedlich sind:

{| class="wikitable"
|-
! <math>x_1</math>
! <math>x_2</math>
! <math>y</math>
|-
| 0 || 0 || 0
|-
| 0 || 1 || 1
|-
| 1 || 0 || 1
|-
| 1 || 1 || 0
|}

In der [[Disjunktive Normalform|disjunktiven Normalform]] geschrieben:
: <math>y=\overline{x_1}x_2 \vee x_1\overline{x_2}</math>

=== Beispiel Mehrheits-Funktion ===
Angenommen man hat drei Personen, die jeweils einen Schalter vor sich haben ([[Kreuzschaltung]]). Eine Lampe ''l'' soll nur aufleuchten, wenn die Mehrheit, also zwei der Personen oder alle drei, ihren Schalter betätigen:

: <math>l=\overline{s_1}s_2s_3\vee s_1\overline{s_2}s_3\vee s_1s_2\overline{s_3}\vee s_1s_2s_3</math> 
Da sich <math>\overline{s_1}s_2s_3</math> und <math>s_1s_2s_3</math> nur in einem Zustand unterscheiden, kann man den sich unterscheidenden Teil wegfallen lassen und erhält <math>s_2s_3</math>.

Das Gleiche gilt für <math>s_1\overline{s_2}s_3</math> und <math>s_1s_2s_3</math>, sowie für <math>s_1s_2\overline{s_3}</math> und <math>s_1s_2s_3</math>, so dass am Ende folgende optimierte Funktion übrig bleibt:

: <math>l=s_2s_3\vee s_1s_3\vee s_1s_2</math>

== Vollständige Logiksysteme ==
Für ein ''vollständiges System'' oder auch die ''Verknüpfungsbasis'' wird entweder die Grundverknüpfungen AND oder OR benötigt. Zusätzlich benötigt man das NOT. Für einen Schaltungsentwurf hat dieser Umstand einen Vorteil: Es werden lediglich zwei Grundschaltungen benötigt, die dieses vollständige System ((AND oder OR) und NOT) realisieren. Durch eine entsprechende Kombination der Grundoperatoren können dann alle anderen Operatoren gebildet werden.

Die [[NAND-Gatter#Realisierung|NAND]]-Verknüpfung bzw. [[NOR-Gatter#Logiksynthese|NOR]]-Verknüpfung stellt bereits jeweils ein solches vollständiges System dar.

== Normalformen ==
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)
* [[Negationsnormalform]] (NNF)

== Besondere Boolesche Funktionen ==
* Die immer ''wahr'' berechnende Funktion heißt ''[[Tautologie (Logik)|Tautologie]]''.
* Die immer ''falsch'' berechnende Funktion heißt ''[[Kontradiktion]]''.
* Einstellige Boolesche Funktionen, die immer genau den Eingangswert zurückliefern, nennt man ''[[Identität (Logik)|Identität]]''.
* Einstellige Boolesche Funktionen, die immer genau die Umkehrung des Eingangswertes zurückliefern, nennt man ''[[Negation]]''.
* Eine Boolesche Funktion heißt [[Symmetrische Funktion|symmetrisch]], wenn der Funktionswert nur von der Anzahl der Einsen im Argument, jedoch nicht von deren Position abhängt, also invariant gegenüber Permutationen der Eingabevariablen ist.

== 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.

<gallery heights="187" widths="250" class="center">
Halbaddierer Aufbau XOR.svg|Halbaddierer-Schaltung (Und- und XOR-Gatter)
Halbaddierer Aufbau.svg|Halbaddierer-Schaltung (Inverter, Und- und Oder-Gattern)
Halbaddierer Schaltsymbol.svg|Halbaddierer-Schaltsymbol
</gallery>

== Literatur ==
* Hans Liebig: ''Logischer Entwurf digitaler Systeme.'' 4., bearb. und erw. Aufl., Springer, Berlin 2006, ISBN 978-3-540-26026-4.
* Klaus Gotthard; ''Grundlagen der Informationstechnik.'' (Reihe: Einführungen. Informatik; 1) Lit-Verl., Münster 2001, ISBN 3-8258-5556-2.
* Klaus Gotthard; ''Aufgaben der Informationstechnik'', Teil 1. 2., überarb. Aufl., Logos-Verl., Berlin 2005, ISBN 3-8325-0267-X.

[[Kategorie:Mathematische Logik]]
[[Kategorie:Boolesche Algebra]]

Boolesche Funktion - Versionsgeschichte

imported>Liberatus: /* Unterscheidung nach Stelligkeit */ Was sind Funktionstypen?