= Solution
Two <propositional formulas> are <logically equivalent> if every <Boolean valuation> gives them the same <truth value>. A <disjunctive normal form> is a <logical disjunction> of <logical conjunctions> of <literals>, with a <literal> being a <propositional variable> or its <negation>.
Let $p_1,\ldots,p_n$ include all <propositional variables> appearing in $\phi$. For each <Boolean valuation> $s\in\{T,F\}^n$, put
$$
M_s=\bigwedge_{j=1}^n L_{s,j},\qquad
L_{s,j}=\begin{cases}p_j&s_j=T,\\\neg p_j&s_j=F.\end{cases}
$$
The <minterm> $M_s$ is true exactly for <Boolean valuations> whose restrictions to these <propositional variables> are $s$. Consequently
$$
\boxed{\phi\equiv\bigvee_{s:\,\widetilde s(\phi)=T}M_s.}
$$
Indeed, an <Boolean valuation> making $\phi$ true makes its own <minterm> true, while a true <minterm> in the displayed <logical disjunction> certifies the truth of $\phi$. There are only finitely many <Boolean valuations>, so this is a finite <disjunctive normal form>. If there are no satisfying <Boolean valuations>, use $p\wedge\neg p$ for any <propositional variable> $p$; this is a <disjunctive normal form> for falsity without needing an empty <logical disjunction> convention.
Back to article page
