$\land,\lor$ and $\lnot$ determinate a functionally complete basis

Question

I read that a Boolean algebra is defined by the binary operations $\land$ and $\lor$ and the unary operation $\lnot$ on a set such that $$\varphi\land(\psi\land \chi)=(\varphi\land \psi)\land \chi,\quad \varphi\lor(\psi\lor \chi)=(\varphi\lor \psi)\lor \chi$$ $$\varphi\land \psi=\psi\land \varphi,\quad \varphi\lor \psi=\psi\lor \varphi$$ $$\varphi\lor (\psi\land \chi) = (\varphi\lor \psi) \land (\varphi \lor \chi) ,\quad \varphi \land (\psi\lor \chi) = (\varphi \land \psi) \lor (\varphi \land \chi) $$ $$\varphi \lor (\varphi \land \psi) = \varphi,\quad \varphi\land (\varphi\lor \psi) = \varphi$$ $$\varphi\land 0 =0,\quad \varphi\lor1=1$$ $$\varphi\lor\lnot \varphi=0,\quad \varphi\land\lnot \varphi=1$$

The text states that $\land,\lor$ and $\lnot$ determinates a functionally complete basis in the sense that any function $\{0,1\}^n\to\{0,1\}$ can be expressed by using such operations, and I would like to understand a proof of that.

I have verified that the statement is true for $n=2$. Moreover, I know that the number of all the functions mapping $\{0,1\}^n$ into $\{0,1\}$ are $2^{2^n}$ and I supposed I could verify by induction that we can write all the functions $\{0,1\}^n\to\{0,1\}$ with $\land,\lor$ and $\lnot$, but I am not able to prove it to myself. Could anybody prove it here or give a link to some on line resource? I heartily thank you!

Answer 1

Let $\newcommand{\bbb}{\mathbb{B}}\bbb = \{0,1\}$, then you can express any function $f:\bbb^n\to \bbb$ as

$$f(x_0,x_1,\ldots,x_{n-1}) = \bigvee_{k=0}^{2^{n}-1} g(x_0,k_0)\land \ldots \land g(x_{n-1},k_{n-1}) \land f(k_0,k_1,\ldots,k_{n-1}) $$

where $k_i$ denotes the $i$-th bit of $k$ and

$$g(x_i,k_i) = (x_i \land k_i) \lor (\neg x_i \land \neg k_i) = \begin{cases}x_i & \text{ if }k_i = 1\\\neg x_i &\text{ if } k_i = 0\end{cases}$$

Too give you some intuition,

• $k \in \{0,1,\ldots,2^{n}-1\}$ is a short way of iterating over $\bbb^n$.
• $f(k_0, k_1, \ldots, k_{n-1})$ is a constant (either $0$ or $1$), because we know all the values of $k_i$.
• $g(x_i, k_i)$ effectively encodes "if $x_i$ is equal to $k_i$".
• $g(x_0, k_0)\land \ldots\land g(x_{n-1},k_{n-1})$ encodes "if the input is equal to some particular $k$" (remember that $k$ is an iterator, so we know it's value).
• If a function $h$ takes only a finite number of inputs $i_1, i_2, \ldots, i_m$ for which returns non-zero values $v_1, v_2, \ldots, v_m$, then \begin{align}h(x) &= [\![x=i_1]\!]\cdot v_1 + \ldots+ [\![x=i_m]\!]\cdot v_m\\ &= [\![x=i_1]\!]\cdot h(i_1) + \ldots+ [\![x=i_m]\!]\cdot h(i_m)\end{align} where $[\![b]\!]$ is equal to $1$ if $ b$ is true and $0$ otherwise.
• Similarly $$f(x_0,\ldots,x_{n-1}) = \begin{cases}f(0,\ldots,0)&\text{ for }x_0=0,\ldots,x_{n-1}=0\\\vdots\\f(1,\ldots,1)&\text{ for }x_0=1,\ldots,x_{n-1}=1\end{cases}$$ that is $$f(x_0,\ldots,x_{n-1})=[\![x_0=0,\ldots,x_{n-1}=0]\!]\cdot f(0,\ldots,0) + \ldots + [\![x_0=1,\ldots,x_{n-1}=1]\!]\cdot f(1,\ldots,1)$$ only that we cannot use $+$, $\cdot$ or $[\![\bullet]\!]$, so instead we use $\lor$, $\land$ and $g$.

I hope this helps $\ddot\smile$