Lesson 10: Normal forms: DNF, CNF, minterms, and maxterms (advanced, 15 min)

Any formula can be rewritten as an OR of AND-terms (DNF) or an AND of OR-clauses (CNF). This advanced lesson, about fifteen minutes, reads minterms and maxterms off a truth table, writes the Σm and ΠM forms, and shows why conversions have limits.

Level: advanced15 min9 claims in this lesson were confirmed by the exact checker at build time

Rewrite any formula as an OR of AND-terms or an AND of OR-clauses, read Σm and ΠM forms row by row, and see why conversions are bounded.

The first step defines literals, terms and clauses and shows both normal forms of A XOR B: the DNF (A AND NOT B) OR (NOT A AND B) and the CNF (A OR B) AND (NOT A OR NOT B). The second reads the TRUE rows of a table as minterms, so Σm(A, B, C; 3, 5, 6, 7) is the majority function (A AND B) OR (A AND C) OR (B AND C), with the first input as the most significant bit. The third reads the FALSE rows as maxterms, ΠM(A, B, C; 0, 1, 2, 4), the same function. The fourth converts with laws, eliminating arrows, pushing NOT inward and distributing, so (A AND B) OR C becomes (A OR C) AND (B OR C), and explains why distribution can blow up and why the converter has a bound.

Five of the lesson's claims are equivalences verified at build time, including both canonical forms of the majority function. The exercises ask for the DNF of A -> (B AND C), the CNF of (A AND B) OR C, the value of an indexed form on one row, and a CNF written out from ΠM(A, B; 0, 3).

The CNF and DNF converter in the tools section does the conversions with each law named, and the comparison pages on CNF versus DNF and on minterms versus maxterms show when each form is the shorter one.

Do this lesson interactively in the app

Steps

1. Literals, terms, and clauses

A literal is an input or its negation, such as A or NOT B.

- DNF (disjunctive normal form) is an OR of AND-terms of literals: (A AND NOT B) OR (NOT A AND B). - CNF (conjunctive normal form) is an AND of OR-clauses: (A OR B) AND (NOT A OR NOT B).

Both formulas are equivalent to A XOR B. Every formula has a DNF and a CNF.

parity := A XOR B · outputdnf := (A AND NOT B) OR (NOT A AND B) · outputcnf := (A OR B) AND (NOT A OR NOT B) · output

Literals, terms, and clauses
#	A	B	parity	dnf	cnf
0	FALSE	FALSE	FALSE	FALSE	FALSE
1	FALSE	TRUE	TRUE	TRUE	TRUE
2	TRUE	FALSE	TRUE	TRUE	TRUE
3	TRUE	TRUE	FALSE	FALSE	FALSE

Compare dnf and cnf with parity.

equivalent parity / dnf · holdsequivalent parity / cnf · holds

2. Minterms: one term per TRUE row

A minterm is an AND of all inputs, each plain or negated, that is TRUE on exactly one row. Its index is the row number, with the first input as the most significant bit: for A, B, C, minterm 5 is A AND NOT B AND C (binary 101).

Listing the TRUE rows gives the canonical DNF, written Σm(A, B, C; 3, 5, 6, 7). This is the majority function: TRUE when at least two inputs are.

majority := Σm(A, B, C; 3, 5, 6, 7) · outputexpanded := (A AND B) OR (A AND C) OR (B AND C) · output

Minterms: one term per TRUE row
#	A	B	C	majority	expanded
0	FALSE	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	FALSE	FALSE
2	FALSE	TRUE	FALSE	FALSE	FALSE
3	FALSE	TRUE	TRUE	TRUE	TRUE
4	TRUE	FALSE	FALSE	FALSE	FALSE
5	TRUE	FALSE	TRUE	TRUE	TRUE
6	TRUE	TRUE	FALSE	TRUE	TRUE
7	TRUE	TRUE	TRUE	TRUE	TRUE

Set A=TRUE, B=FALSE, C=TRUE (row 5) and look at majority.

equivalent majority / expanded · holds

3. Maxterms: one clause per FALSE row

A maxterm is an OR of all inputs that is FALSE on exactly one row. Maxterm 0 for A, B, C is A OR B OR C, false only when all three are FALSE.

Listing the FALSE rows gives the canonical CNF: ΠM(A, B, C; 0, 1, 2, 4) is the same majority function. Minterm and maxterm indices together cover every row exactly once.

majority := Σm(A, B, C; 3, 5, 6, 7) · outputmajority_pm := ΠM(A, B, C; 0, 1, 2, 4) · output

Maxterms: one clause per FALSE row
#	A	B	C	majority	majority_pm
0	FALSE	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	FALSE	FALSE
2	FALSE	TRUE	FALSE	FALSE	FALSE
3	FALSE	TRUE	TRUE	TRUE	TRUE
4	TRUE	FALSE	FALSE	FALSE	FALSE
5	TRUE	FALSE	TRUE	TRUE	TRUE
6	TRUE	TRUE	FALSE	TRUE	TRUE
7	TRUE	TRUE	TRUE	TRUE	TRUE

Compare majority_pm with majority.

equivalent majority / majority_pm · holds

4. Converting with laws, within limits

To reach CNF, eliminate -> and <->, push NOT inward (De Morgan), then distribute OR over AND: (A AND B) OR C becomes (A OR C) AND (B OR C).

Distribution can make formulas grow exponentially, so Tangibool bounds conversions (4,096 terms) and never labels a partial result as a complete normal form. Every completed conversion is checked for equivalence.

original := (A AND B) OR C · outputcnf := (A OR C) AND (B OR C) · output

Converting with laws, within limits
#	A	B	C	original	cnf
0	FALSE	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	TRUE	TRUE
2	FALSE	TRUE	FALSE	FALSE	FALSE
3	FALSE	TRUE	TRUE	TRUE	TRUE
4	TRUE	FALSE	FALSE	FALSE	FALSE
5	TRUE	FALSE	TRUE	TRUE	TRUE
6	TRUE	TRUE	FALSE	TRUE	TRUE
7	TRUE	TRUE	TRUE	TRUE	TRUE

Compare original with cnf.

equivalent original / cnf · holds

Exercises

Write A -> (B AND C) in disjunctive normal form (an OR of AND-terms). (write-equivalent)
Write (A AND B) OR C in conjunctive normal form (an AND of OR-clauses). (write-equivalent)
f := Σm(A, B, C; 1, 4, 6). What is f when A=TRUE, B=TRUE, C=FALSE? (predict-output)
Write ΠM(A, B; 0, 3) out as a CNF, one clause per maxterm. (write-equivalent)

Do this lesson interactively in the app

Questions

Is the canonical form the shortest?

Rarely. It has one term per TRUE row, so a function TRUE on half the rows of a four-variable table has eight terms. The Karnaugh map lesson is about making it shorter.

What is the limit on conversions?

The converter stops at 4,096 terms or 20,000 literal occurrences and reports that it stopped, rather than printing a partial form. A chain of fourteen XORs is enough to hit it.

Laws

Tools

CNF and DNF converter: conjunctive and disjunctive normal forms, minterms and maxterms

Practice

CNF and DNF exercises with answers

Lessons

Generated from the Tangibool engine, semantics tangibool-semantics/1, engine 1.0.0, build 2026-11-07. Every table, map, simplification and verdict on these pages was computed by the Tangibool engine when the site was built, and every claim was re-checked by the same exact checker the app uses. Limits are stated where they apply. © 2026 Foreranger LTD.