Skip to content

Sign in Open the app

CNF and DNF exercises with answers

Ten conversions to disjunctive or conjunctive normal form: implications, XOR and the biconditional in both forms, a negation pushed inward, distribution in both directions, and a maxterm list written out as a product of sums. Write the form asked for and compare it with the engine.

A disjunctive normal form (DNF) is an OR of AND terms, each term a product of literals; a conjunctive normal form (CNF) is an AND of OR clauses. The method is always the same: eliminate ->, <-> and XOR, push every NOT down to a variable with De Morgan and double negation, then distribute AND over OR for a DNF or OR over AND for a CNF. The canonical forms go one step further and use full minterms or maxterms, one per row, which is what Σm and ΠM list.

Each answer was verified by an exact equivalence check with its problem before the page was built, so any correct form passes, canonical or not; the solutions give the textbook form and say which laws reach it. The truth table under each problem is the fastest way to check your own: a DNF must be TRUE exactly on the rows named by its terms, and a CNF must be FALSE exactly on the rows named by its clauses.

1. Write A -> B in disjunctive normal form. A -> B

#	A	B	f
0	FALSE	FALSE	TRUE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	FALSE
3	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A -> B

Classification: contingent

Implication elimination: NOT A OR B, which is already a DNF of two one-literal terms (and a CNF of one clause).

2. Write A XOR B in conjunctive normal form. A XOR B

#	A	B	f
0	FALSE	FALSE	FALSE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	TRUE
3	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A XOR B

Classification: contingent

XOR is FALSE on the two rows where the inputs agree, so one clause per such row: A = FALSE, B = FALSE gives A OR B, A = TRUE, B = TRUE gives NOT A OR NOT B. CNF: (A OR B) AND (NOT A OR NOT B).

3. Write A XOR B in disjunctive normal form. A XOR B

#	A	B	f
0	FALSE	FALSE	FALSE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	TRUE
3	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A XOR B

Classification: contingent

XOR elimination: one term per TRUE row, A = TRUE, B = FALSE and A = FALSE, B = TRUE: (A AND NOT B) OR (NOT A AND B).

4. Write A <-> B in disjunctive normal form. A <-> B

#	A	B	f
0	FALSE	FALSE	TRUE
1	FALSE	TRUE	FALSE
2	TRUE	FALSE	FALSE
3	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A <-> B

Classification: contingent

Biconditional elimination: both TRUE or both FALSE, (A AND B) OR (NOT A AND NOT B).

5. Write A <-> B in conjunctive normal form. A <-> B

#	A	B	f
0	FALSE	FALSE	TRUE
1	FALSE	TRUE	FALSE
2	TRUE	FALSE	FALSE
3	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

A <-> B

Classification: contingent

The biconditional is the conjunction of the two implications, (A -> B) AND (B -> A); eliminating each gives (NOT A OR B) AND (A OR NOT B). Each clause is FALSE on one of the two rows where the inputs differ.

6. Write the maxterm list ΠM(A, B; 0, 3) out as a product of sums. ΠM(A, B; 0, 3)

#	A	B	f
0	FALSE	FALSE	FALSE
1	FALSE	TRUE	TRUE
2	TRUE	FALSE	TRUE
3	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

ΠM(A, B; 0, 3)

Classification: contingent

Maxterm 0 is A OR B and maxterm 3 is NOT A OR NOT B: (A OR B) AND (NOT A OR NOT B), the CNF of A XOR B from problem 2. The table is FALSE exactly on A = FALSE, B = FALSE and A = TRUE, B = TRUE.

7. Write NOT (A AND (B OR C)) in disjunctive normal form. NOT (A AND (B OR C))

#	A	B	C	f
0	FALSE	FALSE	FALSE	TRUE
1	FALSE	FALSE	TRUE	TRUE
2	FALSE	TRUE	FALSE	TRUE
3	FALSE	TRUE	TRUE	TRUE
4	TRUE	FALSE	FALSE	TRUE
5	TRUE	FALSE	TRUE	FALSE
6	TRUE	TRUE	FALSE	FALSE
7	TRUE	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

NOT (A AND (B OR C))

Classification: contingent

De Morgan over the AND gives NOT A OR NOT (B OR C), and over the OR gives NOT A OR (NOT B AND NOT C): a DNF with two terms. The step list shows no law, since neither rewrite shortens the expression.

8. Write (A AND B) OR C in conjunctive normal form. (A AND B) OR C

#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	TRUE
2	FALSE	TRUE	FALSE	FALSE
3	FALSE	TRUE	TRUE	TRUE
4	TRUE	FALSE	FALSE	FALSE
5	TRUE	FALSE	TRUE	TRUE
6	TRUE	TRUE	FALSE	TRUE
7	TRUE	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

(A AND B) OR C

Classification: contingent

Distribute OR over AND: (A OR C) AND (B OR C). Each clause is FALSE on the rows where C is FALSE and the variable it names is FALSE.

9. Write (A OR B) AND (C OR D) in disjunctive normal form. (A OR B) AND (C OR D)

#	A	B	C	D	f
0	FALSE	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	FALSE	TRUE	FALSE
2	FALSE	FALSE	TRUE	FALSE	FALSE
3	FALSE	FALSE	TRUE	TRUE	FALSE
4	FALSE	TRUE	FALSE	FALSE	FALSE
5	FALSE	TRUE	FALSE	TRUE	TRUE
6	FALSE	TRUE	TRUE	FALSE	TRUE
7	FALSE	TRUE	TRUE	TRUE	TRUE
8	TRUE	FALSE	FALSE	FALSE	FALSE
9	TRUE	FALSE	FALSE	TRUE	TRUE
10	TRUE	FALSE	TRUE	FALSE	TRUE
11	TRUE	FALSE	TRUE	TRUE	TRUE
12	TRUE	TRUE	FALSE	FALSE	FALSE
13	TRUE	TRUE	FALSE	TRUE	TRUE
14	TRUE	TRUE	TRUE	FALSE	TRUE
15	TRUE	TRUE	TRUE	TRUE	TRUE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

(A OR B) AND (C OR D)

Classification: contingent

Distribute AND over OR, every term of the first factor with every term of the second: (A AND C) OR (A AND D) OR (B AND C) OR (B AND D), four terms.

10. Write Σm(A, B, C; 1, 2) as a canonical disjunctive normal form (full minterms). Σm(A, B, C; 1, 2)

#	A	B	C	f
0	FALSE	FALSE	FALSE	FALSE
1	FALSE	FALSE	TRUE	TRUE
2	FALSE	TRUE	FALSE	TRUE
3	FALSE	TRUE	TRUE	FALSE
4	TRUE	FALSE	FALSE	FALSE
5	TRUE	FALSE	TRUE	FALSE
6	TRUE	TRUE	FALSE	FALSE
7	TRUE	TRUE	TRUE	FALSE

The engine found no law that shortens this expression; it is already as short as its rewriting laws can make it.

Σm(A, B, C; 1, 2)

Classification: contingent

Minterm 1 is A = FALSE, B = FALSE, C = TRUE and minterm 2 is A = FALSE, B = TRUE, C = FALSE; each becomes a full product: (NOT A AND NOT B AND C) OR (NOT A AND B AND NOT C). The two terms also factor as NOT A AND (B XOR C).

Questions

How do I read a maxterm list?

ΠM(A, B; 0, 3) is FALSE exactly on rows 0 and 3. Each listed row becomes one clause that is FALSE on that row only: row 0 (A = FALSE, B = FALSE) gives A OR B, row 3 (A = TRUE, B = TRUE) gives NOT A OR NOT B, and the product of the two clauses is the CNF. The literals of a maxterm are the negations of the row's values.

Related

Laws

Glossary

Compare

See also

Practice

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.