Namespaces
Variants
Actions

Difference between revisions of "Disjunctive normal form"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX, MSC)
Line 1: Line 1:
A propositional formula of the form
+
{{TEX|done}}
 +
{{MSC|03B05}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333001.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
A propositional formula is said to be in ''disjunctive normal form'' if it is of the form
 
+
\begin{equation}\label{eq1}
where each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333002.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333003.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333004.png" />) is either a variable or the negation of a variable. The form (*) is realizable if and only if, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333005.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333006.png" /> do not contain both the formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333007.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333008.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d0333009.png" /> is any variable. For any propositional formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d03330010.png" /> it is possible to construct an equivalent disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d03330011.png" /> containing the same variables as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d03330012.png" />. Such a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d03330013.png" /> is then said to be the disjunctive normal form of the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033300/d03330014.png" />.
+
  \bigvee_{i=1}^n \;\bigwedge_{j=1}^{m_i} C_{ij} ,
 +
\end{equation}
 +
where each $C_{ij}$ ($1,\ldots,n$; $j=1,\ldots,m_i$) is either a variable or the negation of a variable. The form \ref{eq1} is realizable if and only if, for each $i$, $C_{i1},\ldots,C_{im_i}$ do not contain both the formulas $p$ and $\neg p$, where $p$ is any variable. For any propositional formula $A$ it is possible to construct an equivalent disjunctive normal form $B$ containing the same variables as $A$. Such a formula $B$ is then said to be ''the disjunctive normal form'' of the formula $A$.

Revision as of 22:53, 31 July 2012

2010 Mathematics Subject Classification: Primary: 03B05 [MSN][ZBL]

A propositional formula is said to be in disjunctive normal form if it is of the form \begin{equation}\label{eq1} \bigvee_{i=1}^n \;\bigwedge_{j=1}^{m_i} C_{ij} , \end{equation} where each $C_{ij}$ ($1,\ldots,n$; $j=1,\ldots,m_i$) is either a variable or the negation of a variable. The form \ref{eq1} is realizable if and only if, for each $i$, $C_{i1},\ldots,C_{im_i}$ do not contain both the formulas $p$ and $\neg p$, where $p$ is any variable. For any propositional formula $A$ it is possible to construct an equivalent disjunctive normal form $B$ containing the same variables as $A$. Such a formula $B$ is then said to be the disjunctive normal form of the formula $A$.

How to Cite This Entry:
Disjunctive normal form. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Disjunctive_normal_form&oldid=27312
This article was adapted from an original article by S.K. Sobolev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article