B4.2-R3: Discrete Structures

B4.2-R3: Discrete Structures

Chapters / Jan-04 / Jul-04 / Jan-05 / Jul-05 / Jan-06 / Jul-06 / Jan-07 / Jul-07 / Jan-08 / Total
01. Sets, Relations & Functions / 22 / 25 / 27 / 37 / 28 / 28 / 25 / 30 / 36 / 258
02. Mathematical Logic / 0 / 22 / 2 / 7 / 10 / 16 / 14 / 6 / 6 / 83
03. Boolean Algebra / 10 / 10 / 18 / 24 / 10 / 22 / 19 / 24 / 10 / 147
04. Number Theory / 9 / 27 / 20 / 9 / 0 / 10 / 12 / 6 / 4 / 97
05. Groups & Subgroups / 18 / 12 / 22 / 7 / 10 / 18 / 14 / 16 / 6 / 123
06. Combinatorics & Recurrence Relation / 34 / 4 / 16 / 17 / 28 / 12 / 12 / 15 / 16 / 154
07. Graph Theory / 25 / 21 / 19 / 26 / 10 / 22 / 18 / 23 / 36 / 200
08. Finite State Machines & Languages / 18 / 15 / 12 / 9 / 22 / 8 / 22 / 16 / 22 / 144
Total / 136 / 136 / 136 / 136 / 118 / 136 / 136 / 136 / 136 / 1206

1. Sets, Relations & Functions

January-2004 [22]

a)In a science fair of a school, 34 students received awards for scientific projects. Out of which 14 awards were given for projects In Physics, 13 in Biology and 21 In Chemistry. If 3 students received awards in all three subjects, find the number of students received awards for exactly (i) one subject (ii) two subjects. [7]

b)Let A be the set of strings of 0's and 1's of length 3 or less. Define the relation of R on A by xRy if x is contained within y. Draw the Hasse diagram for this relation. [7]

a)Let A = {1,2,3,4.5} X {1.2,3.4.5} and define a relation R on A by (x1,y1)R{ x2,y2) if x1+y1=x2+y2. Show that R is an equivalence relation on A. Determine the equivalence classes [(1,3)],[(2,4)] and [(1,1)]. [8]

July-2004 [21]

a)Let and let Compute

ii)

iii)

iv) (Power set) [4]

c)Let S be a finite set, with | S | = n. Find

i)Number of functions from S to S.

ii)Number of 1 – 1 functions from S to S.

iii)Number of functions from S onto S. [9]

f)Give the Hasse diagram for the following partial order:

ii) [2]

b)Letbe defined by. Letbe defined as

Calculate

ii)

iii)

iv)

vi) [6]

January-2005 [27]

a)Each of the following defines a relation on the positive integers N:

1)x is greater than y

2)xy is the square of an integer

3)x + y = 10

4)x + 4y = 10

Determine, which relations are (i) reflexive (ii) symmetric (iii) anti-symmetric (iv) transitive.

[4]

a)Prove the following:

Let f : A  B and g : B  A be functions such that g o f = 1A and f o g = 1B. Then f is a one-to-one correspondence between A and B, g is a one-to-one correspondence between B and A and each is the inverse of the other. [5]

b)Prove or disprove that if a relation on a set A is transitive and irreflexive, then it is asymmetric. [5]

c)Consider the following assumptions:

S1: All dictionaries are useful

S2: Mary owns only romance novels

S3: No romance novel is useful

Determine the validity of each of the following conclusions:

i)Romance novels are not dictionaries

ii)Mary does not own a dictionary

iii)All useful books are dictionaries

Use Venn diagram to show the representation. [5]

d)Find the Power set of A = {1,2,3,4,5 } [3]

d)Prove by mathematical induction the following:

12 + 22 + 32 + … n2 = (n(n+1)(2n+1))/6 [5]

July-2005 [37]

a)Let R1 and R2 be binary relations defined on set of positive integer by

R1={(a,b) : a-b is an odd positive integer}

And R2={(a,b) : a=b2}.

Is R1 transitive? Is R2 anti-symmetric? Why? [4]

a)i)LetA = {n3 : n is a positive integer}

B = {n2 : n is a positive integer}.

Find A  B. Is the set A  B countable? Justify. [4]

ii)Let x and y be the sets such that x – y = y. Show that both x and y are empty sets. [2]

b)Let x = {1, 2, 3}.

i)How many reflexive relations can be defined on x? [3]

ii)If R ={(1,2), (2,3), (2,1)}, find the smallest transitive relation on x containing R. [5]

c)Let A= {0, 1, 2, 3, …}. Define function f,g and h from A to A by

, and = 0, when x is even.

1, when x is odd.

Is one-one? Is onto? Compute [4]

b)Using mathematical induction, show that

for all [6]

c)Let A = {1, 2, …, 11}. Let R = {() : =3mfor some integer m}

Show that R is equivalence relation. Also, find all the equivalence classes. [5]

a)Let R denote the set of real numbers. Define a function by f() = 3-1 R. If invertible? If yes, find . [4]

January-2006 [28]

a)Can a relation R in a set A be both symmetric and anti symmetric? Justify your answer.

[4]

a)Suppose R is an arbitrary transitive and reflexive relation on a set A. Prove that the relation E defined by “x E y iff x R y and y R x” is an equivalence relation. [9]

b)Prove or disprove the validity of the following argument:

i)Every living thing is a plant or animal.

ii)Ram’s dog is alive and is not a plant.

iii)All animals have heart.

iv)Hence Ram’s dog has a heart. [9]

a)Prove that is R is a partial ordering relation on a set S, then for n  2,there can not be a sequence s1, s2, s3,…. sn of distinct elements of S such that s1 R s2 R s3…RsnRs1. [6]

July-2006 [28]

a)i)Determine the power sets of {, {  }}.

ii)Let S={2, 5, 2, 25, , 5/2} and T ={4, 25, 2, 6, 3/2}

Find ST and Tx(ST). [4]

b)For integers a,b, define a ~ b if and only if 2a + 3b = 5n for some integer n. Show that ~ defines an equivalence relation on Z. (set of Integers). [4]

d)Draw the Hassediagrams for each of the following partial orders.

i)( { 1,2,3,4,5,6}, )

ii)( { {a},{a,b},{a,b,c},{a,b,c,d},{a,c},{c,d} }, ) [4]

g)Show that the functions and

Defined by f(x)=32x+1, are inverse of each others. [4]

c)In a group of 25 students, 12 have taken Mathematics, 8 have taken Mathematics but not Biology. Find the number of students who have taken Mathematics and biology and those who have taken Biology but not Mathematics. [6]

a)Prove by mathematical induction the following, 3n>n3 for n>3. [6]

January-2007 [25]

a)i)If A=  and B={{{a}}},  } then Find (P(P(A))) and P(B). (P denotes Poset Set).

ii)Let A={1, 2, 3, 4, 5} and B={4, 5, 6, 7}. Compute i) A-B, ii) AXB [4]

c)Let X={2, 3, 6, 12, 24, 36} and the relation  be such that x  y if x divides y. Draw the Hasse diagram of < X,  >. [4]

c)In a room containing 25 females, there are 18 females who speak English, 15 females speak French and 22 speak German. 9 females speak both English and French, 11 females speak both French and German whereas 13 speak both German and English. How many females speak all the three languages? [5]

d)Find all Partitions of S={1, 2, 3}. [3]

d)Prove that the relation, “Divides” is a POSET. [3]

b)Prove by mathematical inductions the following, 2n>n3 for n  10. [6]

July-2007 [30]

a)i)Let A={0, 1, 2, 3, …}. Define function f, g and h from A to A by f(x)=2x, g(x)=x+1 and

where . (Treat ‘0’ as an even number). Find (fg) h and hf.

ii)If

and

than find X ∩ Y. [4]

b)Draw the Hasse diagram of D8, the lattice factors of 8 under the relation of ‘divisibility’. Is it totally ordered? [4]

c)Let f and g be permutations defined on the set {1,2,3,4,5} by and . Find f -1 X and f g. Also, express g as a product of transpositions. [4]

a)Let A={a,b,c}. Let R be a relation defined on A by R={(a,b), (b,a),(c,c)}. Find the reflexive, symmetric and transitive closures of the relation R. [6]

b)i)Define ‘difference’ and ‘symmetric difference’ of two sets.

ii)Find the number of integers between 1 and 250 that are divisible by either 6 or 8. [6]

c)Using the principle of mathematical induction, prove that for all [6]

January-2008 [36]

a)Let Dn = (0, 1/n) where n  N: the set of positive integers Find [4]

b)Find the power set of A = {(a,b),c)}. [4]

f)A function f is defined on the set of integers as follows:

Find its domain, range and check for one-one or many one. [4]

a)If R be a relation on the set of integers Z defined by

R = { (x y) : x Z, y Z : x – y is divisible by 3}

Describe the distinct equivalence classes of R. [6]

b)Show that the mapping f : R  R is defined by f(x) = ax +b where a, b, x R, a 0 is invertible. Define its inverse. [6]

c)Consider the poset A = {1,2,3,4,6,9,12,18,36}, I), find the greatest lower bound and the least bound of the sets {6, 15} and {4, 6, 9}. [6]

c)Use mathematical induction to prove that 1+2+3+ … +N=. [6]

2. Mathematical Logic

January-2004 [0]

July-2004 [26]

b)Let Q be the set of all rational numbers, then if the relation is defined as:

; for [4]

d)Construct truth tables for the following wffs. Note any tautology or contradiction or contingents.

ii) [4]

2.Prove the following (do not use a truth table).

a) [6]

b) [6]

c) [6]

January-2005 [2]

g)P(x) : x is even Q(x) : x is prime R(x,y) : x + y is even. The variables x and y are integers. Write English sentence corresponding to each of the following:

i)~( x P(x))

ii)~( x Q(x)) [2]

July-2005 [7]

b)Express the following proposition in symbolic form:

“If I work hard then I get good marks.”

Also, Write its converse, inverse and contrapositive in symbolic form. [3]

d)There are two restaurants next to each other. One has a signboard that says “good food is not cheap” and the other has a signboard that says “cheap food is not good”. Are the two signboards say the same thing? Justify. [4]

January-2006 [10]

b)Write the negation of the following by changing the quantifiers:

“Every complete bipartite graph is not planer.” [4]

b)Obtain the principal conjunctive normal form and principal disjunctive normal form of the formula S given by

(P R)  (Q P) [6]

July-2006 [16]

f)Write the converse, inverse and contrapositive of PQ. [4]

a)Find the principal disjunctive normal form of (PQ)  (~PR)  (QR). [6]

b)Show that ~ (PQ) follows from ~ P~Q. [6]

January-2007 [14]

e)Letp: Food is good

q: service is good

r: restaurant is 5-star

Write following in Symbolic notations

i)It is not true that five star restaurant always means for good food and good service.

ii)Food is good but service is poor. [4]

a)Find the Principal Conjunctive Normal Form of the formula (~ p  R) Λ (QP). [5]

b)Test the validity of the following argument:

If I study, then I will not fail in Mathematics

If I do not play basket ball, then I will study

But I failed Mathematics

Therefore, I must have played basketball. [5]

July-2007 [6]

c)i)State the ‘law of detachment’ and ‘Chain rule’.

ii)Using the laws of logic, prove that . [6]

January-2008 [6]

a)Is the proposition s a valid conclusion from the premises p q, q r, ( q r) and s  p ? [6]

3. Boolean Algebra

January-2004 [10]

b)For each of the networks In the following figurer express the output In terms of the Boolean variables x, y or their complements. Then use the expression for the output to simplify the given network.

[10]

July-2004 [10]

b)Use the Quine-McCluskey’s procedure to find the minimal sum of product form of the expression given below. If there is more than one equivalent solution, find all of them.

x1 x2’ x3 x4’ + x1’ x2’ x3 x4’ + x1’ x2 x3 x4’ +

x1’ x2’ x3’ x4’ + x1’ x2 x3’ x4’ + x1’ x2’ x3’ x4 [10]

January-2005 [18]

a)Use a Karnaugh map to find a minimal sum-of-products form for

E = xyp + xyz + xpypxp + xpyztp [5]

b)Apply Boolean arithematic to show that the following equality is valid

(xp V x) (( x  y) V z )  ( zp V y ) = x  y [5]

c)Consider the founded Lattice L in the following fig.

i)Find the complements, if they exist, of e and f.

ii)Express I in the irredundant join irresucible decomposition in as many ways as possible.

iii)Is L distributive?

iv)Describe the isomorphisms of L with itself. [8]

July-2005 [24]

c)Let x, y, z be the variables in Boolean algebra. Show that

[4]

a)Which of the posets given in the following diagram are lattices? Why?

Find minimal and maximal elements in diagram (i). Also find p(qr) in diagram (iii). [6]

c)Using Karnaugh map, find a minimal sum of products form for

E=(xy’)(xyz) (x’y’z’) (x’yzt’) [6]

c)State ‘absorption’ and ‘Demorgan’s‘ laws of Boolean algebra. [2]

d)Put the Boolean function f(x,y,z)= (xy’)(x’z) in CNF (Conjunction Normal Form). [6]

January-2006 [10]

c)Prove absorption low in a Boolean algebra. [4]

b)Minimize following switching function

m(0, 2, 8, 12, 13). [6]

July-2006 [22]

a)For any a, b, c, d in a lattice (A, ), if a  b and c  d then Prove that (a c) (b d) and (a c) (b d) (where  is join and  is meet operation). [6]

b)Prove that if the meet operation is distributive over the join operation in a lattice, then the join operation is also distributive over the meet operation. [6]

c)Minimize the following expressions using Karnaugh map. [6]

a)Prove that for any a and b in a Boolean algebra

and

[4]

January-2007 [19]

d)What do you mean by DUAL of a statement in Boolean algebra? [4]

a)Prove that both join and meet operations in Lattice algebra and associative. [5]

b)Prove that, in a distributive lattice, if an element has a complement then this Complement is Unique. [5]

c)Find a minimal sum for the Boolean expressions:

E= x +x’yz + xy’z [5]

July-2007 [24]

a)Define ‘Sublattice of a lattice’. Let A={a,b,c}. Let L be the lattice of power set of A under the relation of ‘Contained in’. Let S={,{a}, {b,c}, A}. Then

i)find (a,b) Λ {b,c} in A.

ii)is the set S, a sublattice of L? Justify. Also, draw the Hasse diagram of S. [7]

b)Define the term ‘Boolean Algebra’. State DeMorgan’s laws in a Boolean algebra. Prove any one of them. [5]

b)In any Boolean algebra define terms ‘PDNF’ and ‘PCNF’. Express the following Boolean function and its complement in PDNF:

(x,y,z) / f(x,y,z)
(0,0,0) / 1
(0,0,1) / 0
(0,1,0) / 1
(0,1,1) / 0
(1,0,0) / 0
(1,0,1) / 1
(1,1,0) / 0
(1,1,1) / 1

[7]

c)Simplify, using Karnaugh map the following Boolean function . [5]

January-2008 [10]

g)Simplify f(x,y) = x y’ + xy + x’y [4]

b)Use Karnaugh map to simplify the expression

X = A’B’CD + A’B’CD’ + AB’CD’ + AB’ CD’ [6]

4. Number Theory

January-2004 [9]

a)Find the number of positive integers n where 1  n  100 and n is not divisible by 2,3 or 5.

[9]

July-2004 [27]

e)How many numbers between 100 and 999 inclusive are divisible by 5. [3]

3.Let nth Fibonacci sequence be defined by:

Then

a)Give a closed form formula for the nth term in the sequence. [7]

b) [7]

c) [4]

a)Let n be a positive integer The is – congruent – to – mod – n relation is an equivalence relation on the set of positive integers. [6]

January-2005 [20]

c)Solve the linear congruence equation

i)132x= 169 ( mod 735)

ii)48= 284(mod 356) [2]

a)Write Euclidean algorithm to find gcd(a,b) of two non-negative, non-zero integers a and b. [5]

b)Suppose a  c (mod m) and b  d(mod m) then prove the following:

i)a + b  c + d ( mod m)

ii)a . b  c . d ( mod m) [5]

c)Define RSA Public Key Encryption and give the formula for ab mod z [3]

d)Prove d= gcd(a,b) considering d to be ther smallest positive integer of the form ax + by. [5]

July-2005 [9]

e) i)Solve the congruence 3x 5 (mod 7).

ii)If H.C.F. of a and b is 1 and both a and b divide c, then prove that a b also divides c. (a, b, c are positive integers) [4]

b)Determine the number of integers between 1 and 200 that are divisible by at least one of the integers 2, 3, 5. [5]

January-2006 [0]

July-2006 [10]

c)If Fn satisfies the Fibonacci relation for the Fibonacci series (1,1,2,3…) defined by the recurrence relation, Fn = Fn-1+Fn-2, F0=F1=1 then prove that nth Fibonacci number is given by (for n = 0,1,2,3, ------).

[6]

d)Calculate the greatest common divisor of 240 and 70(Step wise) by using Euclid’s algorithm. [4]

January-2007 [12]

a)Find integers m and n such that 512 m + 320 n = 64. [5]

c)If Fn satisfied the Fibonacci relation for the Fibonacci series (1, 1, 2, 3,…) define by the recurrence relation, Fn =Fn-1 + Fn-2, F0 = F1, then find a formula to find nth Fibonacci number. [7]

July-2007 [6]

c)Solve the simultaneous congruences . [6]

January-2008 [4]

c)Show that the greatest common divisor is unique. [4]

5. Groups & Subgroups

January-2004 [18]

a)Define the binary operation o on Z by x o y = x + y + 1. Show that (Z. o) is an Abelian group. [9]

b)Let <C;*> be a subgroup of the group <G, *> and let a and b be any elements of G. Then show that either C * a = C * b or (C * a)  (C * b) = . [9]

July-2004 [12]

b)Let G=< Z/4,  > be a group, where Z/4 denotes the set of integers module 4 w.r.t the operation  - the addition module 4. Let H={[0], [2]} be a subgroup of G. Find the left cosets of H. [6]

c)Give examples of following with justification:

i)a semigroup without identity.

ii)A subgroup of a group which is not normal.

iii)Non-commulative group. [6]

January-2005 [22]

b)Let G be a group and let a be a fixed element of G. Show that the functions fa : G G defined by fa(x) = axa-1 for xG, is an isomorphism. [4]

a)Let A = {a,b,c} and consider the semigroup (A*, .), where . is the operation of concatenation. If  = abac,  = cba,  = babc, compute

i)(.).
ii).(.)
iii)(.). [6]

b)Describe the quotient semigroup for S = Z with ordinary addition and R defined by a R b,

if and only if a = b (mod 5) [4]

c)Let (G, *) and (G1, *1) be two groups, and let f: G  G1 be a homomorphism from G to G1. then prove the following:

i)If e is the identity in G and e1 is the identity in G1, then f(e) = e1;

ii)If a  G, then f ( a -1 ) = ( f (a) ) -1 [8]

July-2005 [7]

d)Let G be the commutative group.

Let H ={x G : x2 = e}, show that H is subgroup of G. [3]

c)i)Give an example of a non-abelian group. [2]

ii)Find the generators of the group (G, *) where G = {1,2,3,4} and * = multiplication module 5. [2]

January-2006 [10]

g)Let (A,*) be an algebraic system, where * is a binary operation such that for any a and b in A

a*b = a

Show that this operation is associative. [4]

c)Consider the group (Z4, ): the integer modulo 4 group with respect to the operation  : addition modulo 4. Does H={[0], [2]} form a subgroup of Z4. If yes, is it a normal subgroup? Justify. [6]

July-2006 [18]

c)Define a Monoid. [4]

b)Define the following terms:

i)Permutation of a set

ii)Abelian group

iii)Subgroup

iv)Group Homomorphism. [8]

c)Prove that every finite group of order n is isomorphic to a permutation group of degree n. [6]

January-2007 [14]

b)Show that every cyclic group of order n is isomorphic to the group <Zn, †n>. [4]

a)Prove that composition of two homomorphism is also a homomorphism. [5]

b)If {G, *} is an abelian group, show that (a * b)n=an * bn, for all a, b Є G, where n is a positive integer. [5]

July-2007 [16]

e)Define the terms ‘Monoid’ and ‘Group’. Give an example of a group which is not a monoid. [4]

a)Define the term ‘Cyclic group’. Let G={1,2,3,4}. Show that G is a group under the binary composition  5, the multiplication modulo 5. Is G cyclic? Justify. [6]

b)i)Let G be any group is which every element is its own inverse. Show that G is abelian.

ii)Let (a,) be a commutative semi-group, show that if aa = a and bb = b, b then (a*b)*(a*b) = a*b. [6]

January-2008 [6]

a)Let ({a, b}, *) be a semigroup where a*a=b. Show that:

i)a*b = b*a

ii)b*b = b [6]

6. Combinatorics & Recurrence Relation

January-2004 [34]

c)Find the coefficient of x5 in (1-2x)-7. [7]

b)Find the number of ways that one can distribute a dozen apples among 5 children so that no child gets more than 7 apples. [9]

5.Derive the recurrence relation to find the number of distinct binary trees that can be generated with n nodes. Also obtain its solution. [18]

July-2004 [4]

a)In how many ways can a committee of 5 men 7 women be selected out of a panel of 17 men and 23 women? [4]

January-2005 [16]

e)In how many ways can 10 students be divided into three teams, one containing four students and the others three? [3]

i)Define the principle of mutual exclusion and inclusion. [3]

a)Assume that deer population in a country is 200 at time n = 0 and 220 at time n = 1 and that the increase from time n – 1 to time n is twice the increase from time n – 2 to time (n – 1). Write a recurrence relation and an initial condition that define deer population at time n and then solve the recurrence relation. [6]

c)Develop a formula for the solution of a recurrence relation of the form

an = m a n – 1 - 1, a1 = m [4]

July-2005 [17]

g)State pigeon hole principle. Use it to show that in any set having eleven or more positive Integers, there are at least two whose difference is divisible by 10. [4]

a)i)Solve the recurrence relation

an – 4 an -1 + 4 an- 2 = (n+1) 2n [7]

ii)Find the generating function of the sequence

1, a, a2, a3, …

where ‘a’ is a constant. [2]

b)If the letters of the word PRIME are arranged as in dictionary (with or without meaning), find the relative position of word PRIME in this arrangement. [4]

January-2006 [28]

d)How many ways can one right and one left shoe be selected from 10 pairs of shoes without obtaining a pair? [4]

a)Solve the following:

an = 2 a n-1 + 1

where

a0 =0

a1 =1

a2 =3. [9]

b)Find a generating function to count the number of integral solutions of

e1 + e2+ e3 = 10 if for each i, 0  e1 [9]

c)State pigeon hole principle show that in a sequence of n2+1 distinct integers, there is either an increasing subsequence of length(n+1) or decreasing subsequence of length. [6]

July-2006 [12]

a)In how many ways 7 women and 3 men are arranged in a row if the 3 men must always stand next to each other. [6]

b)i)State pigeonhole principle.

ii)Suppose that a patient is given a prescription of 45 pills with the instruction to take at least one pill per day for 30 days. Then prove that there must be a period of consecutive days during which the patient takes a total of exactly 14 pills. [6]

January-2007 [12]

f)How many ways can the letters in word MISSISSIPI can be arranged? [4]

c)A bag can contain six white balls and five red balls. Find the number of ways, four falls can be drawn from the bag if two must be white and two red. [5]

d)State pegions holes principle. [3]

July-2007 [15]

d)A family of 4 brothers and 3 sisters is to be arranged for a photograph in one row. In how many ways they can be seated if

i)all the sisters sit together.

ii)no two sisters sit together. [4]

a)Solve the recurrence relation: an-7an-1+10an-2=3n given that a0=0 and a1=1. [6]

a)In a cricket tournament, seven teams participate. Each team play with the remaining six teams and each team win at least one game. Find the total number of matches to be played. Also, using pigeon-hole principle, show that there are at least two teams having the same number of wins. [5]

January-2008 [16]

e)What is the coefficient of x3 y2 z2 in (x + y + z)9. [4]

b)Solve the recurrence relation

an + 5an-1 + 6an-2 = 3n2 [6]

c)A computer password consists of a letter of the alphabet followed by three or four digits. Find the total number of passwords that can be formed, and also the number of passwords in which no digit repeats. [6]

7. Graph Theory

January-2004 [25]

d)Seven towns K. C, B, M. A, D and L are connected by a system of highways as follows:

i)H1 goes from K to B through C.

ii)H2 goes from B to M and then passes through C as it continues to D.

iii)H3 goes from M through A to K.