Boolean function

A Boolean function is a function on a Boolean hypercube, often with codomain $\{-1,1\}$ or $\{0,1\}$.

A set of Boolean functions is functionally complete if function composition using those operations can express every positive-arity Boolean function. The NAND gate alone suffices: tie its inputs to obtain negation, negate its output to obtain logical conjunction, and apply De Morgan's laws to obtain logical disjunction; then use disjunctive normal form.

Among sixteen binary Boolean truth functions, eight become functionally complete together with negation. The eight affine functions cannot express conjunction because composition preserves affinity. Each of the other eight truth tables has exactly one or three true rows. Negating the output if needed and selected inputs transforms its unique true row to the conjunction table. Thus conjunction and negation become definable and disjunctive normal form expresses every Boolean function.

Suppose a first-order language has logical implication as its only connective and has either or both of the quantifiers, but no primitive falsity. In a singleton structure with every atomic predicate true, all atomic equalities are also true, and structural induction makes every formula true. No formula of this language can therefore express a negated equality. Quantifiers cannot repair this failure of expressive completeness, even though they add syntactic operations beyond propositional connectives.

The Boolean function obtained by assigning a fixed Boolean value $b$ to a chosen Boolean variable $x$ in $f$. The original Boolean function satisfies $f=(\neg x\wedge f{|}_{x=0})\vee (x\wedge f{|}_{x=1})$.

A Directed acyclic graph representing a Boolean function. A decision node tests a Boolean variable and has zero and one successors; evaluation follows the corresponding arrows until a terminal node returns a Boolean value. Sharing subgraphs can make a binary decision diagram much smaller than a binary decision tree.

A vertex that returns a final output rather than performing another test. In a binary decision diagram the two possible outputs are the Boolean constants zero and one.

An internal vertex that tests a condition and selects an outgoing branch. In a binary decision diagram, a decision node tests a Boolean variable and has one zero arrow and one one arrow.

An ordered binary decision diagram with shared equal terminal nodes, no decision node having identical zero and one children, and no two decision nodes having the same tested Boolean variable and the same ordered pair of children. For a fixed variable ordering of a binary decision diagram, it is unique up to labelled graph isomorphism: each nonconstant remaining Boolean cofactor has a uniquely determined first essential Boolean variable, and its two children are recursively determined by its zero and one Boolean cofactors. This uniqueness does not compare different orderings.

A fixed order in which Boolean variables may be tested along each branch of an ordered binary decision diagram. Branches may skip a test, but cannot reverse the order. The order can change the number of distinct remaining Boolean cofactors and therefore the size of the representation.

In Boolean algebra, the product $yz$ is the consensus of $xy$ and $\bar{x}z$. If $yz=1$, either $x=1$ and $xy=1$, or $x=0$ and $\bar{x}z=1$, so adding the consensus does not change the Boolean function. It can change a circuit's transient behavior: while $x$ switches, the two original product terms may briefly both be zero because of unequal propagation delays, but $yz$ remains one. Keeping the logically redundant consensus product can therefore remove a static-one logic hazard.

An input combination at which a Boolean function's specification imposes no required output value. Karnaugh map minimization may assign either value independently to simplify the implemented Boolean circuit. The resulting circuit still assigns a definite output to every input. An unused finite-state machine encoding is therefore an optimization opportunity, but its eventual transitions must be checked if recovery from that encoding matters.

For an odd number of input bits, this Boolean function is one exactly when fewer than half of the inputs are one. For three inputs, $m(a,b,c)=\neg a\neg b\vee \neg a\neg c\vee \neg b\neg c$. Each term says that a specified pair of inputs is zero; at most one input can then be one. This proves both directions of the formula.

A truth table arranged so neighbouring cells differ in one Boolean variable, using Gray code order along each multi-bit axis. Opposite edges are also adjacent. A valid group contains all $2^k$ combinations of $k$ varying variables while every other variable stays fixed; it eliminates those $k$ variables and gives an implicant; covering the one-cells yields a disjunctive normal form. The method is associated with Maurice Karnaugh.

A Boolean function satisfying the displayed condition. Composition of one-preserving Boolean functions is one-preserving, since each inner output is one on an all-one input. Consequently structural induction shows that a variable-built propositional formula using only one-preserving logical connectives, such as $\wedge ,\vee ,\to$, is true under the all-one Boolean valuation.

A logical conjunction $T$ of literals is an implicant of a Boolean function $f$ if every Boolean valuation making $T$ true also makes $f$ true. Every term in a disjunctive normal form is an implicant of the represented Boolean function. To rule out a one-literal term, it suffices to find a false Boolean valuation of $f$ where that literal is true.

An implicant from which no literal can be removed while preserving the implication to the Boolean function. A prime implicant is essential when it covers a one-input assignment that no other prime implicant covers.

A Boolean function expressing whether its argument satisfies a property. Membership in a set is represented by its characteristic predicate. Returning a function lets a tree fold return a predicate that subsequently checks membership of a binary search tree.

A linear Boolean function is a linear map from ${\mathbb{F}}_2^n$ to ${\mathbb{F}}_2$. Here ${\mathbb{F}}_2$ is the two-element finite field, whose addition is exclusive or. Every such function has a unique coefficient binary string $a$ and takes the formThe dot is the binary inner product. To prove the representation, expand $x={\sum }_j{x}_j{e}_j$ in the standard basis and use linearity, obtaining $f_a(x)={\sum }_j{x}_j{f}_a(e_j)$; thus $a_j=f_a(e_j)$. For example, $a=101$ gives $f_a(x)=x_1\oplus x_3$. Adding a nonzero constant produces an affine map, not a linear map.

A Boolean function on a finite nonempty domain is balanced when it is zero on exactly half the inputs and one on the other half. For a one-bit domain, the balanced functions are $f(x)=x$ and $f(x)=1\oplus x$, while the remaining two functions are constant functions. The Deutsch algorithm distinguishes these two classes with one Boolean quantum oracle query in the absence of noise.

Under uniform independent input bits, a zero-one Boolean function is quite fair when its mean lies between one quarter and three quarters. This convention excludes functions whose output is nearly constant; it does not require exact balance or equal coordinate influences.

The algebraic normal form is the unique multilinear polynomial representation of a Boolean function over the field with two elements, using exclusive or for addition and ordinary bit multiplication for products. The empty product is one. Existence and uniqueness follow by induction from $f(z^{\prime },z_d)=f(z^{\prime },0)\oplus z_d(f(z^{\prime },0)\oplus f(z^{\prime },1))$: the first polynomial supplies all coefficients not containing $z_d$, and the difference supplies exactly those that do. For split inputs $(x,y)$, each monomial factors into one locally computed product of Alice's bits and one of Bob's bits, yielding a separated Boolean decomposition.

Every Boolean function of distributed inputs is an exclusive or of products of locally computable bits. The displayed identity follows because exactly one indicator is one. It uses at most $2^m$ terms, each a function of $x$ times a function of $y$; exchanging the two input roles gives at most $2^n$ terms. This elementary truth-table factorization is useful for distributed computation with PR boxes and does not depend on a probabilistic approximation.

A $p$-random restriction independently leaves each coordinate live with probability $p$, otherwise fixing it to zero or one with probability $(1-p)/2$ each. Composing independent restrictions with live probabilities $p_1,\dots ,p_d$ produces the same distribution with live probability ${\prod }_j{p}_j$. Fixed values stay unbiased.

A tribes function is an OR of AND blocks: partition $mw$ coordinates into $m$ blocks of size $w$, and let $f=1$ when at least one block consists entirely of ones. For independent random variables with each bit uniform, $\mathbb{P}(f=0)=(1-2^{-w}{)}^m$. The influence of a variable is $2^{-(w-1)}(1-2^{-w}{)}^{m-1}$, because every other bit in its block must be one and every other block must fail. Taking $m$ approximately $(\log 2)2^w$ keeps both output probabilities bounded away from zero and gives influences of order $\log (mw)/(mw)$. This shows the order in the Kahn-Kalai-Linial theorem is sharp.

Choose $w\ge 1$ maximal such that $wm\le n$ for the displayed $m$, and take the OR of $m$ AND blocks of size $w$, ignoring unused coordinates. Its failure probability is $(1-2^{-w}{)}^m$, between one quarter and three quarters. Active coordinates have influence $2^{1-w}(1-2^{-w}{)}^{m-1}$ and unused ones have zero influence. Maximality gives $2^{1-w}<4(\log 2)(w+1)/n$; for $n\ge 2$, $w\le {\log }_{2}n$, so every influence is below $8\log n/n$. The construction is therefore a quite fair Boolean function with small influences for every $n\ge 2$. The logarithmic bound cannot hold at $n=1$, where every quite fair function has influence one.

For $m$ tribes of size $w$ with $m\sim (\log 2)2^w$ and $n=mw$, the success probability under the p-biased product measure is $1-(1-p^w{)}^m$. Its $x$-quantile is $p_x=[1-(1-x{)}^{1/m}{]}^{1/w}$. For fixed $0<x<1$,Thus the fixed-error window has order $1/\log n$. For small fixed error the leading coefficient grows with $\log (1/\epsilon )$, so the general Friedgut-Kalai sharp threshold theorem also has the correct error dependence up to absolute constants.

For an input $x$, count the largest family of pairwise disjoint nonempty sets of coordinates such that flipping each set individually changes the Boolean function value. Maximizing over inputs gives block sensitivity. Sensitive sets need not be contiguous and need not consist of single bits. The standard bounded-error quantum query complexity lower bound is $\Omega (\sqrt{\mathrm{bs}(f)})$. A certificate for $f(x)$ meets every sensitive set, so its size bounds their disjoint count.

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is a monotone function when $x_i\le y_i$ for every $i$ implies $f(x)\le f(y)$.

For $f:\{-1,1{\}}^n\to \mathbb{R}$, the characters ${\chi }_S(x)={\prod }_{i\in S}{x}_i$ form an orthonormal basis, and the Fourier-Walsh expansion is

On the finite Boolean hypercube, these coefficients are the Hadamard transform of the vector of function values, with expectation normalization.

Fourier weight is the squared Fourier-Walsh transform coefficient mass on specified levels or a specified family of subsets. Parseval's identity identifies the total weight with $\mathbb{E}|f{|}^2$, and the nonconstant weight with variance. A decision tree of depth at most $s$ has no weight above level $s$.

For a random restriction, first fix the live set $J$ and average over the unbiased assignment $a$ outside it. The coefficient at $U\subset J$ is ${\sum }_{B\subset J^c}\hat{f}(U\cup B){\chi }_B(a)$. Orthogonality eliminates cross terms in its squared expectation. Averaging over $J$ gives the displayed identity. The original Fourier weight is weighted by a binomial distribution survival probability, not simply preserved.

For independent coordinate flips at rate $1/2$, a Walsh character $w_A$ is an eigenfunction with eigenvalue $-|A|$. The generator is self-adjoint and negative semidefinite. Its Dirichlet form of a Markov chain is $-\mathbb{E}[fLf]=\frac{1}{4}{\sum }_i\mathbb{E}(f({\omega }^{(i)})-f(\omega ){)}^2$.

Global sign-even functions have zero coefficients on odd-size Walsh characters. Every nonconstant remaining character has generator eigenvalue at most $-2$, yielding the displayed improvement from gap one to gap two. Combining this with the convexity of a norm proves the sharp Rademacher second-moment inequality.

For $S\subseteq [n]$, the Walsh character on the Boolean hypercube is ${\chi }_S(x)={\prod }_{i\in S}{x}_i$, equivalently $(-1{)}^{{\sum }_{i\in S}{x}_i}$ in the zero-one convention.

Under the $p$-biased product measure ${\mu }_p$ on $\{-1,1{\}}^n$, the coordinates are independent random variables with $\mathbb{P}(x_i=-1)=p$ and $\mathbb{P}(x_i=1)=1-p$. Writing $\mu =1-2p$, $\sigma =2\sqrt{p(1-p)}$, and ${\varphi }_i=(x_i-\mu )/\sigma$, the products ${\varphi }_S={\prod }_{i\in S}{\varphi }_i$ form the $p$-biased Fourier basis.

The $p$-biased Fourier coefficient of $f$ at $S$ is ${\hat{f}}_p(S)={\mathbb{E}}_{{\mu }_p}[f{\varphi }_S]$.

On the unbiased cube, the discrete derivative isFor the p-biased product measure, the normalization factor is $\sigma /2$.

For the $\{-1,1\}$-valued convention on the unbiased Boolean hypercube, the influence of coordinate $i$ is ${\mathrm{Inf}}_i(f)=\Vert D_{i}f{\Vert }_2^2$, where $D_{i}f$ is the discrete derivative of a Boolean function. It equals the probability that flipping coordinate $i$ changes $f$. For the $\{0,1\}$-valued convention, the same flip probability is instead $4\Vert D_{i}f{\Vert }_2^2$, since a nonzero discrete derivative has magnitude $1/2$.

For a zero-one Boolean function, the flip-probability influence is ${\beta }_i=4{\sum }_{S\ni i}\hat{f}(S{)}^2$. Apply Beckner's inequality with noise parameter $\sqrt{\delta }$ to the discrete derivative of a Boolean function, whose nonzero magnitude is $1/2$. Its $L^{1+\delta }$ norm squared is ${\beta }_i^{2/(1+\delta )}/4$. Summing over coordinates gives the displayed weighted Fourier weight bound, a useful intermediate step in influence lower bounds.

The total influence isThis Fourier-Walsh transform identity uses $\{-1,1\}$-valued $f$ and the flip-probability convention for influence of a variable. For $\{0,1\}$-valued $f$, the right-hand side is multiplied by four. Indeed Parseval's identity applied to the discrete derivative of a Boolean function gives $\Vert D_{i}f{\Vert }_2^2={\sum }_{S\ni i}\hat{f}(S{)}^2$; sum over coordinates and apply the chosen normalization.

For the indicator $f$ of a monotone family under a p-biased product measure, the Margulis–Russo formula identifies the derivative of ${\mathbb{E}}_{{\mu }_p}f$ with the suitably normalized total influence of $f$.

A coordinate is pivotal for an increasing event in a configuration when changing only that coordinate changes whether the event occurs. Its pivotal probability is the coordinate's influence.

The noise operator averages $f(y)$ over a random $y$ correlated with $x$ by $\rho$. It acts diagonally on the Fourier-Walsh transform:

For $1<p\le q<\infty$ and $0\le \rho \le \sqrt{(p-1)/(q-1)}$, the noise operator on the Boolean hypercube satisfies $\Vert T_{\rho }f{\Vert }_q\le \Vert f{\Vert }_p$ for the uniform probability measure. In particular,Here $\hat{f}(S)$ are Fourier-Walsh transform coefficients. The endpoint $\rho =0$ follows by averaging. This hypercontractive inequality on the Boolean hypercube controls Fourier-Walsh transform coefficients of discrete derivatives of a Boolean function and is a principal ingredient in the Kahn-Kalai-Linial theorem.

For a subset of the unbiased Boolean hypercube of density $\alpha$, use normalized Fourier-Walsh transform coefficients. Applying Beckner's inequality with $\rho =1/\sqrt{3}$ gives $\Vert T_{\rho }{1}_A{\Vert }_2^2\le \Vert 1_A{\Vert }_{4/3}^2={\alpha }^{3/2}$. On levels at most two the weights ${\rho }^{2|S|}$ are at least $1/9$, giving the displayed bound. Parseval's identity gives total Fourier mass $\alpha$, so when $9\sqrt{\alpha }<1/2$ the higher levels contain strictly more than the lower levels.

The noise stability is

The linear Fourier weight is $W_1(f)={\sum }_{|S|=1}\hat{f}(S{)}^2$.

A $J$-junta is a function whose value depends only on coordinates indexed by $J$. A $k$-junta depends on at most $k$ coordinates.

If $f:\{-1,1{\}}^n\to \{-1,1\}$ satisfies $\Vert f^{\le k}{\Vert }_2^2\ge 1-\epsilon$, then it has a real-valued $J$-junta approximation $g$ with $\Vert f-g{\Vert }_2^2\le 2\epsilon$ and

For every $\epsilon >0$, a Boolean function $f$ has an $\exp (O(\mathbf{I}(f)/\epsilon ))$-junta approximation with squared $L^2$ error at most $2\epsilon$.

Every Boolean function of degree at most $k$ is a $k{2}^{k-1}$-junta.

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is $(\epsilon ,p,r)$-quasirandom when conditioning any set of at most $r$ coordinates to any values changes its ${\mu }_p$-expectation by at most $\epsilon$.

For every $\epsilon ,p,r,\delta$, there is $T$ such that every Boolean function has a set $J$ with $|J|\le T$ for which a ${\mu }_p$-random restriction on $J$ leaves an $(\epsilon ,p,r)$-quasirandom function with probability at least $1-\delta$.