# every proposition is equivalent to a proposition in DNF

###### Theorem.

Given any proposition, there exists a proposition in disjunctive normal form which is equivalent to that proposition.

###### Proof.

Any two propositions are equivalent if and only if they determine the same truth function. Therefore, if one can exhibit a mapping which assigns to a given truth function $f$ a proposition in disjunctive normal form such that the truth function of this proposition is $f$, the theorem follows immediately.

Let $n$ denote the number of arguments $f$ takes. Define

 $V(f)=\{X\in\{T,F\}^{n}|f(X)=T\}$

For every $X\in\{T,F\}^{n}$, define $L_{i}(X)\colon\{T,F\}^{n}\to\{T,F\}$ as follows:

 $L_{i}(X)(Y)=\left\{\begin{matrix}Y_{i}&X_{i}=T\cr\neg Y_{i}&X_{i}=F\end{matrix% }\right.$

Then, we claim that

 $f(Y)=\bigwedge_{X\in V(f)}\bigvee_{i=1}^{n}L_{i}(X)(Y)$

On the one hand, suppose that $f(Y)=T$ for a certain $Y\in\{T,F\}^{n}$. By definition of $V(f)$, we have $Y\in V(f)$. By definition of $L_{i}$, we have

 $L_{i}(Y)(Y)=\left\{\begin{matrix}Y_{i}&Y_{i}=T\cr\neg Y_{i}&Y_{i}=F\end{matrix% }\right.$

In either case, $L_{i}(Y)(Y)=T$. Since a conjunction equals $T$ if and only if each term of the conjunction equals $T$, it follows that $\bigvee_{i=1}^{n}L_{i}(Y)(Y)=T$. Finally, since a disjunction equals $T$ if and only if there exists a term which equals $T$, it follows the right hand side equals equals $T$ when the left-hand side equals $T$.

On the one hand, suppose that $f(Y)=F$ for a certain $Y\in\{T,F\}^{n}$. Let $X$ be any element of $V(f)$. Since $Y\notin V(f)$, there must exist an index $i$ such that $X_{i}\neq Y_{i}$. For this choice of $i$, $Y_{i}=\neg X_{i}$ Then we have

 $L_{i}(X)(Y)=\left\{\begin{matrix}\neg X_{i}&X_{i}=T\cr\neg\neg X_{i}&X_{i}=F% \end{matrix}\right.$

In either case, $L_{i}(X)(Y)=F$. Since a conjunction equals $F$ if and only if there exists a term which evaluates to $F$, it follows that $\bigvee_{i=1}^{n}L_{i}(X)(Y)=F$ for all $X\in V(f)$. Since a disjunction equals $F$ if and only if each term of the conjunction equals $F$, it follows that the right hand side equals equals $F$ when the left-hand side equals $F$.

Title every proposition is equivalent to a proposition in DNF EveryPropositionIsEquivalentToAPropositionInDNF 2013-03-22 15:06:58 2013-03-22 15:06:58 rspuzio (6075) rspuzio (6075) 10 rspuzio (6075) Theorem msc 03B05