# 3-CNF to “independent form”

Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($$\wedge$$). Any combination of operations is allowed, though the fewer operations used the better.

$$\left((a \rightarrow b ) \downarrow b \right) \wedge \left(c \vee d\right) \wedge \left( \left(e \leftarrow f\right) \vee f \right) \tag{IND}$$

This would be valid because all instances of each variable exist in only 1 of the "factors" even if it appears in that factor multiple times.

$$\left((a \rightarrow b ) \downarrow b \right) \wedge \left(a \vee b\right)$$ This would be invalid because the $$a$$ (or the $$b$$) appears in multiple AND "factors"

I have called this (IND) because each of the factors is independent of each other. I'm mainly interested in a way to convert 3-CNF to (IND), if it is possible.

Edit for clarification:

Consider $$\left( a \vee b \vee c\right) \wedge \left(a \vee d \vee e \right)$$. The $$a$$ appears on both sides of the $$\wedge$$ I would like to convert it into format: $$f(a,b,c) \wedge g(d,e)$$ where $$f(a,b,c)$$ and $$g(d,e)$$ can use any operations.

Similarly

Given $$\left( a \vee b \vee c\right) \wedge \left(a \vee b \vee d \right)$$ I would like the $$a$$ and $$b$$ to be on the same side of the $$\wedge$$. It doesn't matter how they are separated, or if any of the other variables move. All that matters is that each instance of a variable appears in only 1 "factor"

$$\underbrace{\left( a \vee b \vee c\right)}_{factor} \wedge \underbrace{\left(d \vee e \vee f \right)}_{factor} \wedge \underbrace{\left(g \vee h \vee i \right)}_{factor}$$

• What is a "factor"? Can $(a\downarrow a)\downarrow (b\downarrow b)$ be considered a factor? Can $(a\downarrow b)\downarrow (a\downarrow b)$ be considered a factor? – John L. Jul 13 '19 at 15:18
• @Apass.Jack I have edited the question so that hopefully a factor is more clear. – Ben Crossley Jul 14 '19 at 11:52
• @Apass.Jack Yes, both of those can be considered factors. – Ben Crossley Jul 14 '19 at 11:54

Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($$\land$$)

In general, it is impossible to separate variables in that way. Consider the formula $$a \leftrightarrow b$$, and assume it can be written in the form $$f(a) \land g(b)$$.

Up to logical equivalence, $$f(a)$$ must be either $$a$$ or $$\lnot a$$. Ditto for $$g(b)$$. We therefore have that $$f(a) \land g(b)$$ must be one of these formulas:

$$a\land b \qquad a\land \lnot b \qquad \lnot a\land b \qquad \lnot a\land \lnot b \qquad$$

However, none of the above ones is equivalent to $$a \leftrightarrow b$$.

(Well, to be pedantic, $$f(a)$$ and $$g(b)$$ could also be the constantly true or constantly false function. Those choices won't work either, obviously.)

• It is interesting or disappointing that OP said the universal gate $\downarrow$ can be used, which means one factor is enough to express any logic formula. – John L. Jul 15 '19 at 19:53
• @Apass.Jack Indeed. The one-factor option is quite underwhelming. And separating variables in impossible in general, so that trivial thing might even be the best one can do. – chi Jul 15 '19 at 21:48