Discrete Mathematics

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

Assignment Problems

Due Date: 26th Nov

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