=========================preview======================
(COMP272)01qbank-sol.pdf
Back to COMP272 Login to download
======================================================
COMP272 Question Bank 1 Suggested Solution Sets, Relations, and Functions Question 1
(a)
True

(b)
False

(c)
True

(d)
True

(e)
True

(f)
True

(g)
False

(h)
True

(i)
False


Question 2
(a) 2{7,8,9}
= {., {7}, {8}, {9}, {7, 8}, {7, 9}, {8, 9}, {7, 8, 9}}

2{7,9}
= {., {7}, {9}, {7, 9}}

Hence 2{7,8,9} . 2{7,9} = {{8}, {7, 8}, {8, 9}, {7, 8, 9}}
Note that each element in the answer is a set containing the digit 8.

(b) 2. = {.}
Note that . is a subset of every set (including the set .).

Question 3
First, we prove A (A B) . A: x A (A B)
.
x A and x (A B)

.
x A


Second, we prove A . A (A B): x A (i)
.
x A or x B

.
x (A B) (ii)

.
x A and x (A B) Combining (i) and (ii)


.x A (A B) Thus, A . A (A B).
(a)
{1}{1, 2}{1, 2, 3}
= {(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3)}


(b)
.{1, 2} = . Note: as there is no element in ., there is no element in the Cartesian product.


Question 5
(a) Let A = {1, 2, 3, 4}, B = {v, w, x, y}, f = {(1,v), (2,v), (3,w), (4,x)}.
(b) Let A = {1, 2, 3, 4}, B = {v, w, x, y, z}, f = {(1,v), (2,x), (3,y), (4,z)}.
(c)
Let A = {1, 2, 3, 4, 5}, B = {w, x, y, z}, f = {(1,w), (2,w), (3,x), (4,y), (5,z)}.

(d)
Let A = {1, 2, 3, 4}, B = {w, x, y, z}, f = {(1,w), (2,x), (3,y), (4,z)}.


Question 6
(a)
R is not re.exive, not symmetric and not transitive.
S is neither re.exive nor transitive but S is symmetric.


(b)
R S is not re.exive, not symmetric and not transitive.


Question 7
To prove that R is an equivalence relation on A, we have to show that it has the following properties:
i) Re.exivity
.a A, f(a)= f(a). Therefore (a, a) R.

ii) Symmetry .a, b A,(a, b) R implies f(a)= f(b). This in turn implies f(b)= f(a), and therefore (b, a) R.
iii) Transitivity .a, b, c A,(a, b) R implies f(a)= f(b) and (b, c) R implies f(b)= f(c). Therefore f(a)= f(c). Therefore (a, c) R
In conclusion, R is an equivalence relation on A.
(a) i) Re.exivity
.a A, a . a =3 0. Therefore (a, a) R.

ii) Symmetry .a, b A,(a, b) R implies a . b =3c for some integer c. This in turn implies (b . a) = 3(.c) for some integer .c. Therefore, (b, a) R.
iii) Transitivity .a, b, c A,(a, b) R and (b, c) R imply a . b =3m and b . c =3n, for some integers m and n. This in turn implies (a . b)+(b . c)= 3m +3n . a . c = 3(m + n). Therefore, (a, c) R. Therefore, R is an equivalence relation on A.
(b)

Languages and Regular Expressions Question 1
a) b.ab. b.ab.ab.
b) b.(b.ab.ab.ab.).
c) b.(ab a). abb b.(ab a).

Question 2
... ..b.
a) It is valid. Observe that L(aa .b.)= {a} .{b} .{a} .{b} .. Now, e {a} ,
.. . .b..b.
b {b} , aa {a} and e {b} . Therefore baa aa .
b) It is valid. Observe that b. a . represents a set of strings