Suppose we have a Boolean formula $\phi(X,Y)$ over the sets of Boolean variables $X$ and $Y$, representing a binary relation. There are in general many tuples in this relation.

Is there a way to augment the formula to a $\phi'(X,Y,Z)$ such that the extra variables from $Z$ act as a primary key? More precisely, we want that any satisfying assignment $\nu$ for $\phi'$ also satisfies $\phi$ when restricted to the original variables, and for any two assignments $\nu$ and $\nu'$ for $\phi'$, $\nu(Z)=\nu'(Z)$ implies that $\nu(X,Y)=\nu'(X,Y)$ (with some notation abuse, forgive me).

The obvious way would be to enumerate all the assignments. For example, for a formula $x\lor y$, which has 3 assignments, one may end up with:

\begin{equation} (z_1\lor z_0) \land (z_1\land z_0 \to x \land y) \land (z_1 \land \neg z_0 \to x \land \neg y) \land (\neg z_1 \land z_0 \to \neg x\land y) \end{equation}

But this is of course exponential and useless. Is there any hope to do better? Am I missing something obvious?

  • 4
    $\begingroup$ What about $\phi(X,Y)\wedge (Z_0=X)\wedge (Z_1=Y)$? $\endgroup$
    – Wei Zhan
    Nov 1 at 23:56
  • $\begingroup$ When you write "any assignment $\nu$ for $\phi'$", do you actually mean "any assignment $\nu$ that satisfies $\phi'$"? $\endgroup$
    – D.W.
    Nov 2 at 6:08
  • $\begingroup$ Hi, yes, of course. I've edited the question. $\endgroup$
    – gigabytes
    Nov 2 at 10:01


Your Answer

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