comp2022 Tutorial 0: Assumed Knowledge s2 2020
This tutorial contains some revision questions to help you refresh your memory on some discrete mathematics topics. Most of the questions are extracted from chapter 0 of ”Introduction to the Theory of Computation”, by Michael Sipser.
Problem 1. Examine the following formal descriptions of sets so that you under- stand which members they contain. Write a short informal English description of each set.
a) {1,3,5,7,…}
b) {…,−4,−2,0,2,4,…}
c) {n|n=2mforsomem∈N}
d) {n | n = 2m for some m ∈ N, and n = 3k for some k ∈ N}
e) {w|wisastringof0sand1sandwequalsthereverseofw} f) {n|nisanintegerandn=n+1}
Problem 2. Write formal descriptions of the following sets.
a) The set containing the numbers 1, 10, and 100
b) The set containing all integers that are greater than 5
c) The set containing all natural numbers that are less than 5 d) The set containing the string aba
e) The set containing the empty string f) The set containing nothing at all
Problem 3. Let A be the set {x,y,z} and B be the set {x,y}. a) Is A a subset of B?
b) Is B a subset of A?
c) What is A ∪ B?
d) What is A ∩ B?
e) What is A × B?
f) What is the power set of B?
1
comp2022 Tutorial 0: Assumed Knowledge s2 2020 Problem 4. If A has a elements and B has b elements, how many elements are in
A × B? Explain your answer.
Problem 5. If C is a set with c elements, how many elements are in the power set
of C? Explain your answer.
Problem 6. Let X be the set {1,2,3,4,5} and Y be the set {6,7,8,9,10}. The unary function f : X → Y and the binary function g : X×Y → Y are described in the following tables.
n f(n) 16 27 36 47 56
is the value of f (2)?
are the range and domain of f ? is the value of g(2, 10)?
are the range and domain of g? is the value of g(4, f (4))?
g678910 11010101010 2789106 377889 4987610 566666
a) What b) What c) What d) What e) What
Problem 7. For each part, give a relation that satisfies the stated condition. a) Reflexive and symmetric but not transitive.
b) Reflexive and transitive but not symmetric.
c) Symmetric and transitive but not reflexive.
2