Discrete Mathematics — Winter 2024

Define onto function. Check whether the function f:ℝ → ℝ defined by f(x) = x2 is one-one and onto.

For the relation R = {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)} on the set A = {1,2,3,4}. Check whether it is reflexive, symmetric, anti-symmetric, transitive.

(i) Ahistory class contains 8 male students and 6 female students. Find the number n of ways that the class can elect:

1 class representative (b) 2 class representatives, 1 male and female (c) 1 president and 1 vice president. (ii) Define elementary cycle, loop, tree and pendent vertex.04

Show that if every element in a group is its own inverse, then the group must be abelian.

Identify the statement (p → q) ⇆ (¬p⋁q) is tautology or contradiction.

Use a truth table to determine whether the following argument form is valid. p → q q → r ∴ p → r

(i) Symbolize the following expressions “x is the father of the mother of y” where P(x): x is a person. F(x,y): x is the father of y. M(x,y): x is the mother of y.04 (ii) Show that the premises “Everyone in this discrete mathematics class has taken a course in computer science” and “Marla is a student in this class” imply the conclusion “Marla has taken a course in computer science.”1

Define homomorphism. Let Gbe the group of real numbers under addition, and let G′ be the group of positive real numbers under multiplication. Check whether the mapping f ∶ G → G′ defined by f(a) = 2a is a homomorphism.

Suppose that 100 mathematics students at a college taking at least one of the languages French, German, and Russian, given the following data: 65 study French, 45 study German, 42 study Russian, 20 study French and German, 25 study French and Russian, 15 study German and Russian. (1) Find the number of students who study all the three languages. (2) Find the number of students who study only French.

(i) The subset H = {0,2} is a subgroup of (ℤ ,+4). Is Ha normal4 subgroup?04 (ii) Let ℤ denotes the integers modulo m. Check whether ℤ is a m m group under addition. If so, is it abelian group?

Find all the generators of cyclic group (ℤ ,+5).

Prove that A∩B = A∩Cif and only if A∩B = A∩C.

Consider the ring ℤ = {0,1,2,…,29} of integers modulo 30.30

Let A = {1,2,3,4} and the relation R = {(1,1),(1,4),(4,1),(4,4),(2,2),(2,3),(3,2),(3,3)} on A. Write the matrix of Rand check whether the relation is an equivalence.

Let X = {2,3,6,12,24,36} and the relation ≤ be such that x ≤ y if x divides y. Find

Lower bound of {3,6}, (ii) Upper bound of {3,6}, (iii) GLB of {3,6}, if exist, (iv) LUB of {3,6}, if exist.

Solve the recurrence relation using the method of generating function a −5 a + 6a = 3n, n ≥ 2, a = 0, a = 2. n n−1 n−2 0 1

Let the relation R = {(1,2),(2,3),(3,3)} on A = {1,2,3}. Find the transitive closure of R.

Solve a = 2 a +3a , a = 1, a = 2. n n−1 n−2 0 1

Draw Hasse diagram of 〈S ,D〉. Prove that 〈S ,D〉 is a lattice,3030 where Dis the relation of “division” in ℕ such that for any a,b ∈ ℕ, aDb if and only if a divides b and S , (n ∈ ℕ) is the set of all n divisors of n.

Find the number of edges in a r-regular graph with n vertices.

Check whether the following graphs are isomorphic or not.

In which order does a pre-order, in-order and post-order traversal visit the vertices of the ordered rooted tree shown in figure?

Atree Thas 4 vertices of degree 2, 3 vertices of degree 3, 1 vertex of degree 4. Find the number of pendant vertices in the tree T.

Find reachable set of each node of the given digraph.

Define adjacency matrix. Use Warshall's algorithm to obtain path matrix from the adjacency matrix of