Course/Branch: B. Tech. / CSE
Subject Name & Subject Code: Discrete Structure & Theory of Logic & BCS303
Short Answer type questions:
1. List and describes the representation of a set.
2. Define the symmetric difference of two sets.
3. Is there any set P in which every relation in P is symmetric?
4. Draw the digraph of R ={(1,2), (2,1), (3,4),(4,3), (3,5), (5,3), (4,5), (5,4), (5,5)} on the set A={1,2,3,4,5}.
5. Illustrate the inverse functions.
6. Illustrate the binary operation.
7. Write necessary conditions to satisfy the ring.
8. Define “Normal Subgroup” in brief.
9. What are the sufficient conditions of a Group?
10. What do you mean by cyclic group?
Long Answer type questions:
11. Let A, B, C and D be sets. Suppose R be a relation from A to B, S is a relation from B to C and T is a relation from C to D. Then prove that (RoS)oT=Ro(SoT).
12. Let A and B be two sets then prove that the composition of any function with the identity
is the function itself i.e. foIA=IBof=f.
13. If R is a relation N× N defined by (a,b)R(c,d) iff a + d = b + c, show that R is an equivalence relation.
14. In a city of 1000 families, it was found that 40% families buy newspaper A, 20 % families buy newspaper B and 10% buy C. Only 5% families’ buy A and B, 3% buy B and C and 4% buy A and C and 2% families buy all the three newspapers. Find the number of families which buy
(i) A only
(ii) B only
(iii) None of A, B, and C
15. Prove that 13 + 23 + 33 + · · · + n3 = n2(n+1)2/4, n>=1 by using induction.
16. 12+ 22+32+ …..+n2= n(n+1)(2n+1)/6, n>=1 by using induction.
17. Compare between coset and partition of set with suitable example.
18. Let A B C be three sets & f:A->B & g:B->C are two one one onto fn then prove that composite function gof:A->C is also one one onto and (gof)-1=f-1og-1.
19. State and prove the Lagrange's Theorem.
20. A non void subset H of a Group G is a subgroup of G if and only if
(i) a Є H, b Є H => a * b Є H
(ii) a Є H => a-1Є H where a-1 is inverse of a in G
21. Prove that the identity element of a subgroup is the same as that of the group.
22. How many generators are there of the cyclic group G of order 6?
23. If * is an associative binary operation in A, then the inverse of every invertible element is unique”. Prove it.
24. Show that the set of all integers I forms an abelian group with respect to the binary operations * defined by the rule a * b = a + b + 1, for all a, b Є I and Prove that every field is an integral domain.
Course/Branch: B. Tech. / CSE
Subject Name & Subject Code: Discrete Structure & Theory of Logic & BCS303
Short Answer type questions:
1. Show that a lattice with 5 elements is not a boolean algebra.
2. Write the contra positive of the implication: “if it is Sunday then it is a holiday”.
3. Show that the propositions 𝑝→𝑞𝑎𝑛𝑑 ¬𝑝∨𝑞 are logically equivalent.
4. Differentiate complemented lattice and distributed lattice.
5. State De Morgan’s law and Absorption Law.
6. Translate the conditional statement “If it rains, then I will stay at home” into contrapositive, converse and inverse statement.
7. Let A = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24} be ordered by the relation ‘a divides b’. Find the Hasse diagram.
8. If L be a lattice, then for every a and b in L prove that a ˄ b = a if and only if a ≤ b.
9. Write the negation of the following statement: “If I wake up early in the morning, then I will be healthy.”
10. Express the following statement in symbolic form: “All flowers are beautiful.”
Long Answer type questions:
11. Show that ((P ∨ Q) ∧ ¬(¬ Q∨ ¬ R)) ∨ (¬ P Q ∨ ¬ ) ∨ (¬ P R ∨ ¬ ) is a tautology.
12. Let (L,∨,∧,≤) be a distributive lattice and a b, ∈ L . If a ∧ b = a ∧ c and a ∨ b = a ∨ c then show that b =c.
13. Explain various Rules of Inference for Propositional Logic.
14. Prove the validity of the following argument “if the races are fixed so the casinos are crooked, then the tourist trade will decline. If the tourist trade decreases, then the police will be happy.
The police force is never happy. Therefore, the races are not fixed.
15. Construct the truth table for the following statements: i) (P→Q’)→P’ ii) P↔(P’˅Q’).
16. 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) II ) a˄ (a′˅ b)=a˄ b.
17. i) Justify that (D36,\) is lattice.
ii) 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.
18. 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.”
19. 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.
20. Prove the validity of the following argument “If I get the job and work hard, then I will get promoted. If I get promoted, then I will be happy. I will not be happy. Therefore, either I will not get the job, or I will not work hard.”
21. Simplify the Boolean function F (A, B, C, D) = ∑ (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11) Also draw the logic circuit of simplified F.
22. Simplify the following Boolean expressions using Boolean algebra
i. xy + x΄z +yz ii. C(B + C)(A + B + C) iii. A + B(A + B) + A(A΄ + B) iv. XY + (XZ)΄+ XY΄Z(XY+Z)
23. Define tautology, contradiction and contingency? Check whether (p ˅ q) ˄ ( ~ p ˅ r) → (q ˅ r) is a tautology, contradiction or contingency.
24. Obtain the principle disjunctive and conjunctive normal forms of the
formula ( ~ p →r) 
(q ↔ p).
25. Translate the following statements in symbolic form
i. The sum of two positive integers is always positive.
ii. ii. Everyone is loved by someone. iii. iii. Some people are not admired by everyone.
iii. If a person is female and is a parent, then this person is someone’s mother
SUBJECTIVE QUESTIONS BL
Group and Subgroup
Prove that the inverse of the product of two elements of a group G is the product of the
Q1) inverse taken in the reverse order.
To show that the necessary and sufficient condition for a non-empty subset H of a group
Q2) (G,*) to be a subgroup is a Є H, b Є H => a * b -1 Є H, where b -1 is the inverse of b in G.
Q3) If * is an associative binary operation in A then the inverse of every invertible element is
unique”. Prove it. 3
Q4) Prove that the identity element of a subgroup is the same as that of the group. 3
Cyclic group, Cosets, Normal subgroups
Q5) If G is an additive group of all integers and H is an additive subgroup of all even integers
2 of G, then find all the cosets of H in G.
Q6) Prove that if G is an abelian group, then every subgroup H of G is normal in G.
Q7) How many generators are there of the cyclic group G of order 6? 2
Q8) State and prove the Lagrange's Theorem.
Q9) If a cyclic group G is generated by an element a of order n, then show that a m is a generator
of G if and only if the greatest common divisor of m and n is 1 i.e., if and only if m and n are 3 relative primes.
Permutation and symmetric groups, group Homomorphism
Q10) Let G be an abelian group. Then prove that any subgroup of G is normal. 3
Q11) Let A={1,2,3,4,5}, find (1,3) 0 (2,4,5)o(2,3). 2
Rings and Fields
Q12) If R is a ring such that a^2 =a , for all a belong to R then prove that R is commutative ring
Q13) Prove that a ring R is without zero divisors iff the cancellation law holds in R.
Q14) Prove that a ring R is commutative iff (a + b) 2 = a 2 + 2ab + b 2 , ∀ a, b ∈ R.
SHORT-ANSWER TYPE QUESTIONS BL
Group and Subgroup
Q1) List the properties of abelian group. 1
Q2) Define the order of a group. 1
Q3) What do you mean by semigroup?
Cyclic group, Cosets, Normal subgroups
Q4) Show that every cyclic group is an abelian group. 2
Q5) How to calculate the index of subgroup of group. 1
Permutation and symmetric groups, group Homomorphism
Q6) List the properties of a monoid. 1
Q7) Simplify the following: i) ( 1 3 4 ) − 1 ii) ( 2 5 4 1 ) − 1 2
Rings and Fields
Q8) Define the Integral domain. 1
Q9) Define the subring of the Ring. 1
Q10) Prove that a division ring has no divisor of zero. 3
REFERENCES
TEXT BOOKS:
Ref. [ID] Authors Book Title Publisher/Press Edition & Year of
Publication
[T1] Swapan Kumar Sarkar Discrete Mathematics S. Chand 6 th Ed, 2009
[T2] Y. N. Singh Discrete Mathematical Structures Wiley, India 1 st Ed.,2010
[T3] B. K. Sharma & R. S.
Sirohi Discrete Mathematics Dhanpat Rai
Publications 1 st Ed, 2011
REFERENCE BOOKS:
Ref. [ID] Authors Book Title Publisher/Press Edition & Year of
Publication
[R1] Kenneth. H. Rosen ,Discrete mathematics and its
applications
McGraw-Hill
1 st Ed.,1999
ONLINE/DIGITAL REFERENCES:
Ref. [ID] Source Name Source Hyperlink
[D1] Lecture Notes in Group
theory https://www.javatpoint.com/discrete-mathematics-group
Comments
Post a Comment