EXERCISES
1. Determine whether each of the following pairs of sets is equal
(a) φ φ
, { }
(b) {
}
{ }, { , { }}
2 2 2
(c) {1, 3, 3, 5, 5, 5}, {5, 3, 1}
2. For each of the following sets, determine whether 5 is an element of that
set.
(a) {
}
x R x
∈ | is an integer greather than 1
(b) {
}
x R x
∈ | is the square of an integer
(c) { }
5 5
, { }
3. Determine whether each of the following statements is True or False.
(a) x x
∈{ } (b) φ { }
⊆ x (c) φ ∈{ }
x
4. If A, B and C are sets such that A B
⊆ and B C
⊆ , show that A C
⊆ .
5. Find the Cardinality of each of the following sets.
(a) {1} (b) { }
{ }
1
(c) { }
1 1
, { } (d) {
}
1 1 1 1
, { }, { , { }}
6. Determine the powerset of the following sets.
(a) {a} (b) {a, b} (c) {
}
φ φ
, { }
7. Determine the number of elements in each of the following sets.
(a) (
)
P P ( )
φ
(b) (
)
P
a a
a
{ , , { }, {{ }}}
φ
8. Given A = {a, b, c, d} and B = {y, z}, find {a} A × B (b) B × A.
9. Find out the cartesian product A × B × C, where A is the set of all airlines
and B and C are both the set of all cities in Australia.
10. If A is a set, show that φ
φ
× = × =
A A
A.
11. Determine how many elements will A B
× have if A has in elements and
B has n elements.
12. Show that the ordered pair (a, b) can be defined in terms of sets as
{
}
{ }, { , }
a a b , (Hint: First show that {
}
{ }, { , } { }, { , }
a a b
c c d
=
if and only
if a = c and b = d).
13. Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find (a) A B
∪ (b) A B
∩
(c) A B
− (d) B A
− .
14. Show that A A
= , for a given set A.
15. Show that (a) A B B A
∪ = ∪
(b) A B B A
∩ = ∩ .
16. Show that if A and B are sets, A B A B
− = ∩ .
17. Show that if A and B are sets, then (
) (
)
A B
A B
A
∩
∪
∩
= .
18. What can you say about the sets A and B if the following are true?
(a) A B A
∪ =
(b) A B A
∩ =
(c) A B A
− =
(d) A B B A
∩ = ∩
46
Theory of Automata, Formal Languages and Computation