DM Assignment 1 OSS
DM Assignment 1 OSS
DM Assignment 1 OSS
Ques 7: Show that the set of Positive Rational number is Countable. Let the list of
positive rational numbers as sequence r1 , r2 , r3, r4,. rn, Note that every Positive
rational number is a quotient p/q of positive integers.
Ques 8: Find the cardinality of the set A U B where A and B are any arbitrary sets.
Ques 9: Among Integers 1 to 300
a. How many of them are divisible neither by 3 nor by 5 , nor by 7?
b. How many of them are divisible by 3 but not by 5 nor by 7?
Ques 10: It is known that in university 60 % of professors play tennis , 50 % of them
play bridge , 70% jog, 20 % play tennis and bridge, 40 % play bridge and jog and 30 %
play tennis and jog. If someone claimed that 20 % professors jog and play tennis and
bridge, would you believe his claim? Why?
Ques 11: Draw a Venn diagram and test the validity of the following argument:
All guilty people will be arrested. All thieves are guilty people. Therefore, all thieves
will be arrested.
Ques12:
a. Prove the identity: (A U B) ( A U BC ) = A
b. Prove (A U B) \(A B) = ( A/B) U (B|A)
Ques 13:
a. Find all the partitions of S = {1,2,3}
b. Determine the power set Power (A) of A = {a,b,c,d}
B. FUNCTIONS
Ques14: let the functions f and g be defined by f(x)=2x+1 and g(x)=x2 2. Find the
formula defining the composition function g o f.
Ques 15: Let f: R R be defines by f(x) = 2x-3. Now f is one to one and onto; hence f
has an inverse function f-1. Find the formula for f-1?
Ques 16: Find the cardinal number of each set?
A. A ={a,b,c,d.y, z}
B. B= {1,-3,-5,11,-28}
C. C={x:x N, x2= 5}
D. D= {10, 20, 30, 40, 50,}
E. E= {6, 7, 8, 9,}
Ques 17: Let a and b be positive integers, and suppose Q is defined recursively as
follows:
Q(a, b) =0
if a <b
Q((a-b), b)+1
if b<=a
Find :
a. Q(2,5)
b. Q(12,5)
c. What does this function do? Find Q(5861,7)
Ques 18: Sketch the graph of:
a. F(x) = x2+x-6
b. G(x)= x3-3x2-x+3
Ques 19: Consider functions f:A B and g: B C. Prove the following:
A. if f and g are one to one , then the composition function gof is one to one.
B. If f and g are onto functions, then go f is an onto function.
Ques 20: Find the domain of the real valued functions:
a. f(x)= 81-x2
b. f(x)= 25-x2
c. f(x)= x2-3x-4
d. f(x)= 1/ x-2
Ques 21: Let X={1,2,3,4}. Determine whether or not each relation is a function from X
into X.
a. f={(2,3), (1,4),(2,1),(3,2),(4,4)}
b. g={(3,1),(4,2),(1,1)}
c. h= {(2,1), (3,4),(1,4),(2,1),(4,4)}
Ques 22: Consider the following functions and compute:
a.
b.
c.
d.
gof
ho(gof)
(hog)of
Stat e the necessary and sufficient condition on f and g so that:
(1)
g0f is an onto function
(2)
gof to be one to one
(3)
gof to be one to one onto
e. Construct an example to show that for two functions f and g from A to A, in
general, fog g o f
C. RELATIONS
Ques 23:
a. Given : A= {1,2}, b= { x,y,z} and C= {3,4} Find: A X B X C
b. Let A= { 1,2 }, B={a,b,c} and C= {c, m, d}. Find (A X B) (A X C) and (B C)
c. Prove (A
d. X B) (A X C) = A X (B C)
Ques 24: Let A= {1,2,3,4,6} and let r be the relation on a defined by x divides y,
written x|y.(Note x|y iff there exists an integer z such that xz=y.)
a) Write R as a set of ordered pairs
b) Draw its directed graph.
c) Find the inverse relation R-1 of R. Can R-1 be described in word?
Ques 25: Let R and S be the following relations on A ={1,2,3}:
R={(1,1),(1,2),(2,3),(3,1),(3,3)}, S={(1,2),(1,3),(2,1),(3,3)}
Find
a. R S, R U S, Rc
b. RoS
c. S2=SoS
Ques 26: Given A= {1,2,3,4}. Consider the following relation in A:
R= {(1,1),(2,2),(2,3),(3,2),(4,2),(4,4)}
a. Draw its Directed Graph.
b. Is R i) Reflexive ii) Symmetric iii)Transitive or iv) antisymmetric?
c. Find R2 = Ro R
Ques 27: Let A be a set of non zero integers and let be the relation on A X A defined
by (a, b) (c, d) whenever ad= bc. Prove that is an equivalence relation?
Ques 28: Let R be the following equivalence relation on the set A ={ ,2,3,4,5,6}:
R= {(1,2),(1,5),(2,2),(2,3),(2,6),(3,2),(3,3),(3,6),(4,4),(5,1),(5,5),(6,2),(6,3),(6,6)}
Find the partition of A induced by R, i.e. find the equivalence classes of R.
Ques 29: From the following Digraphs, write relation as set of ordered pairs and check
for equivalence or partial ordering.
a.
b.
Ques 31: Find the minimum number n of integers to be selected from S= {1,2,,9} so
that:
a. The sum of two of the n integers is even.
b. The Difference of two of the n integers is 5.
E. MATHEMATICAL INDUCTION
Ques 32: Prove the proposition that the sum of the first n positive integers is n(n+1)/2;
that is
P(n):1+2++n=1/2n(n+1)
Ques 33: Prove the proposition P that the sum of the squares of the first positive integers
is n(n+1)(2n+1)/6; that is
P(n):12+22+.+n2=n(n+1)(2n+1)/6
and
Tn = tn-1 + 4n
for n>=1