Saurastra University 2006 M.Sc Computer Science Mathematics : - VII (Advanced Discrete Mathematics) - Question Paper

M. Sc. (Part - II) exam
April / May – 2006
Mathematics : Paper - VII
(Advanced Discrete Mathematics)
(New Course)
Time : three Hours] [Total Marks : 80
Instructions : (i) ans all the ques..
(ii) every ques. carries 16 marks.
1 (a) Let bS,*g, bT,*¢g be monoids with identities e,e,'. If 5
f : S ® T is a surjective homomorphism then prove that
f e e bg= ¢. Deduce that there exists no surjective homomorphism
from Z, X b g to . 2Z, X b g
(b) Let Mn IR b g denote the semigroup of all n×n matrices 5
over IR under matrix multiplication. describe a relation
~ on Mn IR b g by A ~ B A, B  Mn IR c b gh iff
det A det B bg= bg. Prove ~ is a congruence relation. State
the fundamental homomorphism theorem of semigroups.
Using it deduce that Mn IR
IR, X b g b g ~
~ .
(c) (i) When do we say that 2 statements are logically 3
equivalent. Let p, q be any 2 propositions. Prove
that pÞ q is logically equivalent to ~ q Þ ~ p.
(ii) describe : (a) universally quantified statement. 3
(b) existentially quantified statement and illustrate
them with examples. State generalized De Morgan
laws for logic.
OR
1 (a) If L1 one d , £ i and L2 two d ,£ i are lattices then prove that 4
bL, £g is a lattice where L = L ´ L one two and £ is the product
partial order. Illustrate that L need not be a lattice
under the lexicographic order.
(b) describe a complete lattice. Illustrate it with an example. 2
(c) Let n > 1. Prove that Dn the lattice of positive divisions 3
of n under divisibility relation is complemented iff n is
the product of distinct primes.
(d) describe (a) a modular lattice (b) a distributive lattice. 3
Illustrate that a modular lattice need not be distributive.
(e) Show that in any lattice L, 4
bx Ù ygÚby Ù zgÚbz Ù xg£ bx Ú ygÙby Ú zgÙbz Ú xg for all
x, y, z in L with equality if L is distributive.
2 (a) describe a Boolean algebra. Let A = 1,2,3, 4,5, , 6,7,8 l q and 5
R be the relation on A described by
R  { , , , , , , , , , , , , ,
, , , , , , , , , , , , ,
, , , , , , , , , , , , ,
, , , , , , , , , , }
1 two one 1 one three one four two 2 two four three 3
3 four 4 four five one five two five three five four five 5
5 six five seven five eight six two six four six 6 six 8
7 three seven four seven 7 seven eight 8 four eight 8
bbbb ggggbbbb ggggbbbb ggggbbbb ggggbbbbggggbbbbggggbbbggg
Prove or disprove that A, R b g is a Boolean Algebra.
(b) Let bA, £g be a finite Boolean Algebra. Prove that any 5
nonzero element of A can be expressed as the joint of

Earning:   Approval pending.