Namespaces
Variants
Actions

Difference between revisions of "Disjunctive normal form"

From Encyclopedia of Mathematics
Jump to: navigation, search
(TeX, MSC)
m (→‎References: isbn link)
 
(2 intermediate revisions by one other user not shown)
Line 2: Line 2:
 
{{MSC|03B05}}
 
{{MSC|03B05}}
  
A propositional formula is said to be in ''disjunctive normal form'' if it is of the form
+
A canonical form for a [[propositional formula]].  A formula is said to be in ''disjunctive normal form'' if it is of the form
 
\begin{equation}\label{eq1}
 
\begin{equation}\label{eq1}
 
   \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]]).
 +
 
 +
The form \ref{eq1} may be referred to as a disjunctive form: for a given set of $m$ propositional variables $p_1,\ldots,p_m$, the normal form is that in which each term $\wedge C_{ij}$ contains exactly $m$ terms $C_{ij}$, each being either $p_j$ or $\neg p_j$, and in which no term is repeated.  This form is then unique up to order.  The formula may be read as expressing the rows of the [[truth table]] for a propositional formula, in which each term describes one particular row of the table, corresponding to an assignment of truth values to the $p_j$, and the disjunctive form corresponds to the truth value assignments for which the formula takes the value "true".
 +
 
 +
====References====
 +
* Paul M. Cohn, ''Basic Algebra: Groups, Rings, and Fields'', Springer (2003) {{ISBN|1852335874}}

Latest revision as of 16:22, 18 November 2023

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

A canonical form for a propositional formula. A 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).

The form \ref{eq1} may be referred to as a disjunctive form: for a given set of $m$ propositional variables $p_1,\ldots,p_m$, the normal form is that in which each term $\wedge C_{ij}$ contains exactly $m$ terms $C_{ij}$, each being either $p_j$ or $\neg p_j$, and in which no term is repeated. This form is then unique up to order. The formula may be read as expressing the rows of the truth table for a propositional formula, in which each term describes one particular row of the table, corresponding to an assignment of truth values to the $p_j$, and the disjunctive form corresponds to the truth value assignments for which the formula takes the value "true".

References

  • Paul M. Cohn, Basic Algebra: Groups, Rings, and Fields, Springer (2003) ISBN 1852335874
How to Cite This Entry:
Disjunctive normal form. Encyclopedia of Mathematics. URL: http://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