BT0069, Discrete Mathematics

Dear students get fully solved  SMU BSC IT assignments

Send your semester & Specialization name to our mail id :

“ help.mbaassignments@gmail.com ”

or

Call us at : 08263069601

ASSIGNMENT

PROGRAM	BSc IT
SEMESTER	SECOND
SUBJECT CODE & NAME	BT0069, Discrete Mathematics
CREDIT	4
BK ID	B0953
MAX.MARKS	60

Q.1 If U = {a,b,c,d,e}, A ={a,c,d}, B = {d,e}, C = {b,c,e}

Evaluate the following:

(a) A’ ´ (B-C)

(b)(AÈB)’´(BÇC)

(c)(A-B)´(B-C)

(d)(BÈC)’´A

(e)(B-A)´C’

Answer:

(a) A’ ´ (B-C)

A’ = set of those elements which belong to U but not to A.

A’ = (b, e)

(B-C) = (d)

 A’ ´ (B-C) = (b,e)´(d)

(b)(AÈB)’´(BÇC)

(AÈB) = (a, c, d, e)

(AÇB)’ = (b)

2 (i) State the principle of inclusion and exclusion.

(ii) How many arrangements of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 contain at least one of the patterns 289, 234 or 487? 4+6 10

Answer:

I)                    Principle of Inclusion and Exclusion

For any two sets P and Q, we have;

i) |P ﮟ Q| ≤ |P| + |Q| where |P| is the number of elements in P, and |Q| is the number elements in Q.

ii) |P ∩ Q| ≤

3 If G is a group, then

i) The identity element of G is unique.

ii) Every element in G has unique inverse in G.

iii)

For any a єG, we have (a-1)-1 = a.

iv) For all a, b є G, we have (a.b)-1 = b-1.a-1.   4x 2.5 10

Answer:  i) Let e, f be two identity elements in G. Since e is the identity, we have e.f= f. Since f is the identity, we have e.f = e. Therefore, e = e.f = f. Hence the identity element is unique.

ii)Let a be in G and a1, a2 are

4 (i) Define valid argument

(ii) Show that ~(P  ^Q) follows from ~ P ^ ~Q. 5+5= 10

Answer: i)

Definition

Any conclusion, which is arrived at by following the rules is called a valid conclusion and argument is called a valid argument.

ii) Assume ~(~(P ÙQ)) as an additional premise. Then,

5 (i) Construct a grammar for the language.

'L⁼{x/ xє{ ab} the number of as in x is a multiple of 3.

(ii)Find the highest type number that can be applied to the following productions:

1. S→ A0, A → 1 І 2 І B0, B → 012.

2. S → ASB І b, A → bA І c ,

3. S → bS  І bc.  5+5 10

Answer: i)

Let T = {a, b} and N = {S, A, B},

S is a starting symbol.

The set of productions: F

6 (i) Define tree with example

(ii) Any connected graph with ‘n’ vertices and n -1 edges is a tree. 5+5 10

Answer: i)

Definition

A connected graph without circuits is called a tree.

Example

Consider the two trees G1 = (V, E1) and G2 = (V, E2) where V = {a, b, c, d, e, f, g, h, i, j}

E1 = {{a, c}, {b, c}, {c, d}, {c, e}, {e, g

ii)

We prove this theorem by induction on the number vertices n.

If n = 1, then G contains only one vertex and no edge.

So the number of edges in G is n -1 = 1 - 1 = 0.

Suppose the induction hypothesis that the statement is true for all trees with less than „n‟ vertices. Now let us consider a tree with „n‟ vertices.

Let „ek‟ be any edge in T whose end vertices are vi and vj.

Since T is a tree, by Theorem 12.3.1,

Dear students get fully solved  SMU BSC IT assignments

Send your semester & Specialization name to our mail id :

“ help.mbaassignments@gmail.com ”

or

Call us at : 08263069601