Discrete Mathematics — Summer 2024

Define injective function. Given A = {2,5,6}, B = {3,4,2}, find (A − B) and (B − A).

Determine the relation ≤ (less than or equal) on the set ℤ of integers are reflexive, symmetric, anti-symmetric, transitive.

(i) Check whether the function f(x) = x3 −2, for x ∈ ℝ is invertible function. If so, find f−1(x). (ii) Prove that a tree with n vertices has n−1 edges.

Identify the statement (¬q⋀(p → q)) → ¬p is tautology or contradiction without constructing the truth table.

Let Gbe the subset of 2 × 2 real matrices with a nonzero determinant. Check whether Gis group under matrix multiplication. If so, is it abelian group?

(i) Symbolize the expression “John is a bachelor and this painting is red”. (ii) Express the following using predicate, quantifier and logical connectives. Also verify the validity of the consequence. Everyone who graduates gets a job. Ram is graduated. Therefore, Ram got a job.

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

Let g be a homomorphism from a group (G,∗) to a group (H,∆). Show that g(e ) = e and for any a ∈ G, G H g(a−1) = (g(a))−1.

04 Prove that : A∪(B∩C) = (A∪B)∩(A∪C).

(i) Prove that every cyclic group is abelian. (ii) Consider the set of positive integers ℕ. Check which of (ℕ,+) and (ℕ,×) are semigroup and which are monoid? OR1

Find left cosets and right cosets of H = {0,3} in the group (ℤ ,+ ).

(i) Suppose repetitions are not allowed, how many four digit numbers can be formed from six digits 1,2,3,5,7,8? (ii) How many of such numbers less than 4000? (iii) How many in (i) are even? (iv) How many in (i) are divisible by 10?

Show that (R,+, ×) is an integral domain, where R = {a+b√5 / a, b ∈ ℤ }.

Let S = {1,2,3,4} and R = {(1,1),(1,4),(2,2),(2,3),(3,2),(3,3),(4,1),(4,4)} . Draw the graph of Rand hence write partition of S.

Define Lattice. Draw the Hasse diagram of (S ,D), where Dis the relation of12 “division” in ℕ such that for any a,b ∈ ℕ , aDb iff a divides b and Sis the set12 of all divisors of 12.

Let ⟨L,≤⟩ be a lattice. Show that for a,b,c ∈ L, following inequalities holds.

a ⊕(b ∗ c) ≤ (a⊕b) ∗ (a⊕c) and (ii) a ∗ (b⊕c) ≥ (a ∗ b)⊕(a ∗ c).

Let the POSET (ρ(A),≤) where A = {a,b,c}, relation is subset. Find

Upper bound of {{ },{a},{c}}, (ii) GLB of {{ },{a},{c}}, if exist, (ii) LUB of {{ },{a},{c}}, if exist.

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

Define Isolated node, Binary tree and Regular graph.

Check whether the following graphs are isomorphic or not.

Define path matrix. Warshall's algorithm to obtain path matrix from the adjacency matrix of following graph OR2

Agraph Ghas 15 edges, 3 vertices of degree 4 and other vertices of degree 3. Find the number of vertices in G.

Find all the node base of the given digraph. Also find d(V ,V ),d(V ,V ).

Draw binary trees whose post-order produced the string d-e-c-g-j-h-f-b-l-n-q-r-p-m-k-a and pre-order produced the string a-b-d-h-e-i-j-c- f-g-k and in-order produced the string h-d-b-i-e-j-a-f-c-k-g.