Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 1 / b

Table of contents
- Solution b

Solution

Prove both identities by mathematical induction. The base case

n = 2

is the two-set form of De Morgan's laws. For the union identity, suppose the result holds for

n

. Applying the two-set identity and then the inductive hypothesis gives

A ∖ i = 1 ⋃ n + 1 B_{i} = (A ∖ i = 1 ⋃ n B_{i}) \cap (A ∖ B_{n + 1}) = (i = 1 ⋂ n (A ∖ B_{i})) \cap (A ∖ B_{n + 1}) = i = 1 ⋂ n + 1 (A ∖ B_{i}) .

For the intersection identity, the corresponding step is

A ∖ i = 1 ⋂ n + 1 B_{i} = (A ∖ i = 1 ⋂ n B_{i}) \cup (A ∖ B_{n + 1}) = (i = 1 ⋃ n (A ∖ B_{i})) \cup (A ∖ B_{n + 1}) = i = 1 ⋃ n + 1 (A ∖ B_{i}) .

These close the two inductions.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version