MA2265-DISCRETE MATHEMATICS Questions Bank 2014

Anna University, Chennai

Dhanalakshmi Srinivasan Institute of Research and

Technology

Siruvachur, Perambalur - 621113

MA2265-DISCRETE MATHEMATICS QUESTION BANK

Unit – I Logic and Proofs

1. Show that p Ú ( q Ù r ) and ( p Ú q ) Ù ( p Ú r ) are logically equivalent. (N/D 2012)

(Hint: Draw the table with 8 columns.the columns are p,q,r, ( p Ú q ), ( p Ú r ), ( q Ù r ), p Ú ( q Ù r ), ( p Ú q ) Ù ( p Ú r ).)

2. Without using the truth table, prove that Øp ® (q ® r ) º q ® ( p Ú r ) .

(Hint : Using (p ® q ) Þ Ø( p Ú q ). (N/D 2010)

3. Prove (( p Ú q ) Ù Ø(Øp Ù (Øq Ú Ør )))Ú (Øp Ù Øq )Ú (Øp Ù Ør ) is a tautology.

(Hint: Using Demorgan’s law and Distributive law). (N/D 2013)

4.	Without using truth table find the PCNF and PDNF of
	P ® (Q Ù P ) Ù (ØP ® (ØQ Ù ØR)) . (Hint: Using Distributive law and Commutative law).	(A/M 2011)
5.	Find the principal disjunctive normal form of the statement,
	(q Ú ( p Ù r ))Ù ~(( p Ú r ) Ù q ).	(N/D 2012)

(Hint: Using Demorgan’s law and Distributive law and Idempotent Rule).

6. Show that: (P ® Q ) Ù (R ® S ), (Q Ù M ) Ù (S ® N ), Ø(M Ù N ) and

(P ® R ) Þ ØP . (A/M 2011)

(Hint: Using Rule P, Rule T, (Taking Ø),

And Demorgan’s law).

7. Prove that the following argument is valid: p ® Øq , r ® q , r Þ Øp .

(Hint: Using Rule P, Rule T). (M/J 2012)

8.	Prove that the premises a ® (b ® c ),	d ® (b Ù Øc)	and (a Ù d ) are
	inconsistent. (Hint: Using Rule P, Rule T, and
	Demorgan’s law).		(N/D 2010)

9. Using indirect method of proof, derive p ® Øs from the premises

p ® (q Ú r ), q ® Øp , s ® Ør and p . (N/D 2011)

(Hint: Using Additional Property, Rule Pand Rule T).

10. Show that the hypothesis, “It is not sunny this afternoon and it is colder than yesterday”, “we will go swimming only if it is sunny”, “If we do not go swimming, then we will take a canoe trip” and “If we take a canoe trip, then we will be

home by sunset” lead to the conclusion “We will be home by sunset”.

(Hint: Assume the given statements are A,B,C,D and E, then we apply Rule P

and Rule T). (N/D 2012),(N/D 2013)

UNIT – II COMBINATORICS

1. Prove by the principle of mathematical induction, for ' n ' a positive integer,

12 + 2 2 + 3 2 + ... + n2 = n( n + 1)(2 n + 1) . (A/M 2011) (M/J 2012)

6

(Hint: i) we Prove P(1) is true. ii) Assume P(k) is true.

iii) We prove P(k+1) is true from P(k).

2. Using mathematical induction to show that

1 1 1 1

+ + + ... + > n , n ³ 2 . (N/D 2011)

1 2 3 n

(Hint: i) We Prove P(1) is true. ii) Assume P(k) is true.

iii) We prove P(k+1) is true from P(k).

3. Prove by mathematical induction that 6 n + 2 + 72 n+1 is divisible by 43 for each positive integer n . (N/D 2013)

(Hint: i) We Prove P(1) is true. It is divisible by 43. ii) Assume P(k) is true. It is divisible by 43. iii) We prove P(k+1) is true from P(k).

4.	Prove, by mathematical induction, that for all n ³ 1, n 3 + 2	n is a multiple of 3.
	(Hint: i) We Prove P(2) is true. It is multiple of 3. ii) Assume P(k) is true. It is multiple of 3. iii) We prove P(k+1) is true from P(k).	(N/D 2010)

5. State the Strong Induction (the second principle of mathematical induction).

Prove that a positive integer greater than 1 is either a prime number or it can be

written as product of prime numbers. (M/J 2013)

(Hint: i) We Prove P(1) is true. it can be written as product of prime numbers. ii) Assume P(j) is true. j<=k And we take Case i) P(k) is Prime and

Case ii) P(k) is composite.

iii) We prove P(k+1) is true from P(k).

6. What is the maximum number of students required in a discrete

Mathematics

class to be sure that at least six will receive the same grade if there are five possible grades A, B, C, D and F? (N/D 2012)

(Hint: using Generating pigeon hole principle).

7. A box contains six white balls and five red balls. Find the number of ways four balls can be drawn from the box if

(1) They can be any colour

(2) Two must be white and two red

(3) They must all be the same colour

(Hint: using Combinations).

(A/M 2011)

8. Find the generating function of Fibonacci sequence. (N/D 2013)

(Hint: i)Find characteristic equation and solved it. We get the characteristic solution.

ii) find the value of arbitrary constants for C.S.

9. Using the generating function, solve the difference equation

yn +2 - yn +1 - 6 yn = 0, y1 = 1, y0 = 2 . (N/D 2010)

(Hint: By using the Generationg function definition.

i)Find G(x) and the coefficient of xn).

10.Using method of generating function to solve the recurrence relation

a = 4a

n

n -1

- 4a

n -2

+ 4n ; n ³ 2 , given that a

= 2 and a = 8 . (N/D 2011)

0 1

(Hint: By using the Generationg function definition.

i)Find G(x) and the coefficient of xn).

11. There are 2500 students in a college, of these 1700 have taken a course in C, 1000 have taken a course Pascal and 550 have taken a course in Networking. Further 750 have taken courses in both C and Pascal. 400 have taken courses in both C and Networking, and 275 have taken courses in both Pascal and Networking. If 200 of these students have taken courses in C, Pascal and Networking.

How many of these 2500 students have taken a course in any of these three courses C, Pascal and Networking?

How many of these 2500 students have not taken a course in any of these three courses C, Pascal and Networking? (A/M 2011)

(Hint: we consider A,B and C for courses C, Pascal and Networking.

Take the Intersections of all courses. Use the formula (AUBUC).

12. A total of 1232 students have taken a course in Spanish, 879 have taken a course in French, and 114 have taken a course in Russian. Further, 103 have taken courses in both Spanish and French, 23 have taken courses in both Spanish and Russian, and 14 have taken courses in both French and Russian. If 2092 students

have taken atleast one of Spanish, French and Russian, how many students have

taken a course in all three languages? (N/D

(Hint: we consider A,B and C for courses C, Pascal and Networking.

Take the Intersections of all courses. Use the formula (AUBUC).

Unit – III Graph Theory

1. Draw the complete graph K5 with vertices A , B , C , D , E . Draw all complete sub graph of K5 with 4 vertices.

(Hint:By using the complete graph definition) (N/D 2010)

2. Draw the graph with 5 vertices, A , B , C , D , E such that deg( A) = 3 , B is an

Odd vertex, deg( C ) = 2 and D and E are adjacent. (A/M 2011) (N/D 2010)

(Hint: Step 1: Mark the given Vertices.

Step 2: 3 lines connect at the Vertex A. Step 3: 2 lines connect at the Vertex C.

Step 4: we connect the Vertices D and E)

3. Determine which of the following graphs are bipartite and which are not. If a

graph is bipartite, state if it is completely bipartite. (N/D 2011)

(Hint: By using definition bipartite and complete bipartite.

Ist the geiven set of vetices divided into two sets. And then we check each

vertex of one set is adjacent to another set.

4. Prove that an undirected graph has an even number of vertices of odd degree. (N/D

2012)

(Hint: By Using the Handshaking Theorem.

5. Prove that the maximum number of edges in a simple disconnected graph G

with n vertices and k components is (n - k )(n - k + 1) . (N/D 2011)

2

(Hint: we consider sum of the vertices is ‘n’,then taking the square on both

sides and simplify. We apply the result maximum number of edges of G).

6. Show that graph G is disconnected if and only if its vertex set V can be partitioned into two nonempty subsets V1 and V2 such that there exists no edg vertex is in V1 and the other in V2 . (M/J 2012) (Hint: By using the definition of bipartite graph.

i) The necessary part is vertex set is partitioned then we prove the given

Graph is disconnected.

ii) the sufficient part is graph is disconnected ,then we prove vertex set of Ggraph is partitioned

7. If all the vertices of an undirected graph are each of degree k , show that the

number of edges of the graph is a multiple of k . (N/D 2010)

(Hint: (Hint: By Using the Handshaking Theorem).

8. Prove that a connected graph G is Eulerian if and only if all the vertices are

even degree. (M/J 2012),(N/D 2013)

(Hint: Write the definition for Eularian graph.

Find the degree of internal and external

of G

9. Let G be a simple undirected graph with n vertices. Let u and v be two non adjacent vertices in G such that deg( u ) + deg( v ) ³ n in G . Show that G is

Hamiltonian if and only if G + uv is Hamiltonian. (A/M 2011)

(Hint: By using the Dirac theorem for the proof).

---

Unit – IV Algebraic Structures

· Group, Subgroup and Normal Subgroup

1. If (G,*) is an abelian group, show that (a * b ) 2 = a 2 * b2 . (N/D 2010)

(Hint: Assume G is abelian, By using Associative law and left cancellation law).

2. State and prove Lagrange’s theorem.

(N/D 2010),(A/M 2011),(M/J 2012),(N/D 2013)

Lagrange’s Theorem.

Statement:

If G is a finite group and H is a subgroup of G, then |H| divides |G|.

Proof. The right cosets of H in G form a partition of G, so G can be written as a disjoint union G = Ha1 ,…… Hak for a finite set of elements a1, a2, . . . , ak ∈ G.

By Lemma, the number of elements in each coset is |H|. Hence, counting all the elements in the disjoint union above, we see that |G| = k|H|. Therefore, |H| divides |G|.

. If G is of order n , that is, G = n , then a n = e , so that

G = {a , a 2 , a 3 , ..., a n = e} . Further more n is a least positive integer for which

a n = e . (N/D 2011)

(Hint : First suppose that a is of finite order n. then the cyclic subgroup <a> generated by

a, namely <a> = { ak / k ∈ Z}

is of order n. As such, there must be repetitions in the infinite entries in <a>. That is as = at for some positive integers s and t with s > t. This implies that as-t = e. Let m be the smallest of such integer. That is, m is the smallest positive integer such that am = e. if k is any integer, then by division algorithm, we may write k = mq+r where q and r are integers such that 0 ≤ r < m.

Hence ak = aqm+r

= (am )q ar

= eq ar

= ar

Thus, every integral power of a is equal to ar for some positive integer r, 0 ≤ r < m. Hence <a> must be of the form

<a> = {a0 =e, a, a2,……, am-1 }

={ a, a2,……, am = e}

we note that no two elements of <a> shown here can be equal. Because if au=av

for u < v ≤ m, then av-u =e with v-u < m: this is not possible since m is the smallest positive integer such that am=e.

Hence <a> contains exactly m elements as shown. But by hypothesis o(<a>)=n, Hence m=n: that is

<a> = { a, a2,……, an = e}

Thus an = e is the smallest such positive integer. Conversely,

every element of < a> is of the form ar where r is the positive integer such that 0 ≤ r < n; that is,

<a> = {a0 =e, a, a2,……, an-1 }

={ a, a2,……, an = e}

Also, no two elements of <a> shown here can be equal. Hence o(a) = n or a is of order n. This completes proof.

4. Prove that intersection of any two subgroups of a group (G,*) is again a subgroup of (G,*) . (N/D 2013)

(Hint we prove this by using the definition of Subgraph).

5. Prove that intersection of two normal subgroups of a group (G,*) is a normal subgroup of a group (G,*) . (M/J 2013) (Hint we prove this by using the definition of

Subgraph).

6. Prove that every cyclic group is an abelian group. (N/D 2013)

(Hint: Let G be a cyclic group and g be a generator of G. Consider any a, b ∈ G. Then a= gm

and b = gn for some integers m and n.

Hence ab = gm gn

= gm+n

= gn+m

=gn gm

=ba

This shows that G is abelian).

7. Prove that the necessary and sufficient condition for a non empty subset H of a group G,* to be a sub group is a , b Î H Þ a * b -1 Î H . (N/D 2012)

(Hint: Let H be a subgroup of G.

So H is a group by itself and hence for all a, b in H we have a, b-1 H and so a*b-1 H. Conversely, suppose for all a, b in H if a * b-1 H.

(i) For a H, take b = a we have a * a-1 = e H. (ii) For b H, take a = e then e * b-1 = b-1 H.

(iii) For a H, take b = b-1 => a * (b-1) -1 = a * b H.

Thus by (i), (ii), (iii), H is a group and hence a subgroup of G.

---

Unit – V

Lattices and Boolean algebra

· Partially Ordered Set (Poset)

1. Show that ( N , £) is a partially ordered set where N is set of all positive

integers and £ is defined by m £ n iff n - m is a non-negative integer.

(Hint we prove i) R is reflexive.

ii) R is Antisymmetric.

iii) R is partial order relation). (N/D 2010)

2. Draw the Hasse diagram for (1) P1 = {2, 3,6,12, 24} (2) P2 = {1, 2, 3,4,6,12} and

£ is a relation such x £ y if and only is x | y . (A/M 2011)

(Hint: Using the Hasse diagram for (X,R).

3. Prove that every chain is a distributive lattice. (N/D 2013)

(Hint: We prove (L,⋀,∨) satisfies Distributive property).

4. Prove that every distributive lattice is modular. Is the converse true? Justify your claim. (A/M 2011) (Hint: we take (L,⋀,∨) is

Distributive lattices).

5. Prove that Demorgan’s laws hold good for a complemented distributive lattice(Hint: Using the distributive rule ,Associative rule (N/D 2011),(M/J 2013)

6. Let B be a finite Boolean algebra and let A be the set of all atoms of B . Then prove that the Boolean algebra B is isomorphic to the Boolean algebra P ( A) ,

where P ( A) is the power set of A . (M/J 2012)

(Hint: We prove by using the induction method and definition of Boolean algebra).