Disjunctive normal form

From Encyclopedia of Mathematics
Revision as of 20:53, 31 July 2012 by Jjg (talk | contribs) (TeX, MSC)
Jump to: navigation, search

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:
This article was adapted from an original article by S.K. Sobolev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article