This is a book about boolean functions, \begin{equation*} f : \{0,1\}^n \to \{0,1\}. \end{equation*} Here $f$ maps each length-$n$ binary vector, or string, into a single binary value, or bit. Boolean functions arise in many areas of computer science and mathematics. Here are some examples:
- In circuit design, a boolean function may represent the desired behaviour of a circuit with $n$ inputs and one output.
- In graph theory, one can identify $v$-vertex graphs $G$ with length-$\binom{v}{2}$ strings indicating which edges are present. Then $f$ may represent a property of such graphs; e.g., $f(G) = 1$ if and only if $G$ is connected.
- In extremal combinatorics, a boolean function $f$ can be identified with a “set system” $\mathcal{F}$ on $[n] = \{1, 2, \dots, n\}$, where sets $X \subseteq [n]$ are identified with their $0$-$1$ indicators and $X \in \mathcal{F}$ if and only if $f(X) = 1$.
- In coding theory, a boolean function might be the indicator function for the set of messages in a binary error-correcting code of length $n$.
- In learning theory, a boolean function may represent a “concept” with $n$ binary attributes.
- In social choice theory, a boolean function can be identified with a “voting rule” for an election with two candidates named $0$ and $1$.
We will be quite flexible about how bits are represented. Sometimes we will use $\mathsf{True}$ and $\mathsf{False}$; sometimes we will use $-1$ and $1$, thought of as real numbers. Other times we will use $0$ and $1$, and these might be thought of as real numbers, as elements of the field ${\mathbb F}_2$ of size $2$, or just as symbols. Most frequently we will use $-1$ and $1$, so a boolean function will look like \begin{equation*} f : \{-1,1\}^n \to \{-1,1\}. \end{equation*} But we won’t be dogmatic about the issue.
We refer to the domain of a boolean function, $\{-1,1\}^n$, as the Hamming cube (or hypercube, $n$-cube, boolean cube, or discrete cube). The name “Hamming cube” emphasizes that we are often interested in the Hamming distance between strings $x, y \in \{-1,1\}^n$, defined by \begin{equation*} \mathrm{Dist}(x,y) = \#\{i : x_i \neq y_i\}. \end{equation*} Here we’ve used notation that will arise constantly: $x$ denotes a bit string and $x_i$ denotes its $i$th coordinate.
Suppose we have a problem involving boolean functions with the following two characteristics:
- the Hamming distance is relevant;
- you are counting strings, or the uniform probability distribution on $\{-1,1\}^n$ is involved.
These are the hallmarks of a problem for which analysis of boolean functions may help. Roughly speaking, this means deriving information about boolean functions by analyzing their Fourier expansion.
Sorry if I’ve misunderstood, but in the second example at the top of the page you’ve written:
“…Then f may represent a property of such graphs; e.g., f(G)=1 if and only if f is connected.”
Should this not read: “if and only if G is connected.”?
Whoops — bit of a blunder to have an error in the first paragraph! Thanks, I fixed it.
linguistic error:
I think it should be:
in a binary error-correcting*
instead of an binary error-correcting
Thanks! Right on page 1, too