Scope, notation, and computational model
On this page · Permalink · Source line 1
13.1 Boolean and algebraic conventions
On this page · Permalink · Source line 3
A Boolean function is a map \(f:{\{0,1\}}^n\to{\{0,1\}}\). Unless a different field is explicitly stated, polynomials are the unique multilinear representatives in
Addition in this ring is XOR. Multiplication is AND. Boolean OR is written \(\lor\) and satisfies \(a\lor b=a+b+ab\). A statement \(h\le f\) is pointwise and means that \(h\) has no positive value at a negative input of \(f\).
The degree of a nonzero function is its multilinear algebraic degree. A nonzero constant has degree zero. For mathematical statements involving a constant-zero function we use \(\deg0=-\infty\); stored profile tables and Python helpers use their documented sentinels instead. Those implementation conventions do not change the inequalities.
For \(S\subseteq[n]\), write \(x^S=\prod_{i\in S}x_i\) and let \(1_S\) be the input with support \(S\). A minterm of a monotone function means an inclusion-minimal positive support, not an arbitrary positive input.
| Symbol | Meaning |
|---|---|
| \(C(f)\) | Minimum fan-in-two AND/OR/NOT gate count, allowing fan-out. |
| \(L(f)\) | Minimum total NOT/CNOT/Toffoli count of a restored implementation. |
| \(T\) | Number of Toffoli gates in a specified implementation. |
| \({T_{\mathrm{rest}}}(f)\) | Minimum such Toffoli count, allowing any finite zero workspace. |
| \(M(f)\) | Minimum AND count in an XOR–AND computation, with affine operations uncharged. |
| \(I_f\) | Boolean functions supported only on positive inputs of \(f\). |
| \(\alpha_1(f)\) | Minimum degree of one nonzero member of \(I_f\). |
| \(\beta_v(f)\) | Minimum degree of a member of \(I_f\) that is one at \(v\). |
| \(\beta(f),\beta^*(f)\) | Complete-cover degree and its affine-output optimization. |
| \([P]_2\) | Homogeneous degree-two component of the multilinear polynomial \(P\) in the specified coordinates. |