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

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!

• Hint: Prove that any Boolean function $f$ of $n$ variables $x_1, \dots, x_n$ can be decomposed as $$f(x_1, \dots, x_n) = (x_n \wedge f(x_1, \dots, x_{n-1}, 1) \vee (\overline{x_n} \wedge f(x_1, \dots, x_{n-1}, 0)).$$ Then use induction. – Random Jack Jan 29 '15 at 10:32
• @RandomJack ...therefore, if I correctly understand, the set of all functions $\mathbb{B}^{n}\to\mathbb{B}$ are biunivocal with the set of couples of functions (whose number is $2^{2^{n-1}}$) $\mathbb{B}^{n-1}\to\mathbb{B}$, and this set has cardinality $(2^{2^{n-1}})^2=2^{2^n}$. Thank you very much! – Self-teaching worker Jan 29 '15 at 16:00

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$

• Thank you very much! What I don't understand is how the decomposition of $f$ is derived and what $k$ is... $\infty$ thanks again!!! – Self-teaching worker Jan 29 '15 at 16:01
• @Self-teachingDavide $k$ is a natural number in $\{0,1,\ldots,2^n-1\}$, that is used only to enumerate all the $n$-bit strings. The intuition is that if you memorize all the values of $f$, for all the possible inputs, then you can recreate $f$ from them. – dtldarek Jan 29 '15 at 17:55
• Therefore I see that the argument of $f(k_0,...,k_{n-1})$ for $0\le k\le 2^n -1$ spans all $\mathbb{B}^n$. But I still cannot see how $\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_{n-1})$ equates $f(x_0,...,x_{n-1})$ (and how we derive that all Boolean functions can be expressed with $\land,\lor,\lnot$, from this representation)... :-( Thank you so much again!!! – Self-teaching worker Jan 29 '15 at 18:27
• @Self-teachingDavide I've added some more explanations. – dtldarek Jan 29 '15 at 23:15