| Website for students | VTU NOTES

Computer Science & Engg/Information Science & Engg

Semester: 3rd

Sub Code:06CS34

Sub Name: Discrete Mathematical structures

Instructions: Answer any five questions selecting at least two questions from each part.

1. (a) Prove that : A ∆ B = (B∩A)  (A B) = (B-A)(A-B)6 marks

(b) Show by means of an expression that A x B  B-A and (AB)-(AB) = (A-B)

(B-A)5 marks

(c) Out of 30 students in a dormitory, 15 take an art course, 8 take a biology course,

and 6 take a chemistry course. It is known that 3 students take all three courses.

Show that 7 or more students take none of the course.6 marks

(d) Define countable set with example.2 marks

  1. (a) If statement q has the truth value 1, determine all truth value assignments for

the primitive statements p, r, and s for which the truth value of the statement

[q{pr)s}]  {s (r  q)} is 1.4 marks

(b) Prove the validity of the following argument

u r

(rs)(pt)

q(us)

t Therefore qp6 marks

(c) Prove the following equivalence without the truth table:

(i) p[p  (pq)]  p

(ii) {{pq)r}q]  q  r6 marks

(d)Define the terms: Rule of syllogism, Modus ponens.

Test whether the following argument is valid:

If Ram’s computer program is correct then he will be able to complete his computer science assignment in at most two hours.

It takes Ram over two hours to complete his computer science assignment.

Therefore Ram’s computer program is incorrect.4 marks

  1. (a) For a prescribed universe and any open statement p(x), q(x) in the variable x, prove that : x [p(x) v q(x)] x p(x) v x q(x) 4 marks

(b) Write down the following proposition in symbolic form, and find its negation,

(i) For all integers n, if n is not divisible by 2, then n is odd.

(ii) All integers are rational numbers and some rational numbers are not integers.

(iii) For the universe of integers, if r(x): 2x +1 = 5; s(x): x2 =9 are open sentences. Obtain the negation of a quantified statement x [r(x)s(x)]. 6 marks

(c) For the universe of all people, find whether the following is a valid statement:

All mathematics professors have studied calculus

Ramanujan is a mathematics professor

Therefore Ramanujan has studied calculus.6 marks

(d)Define the Rule of Universal specification and the Rule of Universal

Generalization.4 marks

  1. (a) State the following:

(i) Well-Ordering Principal

(ii) Principal of mathematical induction.5 marks

(b) Prove by mathematical induction

(i)For every positive integer n, 3 divides (n3 – n).

(ii)For all positive integers n>=6, 4n < ( n2-7).10 marks

(c) If nN, prove that 5Fn+2 =L n+4-L n.5 marks

5. (a)Let R and S are symmetric relations on the set A. Prove that intersection of these two is

also symmetric.4 marks

(b) Define stirling number of the second kind . Let a={1,2,3,4,5,6,7} and B={w,x,y,z} find

the number of onto functions from A to B7 marks

(c) Let T be the set of all triangles. Define a relation R on T by t1 R t2 if t1and t2 have an

angle of same measure. Verify whether R is an equivalence relation. 5 marks

(d) Prove that a function f : AB is invertible iff it is one-one and onto. 4 marks

  1. (a) Define the different properties of relation with examples.4 marks

(b) Verify that (A, R) is a poset and draw its Hasse diagram where u= {1,2,3}, A =

p(u) and R is a subset relation on A.8 marks

(c)Let A = {1,2,3,4,5}. Define a relation r on A x A as (x1, y1)) R (x2, y2) if x1 + y1 = x2 + y2

(i)Verify that R is an equivalence relation

(ii)Determine the equivalence classes {(1, 3)],[(2, 4)], and [(1,1)]

(iii)Determine the partition on A induced by R.8 marks

  1. (a) Define an abelian group. Let (G, *) be the set of all non-zero real numbers and let

a*b = !ab. Show that (G, *) is an Abelian group.8 marks

(b) Define acyclic group with an example. Prove that every cyclic group is abelian.

6 marks

(d) If (G, *) and (H,*) are groups with respective identities eG and eH , and f : G  H is an

isomorphism, prove that f(eG) = eH.6 marks

  1. (a) Prove that in a group code the minimum distance between distinct code words is the

minimum of the weights of the nonzero elements of the code6 marks

(b) Define a group code. Consider the encoding function E: Z2 2 > Z2 6 of the triple repetition

code where E(00)=000000, E(10) = 101010, E(01) = 010101, E(11)=111111. Prove that C

= E(Z2 2) is a group code.8 marks

(c) Define a ring. If R is a ring with unity and a,b are units in R Prove that ab is a unit in R

and that (ab)-1=b-1a-16 marks

| Website for students | VTU NOTES