DNFDNF2004-03-09 13:43:322004-03-09 13:43:32Definition% 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 DNF formula, meaning Disjunctive Normal Form, if it is a disjunction of conjunctions of literals (a literal is a propositional variable or its negation). Hence, a DNF is a formula of the form: $K_1 \vee K_2 \vee \ldots \vee K_n$, where each $K_i$ is of the form $l_{i1} \wedge l_{i2} \wedge \ldots \wedge l_{im}$ for literals $l_{ij}$ and some $m$ which can vary for each $K_i$.
Example: $(x\wedge y \wedge \neg z) \vee (y\wedge \neg w \wedge \neg u) \vee (x \wedge v)$.