II/BCA/202 Student's Copy
2 0 1 8
CBCS
2nd Semester
BACHELOR OF COMPUTER APPLICATIONS
Paper No. BCA-202
Mathematics—II Discrete Mathematics
Full Marks 75
Time 3 hours
PART A—OBJECTIVE
Marks 25
The figures in the margin indicate full marks for the questions
SECTION—A
Marks 15
1. Tick the correct answer in the brackets provided 1×10=10
A set A is a proper subset of a set if
A Í B A ¹ B
A B Both and
In a distributive lattice, if b Ù c then
b £ c c £ b
c b b Ù c 0
For any statement formula P the statement ù P ®ùQ is called its
inverse converse
contrapositive transitive
If A and B are well-formed formulas, then
A Ù B is not well-formed formula
A Ú B is not well-formed formula
A ¯B is not well-formed formula
A B is well-formed formula
/538 1 Contd.
The number of different messages than can be represented by
sequences of 3 dashes and 2 dots is
7 8
6 10
The third term in the expansion of (2x 3y is
720 x 3y2 720 x2y3
670 x 3y2 670 x2y3
Any subgroup of a cyclic group
is non-Abelian has order 5
is cyclic is non-cyclic
In the group under multiplication modulo 10, the identity
element is
4 6
2 8
An edge of a graph that is not self-loop is called a/an
loop empty
proper edge regular edge
A graph without multiple edges and loops is called
digraph tree
branch simple graph
2. Tick whether the following statements are True or False 1×5=5
A closed walk that does not contain a repeated edge is called a loop.
T F
Every finite group is isomorphic to a permutation group.
T F
A sequence of n distinct elements of a finite set A with n elements is
called a permutation.
T F
A product of the variables and their negations in a formula is called
elementary sum.
T F
A set A is said to be uncountable if A is finite or countable.
T F
II/BCA/202/538 2 Contd.
SECTION—B
Marks 10
Answer the following questions 2×5=10
1. Compute the total number of students in a class if 50 students take
Mathematics and 6 students take Computer Science but 30 students are
taking both the courses.
2. Write the truth table for ÚQ )Úù P.
3. Show that C 6C 6C k3.
4. If a2 e " a ÎG, then show that G is Abelian.
5. Define a subgraph and a tree.
PART B—DESCRIPTIVE
Marks 50
The figures in the margin indicate full marks for the questions
1. Define a Boolean algebra and write its basic properties. 5
Let n p1p2 ... pk where pi are distinct primes known as set of atoms.
Show that the poset Dn is a Boolean algebra. 5
OR
If B and C are sets, prove that A Ç(B Ç B ÇC). 5
Draw Venn diagrams and show the sets È B B A
A È B and A Ç where A Ç B ¹ f and denotes complement. 5
2. Show that ù P Ù ùQ Ù R Ú Ù R Ú Ù R Û R. 5
Obtain disjunctive normal form of ù ÚQ ÙQ 5
OR
Obtain the principal disjunctive normal form of
P ®Q )Ùù (ùQÚù P 5
Define tautologies. Explain them with an example. 5
3. Find the number of distinguishable permutations of the letters in the
word 'Mathematics'. What is a 'combination'?
II/BCA/202/538 3 Contd.
Find the term independent of x in the expansion of 4
A woman has 11 close friends and she wants to invite 5 of them to
dinner. In how many ways can she invite them, if—
there is no restriction on the choice;
two particular persons will not attend separately?
Find the sum of the coefficients of even powers of x in the expansion
of x x2 x 3)5. 5
4. Prove that the set G of all non-zero complex numbers is a group under
usual multiplication. 5
State and prove Lagrange's theorem. 5
OR
Let G be a group such that (ab anbn for 3 consecutive integers n for
all b ÎG. Show that G is Abelian. 5
Show that union of two subgroups is a subgroup if one of them is
contained in the other. 5
5. Prove that a tree with n vertices has edges. 5
Let G be a planar graph with v vertices, e edges and f faces. Then show
that
v e f 2 5
OR
Obtain a minimal spanning tree for the graph G 10