3. Reduction of expressions to normal form.

A typical example:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


$(x \vee ( y' \vee z)')' = x' \wedge (y' \vee z)'' = x' \wedge (y' \vee z)$ 		 (cmpl's inside)


$= (x' \wedge y') \vee (x' \wedge z)$		(distribute)


$= [(x' \wedge y') \wedge (z \vee z')] \vee [(x' \wedge z) \wedge(y \vee y')]$ 		(break into atoms)


$= (x' \wedge y' \wedge z) \vee (x' \wedge y' \wedge z') \vee (x' \wedge y \wedge z) \vee (x' \wedge y' \wedge z)$

Any repeated meet-terms should be deleted. The final result is a join of distinct meets, with each meet involving all variables, possibly complemented. These meets correspond to the atoms in a free Boolean algebra, or equivalently, to the ``puzzle pieces'' in its Venn diagram.

Note. Determining whether an arbitrary Boolean expression reduces to 0 is the prototypical NP-complete problem. Many hard problems, such as the ``traveling salesman problem'', are equivalent to it in difficulty.