Normal Forms (DNF, CNF)

Math for CS · Axiom Academy

Standardized representations of Boolean expressions and the SAT problem Any Boolean expression can be written in many equivalent ways. Normal forms are standardized formats that make expressions easier to analyze, compare, and process algorithmically. Two forms dominate computer science: CNF and DNF. Structure: (l_1 l_2 ) (l_3 l_4 ) Each clause is an "or-clause." The entire expression is true only when every clause is satisfied. Each term is an "and-term." The expression is true when at least one term is fully satisfied. Follow these steps to convert any expression: Eliminate implications: Replace p q with p q Push negations inward: Use De Morgan's laws and double negation until only applies to individual variables Distribute: For CNF, distribute over . For DNF, distribute over . SAT was the first problem proven NP-complete (Cook-Levin theorem, 1971). This means: No known polynomial-time algorithm solves all SAT instances Every problem in NP can be reduced to SAT If you could solve SAT efficiently, you could solve thousands of hard problems efficiently 3-SAT restricts each clause to exactly 3 literals. Even this restricted version is NP-complete. CNF = AND of ORs; DNF = OR of ANDs. Every Boolean expression has both forms. Convert using: eliminate implications, push negations inward, then distribute. SAT (satisfiability of CNF formulas) is the foundational NP-complete problem.

This is the written version of the interactive lesson above. See the full Math for CS course.