B.C.A. (Semester (CBCS) Examination, 2017
DISCRETE MATHEMATICS
Day Date: Friday, 21-04-2017 Max. Marks: 70
Time: 10.30 AM to 01.00 PM
N.B. All questions are compulsory.
Figures to the right indicate full marks.
Use of calculator is allowed.
Q.1 Choose the correct alternatives: 14
The cardinality of set is
11 9 7 None of these
If then the sets are called as sets.
Disjoint Complemented
Identical None of these
The compound statement is
Tautology Contradiction
Neither None of these
The contra positive of is

None of these
If and then the relation R is called relation.
Antisymmetric Symmetric
Reflexive Transitive
If then
0 2 1


None of these



A graph which does not contains any loops and multiple edges is
called graphs.
Page 2 of 3
Multiple Self Complete Simple
10) A graph G has p edges n vertices then its incidence matrix is of
order


11) Empty set is
Infinite set Finite set
Singleton set None of these
12) A function which is both one-one and onto is called as
function.
Injective Bijective
Surjective None of these
13) The statement is
Tautology Contradiction
Neither Valid
14) If and then
1 2
3 4
Q.2 Answer any seven of the following. 14
Define Equivalence relation.
Define Bipartite graph with suitable example.
Find the number of edges in a complete graph with seven
vertices.
Define Tautology and contradiction.
If and then Find and .
If then find power set of A.
Define Bijective function.
State multiplication principle.
State Demorgan's laws for two sets.
Q.3 Attempt any two of the following. 10
Let Let and
be the subset of universal set U. Prove that


Prove that
Let be an equivalence relation defined on set A then prove
that any two equivalence classes are either disjoint or
identical.
Page 3 of 3
Find adjacency and incidence matrix of the following graph.
G
04
Q.4 Attempt any two of the following. 14

Let be the relation defined on the set A given by
Find transitive closure by using warshall's algorithm also draw
digraph of and write indegree and outdegree of each vertex in
.
How many integers between 1 and 567 which are divisible by 3 or
5 or 7.
Define ring sum of two graphs. Hence draw and
for the following graph.
G1 G2
Q.5 Write any two of the following. 14
State and prove mutual Inclusive Exclusive principle for three
sets.
Check the validity of the following argument by using truth table
then find cardinalities of the following sets