Among 100 people at least how many of them were born in the same month?
[3 marks]Prove that: (A∪B)′ ≡ A′ ∩B′.
[4 marks]Define the following: 1) Composition of functions 2) Monoid 3) Existential Quantifier 4) Partially Ordered Set 5) Boolean Algebra 6) Tree 7) Complete Graph
[7 marks]Explain types of a Relation with a suitable example.
[3 marks]Rewrite the following statements using quantifier variables and predicate symbols: 1) All birds can fly. 2) Some women are genius. 3) There is a student who likes Discrete Mathematics but not Probability and Statistics. 4) Each integer is either even or odd.
[4 marks]Determine the validity of the argument given: If Istudy, then Iwill not fail in Discrete Mathematics. If Ido not play cricket, then Iwill study. But Ifailed in Discrete Mathematics. ---------------------------------------------------------- Therefore Imust have played cricket.
[7 marks]Find if the following is a tautology, contradiction or contingency. (p → (q → r)) → ((p → q) → (p → r))
[7 marks]Define: Bounded, Distributive and Complemented Lattices.
[3 marks]Find the transitive closure of R = {(1,2),(3,4),(4,5),(4,1),(1,1)}. Where, A = {1,2,3,4,5}.
[4 marks]Let Abe a set of factors of positive integer m and relation is divisibility on A. For m = 45, show that POSET (A,≤) is a Lattice.
[7 marks]Draw the Hasse diagram of the set {1,3,9,18} under partial order relation ‘divides’ and indicate those which are chains.
[3 marks]Let X = {1,2,3,…,7} and R = {(x,y):x −y is divisble by 3}. Show that Ris an equivalence relation. Draw the graph of R.1
[4 marks]Solve the recurrence relation: a −5a +6a = 2. n+2 n+1 n
[7 marks]Define group with example. Give an example of a non-abelian group.
[3 marks]Let H = {[0],[3]} in Zunder addition. Find left and right cosets in <6 Z ,+ >.66
[4 marks]Prove that G = {1,2,3,4,5,6} is a finite abelian group of order 6 with respect to multiplication modulo 7.
[7 marks]Define subgroup and group Homomorphism.
[3 marks]Is addition a binary operation on {-1,0,1}? Justify.
[4 marks]Explain Cosets and Lagrange’s theorem.
[7 marks]How many nodes are necessary to construct a graph with exactly 8 edges in which each node is of degree 2.
[3 marks]Find the shortest path between each pair of vertices for a simple digraph using Warshall’s Algorithm.
[4 marks]Define Isomorphic Graphs. Verify the following graphs are Isomorphic or not (Justify).
[7 marks]Define Cyclic graph, Null graph and Strongly connected graph.
[3 marks]Draw a graph which is regular but not bipartite.
[4 marks]For the following set of weights construct an optimal binary prefix code. For each weight in the set, give corresponding code word. 5, 7, 8, 15, 35, 40
[7 marks]