Discrete Math Problems: In this page, you can find a list of Discrete Math Problems which can be useful for practice for final exam.

Discrete Math Practice Problems

Q1: Without using truth table show the following: [Solution]

1. P ↔ q ≡ (p ∧ q) ∨ (~ p ∧ ~ q)
2. p ↔ q ≡ (p ∨ q) → (𝑝 ∧ 𝑞)
3. p → (q→r) ≡ ( p∧ q) → r

Q2:

1. Find the number of ways in which 7 different flowers can be arranged in a garland? [Answer: This is Circular Arrangement. We know that for n different items, the number of circular arrangements is (n – 1)!. For 7 flowers, this is (7 – 1)! = 6! = 720. So there are 360 different ways to arrange 7 different flowers in a garland.]
2. If 5 people are seated about a round table then how many different arrangements are possible?

Q3: State the inclusion-exclusion principle for two/three sets.

Among 100 patients admitted to a hospital, 50 are diagnosed with pneumonia, 60 with bronchitis, and 10 with both pneumonia and bronchitis. Determine:

1. The number of patients diagnosed with pneumonia or bronchitis (or both).
2. The number of patients not diagnosed with pneumonia or bronchitis

Q4: Find the total number of integers lying between 1 and 1000 that are divisible by at least one of 2,3 and 7.

Q5: If all the permutations of the letters of the word DIRECTOR be written down as in a dictionary what is the rank of the word?

Q6: State the generalised pigeonhole principle.

1. Find the minimum number of teachers in an institute to be sure that four of them are born in the same month.
2. Find the minimum number of students needed to guarantee that 5 of them belong to same class ( class1 , class2, class3, class4).​
3. Show that at least 3 people out of 25 must have their birthday in the same month when they are in a room.

Q7: Define an enumerable set. Give an example. Prove the following results on enumerable sets:

1. Show that $\mathbb{Z}$ is enumerable.
2. Prove that a subset of an enumerable set is either finite or an enumerable set.
3. Prove that the cartesian product of two enumerable sets is enumerable.
4. Show that $\mathbb{Q}$ is enumerable.

Q8: Define a lattice. Give an example. What is a bounded lattice and a complemented lattice? Show that every chain is a distributive lattice.

Q9: Show that in a distributive complemented lattice (𝐿,∨,∧),∀ 𝑎,𝑏∈𝐿⇒(𝑎∨𝑏)′=𝑎′∧𝑏′,(𝑎∧𝑏)′=𝑎′∨𝑏′ where 𝑎′ is complement of 𝑎.

Q10: Using generating function method or otherwise, solve the following recurrence relations:

1. a_n = 4a_n-1 – 4a_n-2 + 4n for n≥2, where a₀=2 and a₁=8.
2. a_n = 3a_n-1 + 1 for n≥1, where a₀=1.
3. a_n = 7a_n-1 – 12a_n-2+6 for n≥3, where a₁=2 and a₂=8.

Q11: Prove the following theorems:

1. A tree with 𝑛 vertices has (n-1) edges. [Proof]
2. A simple graph with n vertices and k components can have at most $\dfrac{(n-k)(n-k+1)}{2}$ number of edges. [Proof]
3. Show that the chromatic number of a complete graph with n vertices is n. [Proof]
4. Show that the chromatic number of a cycle with n vertices is 2 if n is even and 3 if n is odd. [Proof]
5. Show that a graph G is minimally connected if and only if it is a tree. [Proof]

Q12: What is Kuratwoski’s first graph? What is Kuratwoski’s second graph? [Solution]

Q13: Solve problems regarding Kruskal’s algorithm and Dijkstra’s algorithm.

Logic

1. Mathematical Logic
2. Tautology, Contradiction, and Contingency
3. Logical Equivalence
4. Conjunctive and Disjunctive Normal Form (PDNF & CDNF)
5. Determine whether the following argument is valid
6. Prove that a Distributive Lattice is Modular

Combinatorics

Pigeonhole Principle: Statement, Examples, Generalised Version

Graph Theory

1. Degree of a Vertex in Graph: Definition, Examples, Handshaking Theorem
2. Simple Graph has Two Vertices of Same Degree: proof
3. Prove that a tree with n vertices has (n-1) edges
4. Simple Graph with n Vertices and k Components have at most (n-k)(n-k+1)/2 Edges
5. Chromatic number of a complete graph with n vertices is n