The relation of CNF and DNF used here is explained using a simple example. Assume that there are 6 kinds of food, p1...p6, and there are 5 kinds of vitamins, c1...c5, which are contained in those foods. Table 1 shows the vitamins contained in foods. This table is called an AND-OR table, because an OR combination is used for column elements and an AND combination is used for raw elements.
The purpose here is searching for combinations of foods p1-p5 which can take in all vitamins. In order to take in c1, p1 or p3 or p6 are required. This is expressed as c1 = p1∨p3∨p6. About each vitamin the conditions for required foods are as follows.
The condition which takes in all vitamins is (2). This is the CNF which is the total condition.
This condition is converted into DNF as follows:
Each clause of DNF becomes the combination of the food which satisfies the expression (2). For example p1 and p2 is one of the minimum set. The foods and the vitamins in this example correspond to the test cases and the conditions to be satisfied respectively.