CNFCNF2003-10-16 11:33:002004-03-09 13:43:19Definition% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands hereA propositional formula is a CNF formula, meaning Conjunctive Normal Form, if it is a conjunction of disjunction of literals (a literal is a propositional variable or its negation). Hence, a CNF is a formula of the form: $K_1 \wedge K_2 \wedge \ldots \wedge K_n$, where each $K_i$ is of the form $l_{i1} \vee l_{i2} \vee \ldots \vee l_{im}$ for literals $l_{ij}$ and some $m$ (which can vary for each $K_i$).
Example: $(x\vee y \vee \neg z) \wedge (y\vee \neg w \vee \neg u) \wedge (x\vee v)$.