Unit – 1
Short Answer Type Questions
1. Solve Ackerman Function A (2,1). (2021-22)
2. Let A = {1,2,3,4,5,6} be the set and R = {(1,1) (1,5) (2,2) (2,3) (2,6) (3,2) (3,3,) (3,6) (4,4) (5,1) (5,5) (6,2) (6,3) (6,6)} be the relation defined on set A. Find Equivalence classes induced by R. (2021-22)
3. How many symmetric and reflexive relations are possible from a set A containing ‘n’ elements? (2019-20)
4. Define various types of functions. (2019-20)
5. Define Injective, surjective and bijective function. (2018-19)
6. Find the power set of each of these sets, where a and b are distinct elements.
i) {a} ii) {a, b} iii) {∅, {∅}} iv) {a, {a}} (2018-19)
7. Describe the different types of operation on sets.
8. Describe each of following in roster form :
i. A = {x : x is an even prime}
ii. B = {x : x is a positive integral divisor of 60}
iii. C = {x ∈ R : x2 – 1 = 0}
iv. D = {x : x2 – 2x + 1 = 0}
v. E = {x : x is multiple of 3 or 5}
9. Prove for any two sets A and B that, (A U B)' = A' ∩ B'.
10. Define the term partial order relation or partial ordering relation.
11. Express the following statement in symbolic form:- “All flowers are beautiful”.
Long Answer Type Questions
1. Justify that for any sets A, B, and C:
i) (A – (A ∩ B)) = A – B ii) (A – (B ∩ C)) = (A – B) ∪ (A – C) (2021-22)
2. State Principle of Duality. Let A denote the set of real numbers and a relation R is defined on A such that (a, b) R (c, d) if and only if a2 + b2 = c2 +d2. Justify that R is an equivalence relation. (2021-22)
3. Let R = {(1,2) (2,3) (3,1)} defined on A = {1,2,3}. Find the transitive closure of R using Warshall’s algorithm. (2021-22)
4. Justify that “If f: A→B and g: B→C be one-to-one onto functions, then gof is also one to one onto and (gof)-1= f -1 o g -1”. (2021-22)
5. Find the numbers between 1 to 500 that are not divisible by any of the integers 2 or 3 or 5 or 7. (2019-20)
6. Is the “divides” relation on the set of positive integers transitive? What is the reflexive and symmetric closure of the relation? R = {(a, b) | a > b} on the set of positive integers? (2019-20)
7. Prove that if n is a positive integer, then 133 divides 11n+1 + 122n−1. (2018-19)
8. Let n be a positive integer and S a set of strings. Suppose that Rn is the relation on S such that s.Rn.t if and only if s = t, or both s and t have at least n characters and first n characters of s and t are the same. That is, a string of fewer than n characters is related only to itself; a string s with at least n characters is related to a string t if and only if t has at least n characters and t beings with the n characters at the start of s. (2018-19)
9. Let X = {1, 2, 3,....., 7} and R = {(x, y)|(x – y) is divisible by 3}. Is R equivalence relation. Draw the digraph of R. (2017-18)
10. Show that R = {(a, b)|a ≡ b (mod m)} is an equivalence relation on Z. Show that if x1 ≡ y1 and x2 ≡ y2 then (x1 + x2) ≡ (y1 + y2).
11. Let R be binary relation on the set of all strings of 0’s and 1’s such that R = {(a, b)|a and b are strings that have the same number of 0’s}. Is R is an equivalence relation and a partial ordering relation?
12. The following relation on A = {1, 2, 3, 4}. Determine whether the following :
a. R = {(1, 3), (3, 1), (1, 1), (1, 2), (3, 3), (4, 4)}
b. R = A × A
Is an equivalence relation or not?
Unit - 2
Short Answer Type Questions
1. State and justify “Every cyclic group is an abelian group”. (2021-22)
2. State Ring and Field with example. (2021-22)
3. Show that every cyclic group is abelian. (2019-20)
4. Let Z be the group of integers with binary operation * defined by a*b = a + b − 2 , for all a, b ∈ Z . Find the identity element of the group (Z,*). (2019-20)
5. A subgroup H of a group G is a Normal subgroup if and only if hg ∈ H for every h ∈ g and g ∈ G. (2020-21)
6. In a group (G, *) prove that: i) (a-1)-1 = a ii) (ab)-1 = b-1a-1 (2020-21)
Long Answer Type Questions
1. Define the binary operation * on Z by x*y=x + y + 1 for all x,y belongs to set of integers. Verify that (Z,*) is abelian group? Discuss the properties of abelian group. (2021-22)
2. Justify that “The intersection of any two subgroup of a group (G,*) is again a subgroup of (G,*)”. (2021-22)
3. Justify that “If a, b are the arbitrary elements of a group G then (ab)2 = a2b2 if and only if G is abelian. (2021-22)
4. Explain Cyclic group. Let H be a subgroup of a finite group G. Justify the statement“the order of H is a divisor of the order of G”. (2021-22)
5. What is Ring? Define elementary properties of Ring with example. (2019-20)
6. Prove or disprove that intersection of two normal subgroups of a group G is again a normal subgroup of G. (2019-20)
7. What do you mean by cosets of a subgroup? Consider the group Z of integers under addition and the subgroup H = {…., -12, -6, 0, 6 12, ……} considering of multiple of 6
(i) Find the cosets of H in Z
(ii) What is the index of H in Z. (2019-20)
8. Let H be a subgroup of a finite group G. Prove that order of H is a divisor of order of G.
9. Prove that every group of prime order is cyclic.
10. Let Z be the group of integers with binary operation * defined by a*b = a + b − 2, for all a, b ∈ Z. Find the identity element of the group (Z,*).
11. Let G = {1, – 1, i, – i} with the binary operation multiplication be an algebraic structure, where i = √- 1. Determine whether G is an abelian or not.
12. Let G be the set of all non-zero real number and let a * b = ab/2. Show that (G *) be an abelian group.
13. What is meant by a ring? Give examples of both commutative and noncommutative rings.
Unit – 3
Short Answer Type Questions
1. Differentiate complemented lattice and distributed lattice. (2021-22)
2. State De Morgan’s law and Absorption Law. (2021-22)
3. Let A = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24} the ordered by the relation 'a divides b'. Find the Hasse diagram.
Long Answer Type Questions
1. Justify that (D36,\) is lattice. (2021-22)
2. Solve E(x,y,z,t) = Σ (0,2,6,8,10,12,14,15) using K-map. (2021-22)
3. Define Modular Lattice. Justify that if ‘a’ and ‘b’ are the elements in a bounded distributive lattice and if ‘a’ has complement a’ then
I) a ˅ (a’ ˄ b)=a˅ b II) a˄ (a’ ˅ b)=a˄ b (2021-22)
4. Let L1 be the lattice defined as D6 and L2 be the lattice (P(S), ≤), where P(S) be the power set defined on set S= {a, b}. Justify that the two lattices are isomorphic. (2021-22)
5. Solve E(x,y,z,t) = Σ (0,2,6,8,10,12,14,15) using K-map.
6. Justify that (D36,\) is lattice.
7. L1 be the lattice defined as D6 and L2 be the lattice (P(S), ≤), where P(S) be the power set defined on set S= {a, b}. Justify that the two lattices are isomorphic.
8. What is a tautology, contradiction and contingency?
Show that (p ˅ q) ˅ (¬ p ˅ r) (q ˅ r) is a tautology, contradiction or contingency.
Unit – 4
Short Answer Type Questions
1. Translate the conditional statement “If it rains, then I will stay at home” into contrapositive, converse and inverse statement. (2021-22)
2. State Universal Modus Ponens and Universal Modus Tollens laws. (2021-22)
3. Show that the propositions p → q and ¬ p ˅ q are logically equivalent.
Long Answer Type Questions
1. Construct the truth table for the following statements:
i) (P→Q’) → P’ ii) P ↔ (P’ ˅ Q’). (2021-22)
2. Show that ((P˅Q) ˄ ¬(¬Q˅¬R)) ˅ (¬P˅¬Q) ˅ (¬P˅¬R) is tautology by using equivalences.
3. Define a totally ordered set, which elements of poset ({2, 4, 5, 10, 12, 20, 25}, |) are maximal and minimal, where | is divide operation?
4. Use rules of inference to Justify that the three hypotheses (i) ”If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on.” (ii) “If the sailing race is held, then the trophy will be awarded.” (iii) “The trophy was not awarded.” imply the conclusion (iv) “It rained.” (2021-22)
5. Justify that the following premises are inconsistent. (i) If Nirmala misses many classes through illness then he fails high school. (ii) If Nirmala fails high school, then he is uneducated. (iii) If Nirmala reads a lot of books then he is not uneducated. (iv) Nirmala misses many classes through illness and reads a lot of books. (2021-22)
Unit – 5
Short Answer Type Questions
1. Explain Euler’s formula. Determine number of regions if a planar graph has 30 vertices of degree 3 each. (2021-22)
2. Explain pigeonhole principle with example. (2021-22)
3. Define complete and regular graph.
Long Answer Type Questions
1. Justify that “In a undirected graph the total number of odd degree vertices is even”. (2021-22)
2. Justify that “The maximum number of edges in a simple graph is n(n-1)/2” (2021-22)
3. Solve the recurrence relation using generating function.
an+2- 5an+1 +6an =2, with a0=3 and a1=7. (2021-22)
4. Explain the following terms with example: (2021-22)
i. Graph coloring and chromatic number.
ii. How many edges in K7 and K3,3
iii. Isomorphic Graph and Hamiltonian graph.
iv. Bipartite graph.
v. Handshaking theorem
5. Prove that the Order of each sub group of a finite sub group is a divisor of the order of the group
6. Define binary tree. A binary tree has 11 nodes. It is in order and pre order traversal node sequences are: Preorder: ABDHIEJKCFG
In-order: HDIBJEKAFCG
Draw the tree.
No comments:
Post a Comment