B.C.A. (Semester (CGPA) Examination, 2017
DISCRETE MATHEMATICS
Day Date: Friday, 21-04-2017 Max. Marks: 70
Time: 10.30 AM to 01.00 PM
N.B. Q.1 and Q.7 are compulsory.
Attempt any two questions from Q. 3 and 4.
Attempt any one question from Q. 5 and 6.
Use of calculator is allowed
Figures to the right indicate full marks.
Q.1 Choose the correct alternatives: 07
Conjunction of the statements p and q is true if and only if
both the statements p and q are
true false true of false true and false
Let is a natural number less than 10 then
cardinality of set A is
10 9 1
If every element of set A is related to every element of set
B then the relation is called as relation.
void universal function reflexive
If f x2 5x then f
16 36 4 4
The non zero integers a and b are said to be
integers if their g. c d. is 1.
prime reducible relatively prime invertible
If is a binary operation defined on set A and if c
a for all c then is said to be
associative commutative
invertible none of theses
De Morgan‟s law is

Q.1 Fill in the blanks: 04
The inverse of the conditional statement p q is
The cardinality of the set A 0 is
If a set A contains elements then its power set will
contains elements.
Page 2 of 3
If all the elements in matrix of relation R are 1 then
relation R must be relation.
Q.1 State whether the following statements are true or false: 03
If then x is called as pre-image of y.

where C are finite sets.

Q.2 Attempt any two of the following questions. 14
Let A e}. Let R be the relation defined on the set A
given by R
Then write matrix of relation R.
Draw digraph of relation R. Also find in-degree and out-degree
of each element of set A.
Define relatively prime integers. Hence show that the integers
1357 and 1166 are relatively prime.
Show that the function R R defined by
for all
x is bijective function.
Q.3 Attempt any two of the following questions (Any two) 14
How many integers between 1 to 987 which are divisible by 3
or 5 or 7.
Construct the switching circuits for the following Boolean
expression.

ii)
Let R be the relation defined on the set Z by xRy if and only if
(3x 4y) is divisible by y Z. Show that R is an
equivalence relation on Z.
Q.4 Attempt any two of the following questions. 14
Define cardinality of a set. Let U h}.
Let P and Q be the subsets of
then write the following sets and their cardinalities.
P Q ii) P Q iii) P
Prepare the truth table for the following statement. Also state
whether it is tautology or contradiction or neither.

State Fermat‟s theorem. Hence find the remainder when 4398 is
divided by 7.
Q.5 Translate into symbolic form and test the validity of following
argument by using truth table.
"I will pass B.C.A. if and only if I study regular. If I study regular
then Discrete Mathematics is very easy. Discrete Mathematics
is not easy. Therefore I studied regular and I pass B.C.A."
07
Define transitive closure. Hence find transitive closure of
the relation R defined on
07
Page 3 of 3
the set A by using klarshall‟s algorithm.
Q.6 Find g. c.d. of integers 389 and 167 by using Euclidean
algorithm. Also find the integers m and n such that
(g.c.d. of 389, 167) 389 m 167 n
07
Define the following terms:
Union of two sets
ii) Intersection of two sets
iii) Symmetric difference of two sets
07
Q.7 Attempt any two of the following: 14
Let A and B r}. Then show that
Cartesian product of sets A and B is not
commutative.
ii) Union of the sets A and B is commutative.
Show that

ii)
Define the terms
Universal relation
ii) Transitive relation and
iii) Equivalence relation