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

Table of contents
- i a
  - Solution i
- ii a
  - Solution ii

i

Solution

Write each set difference as an intersection with a complement of a set. Applying De Morgan's laws and then the distributive property gives

A ∖ (B \cup C) A ∖ (B \cap C) = A \cap \overline{B \cup C} = A \cap (\overline{B} \cap \overline{C}) = (A ∖ B) \cap (A ∖ C), = A \cap \overline{B \cap C} = A \cap (\overline{B} \cup \overline{C}) = (A ∖ B) \cup (A ∖ C) .

The complements turn the inner union into an intersection and vice versa. Thus

A ∖ (B \cup C) = (A ∖ B) \cap (A ∖ C), A ∖ (B \cap C) = (A ∖ B) \cup (A ∖ C) .

ii

Solution

Apply the distributive property to the intersection with

\overline{C}

:

(A \cap B) ∖ C (A \cup B) ∖ C = (A \cap B) \cap \overline{C} = (A \cap \overline{C}) \cap (B \cap \overline{C}), = (A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C}) .

In the first line the repeated factor

\overline{C}

changes nothing. Rewriting in terms of set differences yields

(A \cap B) ∖ C = (A ∖ C) \cap (B ∖ C), (A \cup B) ∖ C = (A ∖ C) \cup (B ∖ C) .

 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