0
$\begingroup$

I'm having a bit of a problem when trying to convert this CNF formula to DNF:

\begin{align} & \left(a_1 \vee \neg a_2 \vee \neg a_3 \vee ... \vee \neg a_K \right) \wedge \\ & \left(\neg a_1 \vee a_2 \vee \neg a_3 \vee ... \vee \neg a_K \right) \wedge \\ & \left(\neg a_1 \vee \neg a_2 \vee a_3 \vee ... \vee \neg a_K \right) \wedge \\ &... \\ & \left(\neg a_1 \vee \neg a_2 \vee \neg a_3 \vee ... \vee a_K \right) \end{align}

Even though this seems easy at first glance, I fail to see any pattern that would help me reduce this formula to a DNF form. Any help would be great !

$\endgroup$

1 Answer 1

2
$\begingroup$

I'll first take the dual of your statement by swapping all $\lor$'s with $\land$'s, and vice versa:

$$\left(a_1 \land \neg a_2 \land \neg a_3 \land ... \land \neg a_K \right) \lor$$

$$\left(\neg a_1 \land a_2 \land \neg a_3 \land ... \land \neg a_K \right) \lor$$

$$\left(\neg a_1 \land \neg a_2 \vee a_3 \land ... \land \neg a_K \right) \lor$$

$$...$$

$$\left(\neg a_1 \land \neg a_2 \land \neg a_3 \land ... \land a_K \right) $$

Why did I do this? It is because this statement has an easy to understand interpretation: it says that exactly one of the variables is true.

Now, that statement can be paraphrased as saying that you want at least one of the variables to be true, but never two.

In logic, that would be:

$$(a_1 \lor a_2 \lor .... \lor a_K) \land$$

$$\neg (a_1 \land a_2) \land \neg (a_1 \land a_3) \land .... \land \neg (a_1 \land a_K) \land \neg (a_2 \land a_3) \land .... \land (a_{K-1} \land a _K)$$

Applying DeMorgan:

$$(a_1 \lor a_2 \lor ... \lor a_K) \land$$

$$(\neg a_1 \lor \neg a_2) \land (\neg a_1 \lor \neg a_3) \land ... \land ( \neg a_1 \lor \neg a_K) \land (\neg a_2 \lor \neg a_3) \land ... \land (\neg a_{K-1} \lor \neg a_K)$$

OK ... but how does that relate to your statement? Well, note that if my starting statement (in DNF) is the dual of your starting statement (in CNF), then the dual of my statement converted into CNF will be the dual of the conversion of your statement into DNF. So, we just need to get the dual of my end result, and that will be the DNF of your original statement. In other words, the DNF of your statement is:

$$(a_1 \land a_2 \land ... \land a_K) \lor$$

$$(\neg a_1 \land \neg a_2) \lor (\neg a_1 \land \neg a_3) \lor ...\lor (\neg a_1 \land \neg a_K) \lor (\neg a_2 \land \neg a_3) .... \lor (\neg a_{K-1} \land \neg a_K)$$

$\endgroup$
2
  • $\begingroup$ I didn't even think to do it this way. Thank you very much for your fast and clean help, I can finally sleep in peace! $\endgroup$
    – Gogol31
    Commented Dec 3, 2019 at 3:21
  • $\begingroup$ @Gogol31 Great, glad I could help (and get you some sleep)! :) $\endgroup$
    – Bram28
    Commented Dec 3, 2019 at 3:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .