Discrete Mathematics/Set theory/Exercises
Set Theory Exercise 1Edit
1
- Is each of the following a well-defined set? Give brief reasons for each of your answers.
- (a) The collection of all alphanumeric characters.
- (b) The collection of all tall people.
- (c) The collection of all real numbers x for which:
- 2x – 9 = 16.
- (d) The collection of all integers x for which:
- 2x – 9 = 16.
- (e) The collection of all good tennis players.
2
- U = {natural numbers}; A = {2, 4, 6, 8, 10}; B = {1, 3, 6, 7, 8}
- State whether each of the following is true or false:
- (a) 2 ∈ A
- (b) 11 ∈ B
- (c) 4 ∉ B
- (d) A ∈ U
- (e) A = {even numbers}
3
- U = R; A = {4, √2, 2/3, -2.5, -5, 33, √9, π}
- Using the {…} set notation, write the sets of:
- (a) natural numbers in A
- (b) integers in A
- (c) rational numbers in A
- (d) irrational numbers in A
4
- True or false?
- (a) ø = {0}
- (b) x ∈ { x }
- (c) ø = { ø }
- (d) ø ∈ { ø }
5
- The following sets have been defined using the | notation. Re-write them by listing some of the elements.
- (a) {p | p is a capital city, p is in Europe}
- (b) {x | x = 2n - 5, x and n are natural numbers}
- (c) {y | 2y^{2} = 50, y is an integer}
- (d) {z | 3z = n^{2}, z and n are natural numbers}
Set Theory Exercise 2Edit
1
In A? | In B? | In C? | Region |
---|---|---|---|
Y | Y | Y | |
Y | Y | N | |
Y | N | Y | |
Y | N | N | |
N | Y | Y | |
N | Y | N | |
N | N | Y | |
N | N | N |
- Copy the truth table to the right, and write at the end of each row the number of the corresponding region in Fig. 4 Venn Diagrams.
2
- If U = {letters of the alphabet}, A = {a, a, a, b, b, a, c}, B = {c, b, a, c} and C = {a, b, c}, what can be said about A, B and C?
3
- U = {natural numbers}; A = {2, 4, 6, 8, 10}; B = {1, 3, 6, 7, 8}
- State whether each of the following is true or false:
- (a) A ⊂ U
- (b) B ⊆ A
- (c) ø ⊂ U
4
- U = {a, b, c, d, e, f, g, h}; P = {c, f}; Q = {a, c, d, e, f, h}; R = {c, d, h}
- (a) Draw a Venn diagram, showing these sets with all the elements entered into the appropriate regions. If necessary, redraw the diagram to eliminate any empty regions.
- (b) Which of sets P, Q and R are proper subsets of others? Write your answer(s) using the ⊂ symbol.
- (c) P and R are disjoint sets. True or False?
5
- Sketch Venn diagrams that show the universal set, U, the sets A and B, and a single element x in each of the following cases:
- (a) x ∈ A; A ⊂ B
- (b) x ∈ A; A and B are disjoint
- (c) x ∈ A; x ∉ B; B ⊂ A
- (d) x ∈ A; x ∈ B; A is not a subset of B; B is not a subset of A
Set Theory Exercise 3Edit
1
- U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
- A = {2, 4, 6, 8, 10}
- B = {1, 3, 6, 7, 8}
- C = {3, 7}
- (a) Illustrate the sets U, A, B and C in a Venn diagram, marking all the elements in the appropriate places. (Note: if any region in your diagram does not contain any elements, re-draw the set loops to correct this.)
- (b) Using your Venn diagram, list the elements in each of the following sets:
- A ∩ B, A ∪ C, A′, B′, B ∩ A′, B ∩ C′, A – B, A Δ B
- (c) Complete the statement using a single symbol: C - B = ... .
2
- True or false?
- (a) | ø | = 1
- (b) | { x, x } | = 2
- (c) | U ∩ ø | = 0
3
- What can you say about two sets P and Q if:
- (a) P ∩ Q′ = ø
- (b) P ∪ Q = P?
4
- Make six copies of the Venn diagram shown alongside, and then shade the areas represented by:
- (a) A ′ ∪ B
- (b) A ∩ B ′
- (c) (A ∩ B) ′
- (d) A ′ ∪ B ′
- (e) (A ∪ B) ′
- (f) A ′ ∩ B ′
5
- Identify the sets represented by each of the shaded areas below, using the set notation symbols ∩, ∪ and ′ only:
(a) | (b) |
(c) | (d) |
6
- (a) One of the shaded regions in question 5 represents the set A – B. Identify which one it is, and hence write a definition of A – B using only symbols from the list ∩, ∪ and ′.
- (b) Again using one of your answers to question 5, write a definition of A Δ B using only symbols from the list ∩, ∪ and ′. (There are two possibilities here – see if you can find them both!)
Set Theory Exercise 4Edit
1
- (a) If A = {1, 2, 3, 4}, write down P(A) by listing its elements. What is the value of | P(A) |?
- (b) If | A | = 5, what is the value of | P(A) |?
- (c) If | A | = 10, what is the value of | P(A) |?
2
- Prove the following identities, stating carefully which of the set laws you are using at each stage of the proof.
- (a) B ∪ (ø ∩ A) = B
- (b) (A ′ ∩ U) ′ = A
- (c) (C ∪ A) ∩ (B ∪ A) = A ∪ (B ∩ C)
- (d) (A ∩ B) ∪ (A ∩ B ' ) = A
- (e) (A ∩ B) ∪ (A ∪ B ' ) ′ = B
- (f) A ∩ (A ∪ B) = A
Set Theory Exercise 5Edit
1
- X = {a, c} and Y = {a, b, e, f}.
- Write down the elements of:
- (a) X × Y
- (b) Y × X
- (c) X^{ 2} (= X × X)
- (d) What could you say about two sets A and B if A × B = B × A?
2
- A chess board’s 8 rows are labelled 1 to 8, and its 8 columns a to h. Each square of the board is described by the ordered pair (column letter, row number).
- (a) A knight is positioned at (d, 3). Write down its possible positions after a single move of the knight.
- (b) If R = {1, 2, ..., 8}, C = {a, b, ..., h}, and P = {coordinates of all squares on the chess board}, use set notation to express P in terms of R and C.
- (c) A rook is positioned at (g, 2). If T = {2} and G = {g}, express its possible positions after one move of the rook in terms of R, C, T and G.
3
- In a certain programming language, all variable names have to be 3 characters long. The first character must be a letter from 'a' to 'z'; the others can be letters or digits from 0 to 9.
- If L = {a, b, c, ... , z}, D = {0, 1, 2, ..., 9}, and V = {permissible variable names}, use a Cartesian product to complete:
- V = {pqr | (p, q, r) ∈ ... }
4
- It is believed that, for any sets A, B and C, A × (B ∩ C) = (A × B) ∩ (A × C).
- (Note that, if this is true, it says that × is distributive over ∩.)
- Copy and complete the two Cartesian diagrams shown below – one for the expression on each side of the equation – to investigate this.
- Do you think that the proposition is true?