Boolean function
In
mathematics, a
(finitary) Boolean function is a
function of the form f :
Bk →
B, where
B = {0, 1} is a
Boolean domain and
k is a nonnegative integer called the arity of the function. In the case where
k = 0, the "function" is essentially a constant element of
B.Every
k-ary Boolean formula can be expressed as a
propositional formula in
k variables
x1,…,
xk, and two propositional formulas are logically equivalent if and only if they express the same Boolean function. There are
22k
k-ary functions for every
k.
Boolean functions in applications
A Boolean function describes how to determine a
Boolean value output based on some
logical calculation from Boolean inputs. Such functions play a basic role in questions of
complexity theory as well as the design of circuits and chips for
digital computers. The properties of Boolean functions play a critical role in
cryptography, particularly in the design of
symmetric key algorithms (see
substitution box).Boolean functions are often represented by sentences in
propositional logic, and sometimes as multivariate
polynomials over
GF(2), but more efficient representations are
binary decision diagrams (BDD),
negation normal forms, and
propositional directed acyclic graphs (PDAG).
See also
{{col-begin}}{{col-break|width=30%}}
{{col-break}}
{{col-end}}{{Logic}}
Boolesche FunktionFunción booleanaتابع بولیFonction booléenneFunzione booleanaブール関数Булева функция布尔函数
(...as imported from WP)
article has not been saved locally
