Seat No.: ________ Enrolment No.
___________
GUJARAT TECHNOLOGICAL UNIVERSITY
BE - SEMESTER–IV (NEW) EXAMINATION – WINTER 2021
Subject Code:3140708 Date:24/12/2021
Subject Name:Discrete Mathematics
Time:10:30 AM TO 01:00 PM Total Marks: 70
Instructions:
1. Attempt all questions.
2. Make suitable assumptions wherever necessary.
3. Figures to the right indicate full marks.
4. Simple and non-programmable scientific calculators are allowed.
Q.1 (a) Show that for any two sets 𝐴 and 𝐵, 𝐴 − (𝐴 ∩ 𝐵) = 𝐴 − 𝐵. 03
(b) If 𝑆 = {𝑎, 𝑏, 𝑐}, find nonempty disjoint sets 𝐴1 and 𝐴2 such that 𝐴1 ∪ 𝐴2 = 𝑆. 04
Find the other solutions to this problem.
(c) Using truth table state whether each of the following implication is tautology. 07
a) (𝑝⋀𝑟) → 𝑝
b) (𝑝⋀𝑞) → (𝑝 → 𝑞)
c) 𝑝 → (𝑝⋁𝑞)
Q-2 (a) Given 𝑆 = {1, 2, 3, − − − − ,10} and a relation 𝑅 on 𝑆. Where, 03
𝑅 = {〈𝑥, 𝑦〉|𝑥 + 𝑦 = 10} . What are the properties of relation 𝑅?
(b) Let 𝐿 denotes the relation “less than or equal to” and 𝐷 denotes the relation 04
“divides”. Where 𝑥𝐷𝑦 means “x divides y”. Both 𝐿 and 𝐷 are defined on the set
{1, 2, 3, 6}. Write 𝐿 and 𝐷 as sets, find 𝐿 ∩ 𝐷.
(c) Let 𝑋 = {1, 2, 3, 4, 5, 6, 7} and 𝑅 = {〈𝑥, 𝑦〉|𝑥 − 𝑦 𝑖𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 3}. Show that 𝑅 07
is an equivalence relation on. Draw the graph of 𝑅.
OR
(b) Define equivalence class generated by an element 𝑥 ∈ 𝑋. Let Z be the set of 07
integers and let 𝑅 be the relation called “congruence modulo 3” defined by
𝑅 = {〈𝑥, 𝑦〉|𝑥 ∈ 𝑍⋀𝑦 ∈ 𝑍⋀(𝑥 − 𝑦) 𝑖𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 3}
Determine the equivalences classes generated by the element of 𝑍.
Q.3 (a) Let 𝑓(𝑥) be any real valued function. Show that 𝑔(𝑥) = 𝑓(𝑥)+𝑓(−𝑥) is always an 03
2
𝑓(𝑥)−𝑓(−𝑥)
even function where as ℎ(𝑥) = is always an odd function.
2
(b) The Indian cricket team consist of 16 players. It includes 2 wicket keepers and 5 04
bowlers. In how many ways can cricket eleven be selected if we have select 1
wicket keeper and at least 4 bowlers?
(c) Let 𝐴 be the set of factors of particular positive integer 𝑚 and ≤ be the relation 07
divides, that is
≤= {〈𝑥, 𝑦〉|𝑥 ∈ 𝐴⋀𝑦 ∈𝐴⋀(𝑥 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑦)} Draw the Hasse diagrams for
a) 𝑚 = 45
b) 𝑚 = 210.
OR
Q-3 (a) Find the composition of two functions 𝑓(𝑥) = 𝑒 𝑥 and 𝑔(𝑥) = 𝑥 3 , (𝑓 ∘ 𝑔)(𝑥) and 07
(𝑔 ∘ 𝑓)(𝑥). Hence, show that (𝑓 ∘ 𝑔)(𝑥) ≠ (𝑔 ∘ 𝑓)(𝑥).
(b) In a box, there are 5 black pens, 3 white pens and 4 red pens. In how many ways 04
can 2 black pens, 2 white pens and 2 red pens can be chosen?
(c) Let 𝐴 be a given finite set and 𝜌(𝐴) its power set. Let ⊆ be the inclusion relation 07
on the elements of 𝜌(𝐴). Draw Hass diagram for 〈𝜌(𝐴), ⊆〉 for
a) 𝐴 = {𝑎, 𝑏, 𝑐}
b) 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑}
1
Q.4 (a) Let 〈𝐿, ≤〉 be a lattice. Show that for 𝑎, 𝑏, 𝑐 ∈ 𝐿, following inequalities holds. 07
𝑎 ⊕ (𝑏 ⋆ 𝑐) = (𝑎⨁𝑏) ⋆ (𝑎⨁𝑐)
𝑎 ∗ (𝑏⨁𝑐) = (𝑎 ∗ 𝑏)⨁(𝑎 ∗ 𝑐)
(b) Let 𝐺 = {(𝑎, 𝑏)|𝑎, 𝑏 ∈ 𝑅}. Define binary operation (∗) on 𝐺 as 07
(𝑎, 𝑏), (𝑐, 𝑑) ∈ 𝐺, (𝑎, 𝑏) ∗ (𝑐, 𝑑) = (𝑎𝑐, 𝑏𝑐 + 𝑑). Show that an algebraic structure
(𝐺,∗) is a group.
OR
Q-4 (a) Let 𝐺 be the set of non-zero real numbers. Define binary operation (∗) on 𝐺 as 07
𝑎𝑏
𝑎 ∗ 𝑏 = 2 . Show that an algebraic structure (𝐺,∗) is an abelian group.
(b) Explain the following terms with proper illustrations. 07
a) Directed graphs
b) Simple and elementary path
c) Reachability of a vertex
d) Connected graph.
Q-5 (a) Show that sum of in-degrees of all the nodes of simple digraph is equal to the sum 07
of out-degrees of all the nodes and this sum equal to the number of edges in it.
(b) Let = {1, 2, 3, 4} . For the relation 𝑅 whose matrix is given, find the matrix of the 07
transitive closure by using Warshall’s algorithm.
1 0 0 1
1 1 0 0
𝑀𝑅 = [ ]
0 0 1 0
0 0 0 1
OR
Q-5 (a) Define tree and root. Also prove that tree with 𝑛 vertices has 𝑛 − 1 edges. 07
(b) Define in-degree and out-degree of a vertex and matrix of a relation. Let 𝐴 = 07
{𝑎, 𝑏, 𝑐, 𝑑} and let 𝑅 be the relation on 𝐴 that has the matrix
1 0 0 0
0 1 0 0
𝑀𝑅 = [ ]
1 1 1 0
0 1 0 1
*************
