4
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Random Jack Jan 29 '15 at 10:32
  • $\begingroup$ @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! $\endgroup$ – Self-teaching worker Jan 29 '15 at 16:00
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thank you very much! What I don't understand is how the decomposition of $f$ is derived and what $k$ is... $\infty$ thanks again!!! $\endgroup$ – Self-teaching worker Jan 29 '15 at 16:01
  • 1
    $\begingroup$ @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. $\endgroup$ – dtldarek Jan 29 '15 at 17:55
  • $\begingroup$ 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!!! $\endgroup$ – Self-teaching worker Jan 29 '15 at 18:27
  • 1
    $\begingroup$ @Self-teachingDavide I've added some more explanations. $\endgroup$ – dtldarek Jan 29 '15 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.