# Making primary keys explicit in a Boolean relation

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?

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