How to get CNF of propositional formula form DNF of its complement?

Question

Explain how to read off a CNF for propositional formula directly from a DNF from its complement.

I've managed to explain it in words, but can't write a rigorous proof of that. How to show this in mathematical notations? Thanks.

Answer 1

As Fizz pointed out in comments, we can use De Morgan's laws. I'll post it, since someone might need it.

Explanation: Let $P$ be propositional formula in question, $\neg P$ its complement, and $S$ denotes DNF of $\neg P$. $$S::=Q_1 \vee \cdots \vee Q_k, $$ where $Q_i,(1 \leq i \leq k)$ is AND-clause(s). Applying De Morgan's (distribution of $\neg$ over $\vee$) rule to S, we get $$\neg S::= Q_1' \wedge \cdots \wedge Q_k',$$ where $Q_i'::=\neg Q_i, (1\leq i \leq k). $ Since negating AND-clauses produce OR-clauses, we have AND of OR-clauses in $\neg S$, which is exactly CNF for P.
Thus we've showed how to get CNF of propositional formula from DNF of its complement: Negating DNF of complement gives CNF of proposition. df