First page Back Continue Last page Graphics

Canonical Cover Exercise


Notes:

Following the algorithm of Figure 7.8 we perform the following steps:
1. Initially we cannot apply the union rule
2. We check whether B is extraneous in ABC.
From AB we deduce AAB by augmentation.
From AAB and ABC we deduce AC by transitivity.
We can thus replace ABC by AC without making F stronger.
3. We can now apply the union rule to replace AB and AC by ABC.
4. We now check whether D is extraneous in DEC.
From EBCD and the trivial BCDD we deduce ED by transitivity.
From ED we deduce EDE by augmentation.
From EDE and DEC we deduce EC by transitivity.
We can thus replace DEC by EC without making F stronger.
5. We can now apply the union rule to replace EC and EBCD by EBCD.

The resulting set is {ABC, EBCD}. It can not be reduced any further.