(CSE)-302 – Discrete Structure

Out of 120 students surveyed, it was found that 20 students have studied French, 50 students have studied English, 70 students have studied Hindi, 5 have studied English and French, 20 have studied English and Hindi, 10 have studied Hindi and French, only 3 students have studied all the three languages. Find how many students have studied:

i) Hindi alone

ii) French alone

iii) English, but not Hindi

iv) Hindi, but not French

If R be a relation in the set of integers Z defined by R = {(x, y) : x ∈ Z, y ∈ Z, (x - y) is multiple of 3}. Show that it is an equivalence relation.

If f : R → R is defined by: f(x) = {3x - 12, x > 3; 2x² + 3, -2 < x ≤ 3; 3x² - 7, x ≤ -2}. Find f⁻¹(3), f⁻¹(0), and f⁻¹(-2).

Show that 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6, n ≥ 1 by mathematical induction.

Prove that F = {a + b√2 | a, b are rational} is a field.

Define the following:

i) Symmetric Group

ii) Normal Subgroup

iii) Homomorphism

Construct the truth table of the following formula:

i) (∼(p ∨ (q ∨ r)) ⇔ ((p ∨ q) ∧ (p ∨ r)))

ii) ((∼q ⇒ ∼p) ⇒ (p ⇒ q))

Write the negation of the following:

i) If the determinant of a system of linear equations is zero then either the system has no solution or has an indefinite number of solutions.

ii) Either today is not a Sunday or today is not a Wednesday.

Show that the proposition ∼(p ∧ q) and ∼p ∨ ∼q are logically equivalent.

Obtain the conjunctive normal form (CNF) of:

i) p ∧ (p ⇒ q)

ii) ∼p ⇒ [r ∧ (p ⇒ q)]

Determine whether the graphs F₁ and F₂ are isomorphic.

Find an Euler Path in the graph below.

Define a lattice. Let (L, ≤, ∨, ∧) be a lattice, and a, b, c, d ∈ L be such that a ≤ b and c ≤ d. Show that a ∨ c ≤ b ∨ d and a ∧ c ≤ b ∧ d.

Show that D₁₂ and D₁₈ are isomorphic lattices. Further, show that none is isomorphic to the lattice D₂₀.

Show that aₙ = c₁2ⁿ + c₂4ⁿ is a solution of the recurrence relation aₙ - 6aₙ₋₁ + 8aₙ₋₂ = 0.

Find the sequence having the generating function G(x) given by: G(x) = x / (1 - 2x)