Discrete Mathematics — Winter 2021

Show that for any two sets Aand B, A−(A∩B) = A−B.

If S = {a, b, c}, find nonempty disjoint sets Aand Asuch that A ∪A = S. Find the other solutions to this problem.

Using truth table state whether each of the following implication is tautology.

(p⋀r) → p

(p⋀q) → (p → q)

p → (p⋁q) Q-2 (a) Given S = {1,2,3,−−−−,10} and a relation Ron S. Where, R = {〈x,y〉|x+y = 10} . What are the properties of relation R?

Let Ldenotes the relation “less than or equal to” and Ddenotes the relation “divides”. Where xDy means “x divides y”. Both Land Dare defined on the set {1,2,3, 6}. Write Land Das sets, find L∩D.

Let X = {1,2,3,4,5,6,7} and R = {〈x,y〉|x−y is divisible by 3}. Show that R is an equivalence relation on. Draw the graph of R.

Define equivalence class generated by an element x ∈ X. Let Zbe the set of integers and let Rbe the relation called “congruence modulo 3” defined by R = {〈x,y〉|x ∈ Z⋀y ∈ Z⋀(x−y) is divisible by 3} Determine the equivalences classes generated by the element of Z.

f(x)+f(−x) Let f(x) be any real valued function. Show that g(x) = is always an2 f(x)−f(−x) even function where as ℎ(x) = is always an odd function.2

The Indian cricket team consist of 16 players. It includes 2 wicket keepers and bowlers. In how many ways can cricket eleven be selected if we have select 1 wicket keeper and at least 4 bowlers?

Let Abe the set of factors of particular positive integer m and ≤ be the relation divides, that is ≤= {〈x,y〉|x ∈ A⋀y ∈A⋀(x divides y)} Draw the Hasse diagrams for

m =

m = 210.

Q-3 (a) Find the composition of two functions f(x) = ex and g(x) = x3, (f∘g)(x) and (g∘f)(x). Hence, show that (f∘g)(x) ≠ (g∘f)(x).

In a box, there are 5 black pens, 3 white pens and 4 red pens. In how many ways can 2 black pens, 2 white pens and 2 red pens can be chosen?

Let 〈L,≤〉 be a lattice. Show that for a,b,c ∈ L, following inequalities holds. a⊕(b⋆c) = (a⨁b)⋆(a⨁c) a∗(b⨁c) = (a∗b)⨁(a∗c)

Let G = {(a,b)|a,b ∈ R}. Define binary operation (∗) on Gas (a,b),(c,d) ∈ G,(a,b)∗(c,d) = (ac,bc+d). Show that an algebraic structure (G,∗) is a group.

Q-4 (a) Let Gbe the set of non-zero real numbers. Define binary operation (∗) on Gas ab a∗b = . Show that an algebraic structure (G,∗) is an abelian group.2

Explain the following terms with proper illustrations.

Directed graphs

Simple and elementary path

Reachability of a vertex