Scribd
Upload
4 views2 pages

DMS Assignment Unit2

The document outlines an assignment for a Discrete Mathematics course, focusing on Set Theory, Relations, Functions, Posets, and Lattices. It includes various problems and definitions related to power sets, partial orders, equivalence relations, and the Inclusion-Exclusion Principle. The assignment is divided into three parts, each containing multiple questions that require mathematical proofs, calculations, and diagrammatic representations.

Uploaded by

Anil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

DMS Assignment Unit2

The document outlines an assignment for a Discrete Mathematics course, focusing on Set Theory, Relations, Functions, Posets, and Lattices. It includes various problems and definitions related to power sets, partial orders, equivalence relations, and the Inclusion-Exclusion Principle. The assignment is divided into three parts, each containing multiple questions that require mathematical proofs, calculations, and diagrammatic representations.

Uploaded by

Anil
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment-2

Subject: 4CS1-01: Discrete Mathematics


Unit–2: Set Theory, Relations, Functions, Posets & Lattices

Part–A

1. Define power set. How many elements are there in P(A) if |A| = n?
2. Define partial order relation with one example.
3. What is a bounded lattice?
4. Define antisymmetric relation.
5. State the Inclusion–Exclusion Principle for two sets.
6. If |A| = 20, |B| = 15, and |A ∩ B| = 8, find |A ∪ B|.
7. Let A = {1,2,3,4}, B = {2,4,6}. Find A × B and its cardinality.
8. Determine whether R = {(1,1),(2,2),(3,3),(1,2)} on A = {1,2,3} is a partial order relation.
9. In a group of 100 students: 60 like Mathematics, 45 like Physics, 25 like Chemistry,
20 like both Math & Physics, 15 like Math & Chemistry, 10 like Physics & Chemistry,
5 like all three. Find how many like at least one subject.
10. Draw the Hasse diagram for A = {1,2,3,6} under divisibility relation.

Part–B

1. (a) Define equivalence relation.


(b) Let relation R on Z be defined as aRb iff a ≡ b (mod 4).
(i) Prove that R is an equivalence relation.
(ii) Find all equivalence classes.

2. Prove the identity using algebra of sets:


(A − B) ∪ (A ∩ B) = A.

3. Let A = {1,2,3}. Define R = {(1,2),(2,3),(1,3)}.


(i) Find R².
(ii) Determine transitive closure of R.
(iii) Is R transitive?

4. Let f: R → R defined by f(x) = x³ − x.


(i) Determine whether the function is one–one.
(ii) Determine whether the function is onto.
(iii) Justify your answer mathematically.
5. Let (D30, |) be the set of divisors of 30 under divisibility.
(i) List all elements.
(ii) Draw the Hasse diagram.
(iii) Determine whether it forms a lattice.
(iv) Identify greatest and least elements.

Part–C

1. (a) State Inclusion–Exclusion formula for three sets. (2 Marks)


(b) In a company of 150 employees: 70 know C, 65 know C++, 60 know Java,
30 know C & C++, 25 know C & Java, 20 know C++ & Java, 10 know all three.
(i) How many know at least one language?
(ii) How many know exactly one language?
(iii) How many know none?

2. Let A = {2,3,4,6,12} under divisibility.


(i) Construct the Hasse diagram.
(ii) Identify minimal and maximal elements.
(iii) Does every pair have LUB and GLB?
(iv) Is it a lattice? Justify.

3. Let R on A = {1,2,3,4} be:


R = {(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(1,3)}.
(i) Check reflexivity, symmetry, antisymmetry, transitivity.
(ii) Find transitive closure.
(iii) Determine whether it is a partial order.

4. Consider power set P(S) where S = {a,b,c}.


(i) Draw lattice diagram under inclusion.
(ii) Prove it is bounded.
(iii) Show that it is complemented.
(iv) Verify distributive property.

5. Let A, B, C be finite sets such that:


|A| = 40, |B| = 35, |C| = 30,
|A ∩ B| = 15, |A ∩ C| = 12, |B ∩ C| = 10,
|A ∩ B ∩ C| = 5.
(i) Find |A ∪ B ∪ C|.
(ii) Number of elements in exactly two sets.
(iii) Number of elements in exactly one set.

You might also like