Consider a $f(\bar{x^n}) \in \mathscr{P}(n) $ (all boolean functions of $n$ variables). Consider $SB = \{\&, \vee, \lnot \}$ and $CB = \{\&, \lnot\}$, $DB = \{\vee,\lnot \}$.
Let's consider a schematic representation of boolean function, i.e. sequence of $g \in CB$ : all of them has two entries and one exit (so it's a scheme of boolean elements). We call $L_{CB}(f) -$ minimal number of elements in $CB$ to realize $f$.
I didn't find a literature about that, so I'll try to explain. Let's consider $L_{SB}(x \oplus y) = 4$, because it's not hard to draw a scheme: $1) z_1 = x \&y$, $2)z_2 = x \vee y$, $3) z_3 = \lnot z_1$, $4) z_4 = z_3 \& z_2$. So we may represent it like $4$ elements.
According to Ewan's comment $L_{CB}(x \vee y) \le 2L_{SB}(x \vee y) + 2=2+2 =4$, because $L_{SB}(x \vee y) = 1$ (we need just a $\vee$-element). And it's easy to see that $x \vee y = \overline{\bar{x} \& \bar{y}}$ - we need $3$ negation and one conjuction.
Now we want to prove that : $L_{CB} \le 2 L_{SB} + n$ and $L_{DB} \le 2L_{SB} + n$.
I tried to read it somewhere , but can't find it anywhere.
I've tried to show it using induction and Shennon's decomposition $f(x_{1} \dots x_{n}) = x_{n} f(x_1 \dots x_{n-1},1) \vee \bar{x_{n}} f(x_{1} \dots x_{n-1},0)$. But that's doesn't give me the statements. Any hints or links?
The formulas can (syntactically) be seen as rooted directed DAGs, where the leaves are the variables $x_1, \ldots, x_n$, and each non-leaf node is labelled by a logical operation in the corresponding language (or, similarly, the result of the operation).
Thus, the tree of the formula $\overline{a \wedge (\overline{b} \vee c)}$ is has thus $7$ nodes (I can’t draw it, please imagine it):
Three leaves $A,B,C$.
Two nodes named $1$ and $4$, labelled with $\lnot$.
One node $2$ labelled with $\vee$.
One node $3$ labelled with $\wedge$.
$ $
$1$ is the parent node of $B$ only.
$2$ is the parent node of $1$ and $C$.
$3$ is the parent node of $A$ and $2$.
$4$ is the parent node of $3$.
The statement can be rephrased (for instance) as: let $f$ be a formula corresponding to a tree with $d$ non-leaf nodes, labelled in $SB$. Then there exists a formula $g$ corresponding to a tree labelled in $CB$ with $\leq 2d+n$ not-leaf nodes such that $f$ and $g$ are logically equivalent.
The first thing coming to mind with this formalism is to reason by induction over the height of the DAG (ie the maximal distance from the root (=final result) to the variables) representing $f$.
The initializations are easy ($f$ is a variable).
If $f= \lnot f_1$, or $f=f_1 \wedge f_2$, we can simply transform $f_1$ (and if necessary $f_2$) by induction hypothesis and add the relevant operation and it works.
However, if $f=f_1 \vee f_2$, then the natural de Morgan equivalence gives $f=\overline{\overline{f_1} \wedge \overline{f_2}}$, and by directly using the induction hypothesis we need to add four gates (from one) to the modified graphs of $f_1$ and $f_2$.
This suggests that the “induction-provable formula” is $L_{CB} \leq 3L_{SB}+n$. So we’re going to need to find something smarter.
Consider a formula $f$ and the associated DAG $\Gamma$ labelled in $SB$ with $d$ non-leaf nodes.
Define $\Gamma’$ as a copy of $\Gamma$ except that all the leaves represent $\overline{x_i}$, and that the $\vee$ and the $\wedge$ are exchanged (morally, $\Gamma’$ computes the negation of $f$ from the bottom up).
Let then $\Gamma_0$ be the following rooted DAG with labels in $CB$:
1) its nodes are the reunion of the nodes of $\Gamma$ and $\Gamma’$
2) its leaves are the leaves of $\Gamma$ (thus it has $2d+n$ non-leaves)
3) each leaf of $\Gamma’$, corresponding to some $\overline{x_i}$, is labelled in $\Gamma_0$ by $\lnot$, and is a parent of the node of $\Gamma$ corresponding to $x_i$.
4) If $x$ is a nonleaf node of $\Gamma$ or $\Gamma’$ labelled by $\lnot$, it has in $\Gamma_0$ the same label and the same child node.
5) If $x$ is a nonleaf node in $\Gamma$ with label $\wedge$, and $x’$ is the corresponding node in $\Gamma’$ (thus labelled in $\Gamma’$ with $\vee$), then $x$ has the same label and child nodes in $\Gamma_0$ as in $\Gamma$; $x’$ is labelled in $\Gamma_0$ by $\lnot$ and its child node in $\Gamma$ is $x$.
6) Same as 5) if $x$ is labelled $\vee$ instead, except that it is $x’$ that keeps its label and children while $x$ becomes labelled with $\lnot$ and a parent of $x’$.
7) the root of $\Gamma_0$ is the root of $\Gamma$.
By construction, $\Gamma_0$ represents a formula logically equivalent to $f$, by with only $2d+n$ logical operations, all from $CB$.
Of course, a similar construction works with $DB$ instead of $CB$.