Boolesche Funktion

Im Mathematik, a Boolesche Funktion ist ein Funktion Deren Argumente und resultieren Werte aus einem Zwei-Element-Satz (normalerweise {true, false}, {0,1} oder {-1,1}).^[1][2] Alternative Namen sind Schaltfunktion, besonders bei älteren Informatik Literatur,^[3][4] und Wahrheitsfunktion (oder logische Funktion), benutzt in Logik. Boolesche Funktionen sind Gegenstand von boolsche Algebra und Schalttheorie.^[5]

Eine boolesche Funktion nimmt die Form an ${\ displaystyle f: \ {0,1 \}^{k} \ to \ {0,1 \}}$, wo ${\ displayStyle \ {0,1 \}}$ ist als die bekannt Boolesche Domain und ${\ displayStyle K}$ ist eine nicht negative Ganzzahl genannt Arity der Funktion. Für den Fall wo ${\ displayStyle k = 0}$, Die Funktion ist ein konstantes Element von ${\ displayStyle \ {0,1 \}}$. Eine boolesche Funktion mit mehreren Ausgängen, ${\ displayStyle f: \ {0,1 \}^{k} \ to \ {0,1 \}^{m}}$ mit ${\ displayStyle m> 1}$ ist ein vektorial oder vektorbewertet Boolesche Funktion (eine S-Box in Kryptographie).^[6]

Es gibt ${\ displayStyle 2^{2^{k}}}$ verschiedene boolesche Funktionen mit ${\ displayStyle K}$ Argumente; gleich der Anzahl der verschiedenen Wahrheitstabellen mit ${\ displayStyle 2^{k}}$ Einträge.

Jeder ${\ displayStyle K}$-ary boolesche Funktion kann als ausgedrückt werden Aussageformel in ${\ displayStyle K}$ Variablen ${\ displayStyle x_ {1}, ..., x_ {k}}$und zwei sätzeale Formeln sind logisch äquivalent Wenn und nur wenn sie die gleiche boolesche Funktion ausdrücken.

Beispiele

Die rudimentären symmetrischen booleschen Funktionen (Logische Verbindungen oder Logik -Tore) sind:

• NICHT, Negation oder ergänzen - was eine Eingabe empfängt und true zurückgibt, wenn diese Eingabe falsch ist ("nicht")

• UND oder Verbindung - wahr, wenn alle Eingaben wahr sind ("beide")

• ODER oder disjunktion - wahr, wenn eine Eingabe wahr ist ("entweder")

• Xor oder Exklusive Disjunktion - wahr, wenn einer seiner Eingaben wahr ist und der andere falsch ("nicht gleich")

• NAND oder Sheffer Schlaganfall - wahr, wenn nicht der Fall ist, dass alle Eingaben wahr sind ("nicht beide")
• NOCH oder logisch nor - wahr, wenn keiner der Eingaben wahr ist ("weder")
• Xnor oder logische Gleichheit - wahr, wenn beide Eingänge gleich sind ("gleich")

Ein Beispiel für eine kompliziertere Funktion ist die Mehrheitsfunktion (einer ungeraden Anzahl von Eingängen).

Darstellung

Eine Boolesche Funktion kann auf verschiedene Weise angegeben werden:

• Wahrheitstabelle: Auflistung des Wertes für alle möglichen Werte der Argumente explizit auflisten
  • Marquand-Diagramm: Wahrheitstabellenwerte, die in einem zweidimensionalen Raster angeordnet sind (in a verwendet Karnaugh -Karte)
  • BinärentscheidungsdiagrammDie Werte der Wahrheitstabelle am Ende eines Binärbaums auflisten
  • Venn-Diagrammdie Werte der Wahrheitstabelle als Färbung der Regionen der Ebene darstellen

Algebraisch, als Aussageformel Verwenden von rudimentären booleschen Funktionen:

• Negation normale Form, eine willkürliche Mischung aus und und Ors der Argumente und deren Ergänzungen
• Disjunktive normale Form, als oder von den Argumenten und ihrer Ergänzungen
• Konjunktive normale Form, als und von Ors der Argumente und ihrer Ergänzungen
• Kanonische Normalform, eine standardisierte Formel, die die Funktion eindeutig identifiziert:
  • Algebraische Normalform oder Zhegalkin Polynom, als Xor von und der Argumente (keine Ergänzungen zulässig)
  • Voll (Kanonisch) disjunktive normale Form, ein oder von ands jeweils jedes Argument oder Komplement (Komplement (Komplement) (Minterms)
  • Voll (Kanonisch) Konjunktive normale Form, an und von ors, die jedes Argument oder Komplement enthalten (Maxterms)
  • Blake Canonical Form, das oder von allen Prime Implicants der Funktion

Boolesche Formeln können auch als Diagramm angezeigt werden:

• Propositional gerichtete acyclische Graphen
  • Digitaler Schaltung Diagramm von Logik -Tore, a Boolesche Schaltung
  • Und Übervertebiagrammnur und nicht und nicht

Um elektronische Schaltkreise zu optimieren, können Boolesche Formeln sein minimiert Verwendung der Quine -McCluskey -Algorithmus oder Karnaugh -Karte.

Analyse

Eigenschaften

Eine Boolesche Funktion kann eine Vielzahl von Eigenschaften haben:^[7]

• Konstante: Ist immer wahr oder immer falsch, unabhängig von seinen Argumenten.
• Monoton: Für jede Kombination von Argumentwerten kann das Ändern eines Arguments von False in True nur dazu führen, dass die Ausgabe von False zu True und nicht von True zu False wechselt. Eine Funktion soll sein Unate in einer bestimmten Variablen, wenn es sich um Änderungen dieser Variablen handelt.
• Linear: Für jede Variable macht das Umdrehen des Wertes der Variablen entweder immer einen Unterschied im Wahrheitswert oder macht nie einen Unterschied (a) Paritätsfunktion).
• Symmetrisch: Der Wert hängt nicht von der Reihenfolge seiner Argumente ab.
• Schreibgerichtete: Kann mit ausgedrückt werden mit Verbindung, disjunktion, und Negation mit einer einzelnen Instanz jeder Variablen.
• Ausgewogen: wenn es Wahrheitstabelle enthält eine gleiche Menge an Nullen und Einsen. Das Hamming -Gewicht der Funktion ist die Anzahl derjenigen in der Wahrheitstabelle.
• Gebogen: seine Derivate sind alle ausgeglichen (das Autokorrelationsspektrum ist Null)
• Korrelationsimmun zu mTH -Reihenfolge: Wenn der Ausgang mit allen (linearen) Kombinationen von höchstens unkorreliert ist m Argumente
• Ausweichend: Wenn die Bewertung der Funktion immer den Wert aller Argumente erfordert
• Eine boolesche Funktion ist a Sheffer -Funktion Wenn es verwendet werden kann, um (nach Zusammensetzung) eine beliebige booleale Funktion zu erstellen (siehe Funktionale Vollständigkeit)
• Das algebraischer Abschluss einer Funktion ist die Reihenfolge der höchsten Ordnung monomial in seiner Algebraische Normalform

Komplexität der Schaltung Versuche, boolesche Funktionen in Bezug auf die Größe oder Tiefe der Schaltungen zu klassifizieren, die sie berechnen können.

Abgeleitete Funktionen

Eine boolesche Funktion kann mit Verwendung zerlegt werden Booles Expansionstheorem positiv und negativ Shannon Cofaktoren (Shannon -Expansion), die (k-1) -ary-Funktionen sind, die sich aus der Festlegung eines der Argumente (auf Null oder eins) ergeben. Die allgemeinen (k-ary) Funktionen, die durch Auferlegen einer linearen Einschränkung für eine Reihe von Eingängen (ein linearer Unterraum) erhalten werden Unterfunktionen.^[8]

Das Boolesche Derivat der Funktion zu einem der Argumente ist eine (k-1) -Rary-Funktion, die zutrifft, wenn die Ausgabe der Funktion empfindlich gegenüber der ausgewählten Eingangsvariablen ist. Es ist der XOR der beiden entsprechenden Cofaktoren. Ein Derivat und ein Cofaktor werden in a verwendet Reed -Müller -Expansion. Das Konzept kann als K-Ary-Derivat in Richtung DX verallgemeinert werden, das als Differenz (xor) der Funktion bei x und x + dx erhalten wird.^[8]

Das Möbius transformiert (oder Boole-möbius transformiert) einer Booleschen Funktion ist der Satz von Koeffizienten seiner Polynom (Algebraische Normalform) als Funktion der monomialen Exponentenvektoren. Es ist ein selbstinvers verwandeln. Es kann effizient mit a berechnet werden Schmetterlingsalgorithmus (""Schnelle Möbius -Transformation"), analog zum Schnelle Fourier-Transformation.^[9] Zufällig Boolesche Funktionen entsprechen ihrer möbius -Transformation, d. H. Ihre Wahrheitstabellenwerte (Minuted), die ihren algebraischen (monomialen) Koeffizienten entsprechen.^[10] Es gibt 2^2^(k–1) übereinstimmende Funktionen von k Argumente.^[11]

Kryptografische Analyse

Das Walsh transformiert einer Booleschen Funktion ist eine K-Ary-Ganzzahl-Funktion, die die Koeffizienten einer Zersetzung in die lineare Funktionen (Walsh funktioniert) analog zur Zersetzung realer Wertfunktionen in Harmonische bis zum Fourier-Transformation. Sein Quadrat ist das Leistungsspektrum oder Walsh spectrum. Der Walsh -Koeffizient eines einzelnen Bitvektors ist ein Maß für die Korrelation dieses Bits mit der Ausgabe der Booleschen Funktion. Der maximale (im absoluten Wert) Walsh -Koeffizient wird als der bezeichnet Linearität der Funktion.^[8] Die höchste Anzahl von Bits (Reihenfolge), für die alle Walsh -Koeffizienten 0 sind (d. H. Die Unterfunktionen sind ausgeglichen) Elastizitätund die Funktion soll sein Korrelationsimmun zu dieser Reihenfolge.^[8] Die Walsh -Koeffizienten spielen eine Schlüsselrolle in Lineare Kryptanalyse.

Das Autokorrelation einer booleschen Funktion ist eine K-ary-Ganzzahl-Funktion, die die Korrelation zwischen einem bestimmten Satz von Änderungen in den Eingängen und der Funktion OUPUT ergibt. Für einen bestimmten Bitvektor hängt es mit dem Hamminggewicht des Derivats in dieser Richtung zusammen. Der maximale Autokorrelationskoeffizient (im absoluten Wert) ist als der bekannt Absolute Indikator.^[7][8] Wenn alle Autokorrelationskoeffizienten 0 sind (d. H. Die Derivate sind ausgeglichen) für eine bestimmte Anzahl von Bits, soll die Funktion das erfüllen Propagationskriterium zu dieser Ordnung; Wenn sie alle Null sind, ist die Funktion a gebogene Funktion.^[12] Die Autokorrelationskoeffizienten spielen eine Schlüsselrolle in Differentialkryptanalyse.

Die Walsh -Koeffizienten einer Booleschen Funktion und deren Autokorrelationskoeffizienten sind durch das Äquivalent des Wiener -Khinchin -Theorem, was besagt, dass die Autokorrelation und das Leistungsspektrum ein Walsh -Transformationspaar sind.^[8]

Diese Konzepte können auf natürliche Weise auf vektorial Boolesche Funktionen unter Berücksichtigung ihrer Ausgangsbits (Koordinaten) individuell oder gründlicher, indem Sie den Satz aller linearen Funktionen von Ausgangsbits betrachten, die als seine bezeichnet werden Komponenten.^[6] Der Satz von Walsh -Transformationen der Komponenten ist als bekannt Lineare Approximationstabelle (Lat)^[13][14] oder Korrelationsmatrix;^[15][16] Es beschreibt die Korrelation zwischen verschiedenen linearen Kombinationen von Eingangs- und Ausgangsbits. Der Satz der Autokorrelationskoeffizienten der Komponenten ist die Autokorrelationstabelle,^[14] verwandt durch eine Walsh -Transformation der Komponenten^[17] zu den weit verbreiteten verwendeten Differenzverteilungstabelle (DDT)^[13][14] Dies listet die Korrelationen zwischen Unterschieden in Eingangs- und Ausgangsbits auf (siehe auch: S-Box).

Echte Polynomform

Auf der Einheit Hypercube

Jede Boolesche Funktion ${\ displayStyle f (x): \ {0,1 \}^{n} \ rightarrow \ {0,1 \}}$ kann einzigartig erweitert (interpoliert) auf die echte Domäne durch eine Multilineares Polynom in ${\ displaystyle \ mathbb {r} ^{n}}$, konstruiert durch Summieren der Wahrheitstabellenwerte multipliziert mit Indikatorpolynome:

Zum Beispiel die Erweiterung der binären XOR -Funktion ${\ displayStyle x \ oplus y}$ istwas gleich istEinige andere Beispiele sind Negation (${\ displayStyle 1-x}$), UND (${\ displayStyle xy}$) und oder (${\ displayStyle x+y-xy}$). Wenn alle Operanden unabhängig sind (keine Variablen teilen), finden Sie eine Polynomform einer Funktion, indem die Polynome der Operatoren wiederholt in einer booleschen Formel angewendet werden. Wenn die Koeffizienten berechnet werden Modulo 2 man erhält die Algebraische Normalform (Zhegalkin Polynom).

Direkte Ausdrücke für die Koeffizienten des Polynoms können abgeleitet werden, indem ein geeignetes Derivat eingenommen wird:

Dies verallgemeinert als die Möbius -Inversion des teilweise bestelltes Set von Bit Vektoren:wo ${\ displayStyle | a |}$ bezeichnet das Gewicht des Bitvektors ${\ displayStyle a}$. Modulo 2 genommen, dies ist das Boolesche Möbius transformiert, geben die Algebraische Normalform Koeffizienten:In beiden Fällen wird die Summe alle Bitvektoren übernommen a überdeckt von m, d.h. die "ein" Teile von a bilden eine Untergruppe der einen Teile von m.

Wenn die Domäne auf das n-dimensionale beschränkt ist Hypercube ${\ displayStyle [0,1]^{n}}$das Polynom ${\ displaystyle f^{*} (x): [0,1]^{n} \ rightarrow [0,1]}$ gibt die Wahrscheinlichkeit eines positiven Ergebnisses bei der Booleschen Funktion f wird angewendet auf n unabhängiger zufälliger (Bernoulli) Variablen mit individuellen Wahrscheinlichkeiten x. Ein besonderer Fall dieser Tatsache ist der Lemma aufpacken zum Paritätsfunktionen. Die Polynomform einer Booleschen Funktion kann auch als natürliche Erweiterung verwendet werden Fuzzy Logic.

Auf dem symmetrischen Hypercube

Oft wird die Boolesche Domain als als angenommen als ${\ displayStyle \ {-1,1 \}}$, mit falsch ("0") Mapping auf 1 und true ("1") bis -1 (siehe Analyse der Booleschen Funktionen). Das Polynom, das entspricht ${\ displayStyle g (x): \ {-1,1 \}^{n} \ rightarrow \ {-1,1 \}}$ wird dann gegeben durch:

Die Verwendung der symmetrischen booleschen Domäne vereinfacht bestimmte Aspekte der Analyse, da die Negation der Multiplizierung mit -1 und entspricht lineare Funktionen sind Monome (XOR ist eine Multiplikation). Diese Polynomform entspricht somit der Walsh transformiert (In diesem Zusammenhang auch als bekannt als als Fourier-Transformation) der Funktion (siehe oben). Das Polynom hat auch die gleiche statistische Interpretation wie das im Standard booleschen Bereich, außer dass es sich jetzt mit den erwarteten Werten befasst ${\ displayStyle e (x) = p (x = 1) -p (x = -1) \ in [-1,1]}$ (sehen Lemma aufpacken zum Beispiel).

Anwendungen

Boolesche Funktionen spielen eine grundlegende Rolle bei Fragen von Komplexitätstheorie sowie das Design von Prozessoren für Digitale Computer, wo sie in elektronischen Schaltungen implementiert werden Logik -Tore.

Die Eigenschaften von Booleschen Funktionen sind in entscheidender Bedeutung Kryptographiebesonders im Design von Symmetrische Schlüsselalgorithmen (sehen Substitutionsbox).

Im Genossenschaftsspiel Theorie, monotone boolesche Funktionen werden genannt Einfache Spiele (Wahlspiele); Dieser Begriff wird angewendet, um Probleme in Theorie der sozialen Wahl.

Siehe auch

Verweise

Weitere Lektüre

• Crama, Yves; Hammer, Peter L. (2011), Boolesche Funktionen: Theorie, Algorithmen und Anwendungen, Cambridge University Press, doi:10.1017/CBO9780511852008, ISBN 9780511852008
• "Boolesche Funktion", Enzyklopädie der Mathematik, EMS Press, 2001 [1994]
• Janković, Dragan; Stanković, Radomir S.; Moraga, Claudio (November 2003). "Arithmetische Ausdrücke Optimierung unter Verwendung der Doppelpolaritätseigenschaft". Serbisches Journal of Electrical Engineering. 1 (71–80, Nummer 1): 71–80. doi:10.2298/sjee0301071j.
• Arnold, Bradford Henry (1. Januar 2011). Logik- und Boolesche Algebra. Courier Corporation. ISBN 978-0-486-48385-6.
• Mano, M. M.; Ciletti, M. D. (2013), Digitales Design, Pearson