2. Disjunctive Normal Form

Disjunctive Normal Form

Literal

A literal is a propositional symbol or the negation of a propositional symbol.

For example, $p$ or $\neg p$ meanwhile $\neg \neg p$ or $p\vee q$ are not since literals may have at most one logical connective and it must be a negation.

Link to original

Disjunctive Normal Form

Disjunctive Normal Form (DNF) is when a formula: ?

• contains no connectives other than conjunction, disjunction and negation.
• only applies negation to propositional symbols (within literals)
• no disjunction appears in a sub-formula of a formula whose main connective is conjunction

Alternatively, you can see it as a disjunction of one or more formulae, each of which is a conjunction of one or more literals.

Link to original

Rewrite Rules

DNF Rewrite Rules

To obtain DNF, we can preform a series of transformations:

$$\begin{array}{rl}F\to G& \Rightarrow \neg F\vee G\\ F⟺G& \Rightarrow (F\to G)\vee (G\to F)\\ \neg (F\vee G)& \Rightarrow \neg F\wedge \neg G\\ \neg (F\wedge G)& \Rightarrow \neg F\vee \neg G\\ \neg \neg F& \Rightarrow F\\ F\wedge (G\vee H)& \Rightarrow (F\wedge G)\vee (F\wedge H)\\ (F\vee G)\wedge H& \Rightarrow (F\wedge H)\vee (G\wedge H)\end{array}$$Link to original

title: Example 1
Represent $P \land (P \rightarrow Q)$ in DNF.
 
$$
	\begin{aligned}
		P \land (P \rightarrow Q) &\Rightarrow P \land (\neg P \lor Q) \\
		&\Rightarrow (P \land \neg P) \lor (P \land Q) \\
		&\Rightarrow 0 \lor (P \land Q) \\
		&\Rightarrow P \land Q
	\end{aligned}
$$

Truth Table to DNF

Given the truth table for $(P\vee \neg Q)\wedge R$ with the models highlighted:

interpretation	$p$	$q$	$r$	$\neg q$	$p\vee (\neg q)$	$(p\vee (\neg q))\wedge r$
$v_0$	0	0	0	1	1	0
$v_1$	0	0	1	1	1	1
$v_2$	0	1	0	0	0	0
$v_3$	0	1	1	0	0	0
$v_4$	1	0	0	1	1	0
$v_5$	1	0	1	1	1	1
$v_6$	1	1	0	0	1	0
$v_7$	1	1	1	0	1	1

We can associate each propositional symbol $P_i$ and interpretation $v_j$ with the literal $P_i$ if $v_j$ makes $P_i$ true or $\neg P_i$ if $v_1$ makes $P_i$ false.

Hence we find that:

• $v_1$ is associated with $\neg P\wedge \neg Q\wedge R$
• $v_5$ is associated with $P\wedge \neg Q\wedge R$
• $v_7$ is associated with $P\wedge Q\wedge R$

So we can now combine these to find the DNF:

$$\begin{array}{rl}\text{DNF}& =(\neg P\wedge \neg Q\wedge R)\vee (P\wedge \neg Q\wedge R)\vee (P\wedge Q\wedge R)\\ & =(\neg Q\wedge R)\vee (P\wedge R)\end{array}$$

Special Cases

These apply to both DNF and CNF.

Any contradictory formula $F$ is equivalent to the single conjunction $P\wedge \neg P$, which can be abbreviated to $0$. Any tautology $F$ is equivalent to the single disjunction $P\vee \neg P$, which can be abbreviated to $1$.