PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (190)
Orphanage
Unclass'd (1)
Unproven (496)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] every proposition is equivalent to a proposition in DNF (Theorem)
Theorem 1   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

$\displaystyle V(f) = \{ X \in \{T,F\}^n \vert f(X) = T \} $
For every $ X \in \{T,F\}^n$, define $ L_i (X) \colon \{T,F\}^n \to \{T,F\}$ as follows:
$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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$.

$ \qedsymbol$



"every proposition is equivalent to a proposition in DNF" is owned by rspuzio.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: index, side, right hand side, disjunction, term, conjunction, arguments, number, mapping, truth function, equivalent, disjunctive normal form, proposition
There is 1 reference to this entry.

This is version 7 of every proposition is equivalent to a proposition in DNF, born on 2005-03-08, modified 2005-03-30.
Object id is 6853, canonical name is EveryPropositionIsEquivalentToAPropositionInDNF.
Accessed 1025 times total.

Classification:
AMS MSC: 03B05 (Mathematical logic and foundations :: General logic :: Classical propositional logic)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)