2-1
1. Determine whether these statements are true or false.
Ex.8
a) ∅ ∈ {∅}
b) ∅ ∈ {∅, {∅}}
c) {∅} ∈ {∅}
d) {∅} ∈ {{∅}}
e) {∅} ⊂ {∅, {∅}}
f) {{∅}} ⊂ {∅, {∅}}
g) {{∅}} ⊂ {{∅}, {∅}}
2-1
2. What is the cardinality of each of these sets?
Ex.18
a) Ø
b) {Ø}
c) {Ø, {Ø} }
d) {Ø, {Ø} ,{Ø,{Ø}}}
2-1
Ex.223. Determine whether each of these sets is the power set of a set, where a and b are distinct elements
a) Ø
b) {Ø, {a}}
c) {Ø, {a}, {Ø, a}}
d) {Ø, {a}, {b}, {a, b}}
2-1
4. Explain why (𝐴𝐴 × 𝐵𝐵) × (𝐶𝐶 × 𝐷𝐷) and 𝐴𝐴 × (𝐵𝐵 × 𝐶𝐶) × 𝐷𝐷 are not the same
Ex.32
2-1
5. Suppose that A × 𝐵𝐵 = ∅ , where 𝐴𝐴 and 𝐵𝐵 are sets, what can you conclude?
Ex.36
2-2
Ex.46. Let 𝐴𝐴 = {𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑, 𝑒𝑒} and 𝐵𝐵 = {𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑, 𝑒𝑒, 𝑓𝑓, 𝑔𝑔, ℎ}. Find
a) 𝐴𝐴 ∪ 𝐵𝐵
b) 𝐴𝐴 ∩ 𝐵𝐵
c) 𝐴𝐴 − 𝐵𝐵
d) 𝐵𝐵 − 𝐴𝐴
2-2
7. Show that if A and B are sets, then(𝐴𝐴 ∩ 𝐵𝐵) ∪ (𝐴𝐴 ∩ 𝐵𝐵�) = 𝐴𝐴.
Ex.20
2-2
8. Show that 𝐴𝐴⨁𝐵𝐵 = (𝐴𝐴 ∪ 𝐵𝐵) − (𝐴𝐴 ∩ 𝐵𝐵)
Ex.35
2-3
Ex.69. Find the domain and range of these functions
b) The function that assigns to each positive integer its largest decimal digit
c) The function that assigns to a bit string the number if ones minus the number of zeros in the string
e) The function that assigns to a bit string the longest string of ones in the string
2-3
10. Find these values:
Ex.8
a) ⌊1.1⌋
b) ⌈1.1⌉
c) ⌊−0.1⌋
d) ⌈−0.1⌉
e) ⌈2.99⌉
f) ⌈−2.99⌉
1 1
g) � + � ��
2 2
1 1 1
h) �� � + � � + �
2 2 2
2-3
11. Determine whether each of these functions from 𝐙𝐙 to 𝐙𝐙 is one to one.
Ex.12
a) 𝑓𝑓(𝑛𝑛) = 𝑛𝑛 − 1
b) 𝑓𝑓(𝑛𝑛) = 𝑛𝑛2 + 1
c) 𝑓𝑓(𝑛𝑛) = 𝑛𝑛3
d) 𝑓𝑓(𝑛𝑛) = ⌈𝑛𝑛/2⌉
2-3
12. Determine whether 𝑓𝑓: 𝐙𝐙 × 𝐙𝐙 → 𝐙𝐙 is onto if
Ex.14
a) 𝑓𝑓(𝑚𝑚, 𝑛𝑛) = 2𝑚𝑚 − 𝑛𝑛
b) 𝑓𝑓(𝑚𝑚, 𝑛𝑛) = 𝑚𝑚2 − 𝑛𝑛2
c) 𝑓𝑓(𝑚𝑚, 𝑛𝑛) = 𝑚𝑚 + 𝑛𝑛 + 1
d) 𝑓𝑓(𝑚𝑚, 𝑛𝑛) = |𝑚𝑚| − |𝑛𝑛|
e) 𝑓𝑓(𝑚𝑚, 𝑛𝑛) = 𝑚𝑚2 − 4
2-3
13. Determine whether each of these functions is a bijection from 𝐑𝐑 to 𝐑𝐑
Ex.18
a) 𝑓𝑓(𝑥𝑥) = −3𝑥𝑥 + 4
b) 𝑓𝑓(𝑥𝑥) = −3𝑥𝑥 2 + 7
c) 𝑓𝑓(𝑥𝑥) = (𝑥𝑥 + 1)/(𝑥𝑥 + 2)
d) 𝑓𝑓(𝑥𝑥) = 𝑥𝑥 5 + 1
2-3
Ex.34
14. Let 𝑓𝑓(𝑥𝑥) = 𝑎𝑎𝑎𝑎 + 𝑏𝑏 and 𝑔𝑔(𝑥𝑥) = 𝑐𝑐𝑐𝑐 + 𝑑𝑑, where 𝑎𝑎, 𝑏𝑏, 𝑐𝑐, and 𝑑𝑑 are constaints. Determine for which
constants 𝑎𝑎, 𝑏𝑏, 𝑐𝑐, and 𝑑𝑑 it is true that 𝑓𝑓 ∘ 𝑔𝑔 = 𝑔𝑔 ∘ 𝑓𝑓.
2-3
Ex.68
15. Suppose that 𝑓𝑓 is a function from 𝐴𝐴 to 𝐵𝐵, where 𝐴𝐴 and 𝐵𝐵 are finite sets with |𝐴𝐴| = |𝐵𝐵|
Show that 𝑓𝑓 is one-to-one iff it is onto
2-S
Ex.13
16. Let 𝑓𝑓 and 𝑔𝑔 be functions from {1, 2, 3, 4} to {𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑} and from {𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑} to {1, 2, 3, 4}
respectively, such that 𝑓𝑓(1) = 𝑑𝑑, 𝑓𝑓(2) = 𝑐𝑐, 𝑓𝑓(3) = 𝑎𝑎, 𝑓𝑓(4) = 𝑏𝑏 and 𝑔𝑔(𝑎𝑎) = 2, 𝑔𝑔(𝑏𝑏) = 1, 𝑔𝑔(𝑐𝑐) = 3,
𝑔𝑔(𝑑𝑑) = 2
a) Is 𝑓𝑓 one-to-one? Is 𝑔𝑔 one-to-one?
b) Is 𝑓𝑓 onto? Is 𝑔𝑔 onto?
c) Does either 𝑓𝑓 or 𝑔𝑔 have an inverse?
2-3
17. How many bytes are required to encode 𝑛𝑛 bits of data where 𝑛𝑛 equals
Ex.54
a) 4?
b) 10?
c) 500?
d) 3000?
2-3
Ex.7018. Prove �⌈𝑥𝑥/2⌉/2� = ⌈𝑥𝑥/4⌉ for all real number 𝑥𝑥
-c)
2-4
Ex.8
19. Find at least three different sequences beginning with the terms 3, 5, 7 whose terms are generated by a
simple formula or rule.
2-4
Ex.10
20. For each of these lists of integers, provide a simple formula or rule that generates the terms of an
integer sequence that begins with the given list. Assuming that your formula or rule is correct, determine
the next three terms of the sequence.
a) 3, 6, 11, 18, 27, 38, 51, 66, 83, 102, …
d) 1, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, …
e) 0, 2, 8, 26, 80, 242, 728, 2186, 6560, 19682, …
2-4
Ex.32
21. Determine whether each of these sets is countable or uncountable. For those that are countable,
exhibit a one-to-one correspondence between the set of natural numbers and that set.
a) the integers greater than 10
d) integers that are multiples of 10
