Funktionale Vollständigkeit - Functional completeness

In der Logik ist ein funktionell vollständiger Satz logischer Verknüpfungen oder boolescher Operatoren einer, der verwendet werden kann, um alle möglichen Wahrheitstabellen auszudrücken, indem Elemente der Menge zu einem booleschen Ausdruck kombiniert werden . Ein bekannter vollständiger Satz von Konnektoren ist { AND, NOT }, bestehend aus binärer Konjunktion und Negation . Jede der Singleton- Mengen {  NAND  } und {  NOR  } ist funktionell vollständig.

Ein funktionell abgeschlossenes Tor oder Torsatz kann auch als Universaltor / Tore bezeichnet werden.

Ein funktionell vollständiger Satz von Gattern kann als Teil seiner Berechnung "Müllbits" verwenden oder erzeugen, die entweder nicht Teil der Eingabe oder nicht Teil der Ausgabe an das System sind.

Im Kontext der Aussagenlogik werden funktional vollständige Konnektivmengen auch ( ausdrücklich ) adäquat genannt .

Aus Sicht der Digitalelektronik bedeutet funktionale Vollständigkeit, dass jedes mögliche Logikgatter als Netzwerk von Gattern der von der Menge vorgeschriebenen Typen realisiert werden kann. Insbesondere können alle Logikgatter entweder nur aus binären NAND-Gattern oder nur aus binären NOR-Gattern aufgebaut werden .

Einführung

Moderne Texte zur Logik nehmen typischerweise eine Teilmenge der Konnektoren als primitiv: Konjunktion ( ); Disjunktion ( ); Verneinung ( ); materiell bedingt ( ); und möglicherweise die bikonditionale ( ). Falls gewünscht, können weitere Konnektoren definiert werden, indem sie in Bezug auf diese Primitive definiert werden. Zum Beispiel kann NOR (manchmal auch als Negation der Disjunktion bezeichnet) 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}$

In ähnlicher Weise kann die Negation der Konjunktion, NAND (manchmal als bezeichnet ), als Disjunktion und Negation definiert werden. Es stellt sich heraus, dass jedes binäre Konnektor in Bezug auf definiert werden kann , also ist dieser Satz funktional vollständig. ${\displaystyle\uparrow}$${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

Es enthält jedoch immer noch eine gewisse Redundanz: Diese Menge ist keine minimale funktional vollständige Menge, da das Bedingte und das B-Bedingte in Bezug auf die anderen Konnektive definiert werden können als

${\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 der kleinere Satz funktionell vollständig ist. Aber das ist immer noch nicht minimal, wie definiert werden kann als ${\displaystyle \{\neg,\land,\lor\}}$${\displaystyle \lor}$

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

Alternativ kann in ähnlicher Weise oder wie folgt 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 Konnektoren, die und eine von enthält, eine minimale funktional vollständige Teilmenge von . ${\displaystyle \neg}$${\displaystyle \{\land,\lor,\rightarrow\}}$${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$

Formale Definition

In Anbetracht der Booleschen Domäne B  = {0,1}, ein Satz F von Booleschen Funktionen ƒ _i :  B ^{n _i}  →  B ist funktional vollständig , wenn der Klon auf B durch die Basisfunktionen erzeugt ƒ _i enthält alle Funktionen ƒ :  B ⁿ  →  B , für alle streng positiven ganzen Zahlen n ≥ 1 . Mit anderen Worten, die Menge ist funktional vollständig, wenn jede boolesche Funktion, die mindestens eine Variable benötigt, durch die Funktionen ƒ _i ausgedrückt werden kann . Da jede boolesche Funktion mindestens einer Variablen durch binäre boolesche Funktionen ausgedrückt werden kann, ist F genau dann funktional vollständig, wenn jede binäre boolesche Funktion durch die Funktionen in F ausgedrückt werden kann .

Eine natürlichere Bedingung wäre, dass der von F erzeugte Klon aus allen Funktionen ƒ :  B ⁿ  →  B für alle ganzen Zahlen n ≥ 0 besteht . Die obigen Beispiele sind jedoch in diesem stärkeren Sinne nicht funktional vollständig, da es nicht möglich ist, eine Nullfunktion , dh einen konstanten Ausdruck, in Bezug auf F zu schreiben , wenn F selbst nicht mindestens eine Nullfunktion enthält. Mit dieser stärkeren Definition hätten die kleinsten funktionell vollständigen Sätze 2 Elemente.

Eine andere natürliche Bedingung wäre, dass der von F erzeugte Klon zusammen mit den beiden nullären konstanten Funktionen funktionell vollständig oder äquivalent funktionell vollständig im Sinne des vorherigen Absatzes ist. Das Beispiel der booleschen Funktion, gegeben durch S ( x ,  y ,  z ) =  z falls x  =  y und S ( x ,  y ,  z ) =  x ansonsten zeigt, dass diese Bedingung streng genommen schwächer ist als die funktionale Vollständigkeit.

Charakterisierung der funktionalen Vollständigkeit

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

• Die monotonen Verbindungen; Das Ändern des Wahrheitswerts einer zusammenhängenden Variablen von F nach T, ohne irgendeine von T nach F zu ändern, führt dazu, dass diese Verknüpfungen niemals ihren Rückgabewert von T nach F ändern , zB .${\displaystyle \vee,\wedge,\top,\bot}$
• Die affinen Konnektoren, so dass jede verbundene Variable entweder immer oder nie den Wahrheitswert beeinflusst, den diese Konnektoren zurückgeben, zB .${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$
• Die selbst-dualen Konnektive, die ihrem eigenen de-Morgan-Dual gleich sind ; wenn die Wahrheitswerte aller Variablen umgekehrt werden, so ist der Wahrheitswert dieser Konnektive zurückkehrt, zum Beispiel , MAJ ( p , q , r ).${\displaystyle \neg}$
• Die wahrheitserhaltenden Verbindungen; sie geben den Wahrheitswert T unter jeder Interpretation zurück, die T allen Variablen zuweist , zB .${\displaystyle \vee,\wedge,\top,\rightarrow,\leftrightarrow}$
• Die fälschungserhaltenden Konnektoren; sie geben den Wahrheitswert F unter jeder Interpretation zurück, die F allen Variablen zuweist , zB .${\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }$

Tatsächlich gab Post eine vollständige Beschreibung des Gitters aller Klone (Gruppen von Operationen, die unter Komposition geschlossen sind und alle Projektionen enthalten) auf der zweielementigen Menge { T , F }, die heute Posts Gitter genannt wird , was das obige Ergebnis als a . impliziert einfache Folgerung: Die fünf erwähnten Konnektivsätze sind genau die maximalen Klone.

Minimale funktional vollständige Operatorsätze

Wenn ein einzelner logischer Verknüpfungs- oder Boolescher Operator für sich allein funktionell vollständig ist, wird er als Sheffer-Funktion oder manchmal als alleiniger hinreichender Operator bezeichnet . Für diese Eigenschaft gibt es keine unären Operatoren. NAND und NOR , die zueinander dual sind , sind die einzigen zwei binären Sheffer-Funktionen. Diese wurden von Charles Sanders Peirce um 1880 entdeckt, aber nicht veröffentlicht, und unabhängig wiederentdeckt und 1913 von Henry M. Sheffer veröffentlicht. In der Terminologie der digitalen Elektronik sind das binäre NAND-Gatter und das binäre NOR-Gatter die einzigen binären universellen Logikgatter .

Im Folgenden sind die minimalen funktional vollständigen Sätze logischer Konnektoren mit einer Stelligkeit 2 aufgeführt:

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 funktionell vollständigen Sätze von mehr als drei höchstens binären logischen Verknüpfungen. Um die obigen Listen lesbar zu halten, wurden Operatoren weggelassen, die eine oder mehrere Eingaben ignorieren. Beispielsweise könnte ein Operator, der die erste Eingabe ignoriert und die Negation der zweiten ausgibt, durch eine unäre Negation ersetzt werden.

Beispiele

• Beispiele für die Verwendung der NAND(↑) Vollständigkeit. Wie veranschaulicht durch
  • ¬A ≡ A ↑ A
  • A ∧ B ≡ ¬(A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
  • A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
• Beispiele für die Verwendung der NOR(↓) Vollständigkeit. Wie veranschaulicht durch
  • ¬A ≡ A ↓ A
  • 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 Gates zu reduzieren. Zum Beispiel wird die Operation "A B", wenn sie durch ↑ Gatter ausgedrückt wird, mit der Wiederverwendung von "A ↑ B" implementiert.

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

In anderen Domänen

Abgesehen von logischen Verknüpfungen (Booleschen Operatoren) kann funktionale Vollständigkeit in anderen Domänen eingeführt werden. Beispielsweise heißt eine Menge reversibler Gatter funktional vollständig, wenn sie jeden reversiblen Operator ausdrücken kann.

Das Fredkin-Tor mit 3 Eingängen ist ein funktionell vollständiges umkehrbares Tor – ein einziger ausreichender Antrieb. Es gibt viele andere universelle Logikgatter mit drei Eingängen, wie zum Beispiel das Toffoli-Gatter .

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

Mengenlehre

Zwischen der Algebra der Mengen und der Booleschen Algebra besteht ein Isomorphismus, dh sie haben die gleiche Struktur . Wenn wir dann boolesche Operatoren in Mengenoperatoren abbilden, gilt der obige "übersetzte" Text auch für Mengen: Es gibt viele "minimale vollständige Menge mengentheoretischer Operatoren", die beliebige andere Mengenbeziehungen erzeugen können. Die populäreren "Minimalen vollständigen Operatorsätze" sind {¬, ∩} und {¬, ∪}. Wenn die universelle Menge verboten ist , sind Mengenoperatoren darauf beschränkt, die Falschheit (Ø) zu erhalten und können nicht mit funktional vollständiger Boolescher Algebra äquivalent sein.

Siehe auch

• Vollständigkeit (Logik)
• Algebra der Mengen
• boolsche Algebra
• NAND-Logik
• NOR-Logik
• Computer mit einem Befehlssatz

Verweise