Conjunctive Normal Form

Author

Eric W. Weisstein
December 16, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Logic/ConjunctiveNormalForm.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/ConjunctiveNormalForm.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

This code by Adam Strzebonski
December 16, 2004

ConjunctiveNormalForm[f_]:=Not[LogicalExpand[Not[f]]]//.{Not[a_Or]:>And@@(Not/@List@@a),Not[a_And]:>Or@@(Not/@List@@a)}

Examples

ConjunctiveNormalForm[a&&b||c&&d]

ConjunctiveNormalForm/@{
a,
Or[a,b]&&Or[!a,c],
Or[a,b,!a]&&Or[c,!b]&&Or[a,!c],
Or[a,b],
a&&Or[b,c]
}//ColumnForm//TraditionalForm