2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Apass.Jack Jul 13 at 15:18
  • $\begingroup$ @Apass.Jack I have edited the question so that hopefully a factor is more clear. $\endgroup$ – Ben Crossley Jul 14 at 11:52
  • $\begingroup$ @Apass.Jack Yes, both of those can be considered factors. $\endgroup$ – Ben Crossley Jul 14 at 11:54
2
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Jul 15 at 19:53
  • $\begingroup$ @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. $\endgroup$ – chi Jul 15 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.