Discrete Math Practice Problems

In this page, you will find practice problems on Discrete Mathematics.

Mid Sem Practice Problems

Q1: What is tautology, contradiction and contingency? Give examples.

Q2: What is a well-formed formula? (Answer:  A well-formed formula is an expression consisting of variables, parentheses, and connective symbols. For example, p∨q.)

Q2: Define an equivalence relation on a non-empty set S. Show the relations defined below are equivalence relations:

1. $\rho$ on $\mathbb{Z}$ by $a \rho b$ if and only if 5 divides a-b.
2. $\rho$ on $\mathbb{Z}$ by $a \rho b$ if and only if 3 divides a²-b².

Q3: Write the definition of a partial order relation on a non-empty set S with an example.

Q4: Draw the Hasse diagram for the divisors of 12, 30, 45, 60, 100.

Q5: Check whether the arguments are valid or not: [View Proof]

1. p∨q, q→r, p→s, ∼s ⇒ r.
2. p∨q, p∨q→∼w, ∼w→u∧∼v, u∧∼v→r∨s ⇒ r∨s.
3. p→∼q, r→q, r ⇒ ∼p.

Q6: Without using truth table show the following: [View Proof]

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

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.

Q9: What is a chain of lattice? (Answer: A chain of a lattice is a subset of a partially ordered set where every pair of elements is comparable, meaning for any a,b in the chain, either a≤b or b≤a.)

Q10: Prove that a distributive lattice is modular. [View Proof]

End of Mid Sem Practice Problems

Notes

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

---

This is the assignment set on Discrete Mathematics for Sec C. The questions are given as follows:

Problems on Discrete Math

Due Date: 26th Nov, 2024

Q1: When a statement are considered to be contingency/contradiction?

Q2: What is an equivalence relation? Give an example.

Q3: If 5 people are seated about a round table then how many different arrangements are possible?

Q4: 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

Q5: [Application of Pigeonhole Principle]

State the generalised pigeonhole principle.

Solve the following problems:

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

Q6: Without using truth table show the following:

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

Q7: Using generating function, solve the following recurrence relations:

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

Q8: Prove the following theorems:

1. A simple graph with 𝑛 vertices (𝑛≥2) must have at least one pair of vertices with the same degree. [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. A tree with 𝑛 vertices has (n-1) edges. [Proof]
4. Let G be a graph in which there is a unique path between each pair of vertices. Prove that G is a tree.

Q9: