# 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):{\{T,F\}}^{n}\to \{T,F\}$ as follows:

$${L}_{i}(X)(Y)=\{\begin{array}{cc}\hfill {Y}_{i}\hfill & \hfill {X}_{i}=T\hfill \\ \hfill \mathrm{\neg}{Y}_{i}\hfill & \hfill {X}_{i}=F\hfill \end{array}$$ |

Then, we claim that

$$f(Y)=\underset{X\in V(f)}{\bigwedge}\underset{i=1}{\overset{n}{\bigvee}}{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)=\{\begin{array}{cc}\hfill {Y}_{i}\hfill & \hfill {Y}_{i}=T\hfill \\ \hfill \mathrm{\neg}{Y}_{i}\hfill & \hfill {Y}_{i}=F\hfill \end{array}$$ |

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}\ne {Y}_{i}$. For this choice of $i$, ${Y}_{i}=\mathrm{\neg}{X}_{i}$ Then we have

$${L}_{i}(X)(Y)=\{\begin{array}{cc}\hfill \mathrm{\neg}{X}_{i}\hfill & \hfill {X}_{i}=T\hfill \\ \hfill \mathrm{\neg}\mathrm{\neg}{X}_{i}\hfill & \hfill {X}_{i}=F\hfill \end{array}$$ |

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 |