Difference between revisions of "Conjunctive normal form"
(LaTeX) |
(MSC 03B05) |
||
| Line 1: | Line 1: | ||
| − | {{TEX|done}} | + | {{TEX|done}}{{MSC|03B05}} |
A propositional formula of the form | A propositional formula of the form | ||
| Line 5: | Line 5: | ||
\bigwedge_{i=1}^n \bigvee_{j=1}^{m_i} \, C_{ij} | \bigwedge_{i=1}^n \bigvee_{j=1}^{m_i} \, C_{ij} | ||
\end{equation} | \end{equation} | ||
| − | |||
where each $C_{ij}$, $i=1,\ldots,n$; $j = 1,\ldots,m_i$, is either an atomic formula (a variable or constant) or the negation of an atomic formula. The conjunctive normal form \ref{eq1} is a [[tautology]] if and only if for every $i$ one can find both formulas $p$ and $\neg p$ among the $C_{i1},\ldots,C_{im_i}$, for some atomic formula $p$. Given any propositional formula $A$, one can construct a conjunctive normal form $B$ equivalent to it and containing the same variables and constants as $A$. This $B$ is called the conjunctive normal form of $A$. | where each $C_{ij}$, $i=1,\ldots,n$; $j = 1,\ldots,m_i$, is either an atomic formula (a variable or constant) or the negation of an atomic formula. The conjunctive normal form \ref{eq1} is a [[tautology]] if and only if for every $i$ one can find both formulas $p$ and $\neg p$ among the $C_{i1},\ldots,C_{im_i}$, for some atomic formula $p$. Given any propositional formula $A$, one can construct a conjunctive normal form $B$ equivalent to it and containing the same variables and constants as $A$. This $B$ is called the conjunctive normal form of $A$. | ||
Latest revision as of 09:28, 29 November 2014
2020 Mathematics Subject Classification: Primary: 03B05 [MSN][ZBL]
A propositional formula of the form \begin{equation}\label{eq1} \bigwedge_{i=1}^n \bigvee_{j=1}^{m_i} \, C_{ij} \end{equation} where each $C_{ij}$, $i=1,\ldots,n$; $j = 1,\ldots,m_i$, is either an atomic formula (a variable or constant) or the negation of an atomic formula. The conjunctive normal form \ref{eq1} is a tautology if and only if for every $i$ one can find both formulas $p$ and $\neg p$ among the $C_{i1},\ldots,C_{im_i}$, for some atomic formula $p$. Given any propositional formula $A$, one can construct a conjunctive normal form $B$ equivalent to it and containing the same variables and constants as $A$. This $B$ is called the conjunctive normal form of $A$.
Comments
The dual of a conjunctive normal form is a disjunctive normal form. Both are also used in the theory of Boolean functions (cf. Boolean functions, normal forms of).
Conjunctive normal form. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Conjunctive_normal_form&oldid=35078