# Difference between revisions of "Disjunctive normal form"

(TeX, MSC) |
(Comment: The dual is a conjunctive normal form) |
||

Line 6: | Line 6: | ||

\bigvee_{i=1}^n \;\bigwedge_{j=1}^{m_i} C_{ij} , | \bigvee_{i=1}^n \;\bigwedge_{j=1}^{m_i} C_{ij} , | ||

\end{equation} | \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$. | + | 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 (is a [[tautology]]) 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$. |

+ | |||

+ | ====Comments==== | ||

+ | The dual of a disjunctive normal form is a [[conjunctive normal form]]. Both are also used in the theory of Boolean functions (cf. [[Boolean functions, normal forms of|Boolean functions, normal forms of]]). |

## Revision as of 11:28, 29 November 2014

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 (is a tautology) 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$.

#### Comments

The dual of a disjunctive normal form is a conjunctive normal form. Both are also used in the theory of Boolean functions (cf. Boolean functions, normal forms of).

**How to Cite This Entry:**

Disjunctive normal form.

*Encyclopedia of Mathematics.*URL: http://www.encyclopediaofmath.org/index.php?title=Disjunctive_normal_form&oldid=35079