All boolean functions are computed by a depth 2 circuit

[evinda]

Hello! (Wave)

I am looking at the following exercise (pg. 92, ex. 11.1 , book:Gems of Theoretical Computer Science by Uwe Schöning ) :

Why can all boolean functions on $n$ variables be computed by a circuit with only 2 levels (a depth 2 circuit) ? What is the size ( number of gates ) of such a circuit in general?

Could you give me a hint how we could show that all boolean functions on $n$ variables be computed by a circuit with only 2 levels? Do we have to use induction? If so, how given that we do not have a specific form of an expression? (Thinking)

 

[I like Serena]

Hey evinda! (Smile)

I think that would be because every boolean expression can be written as a disjunction of conjunctions (or a conjunction of disjunctions).
That is an expression of the form $abc + abef + cef$ (or something like $(p+q+r)(q +s)(t + u)$).
So we can pick for instance a circuit that applies AND gates to selected inputs at the first level, and have a single OR gate at the second level. (Nerd)

 

[evinda]

I think that would be because every boolean expression can be written as a disjunction of conjunctions (or a conjunction of disjunctions).

How can this be proven? (Thinking)

Do we use the distributive laws for boolean algebra, namely the following?

$$x \lor (y \wedge z)=(x \wedge y) \lor (x \wedge z) \\ x \lor (y \wedge z)=(x \lor y) \wedge (x \lor z)$$

That is an expression of the form $abc + abef + cef$ (or something like $(p+q+r)(q +s)(t + u)$).

Why are these expressions disjunctions of conjunctions? How do we see this? (Worried)

 

[I like Serena]

How can this be proven? (Thinking)

Do we use the distributive laws for boolean algebra, namely the following?

$$x \lor (y \wedge z)=(x \wedge y) \lor (x \wedge z) \\ x \lor (y \wedge z)=(x \lor y) \wedge (x \lor z)$$

Why are these expressions disjunctions of conjunctions? How do we see this? (Worried)

Yes. See https://en.m.wikipedia.org/wiki/Disjunctive_normal_form for the explanation and the proof.

 

[Evgeny.Makarov]

It is important that in the book inputs of circuits are $x_1,\dots,x_n,\bar{x}_1,\ldots,\bar{x}_n$ (i.e., variables along with their negations) and that the AND and OR gates can have arbitrary positive number of inputs. And yes, two-level circuits can be manufactured from the disjunctive and conjunctive normal forms.

In fact, this question only makes sense if one specifies the available gates. If all functions of $n$ arguments are available as gates, then all circuits can have depth 1.

 

[evinda]

It is important that in the book inputs of circuits are $x_1,\dots,x_n,\bar{x}_1,\ldots,\bar{x}_n$ (i.e., variables along with their negations) and that the AND and OR gates can have arbitrary positive number of inputs. And yes, two-level circuits can be manufactured from the disjunctive and conjunctive normal forms.

Ok. So we use the fact that any boolean expression can be written as $$ \bigwedge\limits_{i\in \{ 1\ldots n \}} \ \bigvee \limits_{j\in \{ 1\ldots n\} } \ y_{ij} $$

where $y_{ij} \in \{ x_1,\dots,x_n,\bar{x}_1,\ldots,\bar{x}_n \}$, right? But how can we show this? (Thinking)

Or can't we show it for an arbitrary boolean expression, but just for each specific boolean expression seperately?

In fact, this question only makes sense if one specifies the available gates. If all functions of $n$ arguments are available as gates, then all circuits can have depth 1.

You mean that if a boolean expression contains only an OR-gate or only an AND-gate, then it is computed by a depth 1 circuit? So in our case we suppose that the boolean expression contains both the OR- and an AND-operation. Right?

 

[Evgeny.Makarov]

So we use the fact that any boolean expression can be written as $$ \bigwedge\limits_{i\in \{ 1\ldots n \}} \ \bigvee \limits_{j\in \{ 1\ldots n\} } \ y_{ij} $$

where $y_{ij} \in \{ x_1,\dots,x_n,\bar{x}_1,\ldots,\bar{x}_n \}$, right?

Not exactly. Let's denote $x^1$ to be $x$ and $x^0$ to be $\bar{x}$. The statement about the full disjunctive normal form says that for every boolean function $f(x_1,\dots,x_n)$ it is the case that
\[
f(x_1,\dots,x_n)=\bigvee_{(b_1,\dots,b_n)\in\{0,1\}^n} f(b_1,\dots,b_n)x_1^{b_1}\dots x_n^{b_n}
\]
This can be simplified to
\[
f(x_1,\dots,x_n)=\bigvee_{f(b_1,\dots,b_n)=1} x_1^{b_1}\dots x_n^{b_n}.
\]
The corresponding statement about the full conjunctive normal form says that
\[
f(x_1,\dots,x_n)=\bigwedge_{(b_1,\dots,b_n)\in\{0,1\}^n} (f(b_1,\dots,b_n)\lor x_1^{\bar{b}_1}\lor\dots\lor x_n^{\bar{b}_n})
\]
All these equalities can be understood by staring at them intently for 15 minutes and writing some examples. An elementary explanation of full disjunctive normal forms can be found, for example, in Rod Haggarty, Discrete Mathematics for Computing, 1st edition, section 9.1, and also probably in every textbook on discrete math or logic.

You mean that if a boolean expression contains only an OR-gate or only an AND-gate, then it is computed by a depth 1 circuit?

If a boolean expression contains a single disjunction and variables, then it is represented by a circuit with a single OR-gate. And in the last paragraph of post #5 I did not say anything about AND or OR-gates.

 

[evinda]

Not exactly. Let's denote $x^1$ to be $x$ and $x^0$ to be $\bar{x}$. The statement about the full disjunctive normal form says that for every boolean function $f(x_1,\dots,x_n)$ it is the case that
\[
f(x_1,\dots,x_n)=\bigvee_{(b_1,\dots,b_n)\in\{0,1\}^n} f(b_1,\dots,b_n)x_1^{b_1}\dots x_n^{b_n}
\]
This can be simplified to
\[
f(x_1,\dots,x_n)=\bigvee_{f(b_1,\dots,b_n)=1} x_1^{b_1}\dots x_n^{b_n}.
\]
The corresponding statement about the full conjunctive normal form says that
\[
f(x_1,\dots,x_n)=\bigwedge_{(b_1,\dots,b_n)\in\{0,1\}^n} (f(b_1,\dots,b_n)\lor x_1^{\bar{b}_1}\lor\dots\lor x_n^{\bar{b}_n})
\]

So if we have for example the boolean expression $(x_1 \wedge x_2) \lor x_3 $, its disjunctive normal form will be the following, right?

$$f(x_1, x_2, x_3)=x_1^0 x_2^0 x_3^1 \lor x_1^0 x_2^1 x_3^1 \lor x_1^1 x_2^1 x_3^1 \lor x_1^1 x_2^1 x_3^0 \lor x_1^1 x_2^0 x_3^1$$

And its conjunctive normal form will be this one:

\begin{align*}(f(0,0,1)\lor x_1^1 \lor x_2^1\lor x_3^0)&\land (f(0,1,1)\lor x_1^1 \lor x_2^0\lor x_3^0) \\ & \land (f(1,0,0)\lor x_1^0 \lor x_2^1\lor x_3^1) \\ & \land (f(0,1,0)\lor x_1^1 \lor x_2^0\lor x_3^1) \\ & \land (f(1,1,1)\lor x_1^0 \lor x_2^0\lor x_3^0) \\ & \land (f(1,1,0)\lor x_1^0 \lor x_2^0\lor x_3^1) \\ & \land (f(1,0,1)\lor x_1^0 \lor x_2^1\lor x_3^0) \\ & \land (f(0,0,0)\lor x_1^1 \lor x_2^1\lor x_3^1) = \\ =(1\lor x_1^1 \lor x_2^1\lor x_3^0)&\land (1\lor x_1^1 \lor x_2^0\lor x_3^0) \\ & \land (0\lor x_1^0 \lor x_2^1\lor x_3^1) \\ & \land (0\lor x_1^1 \lor x_2^0\lor x_3^1) \\ & \land (1\lor x_1^0 \lor x_2^0\lor x_3^0) \\ & \land (1\lor x_1^0 \lor x_2^0\lor x_3^1) \\ & \land (1\lor x_1^0 \lor x_2^1\lor x_3^0) \\ & \land (0\lor x_1^1 \lor x_2^1\lor x_3^1)\end{align*}

right?

If a boolean expression contains a single disjunction and variables, then it is represented by a circuit with a single OR-gate. And in the last paragraph of post #5 I did not say anything about AND or OR-gates.

Ah. What did you mean with this:

If all functions of $n$ arguments are available as gates

?

 

[Evgeny.Makarov]

So if we have for example the boolean expression $(x_1 \wedge x_2) \lor x_3 $, its disjunctive normal form will be the following, right?

$$f(x_1, x_2, x_3)=x_1^0 x_2^0 x_3^1 \lor x_1^0 x_2^1 x_3^1 \lor x_1^1 x_2^1 x_3^1 \lor x_1^1 x_2^1 x_3^0 \lor x_1^1 x_2^0 x_3^1$$

Yes, except the notation $x^b$ should be used only when $b$ is a variable or an expression, and $x^b$ cannot be reduced to $x$ or $\bar{x}$. When $b$ is 0 or 1, then $x^b$ should be written as $\bar{x}$ or $x$, respectively.

And its conjunctive normal form will be this one:

\begin{align*}(f(0,0,1)\lor x_1^1 \lor x_2^1\lor x_3^0)&\land (f(0,1,1)\lor x_1^1 \lor x_2^0\lor x_3^0) \\ & \land (f(1,0,0)\lor x_1^0 \lor x_2^1\lor x_3^1) \\ & \land (f(0,1,0)\lor x_1^1 \lor x_2^0\lor x_3^1) \\ & \land (f(1,1,1)\lor x_1^0 \lor x_2^0\lor x_3^0) \\ & \land (f(1,1,0)\lor x_1^0 \lor x_2^0\lor x_3^1) \\ & \land (f(1,0,1)\lor x_1^0 \lor x_2^1\lor x_3^0) \\ & \land (f(0,0,0)\lor x_1^1 \lor x_2^1\lor x_3^1) = \\ =(1\lor x_1^1 \lor x_2^1\lor x_3^0)&\land (1\lor x_1^1 \lor x_2^0\lor x_3^0) \\ & \land (0\lor x_1^0 \lor x_2^1\lor x_3^1) \\ & \land (0\lor x_1^1 \lor x_2^0\lor x_3^1) \\ & \land (1\lor x_1^0 \lor x_2^0\lor x_3^0) \\ & \land (1\lor x_1^0 \lor x_2^0\lor x_3^1) \\ & \land (1\lor x_1^0 \lor x_2^1\lor x_3^0) \\ & \land (0\lor x_1^1 \lor x_2^1\lor x_3^1)\end{align*}

First, enumeration of tuples with elements $0$ and $1$ should be done in the order of binary numbers: $(0,0,0)$, $(0,0,1)$, $(0,1,0)$, $(0,1,1)$, $(1,0,0)$, $(1,0,1)$, $(1,1,0)$, $(1,1,1)$. Second, disjunctions with 1 evaluate to 1 and can be eliminated from the conjunction. So the FCNF (full conjunctive normal form) is $(x_1\lor x_2\lor x_3)(x_1\lor\bar{x}_2\lor x_3)(\bar{x}_1\lor x_2\lor x_3)$. I recommend skipping $\land$ just like multiplication is skipped in arithmetic.

What did you mean with this: "If all functions of n arguments are available as gates"?

Well, "disjunction is available as a gate" is equivalent to "we have an OR-gate". Do you understand the difference between functions and gates, and what it means for a gate to realize, or implement, a function? I was saying that if we have gates realizing all functions, then every function is trivially realized by a one-gate circuit.

 

[evinda]

Yes, except the notation $x^b$ should be used only when $b$ is a variable or an expression, and $x^b$ cannot be reduced to $x$ or $\bar{x}$. When $b$ is 0 or 1, then $x^b$ should be written as $\bar{x}$ or $x$, respectively.

So, we write

$$f(x_1, x_2, x_3)=\bar{x_1} \bar{x_2} x_3 \lor \bar{x_1} x_2 x_3 \lor x_1 \bar{x_2} x_3 \lor x_1 x_2 \bar{x_3} \lor x_1 x_2 x_3$$

Right?

First, enumeration of tuples with elements $0$ and $1$ should be done in the order of binary numbers: $(0,0,0)$, $(0,0,1)$, $(0,1,0)$, $(0,1,1)$, $(1,0,0)$, $(1,0,1)$, $(1,1,0)$, $(1,1,1)$. Second, disjunctions with 1 evaluate to 1 and can be eliminated from the conjunction. So the FCNF (full conjunctive normal form) is $(x_1\lor x_2\lor x_3)(x_1\lor\bar{x}_2\lor x_3)(\bar{x}_1\lor x_2\lor x_3)$. I recommend skipping $\land$ just like multiplication is skipped in arithmetic.

Ok. (Nod)

Well, "disjunction is available as a gate" is equivalent to "we have an OR-gate". Do you understand the difference between functions and gates, and what it means for a gate to realize, or implement, a function? I was saying that if we have gates realizing all functions, then every function is trivially realized by a one-gate circuit.

You mean that in our case we consider only the AND- and OR-gates, but if we could also have a gate that contains any operations, and thus a whole function, then every function could be realized by such a one-gate circuit, right?

 

[Evgeny.Makarov]

So, we write

$$f(x_1, x_2, x_3)=\bar{x_1} \bar{x_2} x_3 \lor \bar{x_1} x_2 x_3 \lor x_1 \bar{x_2} x_3 \lor x_1 x_2 \bar{x_3} \lor x_1 x_2 x_3$$

Yes. It's better to type \bar{x}_1 than \bar{x_1}.

You mean that in our case we consider only the AND- and OR-gates, but if we could also have a gate that contains any operations, and thus a whole function, then every function could be realized by such a one-gate circuit, right?

Yes. So any question about the characteristics of a circuit implementing a function (the number of gates in such circuit, its depth, etc.) only makes sense when you specify the set of gates.

 

[evinda]

Yes. It's better to type \bar{x}_1 than \bar{x_1}.

Ok.

Yes. So any question about the characteristics of a circuit implementing a function (the number of gates in such circuit, its depth, etc.) only makes sense when you specify the set of gates.

Yes, in our case we only have OR- and AND-gates.

Why can all boolean functions on $n$ variables be computed by a circuit with only 2 levels (a depth 2 circuit) ?

So is the following a complete justification?Every boolean function $f(x_1,\dots,x_n)$ can be written as $$f(x_1,\dots,x_n)=\bigvee_{f(b_1,\dots,b_n)=1} x_1^{b_1}\dots x_n^{b_n}$$

So we see that every boolean expression is represented by a circuit that applies AND gates to selected inputs at the first level, and that have a single OR gate at the second level.

What is the size ( number of gates ) of such a circuit in general?

The number of gates of such a depth 2 circuit, when we write our expression in its disjunctive normal form, is the number of AND-gates plus one, the OR-gate. Can we find the precise number of gates? (Thinking)

 

[Evgeny.Makarov]

Every boolean function $f(x_1,\dots,x_n)$ can be written as $$f(x_1,\dots,x_n)=\bigvee_{f(b_1,\dots,b_n)=1} x_1^{b_1}\dots x_n^{b_n}$$

So we see that every boolean expression is represented by a circuit that applies AND gates to selected inputs at the first level, and that have a single OR gate at the second level.

I agree.

The number of gates of such a depth 2 circuit, when we write our expression in its disjunctive normal form, is the number of AND-gates plus one, the OR-gate.

Yes.

Can we find the precise number of gates?

It's easy to find an upper bound on the number of minterms (i.e., conjunctions of variables or their negations) in the disjunction. Note that this number coincides with the number of inputs on which the function returns 1. Boolean functions are often specified using truth tables, which list their values for each input tuple. Find the number of different input tuples (i.e., the number of rows in a truth table) of a function with $n$ arguments.

FDNF is unique for any given function, but it can often be reduced. But if you want to study something other than the upper bound on the number of gates, you have to give the precise problem statement first.

 

[evinda]

It's easy to find an upper bound on the number of minterms (i.e., conjunctions of variables or their negations) in the disjunction. Note that this number coincides with the number of inputs on which the function returns 1. Boolean functions are often specified using truth tables, which list their values for each input tuple. Find the number of different input tuples (i.e., the number of rows in a truth table) of a function with $n$ arguments.

At the worst case, we suppose that for all vectors $(x_1, \dots, x_n) \in \{0,1\}^n$ it holds that $f(x_1, \dots, x_n)=1$.

Since we have $2^n$ possible tuples that belong in $\{0,1\}^n$, we will have $2^n$ AND-gates, and so we will totally have $2^n+1$ gates. Right?

FDNF is unique for any given function, but it can often be reduced. But if you want to study something other than the upper bound on the number of gates, you have to give the precise problem statement first.

I see. We can only find the precise number of gates if we have a specific boolean expression.

 

[Evgeny.Makarov]

At the worst case, we suppose that for all vectors $(x_1, \dots, x_n) \in \{0,1\}^n$ it holds that $f(x_1, \dots, x_n)=1$.

Since we have $2^n$ possible tuples that belong in $\{0,1\}^n$, we will have $2^n$ AND-gates, and so we will totally have $2^n+1$ gates.

Yes.

We can only find the precise number of gates if we have a specific boolean expression.

There are various results about the asymptotic behavior of circuit complexity. For example, if all AND and OR gates take two inputs, then the number of gates sufficient for implementing every function of $n$ arguments is $\Theta(2^n/n)$.

 

[evinda]

There are various results about the asymptotic behavior of circuit complexity. For example, if all AND and OR gates take two inputs, then the number of gates sufficient for implementing every function of $n$ arguments is $\Theta(2^n/n)$.

For every boolean function $f(x_1,\dots,x_n)$ we have

$$f(x_1,\dots,x_n)=\bigvee_{f(b_1,\dots,b_n)=1} x_1^{b_1}\dots x_n^{b_n}$$

If we consider that all AND-gates take two inputs, then for all $(b_1, \dots, b_n) \in \{0,1\}^n$ such that $f(b_1, \dots, b_n)=1$ there will be two variables $i,j \in \{1, \dots, n \}$ such that $b_i=b_j=1$ and $b_k=0, \forall k \in \{1, \dots, n \}$ such that $k \neq i,j$.

There are $\binom{n}{2}$ such vectors $(b_1, \dots, b_n)$.

Does this help in order to find the number of gates in this case?

 

[Evgeny.Makarov]

If we consider that all AND-gates take two inputs, then for all $(b_1, \dots, b_n) \in \{0,1\}^n$ such that $f(b_1, \dots, b_n)=1$ there will be two variables $i,j \in \{1, \dots, n \}$ such that $b_i=b_j=1$ and $b_k=0, \forall k \in \{1, \dots, n \}$ such that $k \neq i,j$.

There are $\binom{n}{2}$ such vectors $(b_1, \dots, b_n)$.

Does this help in order to find the number of gates in this case?

Sorry, this makes no sense, even the question: you want to find the number of gates to implement which function? Different functions require different number of gates to implement them.

If the AND gates takes two inputs, this simply means that to join $n$ variables naively you need $n-1$ AND gates. If you break the variables in half, and those again in half and so on, then you need approximately $\log_2n$ AND gates.

You are also saying about variables being equal to 1 or 0, but it is not clear what interpretation you are talking about. An interpretation is a mapping from variables to $\{0,1\}$.

 

[evinda]

Different functions require different number of gates to implement them.

Yes, I understand.

If you break the variables in half, and those again in half and so on, then you need approximately $\log_2n$ AND gates.

In this case, are the gates in the following form?

View attachment 7018

If so, don't we have again $n-1$ AND-gates?

 

[I like Serena]

In this case, are the gates in the following form?

If so, don't we have again $n-1$ AND-gates?

Correct.
We need $n-1$ AND-gates.

It's the depth that is $\lceil \log_2 n\rceil$.

 

[Evgeny.Makarov]

If so, don't we have again $n-1$ AND-gates?

You are right. I made a mistake.

 

[evinda]

Ok, nice. Thank you both for your answers! (Smirk)