[SPRING 2014]
ASSIGNMENT
PROGRAM BSc IT
SEMESTER SECOND
SUBJECT CODE & NAME BT0069, Discrete
Mathematics
CREDIT 4 BK ID
B0953 MAX. MARKS 60
You can pay in 6 instalment of
Rs 125-125 if u have any doubt.
computeroperator4@gmail.com
www.smuassignment.in
www.assignmenthelpforall.blogspot.in
Q. No. 1 A bit
is either 0 or 1: a byte is a sequence of 8 bits. Find the number of bytes
that, (a) can be formed (b)begin with 11 and end with 11 (c)begin with 11 and
do not end with 11 (d) begin with 11 or end with 11. 4x2.5 10
Answer:
(a) Since the bits 0 or 1 can repeat, the eight positions can
be filled up either by 0 or 1 in 28 ways. Hence the number of bytes that can be
formed is 256.
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
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
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.
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}, {f, g}, {g, i}, {h, i}, {i, j}} E2 = {(c, a), (c, b), (c, d), (c, f), (f,
No comments:
Post a Comment