0

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

Ordev Agens
  • 127
  • If $p = x_{1}x_{2}x_{3}x_{4}x_{5}$, what would you want $c(p)$ to be? – Nika Jan 05 '20 at 22:30
  • For this explicit case any value will be fine. I'm interested in cases where $p$ is a product of 1 to 4 variables. Although I'm leaning towards that expected formula doesn't exist. – Ordev Agens Jan 05 '20 at 23:24

1 Answers1

1

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

Axel Kemper
  • 4,943