Question

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}$

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top