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

Table of contents
- i c
  - Solution i
- ii c
  - Solution ii
- iii c
  - Solution iii

i

Solution

An algebraic way to prove the set identity is to show that

D = \overline{A} \cup \overline{B}

is a complement of a set for

A \cap B

. By the distributive property,

(A \cap B) \cap D = (A \cap B \cap \overline{A}) \cup (A \cap B \cap \overline{B}) = \emptyset,

and

(A \cap B) \cup D = (A \cup D) \cap (B \cup D) = U \cap U = U .

A complement of a set is unique: if

D, E

both complement

S

, then

D = D \cap (S \cup E) = D \cap E

, and similarly

E = D \cap E

. Consequently

\overline{A \cap B} = \overline{A} \cup \overline{B} .

ii

Solution

Write the set difference as an intersection and use the fact that taking the complement of a set twice returns that set. The commutativity of intersection gives the reversible calculation

\overline{A} ∖ \overline{B} = \overline{A} \cap \overline{\overline{B}} = \overline{A} \cap B = B \cap \overline{A} = B ∖ A .

iii

Solution

Use the symmetric difference formula from part (b), followed by the set difference identity from part (c)(ii):

\overline{A} \oplus \overline{B} = (\overline{A} ∖ \overline{B}) \cup (\overline{B} ∖ \overline{A}) = (B ∖ A) \cup (A ∖ B) = A \oplus B .

Taking both complements swaps the two ways to belong to exactly one set, leaving their union unchanged:

\overline{A} \oplus \overline{B} = A \oplus B .

 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