Download PTU (I.K.Gujral Punjab Technical University (IKGPTU)) B-Tech (Bachelor of Technology) (CSE-IT)- Computer Science Engineering -Information Technology 2020 December 4th Sem 77626 Discrete Mathematics Previous Question Paper
Roll No.
Total No. of Pages : 03
Total No. of Questions : 18
B.Tech. (CSE/IT) (2018 Batch) (Sem. ?4)
DISCRETE MATHEMATICS
Subject Code : BTCS-401-18
M.Code : 77626
Time : 3 Hrs. Max. Marks : 60
INST RUCT IONS T O CANDIDAT ES :
1 .
SECT ION-A is COMPULSORY cons is ting of TEN questions carrying TWO marks
each.
2 .
SECT ION-B c ontains F IVE questions c arrying FIVE marks eac h and s tud ents
have to atte mpt any FOUR q ues tions.
3 .
SECT ION-C contains THREE questions carrying T EN marks e ach and s tudents
have to atte mpt any T WO questio ns.
SECTION-A
Answer briefly :
1.
Find the Cartesian product A ? A if A = {0, 1, 3).
2.
Construct the truth table of the compound proposition p q p q.
3.
Define contrapositive of a conditional statement and find the same for of the following
statement:
"If you do your homework, you will not be punished"
4.
What is the power set of the empty set? What is the power set of the set {}? Here is an
empty set.
5.
State pigeonhole principle.
6.
Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.
7.
Draw a Complete graph with 5 vertices.
8.
Does there exits a simple graph with six vertices of degrees 1,1,3, 4,6,7? Justify.
9.
Define a permutation group.
10. For any a,b in a Boolean algebra prove that (a+b)'=a'+b'.
1 | M-77626
(S2)-225
SECTION-B
11. Show that p p qand p
q are logically equivalent by developing a series of
logical equivalences.
12. In a survey it was found that 21 people liked product A, 26 liked product B and 29 liked
product C. If 14 people liked products A and B, 12 liked products C and A, 14 people liked
products B and C and 8 liked all the three products. Find how many liked product C only?
13. Let A be the set of integers and R be the relation defined on A?A by (a,b)R (c,d) if ad=bc.
Prove that R is an equivalence relation.
14. Explain the following with suitable examples :
a) Connected graph
b) Planar graph
c) Vertex colouring of a Graph
d) Rooted tree
15. Show that the set G={1,2,3,4,5,6} is a finite abelian group of order 6 w.r.t. multiplication
modulo 7.
SECTION-C
16. a) Prove that 2 is irrational by giving a proof by contradiction.
b) Find the number of arrangements of the letters of the word INDEPENDENCE. In how
many of these arrangements
i) All the vowels always occur together.
ii) Vowels never occur together.
17. a) Prove that a finite integral domain is a field.
b) Using Boolean algebra, show that :
abc+ab'c+abc'+a'bc=ab+bc+ca
18. a) Determine whether the following graph is :
2 | M-77626
(S2)-225
i) Hamiltonian, if yes, find the Hamiltonian cycle.
ii) Eulerian, if yes, find the Euler cycle.
b) Use the well-ordering property to prove the division algorithm which states that if a is
an integer and d is a positive integer, then there are unique integers q and r with 0 r
< d and a = dq + r.
NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any
page of Answer Sheet will lead to UMC against the Student.
3 | M-77626
(S2)-225
This post was last modified on 13 February 2021