Discrete Mathematics — Winter 2023

Afunction f:ℝ+ → ℝ is defined by f(x) = x2 −8. Check whether f is one-one and onto.

Determine the relation ∥ (parallel) on the set Lof lines in the plane are reflexive, symmetric, anti-symmetric, transitive, irreflexive.

1

Show that the functions f(x) = x3 and g(x) = x3 for x ∈ ℝ are inverses of one another.04 (ii) Check whether the following graphs are isomorphic.

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

(i) Show that in a group (G,∗), for any a,b ∈ Gif (a∗b)2 = a2 ∗ b2 then (G,∗) must be abelian. (ii) If (G,∗) be a group then for any two elements a and b of (G,∗), prove that (a∗b)−1 = b−1 ∗ a−1.

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

Express the following using predicate, quantifier and logical connectives. Also verify the validity of the consequence.

Every computer science major takes discrete mathematics. Natasha is taking discrete mathematics. Therefore, Natasha is a computer science major. (ii) All parrots like fruit. My pet bird is not a parrot. Therefore, my pet bird does not like fruit.

Show that (ℤ∗,× ) is cyclic group, where ℤ∗ = ℤ \{0}.

Given A = {x ∶ x is an integer and 1 ≤ x ≤ 5}, B = {3,4,5,17}, and C = {1,2,3,...}, find A∩B, A∪B, A∩B ∩C and A∪C.

(i) Show that every subgroup of a cyclic group is normal (ii) The subset H = {0,2} is a subgroup of (ℤ ,+ ). Find all left and right44 cosets of Hin (ℤ ,+ ). Is Ha normal subgroup?44

Define f:(ℕ×ℕ,∗) → (ℚ,×) by f(a,b) = a . Show that f is a b homomorphism.

In a class of 50 students, 12 enrolled for both Mathematics and Science, 32 enrolled for Science. If the students of the class enrolled for at least one of the two subjects, then how many students enrolled for only Mathematics but not Science?

Consider the ring ℤ = {0,1,2,…,9} of integers modulo 10.10

Find the units of ℤ .10

Let X = {1,2,3,4} and R = {〈x,y〉/ x > y} . Draw the graph of Rand also give its matrix.

Find out maximal compatibility blocks of following simplified graph of digraph and write its relation matrix.

Prove that 〈S 30, D〉 is a Boolean algebra.

Define equivalence relation. Let X = {1,2,3,4,5}, R = {〈x,y〉/ x is divisible by y}. Check whether the relation an equivalence relation?

Let A = {a,b,c,d} and 𝜌(A) its power set. Let ⊆ be the inclusion relation on the elements of 𝜌(A). Draw the Hasse diagram of 〈𝜌(A),⊆〉.

Solve a n = 11a n−1 −39a n−2 + 45a n−3 , a0 = 5,a1 = 11,a2 = 25.

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

Find reachable set of each node of the given digraph. Also find d(V ,V ),d(V ,V ).

Define Strong, unilateral, week component. Also Find strong, unilateral, week component from the given digraph.

Define null graph, centre of a graph and complete graph.

Find the path matrix using adjacency matrix of the following graph.

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