PANDIT DEENDAYAL E NERGY U NIVERSITY , GANDHINAGAR
D EPARTMENT OF MATHEMATICS
DISCRETE MATHEMATICAL STRUCTURES (20MA206T) ASSIGNMENT-1
_________________________________________________________________________________________________________
1) Define a finite set, countably infinite set and uncountable (uncountably infinite) set. Give at least one
example each.
2) In a college entrance process: 300 applied for Engineering, 200 for Medicine, 100 for Law, 50 for both
Engineering and Medicine,30 for both Engineering and Law, 20 for both Medicine and Law, 10 for all
three.
How many students applied for exactly two of the three fields?
3) Draw Venn diagram showing
a) (A ∩ B) ∈ (A ∩ C) but B is not a subset of C.
b)(A ∪ B) = (A ∪ C) but B /= C.
4) Consider the set Z of integers and an integer m > 1. We say that x is congruent to y modulo m,
written x ≡ y (mod m) if x − y is divisible by m. Show that this defines an equivalence relation on Z.
5) Prerequisites in college is a familiar partial ordering of available classes. We say A << B if course A is
a prerequisite for course B. Consider the mathematics courses and their prerequisites given in fol- lowing
table. Draw the Hasse diagram for the partial ordering of these classes. Is this poset a lattice? Justify.
Class Prerequisites
Math 101 None
Math 201 Math 101
Math 250 Math 101
Math 251 Math 250
Math 340 Math 201
Math 341 Math 340
Math 450 Math 101, Math 250
Math 500 Math 450, Math 251
6) Prove that the following argument is valid: 𝑝 →∼ 𝑞, 𝑟 → 𝑞, 𝑟 ⊢∼ 𝑝.
7) Show that the propositions ∼ (𝑝 ∧ 𝑞) and ∼ 𝑝 ∨ ∼ 𝑞 are logically equivalent.
8) Determine the validity of the following argument: 𝑝 → 𝑞, ∼ 𝑞 ⊢ ∼ 𝑝.
9) Draw Hasse diagram for the poset ({2, 4, 5, 10, 12, 20, 25}, ∣). Check if this poset is a lattice or not.
10) Consider the set A={1, 2, 3, 6, 9, 18} under the partial ordering
R={(1,1), (1, 2), (1,3), (1,6), (1,9), (1,18), (2, 2), (2, 6), (2, 18), (3, 3), (3, 6), (3, 9), (3, 18), (6, 6), (6,
18), (9, 9), (18, 18)}.
Draw the Hasse diagram and determine if it is a Lattice. If not, which ordered pair must be addded to R
so that the given structure becomes a Lattice.
1
11) Show that the following are logically equivalent.
a. 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)
b. (𝑝 → 𝑞) ∨ (𝑝 → 𝑟) ≡ 𝑝 → (𝑞 ∨ 𝑟)
c. ~(𝑝 ↔ 𝑞) ≡ 𝑝 ↔ ~𝑞
12) Show that ~(𝑝 ∨ (~𝑝 ∧ 𝑞)) and ~𝑝 ∧ ~𝑞 are logically equivalent by developing a series of logical
equivalences (without using the truth tables).
13) Show that (𝑝 ∧ 𝑞) → (𝑝 ∨ 𝑞) is a tautology by developing a series of logical equivalences (without using
the truth tables).
14) Use mathematical induction to prove that 2𝑛 < 𝑛! for every positive integer n with 𝑛 ≥ 4. (Note that this
inequality is false for n=1, 2, 3.
15) Use mathematical induction to prove that 𝑛3 − 𝑛 is divisible by 3 whenever n is a positive integer.
16) How many relations are there on a set with n elements? Explain your answer.
1 1 0
17) Suppose that the relation R on set A={x,y,z} is represented by the matrix [1 1 1]. Is R reflexive,
0 1 1
symmetric and/or antisymmetric?
18) Let S = {a, b, c, d, e, f, g} be ordered as in Fig. (a), and let X = {c, d, e}.
Find the upper and lower bounds of X. Identify supremum and Infimum of X, if exist.
19) Let S = {1, 2, 3, 4, 5, 6, 7, 8} be ordered as in Fig. (b), and let A = {2, 3, 6}.
Find the upper and lower bounds of A. Identify Sup (A) and Inf (A), if either exists.
1
20) Repeat problem 19 with the subset B = {1, 2, 5}.
21) If you live in Mumbai, then you live in India.
You live in India.
Therefore, you live in Mumbai.
Is this valid?
22) If a student scores more than 90%, then they will get an A grade.
Rina scored 95%.
Rina will get an A grade.
Is this valid?
23) Premises 1: (𝑃 → 𝑄) → 𝑅
Premise 2: 𝑃 → 𝑄.
Can you conclude R?
24) Premises: 𝑃 → 𝑄, 𝑄 → 𝑅, 𝑅 → 𝑆, ∼ 𝑆. Can you conclude ∼ 𝑃?
