Namespaces
Variants
Actions

Difference between revisions of "Conjunctive normal form"

From Encyclopedia of Mathematics
Jump to: navigation, search
(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).

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