Boolean function

Logical connectives
NOT ${\displaystyle \neg A,-A,{\overline {A}},\sim A}$ AND ${\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}$ NAND ${\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}$ OR ${\displaystyle A\lor B,A+B,A\mid B,A\parallel B}$ NOR ${\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}$ XNOR ${\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}$ └ equivalent ${\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}$ XOR ${\displaystyle A{\underline {\lor }}B,A\oplus B}$ └nonequivalent ${\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}$ implies ${\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}$ nonimplication (NIMPLY) ${\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}$ converse ${\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}$ converse nonimplication ${\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

In

A Boolean function takes the form ${\displaystyle f:\{0,1\}^{k}\to \{0,1\}}$, where ${\displaystyle \{0,1\}}$ is known as the Boolean domain and ${\displaystyle k}$ is a non-negative integer called the arity of the function. In the case where ${\displaystyle k=0}$, the function is a constant element of ${\displaystyle \{0,1\}}$. A Boolean function with multiple outputs, ${\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}$ with ${\displaystyle m>1}$ is a vectorial or vector-valued Boolean function (an S-box in symmetric cryptography).^[6]

There are ${\displaystyle 2^{2^{k}}}$ different Boolean functions with ${\displaystyle k}$ arguments; equal to the number of different truth tables with ${\displaystyle 2^{k}}$ entries.

Every ${\displaystyle k}$-ary Boolean function can be expressed as a propositional formula in ${\displaystyle k}$ variables ${\displaystyle x_{1},...,x_{k}}$, and two propositional formulas are logically equivalent if and only if they express the same Boolean function.

The rudimentary symmetric Boolean functions (logical connectives or logic gates) are:

• complement
  - which receives one input and returns true when that input is false ("not")
• AND or conjunction - true when all inputs are true ("both")
• OR or disjunction - true when any input is true ("either")
• XOR or exclusive disjunction - true when one of its inputs is true and the other is false ("not equal")
• NAND or Sheffer stroke - true when it is not the case that all inputs are true ("not both")
• NOR or logical nor - true when none of the inputs are true ("neither")
• XNOR or logical equality - true when both inputs are the same ("equal")

An example of a more complicated function is the majority function (of an odd number of inputs).

A Boolean function may be specified in a variety of ways:

• Truth table: explicitly listing its value for all possible values of the arguments
  • Marquand diagram: truth table values arranged in a two-dimensional grid (used in a Karnaugh map)
  • Binary decision diagram, listing the truth table values at the bottom of a binary tree
  • Venn diagram, depicting the truth table values as a colouring of regions of the plane

Algebraically, as a propositional formula using rudimentary Boolean functions:

• Negation normal form, an arbitrary mix of AND and ORs of the arguments and their complements
• Disjunctive normal form, as an OR of ANDs of the arguments and their complements
• Conjunctive normal form, as an AND of ORs of the arguments and their complements
• Canonical normal form, a standardized formula which uniquely identifies the function:
  • Algebraic normal form or Zhegalkin polynomial, as a XOR of ANDs of the arguments (no complements allowed)
  • Full (canonical)
    minterms
    )
  • Full (canonical)
    maxterms
    )
  • prime implicants
    of the function

Boolean formulas can also be displayed as a graph:

• Propositional directed acyclic graph
  • Digital circuit diagram of logic gates, a Boolean circuit
  • And-inverter graph, using only AND and NOT

In order to optimize electronic circuits, Boolean formulas can be

A Boolean function can have a variety of properties:^[7]

• 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.

A Boolean function may be decomposed using

The Möbius transform (or Boole-Möbius transform) of a Boolean function is the set of coefficients of its polynomial (algebraic normal form), as a function of the monomial exponent vectors. It is a self-inverse transform. It can be calculated efficiently using a butterfly algorithm ("Fast Möbius Transform"), analogous to the Fast Fourier Transform.^[9] Coincident Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients.^[10] There are 2^2^(k−1) coincident functions of k arguments.^[11]

The

The autocorrelation of a Boolean function is a k-ary integer-valued function giving the correlation between a certain set of changes in the inputs and the function output. For a given bit vector it is related to the Hamming weight of the derivative in that direction. The maximal autocorrelation coefficient (in absolute value) is known as the absolute indicator.^[7][8] If all autocorrelation coefficients are 0 (i.e. the derivatives are balanced) for a certain number of bits then the function is said to satisfy the propagation criterion to that order; if they are all zero then the function is a bent function.^[12] The autocorrelation coefficients play a key role in differential cryptanalysis.

The Walsh coefficients of a Boolean function and its autocorrelation coefficients are related by the equivalent of the Wiener–Khinchin theorem, which states that the autocorrelation and the power spectrum are a Walsh transform pair.^[8]

These concepts can be extended naturally to vectorial Boolean functions by considering their output bits (coordinates) individually, or more thoroughly, by looking at the set of all linear functions of output bits, known as its components.^[6] The set of Walsh transforms of the components is known as a Linear Approximation Table (LAT)^[13][14] or correlation matrix;^[15][16] it describes the correlation between different linear combinations of input and output bits. The set of autocorrelation coefficients of the components is the autocorrelation table,^[14] related by a Walsh transform of the components^[17] to the more widely used Difference Distribution Table (DDT)^[13][14] which lists the correlations between differences in input and output bits (see also: S-box).

Any Boolean function ${\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}$ can be uniquely extended (interpolated) to the real domain by a multilinear polynomial in ${\displaystyle \mathbb {R} ^{n}}$, constructed by summing the truth table values multiplied by indicator polynomials:$${\displaystyle 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 ${\displaystyle x\oplus y}$ is$${\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}$$which equals$${\displaystyle x+y-2xy}$$Some other examples are negation (${\displaystyle 1-x}$), AND (${\displaystyle xy}$) and OR (${\displaystyle 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:$${\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}}$$this generalizes as the

of bit vectors:$${\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}$$where ${\displaystyle |a|}$ denotes the weight of the bit vector ${\displaystyle a}$. Taken modulo 2, this is the

$${\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}$$

When the domain is restricted to the n-dimensional hypercube ${\displaystyle [0,1]^{n}}$, the polynomial ${\displaystyle 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 ${\displaystyle \{-1,1\}}$, with false ("0") mapping to 1 and true ("1") to -1 (see Analysis of Boolean functions). The polynomial corresponding to ${\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}$ is then given by:$${\displaystyle 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 ${\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}$ (see piling-up lemma for an example).

Boolean functions play a basic role in questions of

In cooperative game theory, monotone Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory.