19.3. Proof of Transitive Closure Properties

Try these first

1. 1.

   What is meant by the term transitive closure?

   Hint

   Think about connectivity and closure in conditions.

2. 2.

   Define a connectivity relation.

   Hint

   Consider what paths would mean in a graph context.

3. 3.

   What is the connectivity relation R*?

   • Intersection of powers of R
   • Union of powers of R
   • Subset of R

   Hint

   Think about how paths function within graph representations.

4. 4.

   If (a, b) is in R* and (b, c) is also in R*, what can we conclude?

   • True
   • False

   Hint

   R* should maintain transitive characteristics.

5. 5.

   Create a boolean matrix for a given relation R with 5 elements and calculate R*.

   Hint

   Use boolean multiplication and ensure to check reachable paths.

6. 6.

   Prove that R* is the smallest transitive relation expanding R using set theory.

   Hint

   Visualize subsets and demonstrate transitivity through multiple examples.