Consider set of boolean functions of 5 variables: $x_1, x_2, x_3, x_4, x_5$. Let $p = x_1x_3$ and define complement of $p$ as follows: $c(p) = x_2x_4x_5$.
Is it possible to construct a general formula which would provide a complement for arbitrary product using variables $x_1, \ldots, x_5$ and operations $\lor$, $\lnot$ (thus $\land$, $\oplus$)? For example, formula $\overline{x_1x_2x_3x_4x_5}\land p$ gives $p\land\overline{c(p)}$. I'm looking for general expression which would give $c(p)$.
Best Answer
Not a full answer, but an idea.
You could imagine your product function $p$ as:
$$p = (d_1 \lor x_1) \land (d_2 \lor x_2) \land (d_3 \lor x_3) \land (d_4 \lor x_4) \land (d_5 \lor x_5)$$
If parameter variable $d_i$ is $true$, variable $x_i$ is omitted or dropped from the product.
The corresponding complement $c(p)$:
$$c(p) = (d_1 x_1 \lor \neg d_1) \land (d_2 x_2 \lor \neg d_2) \land (d_3 x_3 \lor \neg d_3) \land (d_4 x_4 \lor \neg d_4) \land (d_5 x_5 \lor \neg d_5)$$
In other words:
To obtain a general formula for the complement, it would be sufficient to find five expressions for the drop variable parameters $d_i$.
Variable $x_i$ is present in product $p$, if $p$ is $false$ for all input combinations (= truth-table rows) with $x_i$ $false$. For $x_i$ $true$, there must be at least one combination where $p$ is $true$. It should be possible to translate these constraints into one expression per $d_i$.