Normal Forms for Logic Problems

number of variables

2

3

4

level of difficulty

1

2

3

show solution

new example

¬A	B	¬C
¬A	B	C
¬A	¬B	¬C
A	B	¬C
A	¬B	C
¬A	¬B	C
A	B	C

A	B	C
0	1	1

This Demonstration shows a table with

n

2

-1

rows of

n

propositional variables or their negations. The task is to find values of propositional variables so that the disjunction of elements in each row is satisfied. This condition gives the conjunctive normal form (CNF) of a certain propositional function; on the other hand, the disjunctive normal form (DNF) consists of only one disjunction, from which it is easy to find a solution.

Solving some propositional logic puzzles consists of finding the DNF if the CNF is given.