35. Prove:
(a) A
A B
A
∪
∩
=
(
)
(b) A
A B
A
∩
∪
=
(
)
(c) A B A B
− = ∩
(d) A
A B
A B
∪
∩
= ∪
(
)
(e) A
A B
A B
∩
∪
= ∩
(
)
.
36. Check if the following are functions defined in R to R:
(a) f x
x
( ) =
1
(b) f x
x
( ) =
(c) f x
x
( ) = ±
+
2
1
37. Determine the domain and range of the following functions.
(a) The function that assigns to each positive integer the largest perfect
square not exceeding this integer
(b) The function that assigns to each bit string twice the number of
zeros in that string.
38. Which of the following functions are onto from the set {a, b, c, d}.
(a) f a b f b a f c c f d d
( )
, ( )
, ( ) , ( )
=
=
=
=
(b) f a d f b b f c c f d d
( )
, ( )
, ( ) , ( )
=
=
=
=
39. Determine which of the following functions from Z to Z is one-to-one
(a) f n n
( ) = −1
(b) f n n
( ) =
+
2
1
(c) f n n
( ) =
3
(d)
 
f n
n
( ) =
2
40. Determine which of the following functions is a bijection from R to R.
(a) f x
x
( ) = +
3 1
(b) f x
x
( ) =
+
2
1
2
(c) f x
x
( ) = 3
3
(d) f x
x
x
( ) (
) (
)
=
+
+
2
2
1
4
42. If g is a function from A to B and f is a function from B to C.
(a) Show that if both f and g one onto functions, then f B g is also onto.
(b) Show that if both f and g are one-to-one functions, then f B g is also
one-to-one.
43. If f and f B g are one-to-one, does it follow that g is one-to-one? Justify
your answer.
44. Find f B g and g of where f x
x
( ) =
+
2
1
2
and g x x
( ) = + 5 are functions
from R to R.
48
Theory of Automata, Formal Languages and Computation