Print bookPrint book

Try It Now

Site: Saylor Academy
Course: CS202: Discrete Structures
Book: Try It Now
Printed by: Guest user
Date: Saturday, April 27, 2024, 1:11 AM

Description

Work these exercises to see how well you understand this material.

Table of contents

Exercises

  1. List all partitions of the set A = {a, b, c}.

  2. A student, on an exam paper, defined the term partition the following way: “Let A be a set. A partition of A is any set of nonempty subsets A1, A2, A3, . . . of A such that each element of A is in one of the subsets.” Is this definition correct? Why?

  3. Show that {{2n| n ∈ ℤ},{2n+ 1 | n ∈ ℤ}} is a partition of ℤ. Describe this partition using only words.

  4. A survey of 90 people, 47 of them played tennis and 42 of them swam. If 17 of them participated in both activities, how many of them participated in neither?

  5. Regarding the Theorem 2.3.9,
    1. (a) Use the two set inclusion-exclusion law to derive the three set inclusion- exclusion law. Note: A knowledge of basic set laws is needed for this exercise.
    2. (b) State and derive the inclusion-exclusion law for four sets.

  6. The definition of ℚ = {a/b| a, b ∈ ℤ, b ≠ 0} given in Chapter 1 is awkward. If we use the definition to list elements in ℚ, we will have duplications such as \frac{1}{2}, \frac{-2}{-4}, and \frac{300}{600}. Try to write a more precise definition of the rational numbers so that there is no duplication of elements.

 

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Solutions

  1. Answer: {{a}, {b}, {c}}, {{a, b}, {c}}, {{a, c}, {b}}, {{a}, {b, c}}, {{a, b, c}}

  2. Answer: No. By this definition, it is possible that an element of A might belong to two of the subsets.

  3. Answer: The first subset is all the even integers and the second is all the odd integers. These two sets do not intersect and they cover the integers completely.

  4. Answer: Since 17 participated in both activities, 30 of the tennis players only played tennis and 25 of the swimmers only swam. Therefore, 17 + 30 + 25 = 72 of those who were surveyed participated in an activity and so 18 did not.

  5. Solution: We assume that |A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|.

    |A1 ∪ A2 ∪ A3| = |(A1 ∪ A2) ∪ A3| Why?

    = |A1 ∪ A2| + |A3| − |(A1 ∪ A2) ∩ A3| Why?

    = A1 ∪ A2| + |A3| − |(A1 ∩ A3) ∪ (A2 ∩ A3)| Why?

    = |A1| + |A2| − |A1 ∩ A2| + |A3| − (|A1 ∩ A3| + |A2 ∩ A 3| − |(A1 ∩ A3) ∩ (A2∩ A3)| Why?

    = |A1| + |A2| + |A3| − |A1 ∩ A2| − |A1 ∩ A3| − |A2 ∩ A 3| + |A1∩ A2∩ A3| Why?

    The law for four sets is:

    |A1 ∪ A2 ∪ A3 ∪ A4| = |A1| + |A2| + |A3| + |A4| − |A1 ∩ A2| − |A1 ∩ A3| − |A1 ∩ A4| − |A 2 ∩ A3| − |A2 ∩ A4| − |A3 ∩ A4| + |A1 ∩ A2∩ A3| + |A1 ∩ A2 ∩ A4| + |A1 ∩ A 3∩ A4| + |A2 ∩ A3∩ A4| − |A1 ∩ A2∩ A3∩ A4|

    Derivation:

    |A1 ∪ A2 ∪ A3 ∪ A4| = |(A1 ∪ A2 ∪ A3) ∪ A4|

                                        = |(A1 ∪ A2 ∪ A3| + |A4| − |(A1 ∪ A2 ∪ A3) ∩ A4 

                                        = |(A1 ∪ A2∪ A3| + |A4| − |(A1 ∩ A4) ∪ (A2∩ A 4) ∪ (A3∩ A4)|

                                        = |A1| + |A2| + |A3| − |A1 ∩ A2| − |A1 ∩ A3| − |A2 ∩ A3| + |A1 ∩ A2∩ A3| + |A4| − |A1 ∩ A4| + |A2 ∩ A4| + |A3 ∩ A4| − |(A1 ∩ A 4) ∩ (A2∩ A4)| − |(A1 ∩ A4) ∩ (A3∩ A4)| − |(A2 ∩ A4) ∩ (A3∩ A4)| + |(A1 ∩ A4) ∩ (A2∩ A4) ∩ (A3∩ A4)|

                                        = |A1| + |A2 | + |A3| + |A4| − |A1 ∩ A2 | − |A1  ∩ A3| − |A2 ∩ A3 | − |A1  ∩ A4 | − |A2 ∩ A4| − |A3 ∩ A4 | + |A1  ∩ A2∩ A3 | + |A1 ∩ A2 ∩ A4 | + |A1 ∩ A3∩ A4| + |A2  ∩ A3 ∩ A4| − |A1 ∩ A2∩ A3 ∩ A4 |

  6. Answer: Partition the set of fractions into blocks, where each block contains fractions that are numerically equivalent. Describe how you would determine whether two fractions belong to the same block. Redefine the rational numbers to be this partition. Each rational number is a set of fractions.