=========================preview======================
(COMP272)01qbank.pdf
Back to COMP272 Login to download
======================================================
COMP272 Question Bank #1
Sets, Relations, and Functions
Question 1
Determine whether each of the following is true or false.
a) ...
b) ..
c) . {.}
d) . . {.}
e) {a, b}{a, b, c, {a, b}}
f) {a, b}.{a, b, {a, b}}
g) {a, b}. 2{a,b,{a,b}}
h) {{a, b}} 2{a,b,{a,b}}
TFTTTTFTF
i) {a, b, {a, b}} C {a,b} = {a,b}
Question 2
What are these sets? Write them using braces, commas, and numerals only:
a) 2{7,8,9} . 2{7,9}
{{8}, {7,8}, {8,9}}o
b) 2.
Question 3
Prove the following: A (A B)= A
if a in A, then a must in A^(AuB)if a in A^(AuB), if a in A, ok else if a not in A,it must in B A^(AUB) = (A^A) U (A^B) a can not in this. so a must in A
Question 4
Write each of the following explicitly.
{(1,1),(1,2)}*{1,2,3} = {((1,1),1),((1,1),2),((1,1),3),((1,2),1),((1,2),2),((1,2),3),
a) {1}{1, 2}{1, 2, 3}
{}
b) .{1, 2}
Question 5
For each part, give an example of .nite sets A and B with |A|, |B| 4 and a func-tion f : A . B such that (a) f is neither one-to-one nor onto; (b) f is one-to-one
but not onto; (c) f is onto but not one-to-one; (d) f is onto and one-to-one.
ABCDE
ABCDE
ABCD
12345
ABCDE
12345
1234
12345
1
Question 6
Let R and S be the binary relations on A = {1,..., 7} with the graphical represen-tations shown below:
a) Indicate whether each of R and S is symmetric, re.exive and transitive.
not symmetricnot reflexivenot transitive
b) Repeat the previous part for the relation R S.
not symmetricnot reflexivenot transitive
symmetricnot reflexivenot transitive
Question 7
Let f : A . B. Show that the following relation R is an equivalence relation on A: (a, b) R if and only if f(a)= f(b).
Question 8
If A = {1,..., 7}, de.ne a relation R on A by (x, y) R if and only if x . y is a multiple of 3. (a) Show that R is an equivalence relation on A. (b) Draw a directed graph representing R
Languages and Regular Expressions Question 1
Let = {a, b}. Write regular expressions representing the following sets: situation only has b like "bbbbb"
a) All strings in . with exactly one or two as (but not zero as, or more than
two as).
b) All strings in . with number of as divisible by 3.
c) All strings in . with exactly one occurrence of abb.
Question 2
Which of the following are true? Explain.
a) baa a .b. a .b.
b) b. a . a .b. = a . b.
.
c) a .b. b. c = .
d) abcd (a(cd). b) .
nb2n
e) {anbn : n 0}{bncn : n 0} = {acn : n 0}
Question 3
Write a regular expression representing the following language. Note: 0 is divisible by both 2 and 3:
.
. w {a, b} : number of as in w is divisible by 2, . number of bs in w is divisible by 3, or both
Question 4
Show that the following languages are regular by giving a regular expression for (a(aUbUc)*a)Ua(aUb)*a(aUb)*a(aUb)*
only has an "a"
each