0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Have a look at this related answer. $\endgroup$
    – Axel Kemper
    Commented Apr 3, 2021 at 12:31
  • 1
    $\begingroup$ Hint: apply De Morgan... what happens? (The linked q isn't actually about this.) $\endgroup$
    – got trolled too much this week
    Commented Apr 3, 2021 at 12:47

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.