(CSE)-302 – Discrete Structure

Consider three sets A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6} and C = {1, 5, 7}. Using Venn diagrams, determine and shade the regions corresponding to (A ∪ B) ∩ (B ∩ C) and A ∩ (B ∪ C). Verify if these expressions are equivalent by listing the elements.

Define and illustrate an equivalence relation by constructing an equivalence relation on the set S = {1, 2, 3, 4, 5, 6} where two elements are related if they have the same remainder when divided by 3.

What is pigeonhole principle? Prove it by using mathematical induction and use it to show that in a group of 15 people, at least two share the same birth month.

Explain a recursively defined function. Solve the recurrence relation f(n) = f(n-1) + 3 with initial condition f(0) = 2.

Prove that the set G = {0, 1, 2, 3} under addition modulo 4 is an abelian group. Identify the identity and inverse elements.

Define a homomorphism between two groups. Verify whether the mapping f: R → R defined by f(x) = 2x is a homomorphism under addition.

Consider the propositions p, q and r, where: p: "It is raining." q: "I am carrying an umbrella." r: "I stay dry." Assume the implication (p → q) → r. Construct a truth table for the expression (p → q) → r and determine if it is a tautology or contradiction.

What are predicates in propositional logic? Define universal and existential quantifiers with examples.

Define graph theory and explain the basic terminology of graphs such as vertices, edges, degree and adjacency.

Define and give an example of an isomorphic graph pair. Verify isomorphism between two adjacency matrices.

For the graph G with vertices V = {A, B, C, D} and edges E = {(A, B), (B, C), (C, D), (D, A), (A, C)}, determine:

i) Whether the graph contains a Eulerian path or circuit or not.

ii) All Hamiltonian circuits in the graph G.

How many permutations can be formed from the letters of the word “MATHEMATICS” such that all vowels are together?

What is a Hasse diagram? Draw the Hasse diagram for the set {1, 2, 3, 6, 9, 18} with the divisibility relation.

Define a lattice and prove that every finite lattice has a unique least upper bound and greatest lower bound.

Write short notes on (any four):

i) Finite state machines as language recognizers

ii) Binomial theorem

iii) Permutation group

iv) Partial Ordering Relation

v) Countable and uncountable sets