## You are here

Homeevery proposition is equivalent to a proposition in DNF

## Primary tabs

# 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$.

∎

## Mathematics Subject Classification

03B05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections