Funktionale Vollständigkeit

In der Logik ist eine Menge logischer Verknüpfungen oder Boolescher Operatoren funktional vollständig , wenn sie alle möglichen Wahrheitstabellen durch Kombination ihrer Elemente zu einem Booleschen Ausdruck darstellen kann . ^{[ 1 ] [ 2 ]} Eine bekannte vollständige Menge von Verknüpfungen ist { AND , NOT } . Die einelementigen Mengen { NAND } und { NOR } sind jeweils funktional vollständig. Die Menge { AND , OR } ist jedoch unvollständig, da sie den Operator NOT nicht ausdrücken kann.

Ein funktional vollständiges Gatter (oder eine Menge von Gattern) kann auch als universelles Gatter (oder universelle Menge von Gattern) bezeichnet werden.

Im Kontext der Aussagenlogik werden funktional vollständige Mengen von Konnektiven auch ( expressiv ) adäquat genannt . ^{[ 3 ]}

Aus Sicht der digitalen Elektronik bedeutet funktionale Vollständigkeit, dass jedes mögliche Logikgatter als Netzwerk von Gattern der durch die Menge vorgegebenen Typen realisiert werden kann. Insbesondere lassen sich alle Logikgatter entweder ausschließlich aus binären NAND-Gattern oder ausschließlich aus binären NOR-Gattern zusammensetzen .

Moderne Logiklehrbücher betrachten typischerweise eine Teilmenge der Konnektive als Grundformen: Konjunktion ( ); Disjunktion ( ); Negation ( ); materiale Konditionalausdrücke ( ); und gegebenenfalls den Bikonditional ( ). Weitere Konnektive lassen sich, falls gewünscht, durch Definition mithilfe dieser Grundformen definieren. Beispielsweise kann NOR (die Negation der Disjunktion, manchmal mit ) als Konjunktion zweier Negationen ausgedrückt werden: ${\displaystyle \land }$${\displaystyle \lor }$${\displaystyle \neg }$${\displaystyle \to }$${\displaystyle \leftrightarrow }$${\displaystyle \downarrow }$

${\displaystyle A\downarrow B:=\neg A\land \neg B}$

Analog dazu lässt sich die Negation der Konjunktion, NAND (manchmal auch als ) bezeichnet, mithilfe von Disjunktion und Negation definieren. Jede binäre Verknüpfung kann mithilfe von definiert werden , was bedeutet, dass die Menge funktional vollständig ist. Sie enthält jedoch Redundanz: Diese Menge ist keine minimale funktional vollständige Menge, da die Konditionalaussage und die Bikonditionalaussage mithilfe der anderen Verknüpfungen definiert werden können. ${\displaystyle \uparrow }$${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

${\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}$

Daraus folgt, dass auch die kleinere Menge funktional vollständig ist. (Ihre funktionale Vollständigkeit wird auch durch den Satz über disjunktive Normalformen bewiesen .) ^{[ 4 ]} Sie ist jedoch noch nicht minimal, da sie definiert werden kann als ${\displaystyle \{\neg ,\land ,\lor \}}$${\displaystyle \lor }$

${\displaystyle A\lor B:=\neg (\neg A\land \neg B).}$

Alternativ kann es auch in ähnlicher Weise definiert werden , oder es kann in Bezug auf Folgendes definiert werden : ${\displaystyle \land }$${\displaystyle \lor }$${\displaystyle \lor }$${\displaystyle \rightarrow }$

${\displaystyle \ A\vee B:=\neg A\rightarrow B.}$

Weitere Vereinfachungen sind nicht möglich. Daher ist jede zweielementige Menge von Konnektiven, die und eines von enthält , eine minimale funktional vollständige Teilmenge von . ${\displaystyle \neg }$${\displaystyle \{\land ,\lor ,\rightarrow \}}$${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

Gegeben sei der Boolesche Definitionsbereich B = {0, 1} . Eine Menge F von Booleschen Funktionen f i   : B n  → B ist funktional vollständig , wenn der von den Basisfunktionen f  i  erzeugte Klon auf B alle Funktionen f  : B n  → B für alle positiven ganzen Zahlen n ≥ 1 enthält . Anders ausgedrückt: Die Menge ist funktional vollständig, wenn sich jede Boolesche Funktion mit mindestens einer Variablen durch die Funktionen f i ausdrücken lässt . Da sich jede Boolesche Funktion mit mindestens einer Variablen durch binäre Boolesche Funktionen ausdrücken lässt, ist F genau dann funktional vollständig, wenn sich jede binäre Boolesche Funktion durch die Funktionen in F ausdrücken lässt .

Eine natürlichere Bedingung wäre, dass der von F erzeugte Klon aus allen Funktionen f  : B ^ⁿ → B für alle ganzen Zahlen n ≥ 0 besteht . Die oben genannten Beispiele sind jedoch in diesem strengeren Sinne nicht funktional vollständig, da es nicht möglich ist, eine Nullfunktion, d. h. einen konstanten Ausdruck, durch F auszudrücken , wenn F selbst keine Nullfunktion enthält. Nach dieser strengeren Definition hätten die kleinsten funktional vollständigen Mengen 2ⁿ Elemente.

Eine weitere natürliche Bedingung wäre, dass der von F erzeugte Klon zusammen mit den beiden Nullkonstanten funktional vollständig ist oder, äquivalent dazu, im starken Sinne des vorherigen Absatzes funktional vollständig ist. Das Beispiel der Booleschen Funktion S ( x , y , z ) = z falls x = y und S ( x , y , z ) = x sonst zeigt, dass diese Bedingung deutlich schwächer ist als die funktionale Vollständigkeit. ^{[ 5 ] [ 6 ] [ 7 ]}

Emil Post bewies, dass eine Menge logischer Verknüpfungen genau dann funktional vollständig ist, wenn sie keine Teilmenge einer der folgenden Mengen von Verknüpfungen ist:

• Die monotonen Konnektive; wenn man den Wahrheitswert einer beliebigen verbundenen Variable von F auf T ändert , ohne eine beliebige Variable von T auf F zu ändern , ändert sich der Rückgabewert dieser Konnektive niemals von T auf F , z. B.${\displaystyle \vee ,\wedge ,\top ,\bot }$
• Die affinen Konnektive, so dass jede verbundene Variable entweder immer oder nie den Wahrheitswert beeinflusst, den diese Konnektive zurückgeben, z.B.${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$
• Die selbstdualen Konnektive, die gleich ihrem eigenen de Morgan Dual sind ; wenn die Wahrheitswerte aller Variablen umgekehrt werden, so wird auch der Wahrheitswert dieser Konnektive umgekehrt, z. B. maj ( p , q , r ) .${\displaystyle \neg }$
• Die wahrheitserhaltenden Konnektive; sie liefern den Wahrheitswert T unter jeder Interpretation, die allen Variablen den Wert T zuweist, z . B.${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }$
• Die falschheitserhaltenden Konnektive; sie liefern den Wahrheitswert F unter jeder Interpretation, die allen Variablen den Wert F zuweist, z . B.${\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }$

Post lieferte eine vollständige Beschreibung des Verbandes aller Klone (Mengen von Operationen, die unter Komposition abgeschlossen sind und alle Projektionen enthalten) auf der zweielementigen Menge { T , F } , der heute als Post-Verband bezeichnet wird und aus dem das obige Ergebnis als einfache Folgerung folgt: Die fünf erwähnten Mengen von Konnektiven sind genau die maximalen nichttrivialen Klone. ^{[ 8 ]}

Wenn ein einzelner logischer Verknüpfungsoperator oder Boolescher Operator für sich allein funktional vollständig ist, wird er als Sheffer-Funktion ^{[ 9 ]} oder auch als einziger ausreichender Operator bezeichnet . Es gibt keine unären Operatoren mit dieser Eigenschaft. NAND und NOR , die zueinander dual sind , sind die einzigen beiden binären Sheffer-Funktionen. Sie wurden um 1880 von Charles Sanders Peirce entdeckt, aber nicht veröffentlicht, und 1913 unabhängig davon von Henry M. Sheffer wiederentdeckt und publiziert. ^{[ 10 ]} In der Terminologie der digitalen Elektronik sind das binäre NAND-Gatter (↑) und das binäre NOR-Gatter (↓) die einzigen binären universellen Logikgatter .

Nachfolgend sind die minimalen funktional vollständigen Mengen logischer Konnektive mit Stelligkeit ≤ 2 aufgeführt: ^{[ 11 ]}

Ein Element

{↑}, {↓}.

Zwei Elemente

${\displaystyle \{\vee ,\neg \}}$, , , , , , , , , , , , , , , , ,${\displaystyle \{\wedge ,\neg \}}$${\displaystyle \{\to ,\neg \}}$${\displaystyle \{\gets ,\neg \}}$${\displaystyle \{\to ,\bot \}}$${\displaystyle \{\gets ,\bot \}}$${\displaystyle \{\to ,\nleftrightarrow \}}$${\displaystyle \{\gets ,\nleftrightarrow \}}$${\displaystyle \{\to ,\nrightarrow \}}$${\displaystyle \{\to ,\nleftarrow \}}$${\displaystyle \{\gets ,\nrightarrow \}}$${\displaystyle \{\gets ,\nleftarrow \}}$${\displaystyle \{\nrightarrow ,\neg \}}$${\displaystyle \{\nleftarrow ,\neg \}}$${\displaystyle \{\nrightarrow ,\top \}}$${\displaystyle \{\nleftarrow ,\top \}}$${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$${\displaystyle \{\nleftarrow ,\leftrightarrow \}.}$

Drei Elemente

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$, , , , ,${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$${\displaystyle \{\land ,\nleftrightarrow ,\top \}.}$

Es gibt keine minimalen funktional vollständigen Mengen von höchstens drei binären logischen Verknüpfungen. ^{[ 11 ]} Um die obigen Listen übersichtlich zu halten, wurden Operatoren, die einen oder mehrere Eingaben ignorieren, weggelassen. Beispielsweise kann ein Operator, der die erste Eingabe ignoriert und die Negation der zweiten ausgibt, durch eine unäre Negation ersetzt werden.

Alfred Tarskis Arbeit „On the Primitive Term of Logistic“ bewies, dass sie funktional vollständig ist, ^{[ 12 ]} aber das funktioniert nur, wenn die Quantifizierung über Aussagen (ein Mittel aus der Prädikatenlogik zweiter Stufe ) verwendet wird, weshalb sie für die obige Liste nicht zählt. ${\displaystyle \{\leftrightarrow \}}$

• Beispiele für die Anwendung der NAND(↑)-Vollständigkeit. Wie in ^{[ 13 ] veranschaulicht wird.}
  • ¬ A ≡ A ↑ A
  • A ∧ B ≡ ¬( A ↑ B ) ≡ ( A ↑ B ) ↑ ( A ↑ B )
  • A ∨ B ≡ (¬ A ) ↑ (¬ B ) ≡ ( A ↑ A ) ↑ ( B ↑ B )
• Beispiele für die Anwendung der NOR(↓)-Vollständigkeit. Wie in ^{[ 14 ] veranschaulicht wird.}
  • ¬ A ≡ A ↓ A
  • A ∨ B ≡ ¬( A ↓ B ) ≡ ( A ↓ B ) ↓ ( A ↓ B )
  • A ∧ B ≡ (¬ A ) ↓ (¬ B ) ≡ ( A ↓ A ) ↓ ( B ↓ B )

Beachten Sie, dass eine elektronische Schaltung oder eine Softwarefunktion durch Wiederverwendung optimiert werden kann, um die Anzahl der Gatter zu reduzieren. Beispielsweise wird die Operation " A ∧ B ", wenn sie durch ↑-Gatter ausgedrückt wird, durch die Wiederverwendung von " A ↑ B " implementiert .

X ≡ ( A ↑ B ); A ∧ B ≡ X ↑ X

Abgesehen von logischen Verknüpfungen (Booleschen Operatoren) lässt sich funktionale Vollständigkeit auch in anderen Bereichen einführen. Beispielsweise heißt eine Menge reversibler Gatter funktional vollständig, wenn sie jeden reversiblen Operator ausdrücken kann.

Das Fredkin-Gatter mit drei Eingängen ist ein funktional vollständiges, reversibles Gatter – ein einziger ausreichender Operator. Es gibt viele weitere universelle Logikgatter mit drei Eingängen, wie beispielsweise das Toffoli-Gatter .

Im Quantencomputing sind das Hadamard-Gatter , das CNOT-Gatter und das T-Gatter universell, wenn auch mit einer etwas restriktiveren Definition als der der funktionalen Vollständigkeit.

Zwischen der Mengenalgebra und der Booleschen Algebra besteht ein Isomorphismus ; sie besitzen also dieselbe Struktur . Bildet man Boolesche Operatoren auf Mengenoperatoren ab, so gilt der obige Text auch für Mengen: Es gibt viele „minimale vollständige Mengen von Mengenoperatoren“, die beliebige Mengenrelationen erzeugen können. Die bekanntesten „minimalen vollständigen Operatormengen“ sind {¬, ∩} und {¬, ∪} . Ist die Universalmenge verboten , so sind Mengenoperatoren auf die Erhaltung der Falschheit (Ø) beschränkt und können nicht äquivalent zu einer funktional vollständigen Booleschen Algebra sein.

• Mengenalgebra  – Identitäten und Beziehungen von Mengen
• Boolesche Algebra  – Algebraische Manipulation von „wahr“ und „falsch“
• Vollständigkeit (Logik)  – Charakteristisch für einige logische Systeme
• Dualität von Konjunktion und Disjunktion  – Eigenschaften, die logische Konjunktion und Disjunktion verbinden
• Liste der Themen der Booleschen Algebra
• NAND-Logik  – Logik, die ausschließlich aus NAND-Gattern besteht
• NOR-Logik  – Andere Gatter nur mit NOR-Gattern erstellen
• Ein-Befehlssatz-Computer  – Abstrakte Maschine, die nur einen Befehl verwendet