Convert conjunctive normal form to equivalent boolean formula with only NAND gates

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NAND gates with fan-in 2, without introducing any new dummy boolean variables. I'm wondering how much this will increase the size of the formula. If $\varphi$ has size $n$, how large does the resulting formula need to be? Can I convert $\varphi$ to an equivalent formula with only NAND gates that has size $O(n)$? If $O(n)$ isn't achievable, what's the best that is?

• Let's start by trying some simple examples. Suppose $\varphi(x_1,\dots,x_n) = x_1 \land \dots \land x_n$. Is there a short equivalent formula using only NANDs with fan-in 2? – D.W. Aug 6 '17 at 17:06
• I will have to think about that. How in comments, can I encode the special unicode symbols? Why it shows &and;? – Farewell Stack Exchange Aug 6 '17 at 17:35
• You can use LaTeX to typeset mathematics in a more readable way. See here for a short introduction. – D.W. Aug 6 '17 at 18:03
• Let me try: $\land$. Yes it works. I had to think about that myself. Well back to question: $x1 \land ... \land xn = x1 \land (x2 \land (x3 \land (... \land (xn-1 \land xn))))$ How do I do subscript? $x_1$ Well that doesn't work. I did it. – Farewell Stack Exchange Aug 6 '17 at 18:12

Yes, it can be converted to such a formula of size $O(n)$ (i.e., only a constant-factor increase in formula size). The conversion simply recursively applies the following rules:

\begin{align*} \neg a &\equiv NAND(a,\text{True})\\ a \lor b &\equiv NAND(\neg a, \neg b)\\ a \land b &\equiv \neg NAND(a,b) \end{align*}

It is easy to check that the resulting formula has linear size.

For instance, the clause $x_1 \lor \neg x_2 \lor \neg x_3$ represents $(x_1 \lor \neg x_2) \lor \neg x_3$, so applying the above rules we obtain the boolean formula

$$NAND(NAND(NAND(NAND(x_1,\text{True}),x_2),\text{True}),x_3).$$

In this way, each clause can be converted to a boolean formula of size $O(1)$. All that remains is to convert the conjunction of these clauses, and that can be done by expressing $c_1 \land \cdots \land c_m$ as $((c_1 \land c_2) \land \cdots) \land c_m$ and then applying the rule for $a \land b$ repeatedly.

• And having $\lnot$ and $\top$ in the formula? But NAND is functional complete, so the boolean formula can be expressed only with NANDs, so neither $\lnot$ nor $\top$ are needed. – Farewell Stack Exchange Aug 6 '17 at 18:54
• @ErezZrihen, the formula produced by my method does not have any instances of $\neg$ -- they all get eliminated by the first rule I listed. The definition of a boolean formula that I'm used to allows appearances of $\top$ (True) and $\bot$ (False). If you don't want to allow that, it'd be nice to specify that in the question. In any case, it's not hard to modify this construction to avoid occurrences of "True". I'll let you work out how. Hint: try to find a formula $\psi$ that has only NAND gates, and always evaluates to True. It's not hard. – D.W. Aug 6 '17 at 18:59
• Remember that $\lnot x = NAND(x,x)$, so $x \land y = NAND(NAND(x,y),NAND(x,y))$ and $x \lor y = NAND(NAND(x,x),NAND(y,y))$ – Farewell Stack Exchange Aug 6 '17 at 19:01
• I am aware that $\neg x = NAND(x,x)$. I'm not sure what your point is, though. That's not the construction I suggested. (As a fun exercise to help you understand my answer, try replacing my first rule with $\neg a \equiv NAND(a,a)$, and then see if you can tell whether the same conclusions apply to that variant.) – D.W. Aug 6 '17 at 19:02
• Good that you are aware of this. Thank you for your answer anyway. – Farewell Stack Exchange Aug 6 '17 at 22:40