Namespaces
Variants
Actions

Difference between revisions of "Conjunctive normal form"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(LaTeX)
Line 1: Line 1:
 +
{{TEX|done}}
 +
 
A propositional formula of the form
 
A propositional formula of the form
 
+
\begin{equation}\label{eq1}
<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/c/c025/c025090/c0250901.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
  \bigwedge_{i=1}^n \bigvee_{j=1}^{m_i} \, C_{ij}
 
+
\end{equation}
where each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c0250902.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c0250903.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c0250904.png" />, is either an atomic formula (a variable or constant) or the negation of an atomic formula. The conjunctive normal form (*) is a tautology if and only if for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c0250905.png" /> one can find both formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c0250906.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c0250907.png" /> among the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c0250908.png" />, for some atomic formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c0250909.png" />. Given any propositional formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c02509010.png" />, one can construct a conjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c02509011.png" /> equivalent to it and containing the same variables and constants as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c02509012.png" />. This <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c02509013.png" /> is called the conjunctive normal form of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025090/c02509014.png" />.
+
$$
 +
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====
 
====Comments====
The dual of a conjunctive normal form is a [[Disjunctive normal form|disjunctive normal form]]. Both are also used in the theory of Boolean functions (cf. [[Boolean functions, normal forms of|Boolean functions, normal forms of]]).
+
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|Boolean functions, normal forms of]]).

Revision as of 09:27, 29 November 2014


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).

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