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
Canonical name	EveryPropositionIsEquivalentToAPropositionInDNF
Date of creation	2013-03-22 15:06:58
Last modified on	2013-03-22 15:06:58
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	10
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 03B05