Boolean function

and truth table of a ternary Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually {true, false}, {0,1} or {−1,1}). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory. A Boolean function takes the form f:\{0,1\}^k \to \{0,1\} , where \{0,1\} is known as the Boolean domain and k is a non-negative integer called the arity of the function. In the case where k=0 , the function is a constant element of \{0,1\} . A Boolean function with multiple outputs, f:\{0,1\}^k \to \{0,1\}^m with m>1 is a vectorial or vector-valued Boolean function (an S-box in symmetric cryptography). There are 2^{2^k} different Boolean functions with k arguments; equal to the number of different truth tables with 2^k entries. Every k -ary Boolean function can be expressed as a propositional formula in k variables x_1,...,x_k , and two propositional formulas are logically equivalent if and only if they express the same Boolean function.

and truth table of a ternary Boolean function]] In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually {true, false}, {0,1} or {−1,1}). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory. A Boolean function takes the form f:\{0,1\}^k \to \{0,1\} , where \{0,1\} is known as the Boolean domain and k is a non-negative integer called the arity of the function. In the case where k=0 , the function is a constant element of \{0,1\} . A Boolean function with multiple outputs, f:\{0,1\}^k \to \{0,1\}^m with m>1 is a vectorial or vector-valued Boolean function (an S-box in symmetric cryptography). There are 2^{2^k} different Boolean functions with k arguments; equal to the number of different truth tables with 2^k entries. Every k -ary Boolean function can be expressed as a propositional formula in k variables x_1,...,x_k , and two propositional formulas are logically equivalent if and only if they express the same Boolean function. ===Properties=== A Boolean function can have a variety of properties: Constant: Is always true or always false regardless of its arguments. Monotone: for every combination of argument values, changing an argument from false to true can only cause the output to switch from false to true and not from true to false. A function is said to be unate in a certain variable if it is monotone with respect to changes in that variable. Linear: for each variable, flipping the value of the variable either always makes a difference in the truth value or never makes a difference (a parity function). Symmetric: the value does not depend on the order of its arguments. Read-once: Can be expressed with conjunction, disjunction, and negation with a single instance of each variable. Balanced: if its truth table contains an equal number of zeros and ones. The Hamming weight of the function is the number of ones in the truth table. Bent: its derivatives are all balanced (the autocorrelation spectrum is zero) Correlation immune to mth order: if the output is uncorrelated with all (linear) combinations of at most m arguments Evasive: if evaluation of the function always requires the value of all arguments A Boolean function is a Sheffer function if it can be used to create (by composition) any arbitrary Boolean function (see functional completeness) The algebraic degree of a function is the order of the highest order monomial in its algebraic normal form Circuit complexity attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them. Any Boolean function f(x): \{0,1\}^n \rightarrow \{0,1\} can be uniquely extended (interpolated) to the real domain by a multilinear polynomial in \mathbb{R}^n , constructed by summing the truth table values multiplied by indicator polynomials: f^*(x) = \sum_{a \in {\{0,1\}}^n} f(a) \prod_{i:a_i=1} x_i \prod_{i:a_i=0} (1-x_i) For example, the extension of the binary XOR function x \oplus y is 0(1-x)(1-y) + 1x(1-y) + 1(1-x)y + 0xy which equals x + y -2xy Some other examples are negation ( 1-x ), AND ( xy ) and OR ( x + y - xy ). When all operands are independent (share no variables) a function's polynomial form can be found by repeatedly applying the polynomials of the operators in a Boolean formula. When the coefficients are calculated modulo 2 one obtains the algebraic normal form (Zhegalkin polynomial). Direct expressions for the coefficients of the polynomial can be derived by taking an appropriate derivative: \begin{array}{lcl} f^*(00) & = & (f^*)(00) & = & f(00) \\ f^*(01) & = & (\partial_1f^*)(00) & = & -f(00) + f(01) \\ f^*(10) & = & (\partial_2f^*)(00) & = & -f(00) + f(10) \\ f^*(11) & = & (\partial_1\partial_2f^*)(00) & = & f(00) -f(01)-f(10)+f(11) \\ \end{array} this generalizes as the Möbius inversion of the partially ordered set of bit vectors: f^*(m) = \sum_{a \subseteq m} (-1)^ f(a) where |a| denotes the weight of the bit vector a . Taken modulo 2, this is the Boolean Möbius transform, giving the algebraic normal form coefficients: \hat f(m) = \bigoplus_{a \subseteq m} f(a) In both cases, the sum is taken over all bit-vectors a covered by m, i.e. the "one" bits of a form a subset of the one bits of m. When the domain is restricted to the n-dimensional hypercube [0,1]^n , the polynomial f^*(x): [0,1]^n \rightarrow [0,1] gives the probability of a positive outcome when the Boolean function f is applied to n independent random (Bernoulli) variables, with individual probabilities x. A special case of this fact is the piling-up lemma for parity functions. The polynomial form of a Boolean function can also be used as its natural extension to fuzzy logic. Often, the Boolean domain is taken as \{-1, 1\} , with false ("0") mapping to 1 and true ("1") to −1 (see Analysis of Boolean functions). The polynomial corresponding to g(x): \{-1,1\}^n \rightarrow \{-1,1\} is then given by: g^*(x) = \sum_{a \in {\{-1,1\}}^n} g(a) \prod_{i:a_i=-1} \frac{1-x_i}{2} \prod_{i:a_i=1} \frac{1+x_i}{2} Using the symmetric Boolean domain simplifies certain aspects of the analysis, since negation corresponds to multiplying by −1 and linear functions are monomials (XOR is multiplication). This polynomial form thus corresponds to the Walsh transform (in this context also known as Fourier transform) of the function (see above). The polynomial also has the same statistical interpretation as the one in the standard Boolean domain, except that it now deals with the expected values E(X) = P(X=1) - P(X=-1) \in [-1, 1] (see piling-up lemma for an example). ==Applications== Boolean functions play a basic role in questions of complexity theory as well as the design of processors for digital computers, where they are implemented in electronic circuits using logic gates. The properties of Boolean functions are critical in cryptography, particularly in the design of symmetric key algorithms (see substitution box). In cooperative game theory, monotone Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory. ==See also== Pseudo-Boolean function Boolean-valued function Boolean algebra topics Algebra of sets Decision tree model Indicator function Signed set ==References== ==Further reading==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1360621070 under CC BY-SA 4.0; modifications have been made.