Management Education & Research Institute
BCA Semester – I (Batch 2023 - 26)
Discrete Mathematics
Assignment – I
Submission mode: OFFLINE (Hard copy)
Last date of Submission: 8/12/2023
Q1. a) If ∪ = {a, e, i, o, u} is universal set and
A = {a, e, i} B = {e, o, u} C = {a, i, u}. Then
verify that (A∪ B) – (A ∩ B ) = (A – B ) ∪ (B – A )
for given sets.
b) If R be the relation in N defined as xRy iff
"(x - y) is divisible by m”. Then, prove that R is an equivalence relation.
Q2. Let Z* be the set of all non-zero integers and R be the relation on Z*such
that (a, b) Є R if “ a is the factor of b” i.e., a | b.
i) Investigate R for reflexive, symmetric, anti- symmetric or
transitive.
ii) Is R a partial order on Z*?
Q3. Let A = { 1, 2, 3 }. Check whether the following relations are reflexive,
symmetric, anti-symmetric or transitive.
i) R= {(1,1) , (2,2) ,( 3,3) , (1,3) , (1,2)}
ii) R= {(1,1) , (2,2 ), (1,3 ), (3,1)}
iii) R= {(1,1 ), (2,2) , (3,3 ), (1,2 ),( 2,1) , (2,3) , (3,2)}
Q4. Let R be a relation defined on A= {𝑎, 𝑏, 𝑐} by
𝑅 = {(𝑎, 𝑎) , (𝑎, 𝑏) ,( 𝑏, 𝑎) , (𝑏, 𝑏) ,(𝑏, 𝑐) ,( 𝑎, 𝑐) , (𝑐, 𝑎 ), (𝑐, 𝑏 ), (𝑐, 𝑐)}
Is R an equivalence relation on A ?
Q5. Let 𝐴 = {1, 2, 3, 4} and 𝐵 = {3, 4, 5, 6}
Find the elements of each of the relation R stated below. Also, find the
domain and, range of R.
i) aRb if and only if a<b
ii) aRb if and only if a and b are both odd numbers.
Q6. Draw the directed graph or digraph of the relation
R = {(1, 2), (1,3), (2, 2), (2, 4), (3, 2), (3, 4), (4, 1), (4, 3)} defined
on the set A = {1,2, 3, 4}.
Q7. Draw a Hasse diagram of (X, R) where X = (1, 2, 3, 4, 6, 8, 12, 24} and R
be relation defined as “a divides b” in X.
Q8. Draw the Hasse diagram of poset [Dn, R]
for each value of n= 12, 30, 36, 42
Q9. Prove that the propositions ¬(A B) and [(¬A) (¬B)] are
equivalent.
Q10. Show that p→q and ¬p ˅ q are logically equivalent.
Q11. Prove [(A → B) A] → B is a tautology
Q12. Prove (A VB) [(¬A) (¬B)] is a contradiction
Q13. Show that the following 𝑝˄~𝑞 ˅~(𝑝˄~𝑞) is a tautology.
Q14. Let p : Babin is rich,
q : Babin is happy.
Write simple verbal sentences which describes each of the following
statements.
i) p˅q ii) p˄q iii) q→p iv) p˅~q
v) q⟷p vi) ~p→q vii) ~~p viii) ( ~p˄q) →p
Q15. Show that 𝑝 ⟺ 𝑞 and (𝑝 ⟹ 𝑞) ˄ (𝑞 ⟹ 𝑝) are equivalent
Q 16.
Q17. a) Draw a Hasse diagram of poset [P(S), ⊆] .
b) Prove that [P(S), ⊆] where S = {1, 2, 3} is distributive lattice
for x ˅ y = x ∪ y and x ˄ y = x ∩ y for x, y in P(S)
Q18. Let Dn is the set of all divisors of n. R is the relation “divides”
Prove that poset [Dn, R] for each value of n = 12, 30, 36, 42 is a
distributive lattice where x ˅ y = lcm(x,y ) and x ˄ y = gcd(x, y)
Q19 Consider the poset (D30, D), where D30 = {1, 2, 3, 5, 6, 10, 15, 30} and
D denotes divides relation. Then,
(a) Find all lower bounds of {10, 15}
(b) Find the greatest lower bound of {10, 15}
(c) Find all upper bounds of {10, 15}
(d) Determine the least upper bound of {10, 15}.
(e) Draw the Hasse diagram for D30
Q20. A) Show that the function f(x) = x3 and 𝑔 𝑥 = 𝑥1/3 for all x ∈ R are
inverses of each other.
B) Examine the function 𝑓(𝑥 )= 𝑥2 from the set of integers to the set
of integers for one to one .
