Boolesche Funktion - Wikipedia

In Mathematik und Logik ist eine (finite) Boolesche Funktion (oder Schaltfunktion) eine Funktion der Form ƒ : B ^k → B wobei B = {0, 1} eine -boolesche Domäne und k eine nicht negative Ganzzahl ist, die Arity genannt wird der Funktion. In dem Fall, in dem k = 0 ist, ist die "Funktion" im Wesentlichen ein konstantes Element von B .

Jede k -äre boolesche Funktion kann als Aussageformel in k Variablen x ₁ x ausgedrückt werden. 19659005] k und zwei Satzformeln sind genau dann logisch gleichwertig, wenn sie die gleiche boolesche Funktion ausdrücken. Es gibt 2 ^{2 k} k -äre Funktionen für jeden k .

Boolesche Funktionen in Anwendungen [ edit ]

Eine Funktion, mit der alle booleschen Ausgaben in Relation zu ihrer booleschen Eingabe nach logischen Berechnungsarten ausgewertet werden können. Solche Funktionen spielen eine grundlegende Rolle in Fragen der Komplexitätstheorie sowie beim Entwurf von Schaltungen und Chips für digitale Computer. Die Eigenschaften boolescher Funktionen spielen in der Kryptographie eine entscheidende Rolle, insbesondere beim Entwurf von Algorithmen mit symmetrischen Schlüsseln (siehe Substitutionsfeld).

Boolesche Funktionen werden häufig durch Sätze in Aussagenlogik und manchmal als multivariate Polynome über GF (2) dargestellt. Effizientere Repräsentationen sind jedoch binäre Entscheidungsdiagramme (BDD), Negationsnormalformen und propositionale gerichtete azyklische Diagramme (PDAG).

In der kooperativen Spieltheorie werden monotone boolesche Funktionen einfache Spiele (Abstimmungsspiele) genannt; Dieser Begriff wird angewendet, um Probleme in der Theorie der sozialen Entscheidung zu lösen.

Siehe auch [ edit ]

Referenzen [ edit ]

• Crama, Y; Hammer, P. L. (2011), Boolesche Funktionen: Theorie, Algorithmen und Anwendungen Cambridge University Press, Doi: 10.1017 / CBO9780511852008, ISBN 9780511852008 Hazewinkel, Michiel, Hrsg. (2001) [1994]"Boolesche Funktion", Enzyklopädie der Mathematik Springer Science + Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
• Janković, Dragan; Stanković, Radomir S .; Moraga, Claudio (November 2003). "Optimierung arithmetischer Ausdrücke unter Verwendung der Eigenschaft mit zwei Polaritäten" (PDF) . Serbische Zeitschrift für Elektrotechnik . 1 (71–80, Nummer 1). Archiviert aus dem Original (PDF) am 05.03.2016 . 2015-06-07 .
• Mano, M. M .; Ciletti, M. D. (2013), Digital Design Pearson .