MUN Computer Science 1002 - Lab 5





Individual work

Solve each of the following exercises.

  1. In a proof, you often see a line following from previous by definition. For example, you might say "n is an even number. Then, n=2k for some integer k". In the following, fill in the blank after "then" by using a corresponding definition.
    1. (Definition: an integer a is odd if there exists an integer b such that a=2b+1).
      Let n and m be two odd integers. Then, ...
    2. (Definition: for $a,b \in \mathbb{Z}$, a divides b if there exists $ c \in \mathbb{Z}$ such that a = bc).
      Let n be an integer divisibe by 5. Then,
    3. (Definition: for $a \in \mathbb{R}$, $|a|=a$ if $a \geq 0$, and $|a|= -a$ if $a <0$).
      Suppose $r \in \mathbb{R}$. Then, case 1 ... |r| is ... case 2 ...
  2. For each of the following, describe the union, intersection and symmetric difference of the given sets, their differences and complements (symmetric difference is the union of differences). Draw a Venn diagram, and give an example of an element in every region of the Venn diagram.
    1. $U = $ set of all living creatures. $A =$ set of all mammals. $B = $ set of all pets.
    2. $U = \mathbb{R}$, $A = \{ x \in \mathbb{N}| x$ is prime$\}$, $B = \{x \in \mathbb{Z} | $ last digit of x is 3 $\}$, $C = \mathbb{Q}$.
  3. For each of the following, list or describe all elements in the resulting set.
  4. Give cardinalities of all finite sets from the previous question.

Group exercises

For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

Topic 1: Power sets

Write out power sets of the following sets:

Topic 2: Cartesian product

For each of the following, write a list elements of the Cartesian product.

Topic 3: The rule of inclusion/exclusion.

Review after the group activity

Let $A = \{0,6,9\}$ and $B = \{ \emptyset, \{0\}\}$.

  1. What are the powerset of A and of the powerset of B? Describe the set as $\{ .... \}$ with the list of elements.
  2. What is the Cartesian product of A and B? Describe the set as a list of elements.
  3. What is the cardinality of the Cartesian product of the powerset of A and a powerset of B? Do not list the set, just compute the numbers.
  4. Let $|C|=20$ and $|D|=15$. What are the maximal and minimal values of $|C \cup D|$ and $|C \cap D|$?