# what is the smallest 3-CNF possible that enforces the boolean expression: a = b + c?

What is the smallest 3-CNF system of equations possible that enforces the boolean expression: a = b + c for boolean variables a, b, c?

'Smallest' can be defined as: (1) Number of 3 CNF clauses. (2) Number of new variables introduced in the clauses.

We are interested in both cases.

• What do you mean by $+$? XOR or disjunction? Jan 13 at 11:41
• disjunction.... Jan 13 at 12:15

To begin with, note that $$b+c$$ can be expressed as the disjunction $$b\lor c$$. To enforce equation, you need to express "$$a$$ iff $$(b\lor c)$$", and that can be encoded as the following CNF formula: $$\phi = (\neg a \lor b \lor c) \wedge ((\neg b \wedge \neg c) \lor a)$$

Indeed, I used the fact that $$A\to B \equiv \neg A \lor B$$ and applied that twice. $$\phi$$ is not in CNF form, but you can simplify it to: $$\phi = (\neg a \lor b \lor c) \wedge (\neg b \lor a) \wedge(\neg c \lor a)$$

Note that $$\phi$$ can be read as "c implies a, and b implies a, and a implies at least one of b or c". Can you prove that it is minimal?

• aha. I think this works fine! thanks a lot. Jan 13 at 11:17