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?
