Elements of Discrete Mathematics — DU B.A. (Prog) Mathematics as Major Previous Year Question Papers

1. (a) Determine the following : (i) Compute the truth table of the statement (ii) If p → q is false, then determine the truth value of (~(p ^ q)) → q. Explain your answer. (7.5) (b) Let A = Z (the set of all integers). Define the relation R on A as a Rb if and only if a ≤ b + 1. Determine whether the relation R on A is reflexive, irreflexive, symmetric, asymmetric, antisymmetric or transitive. Is R an equivalence relation on A? (7.5) (c) Using mathematical induction, prove that n! ≥ 2n-1 for every positive integer n. 2. (a) Let f: R×R → R×R be a function defined by f(a,b) = (atb, a-b). Determine whether the function f is one to one or onto (or both or neither). (7.5) (b) Let A = (2, 4, 8, 16, 32). Consider the partial order of divisibility on A. That is, if a and b e A, a > b if and only if a divides b. Draw the Hasse diagram of the Poset (A, ≤). How many maximal and minimal elements are there in (c) Find the lower and upper bounds along with greatest lower and least upper bound of the set B = (1,2, 3, 4, 5), if they exist, in the following Hasse diagram. (7.5) 3. (a) Let A be the set of positive integers and B be the set of even positive integers. Let ≤ and ≤' be the partial order "less than or equal to" on A and B respectively. Show that the function f: A → B given by f(a) = 2a is an order-isomorphism from (b) Let (L, 1, V) be an algebraic lattice. Define a relation 'S' on L by a ≤ b if and only if a v b= b. Prove that (L, ≤) is a lattice ordered set. (c) Define sublattice of a lattice. Prove that every non-empty subset of a chain L is a sublattice of 4. (a) Prove that a join-homomorphism between lattices is an order homomorphism. Also, show by example that the converse need not hold. (b) Determine whether the Diamond lattice and the Pentagon lattice are distributive lattices: (c) Define a complemented lattice. Prove that if L is a distributive lattice, then each x e L has at most one complement. (7.5) 5. (a) (i) State and prove De Morgan's Laws for a Boolean algebra B. (4.5) (i) Show that the lattice ({1,2,3,6,9,18), ged, 1cm) does not form a Boolean algebra for the set of positive divisors of 18. (3) (b) (i) Find the Boolean Polynomials that in duces the function and combine them to bring to a simpler form. (4) (i) Are xy + 2)' + *'+ %' and (xz)' equivalent? (c) Let X = (1,2,3} and P(X) be a power set of X. Show that (P(X), U, n) form a Boolean (b) Draw the symbolic representati ve of the circuit given by-f(x, y, z) = (x+y)(x'+ (y+z)) (y'+ z') (c) Use Quine-Mc-Cluskeys Method to simplify-wx'y'z + w'x'yz + wxyz' + wx'yz + w'x'y'z +