NIET Discrete Structures Past Paper PDF

Noida Institute of Engineering and Technology, Greater Noida Posets, Hasse Diagram and Lattices Unit: 3 Discrete Structures & Theory of Logic Ms. Madneeta (ACSE0306)...

Noida Institute of Engineering and Technology, Greater Noida Posets, Hasse Diagram and Lattices Unit: 3 Discrete Structures & Theory of Logic Ms. Madneeta (ACSE0306) Singh B Tech 3rd Assistant Sem Professor CSE Department Madneeta Singh ACSE0306 Discrete Structures Unit 1 11/05/2020 3  Evaluation Scheme End Evaluation Periods Semest Schemes To Cour Sl. Subject er Cre Subject ta se No. code dit TOTA l Type L T P CT TA PS TE PE L 1 Engineering Mathematics-III 3 1 0 30 20 50 100 150 4 BSC 2 Discrete Structures 3 1 0 30 20 50 100 150 4 ESC Digital Logic and IoT 3 3 0 0 30 20 50 100 150 3 ESC Systems Data Structures and 4 3 0 0 30 20 50 100 150 3 PCC Algorithms - 1 Computer Organization and 5 3 0 0 30 20 50 100 150 3 PCC Architecture Object Oriented Techniques 6 0 0 6 50 100 150 3 PCC using Java Data Structures and 7 Algorithms - 1 0 0 4 50 50 100 2 PCC Lab Digital Logic and IoT 8 Systems 0 0 2 25 25 50 1 ESC Lab 9 Internship Assessment 0 0 2 50 50 1 PW AI & 10 Cyber Ethics/Environmenta 2 0 0 30 20 50 50 100 0 NC l Science 11 MOOCs 110 Total 24 0 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 2 3  Subject Syllabus B. TECH. SECOND YEAR ACSE0306 DISCRETE STRUCTURES Course objective: The subject enhances one’s ability to develop logical thinking and ability to problem- solving. The objective of discrete structure is to enables students to formulate problems precisely, solve the problems, apply formal proofs techniques and explain their reasoning clearly.. Pre-requisites: 1. Basic Understanding of mathematics 2. Basic knowledge algebra. 3. Basic knowledge of mathematical notations 11/04/24 Madneeta Singh ACSE0306 Discrete Structures Unit 3 3  Subject Syllabus Course Contents / Syllabus UNIT-I Set Theory, Relation 8 Hours Set Theory: Definition of sets, countable and uncountable sets, Set operations, Partition of set, Cardinality, Venn Diagrams, proofs of some general identities on sets. Relation : Definition, types of relation, composition of relations, Equivalence relation, Partial ordering relation. UNIT-II Algebraic Structures 8 Hours Algebraic Structures: Definition, Properties, types: Semi Groups, Monoid, Groups, Abelian group, Properties of groups, Subgroup, cyclic group, Permutation group, Cosets, Normal subgroup, Homomorphism and isomorphism of Groups. 11/04/24 Madneeta Singh ACSE0306 Discrete Structures Unit 4 3  Subject Syllabus UNIT-III Posets, Hasse Diagram and Lattices 8 Hours Introduction, ordered set, Hasse diagrams of partially ordered set, isomorphic ordered set, well ordered set, properties of lattices, types of lattices. UNIT-IV Propositional Logic 8 Hours Propositional Logic: Propositions and compound Propositions, Basic logical operations, truth tables, tautologies, Contradictions, CNF, DNF Algebra of Proposition, logical implications, logical equivalence, predicates and quantifiers, Rules of Inference Predicate Logic: First order predicate, Well-formed formula of Predicate, Quantifiers, Inference Theory of Predicate Logic. 11/04/24 Madneeta Singh ACSE0306 Discrete Structures Unit 5 3  Subject Syllabus Definition and terminology, Representation of Graphs, Paths connectivity, Walks, Paths, Cycles, Bipartite, Regular, Planar and connected graphs, Components, Euler graphs, Euler's theorem, Hamiltonian path and circuits, Graph coloring, chromatic number, isomorphism and homomorphism of graphs. Course outcome: After completion of this course students will be able to: CO 1 Apply the basic principles of sets, relations & functions and mathematical K3 induction in computer science & engineering related problems. Understand the algebraic structures and its properties to solve complex CO 2 problems. K2 CO 3 Describe lattices and its types and apply Boolean algebra to simplify digital K2, K3 circuit. CO 4 Infer the validity of statements and construct proofs using predicate logic K3, K5 formulas. CO 5 Design and use the non-linear data structure like tree and graphs to K3, K6 solve real world problems. 11/04/24 Madneeta Singh ACSE0306 Discrete Structures Unit 3 6  Applications in CSE 1. Discrete Structures are useful in studying and describing objects and problems in branches of computer science such as computer algorithms, programming languages. 2. Computer implementations are significant in applying ideas from discrete mathematics to real- world problems, such as in operations research. 3. It is a very good tool for improving reasoning and problem-solving capabilities. 4. Discrete mathematics is used to include theoretical computer science, which is relevant to computing. 5. Discrete structures in computer science with the help of process algebras. 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 7 3  Course Objectives A course discrete structures used to represent discrete objects and relationships between these objects. These discrete structures include sets, relation , permutations, relations, graphs and trees etc. The subject enhances one’s ability to develop logical thinking and ability to problem solving. 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 8 3  Program Outcome Engineering Graduates will be able to Understand: 1. Engineering knowledge 2. Problem analysis 3. Design/development of solutions 4. Conduct investigations of complex 5. Modern tool usage 6. The engineer and society 7. Environment and sustainability 8. Ethics 9. Individual and team work 10. Communication 11. Project management and finance 12. Life-long learning Madneeta Singh ACSE0306 11/05/2020 9 Discrete Structures Unit 3  Program Educational Objectives S. PEO PEO Description No s 1. PEO 1 To have an excellent scientific and engineering breadth to comprehend, analyze, design and provide sustainable solutions for real-life problems using state-of-the-art technologies. 2. PEO 2 To have a successful career in industries, to pursue higher studies or to support entrepreneurial endeavours and to face global challenges. 3. PEO 3 To have an effective communication skill, professional attitude, ethical values and a desire to learn specific knowledge in emerging trends, technologies for research, innovation and product development and contribution to society. 4. PEO 4 To have life-long learning for up-skilling and re-skilling for successful professional career as engineer, scientist, entrepreneur, and bureaucrat for betterment of society. Madneeta Singh ACSE0306 11/05/2020 10 Discrete Structures Unit 3  Program Specific Outcomes Program S. No Specific PSO Description Outcome s 1. PSO 1 Identify, analyse real world problems and design their ethical solutions using artificial intelligence, robotics, virtual/augmented reality, data analytics, block chain technology, and cloud computing. 2. PSO 2 Design and develop the hardware sensor devices and related interfacing software systems for solving complex engineering problems. 3. PSO 3 Understand inter-disciplinary computing techniques and to apply them in the design of advanced computing. 4. PSO 4 Conduct investigation of complex problems with the help of technical, managerial, leadership qualities, and modern engineering tools provided by industry-sponsored laboratories. Madneeta Singh ACSE0306 11/05/2020 11 Discrete Structures Unit 3  CO-PSO mapping PSO1 PSO2 PSO3 PSO4 ACSE0306 1 2 3 -.1 ACSE0306 1 2 3 1.2 ACSE0306 3 2 3 1.3 ACSE0306 2 3 3 -.4 ACSE0306 2 3 2 1.5 11/05/2020 Average 1.8 Madneeta Singh 2.4 ACSE0306 2.8 0.6 12 Discrete Structures Unit 3  Unit 3 Objectives State the algebraic definition of a Boolean algebra The objective of unit 3 to solve problems using the algebraic properties of the elements of a Boolean algebra Define a poset and find the maximum and minimum elements of subsets of posets when they exist Find the supremum and infimum of subsets of posets when they exist Define a lattice and identify lattices among posets 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 13 3  Course Outcome Cours At the end of course , the student will be Bloom’s e able to understand Knowled Outco ge Level me (KL) ( CO) CO1 Apply the basic principles of sets, relations & K3 functions and mathematical induction in computer science & engineering related problems. CO2 Understand the algebraic structures and its K2 properties to solve complex problems. CO3 Describe lattices and its types and apply K2, K3 Boolean algebra to simplify digital circuit. CO4 Infer the validity of statements and construct K3, K5 proofs using predicate logic formulas. CO5 Design and use the non-linear data structure like K3, K6 tree and graphs to solve real world problems. 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 14 3  CO-PO Mapping PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 ACSE0306.1 3 2 2 - - 1 - - - 1 1 3 ACSE0306.2 3 3 2 2 1 - - - - - 2 1 ACSE0306.3 3 3 2 1 - - 3 - 2 2 2 2 ACSE0306.4 3 3 2 1 - - 1 - - 3 2 2 ACSE0306.5 3 3 2 1 - - 3 - - 1 3 3 AVERAGE 3 2.8 2 1.25 1 1 2.33 2 1.75 2 2.2 Mr. Minhaj Nezami Discrete Structures Unit 5 11/04/24 15  Prerequisite & Recap (CO3) Prerequisite Basic Understanding of class 10 mathematics NCERT. Basic Knowledge of sets and algebraic rules Basic Understanding of Set Theory, Relations and Functions. Basic Understanding of Algebraic Structures. Recap Now students are able to develop there logical thinking by using Sets, Relations, Functions and Mathematical Induction, & Algebraic Structures concepts and use in upcoming topic. i.e. Lattices & Boolean Algebra. 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 16 3  Content Video links Daily Quiz Weekly Assignment MCQ Old Question papers Expected Question for University Exam Summary References. 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 17 3  Unit Content  ordered set  Hasse diagrams of partially ordered set  isomorphic ordered set  well ordered set  properties of lattices  types of lattices 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 18 3  Topic Objectives: Lattices and Boolean Algebra(CO3) The student will be able to: – Represent a Hasse Diagram. – Give examples of finite and infinite sets. – Build new sets from existing sets by applying various combinations of the set operations for example intersection union, difference, and complement. – Determine Posets. – Sets are used to define the concepts of relations and functions. The study of geometry, sequences, probability, etc. requires the knowledge of sets. Madneeta Singh ACSE0306 Discrete Structures Unit 19 11/05/2020 3  Topic Prerequisite & Recap (CO3) A Set is a collection of elements. The elements that make up a set can be any kind of mathematical objects: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. Example: A collection of natural numbers, as in, N = {1,2,3,4,5...}. A relation can also be used to define an order on a set. An Ordered set is a relational structure (S, ≤) such that the realtion ≤ is an ordering. An ordered pair is a pair of numbers (x,y) written in a particular order 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 20 3  Ordered Sets & Posets Partial ordering: reflexive, anti-symmetric and transitive binary relation Example: For S = {a,b,c}, partial ordering satisfies Reflexive: a ≤ a Anti-Symmetric: a ≤ b and b ≤ a imply a=b Transitive: if a ≤ b and b ≤ c, then a ≤ c Madneeta Singh ACSE0306 Discrete Structures Unit 21 11/05/2020 3  Terminologies Cartesian Product: the product of two sets A and B such that every element of set A relates to every other element of set B to form ordered pairs. A*B = {(a,1),(a,2),(b,1),(b,2)} Reflexive Relation: A relation R, over a set A, is reflexive if every element of the set is 'related' to itself. Let's consider set A as follows: A = {p,q,r} Therefore, A*A = {(p,p),(p,q),(p,r),(q,p),(q,q), (q,r),(r,p),(r,q),(r,r)} Then the reflexive pairs in A*A would be all the diagonal elements of the matrix i.e. {(p,p),(q,q),(r,r)} as every Madneeta Singh element relates to ACSE0306 11/05/2020 22 itself. Discrete Structures Unit 3  Terminologies Symmetric: A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A. Anti-symmetric Relation: : A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric. Note: A relation can be both symmetric and antisymmetric. A relation can be neither symmetric nor antisymmetric. Madneeta Singh ACSE0306 Discrete Structures Unit 23 11/05/2020 3  Terminologies Madneeta Singh ACSE0306 Discrete Structures Unit 24 11/05/2020 3  POSET(Partially Ordered Set) Madneeta Singh ACSE0306 Discrete Structures Unit 25 11/05/2020 3  Hasse Diagram Example: Find the maximal and minimal elements in the following Hasse diagram Madneeta Singh ACSE0306 Discrete Structures Unit 26 11/05/2020 3  POSET(Partially Ordere d Set) Example Let A be the poset of nonnegative real number with the usual partial order ≤. Then 0 is a minimal element of A. There are no maximal elements of A Example The poset Z with the usual partial order ≤ has no maximal elements and has no minimal elements Madneeta Singh ACSE0306 Discrete Structures Unit 27 11/05/2020 3  POSET(Partially Ordere d Set)  Greatest element: An element a in A is called a greatest element of A if x ≤ a for all x in A.  Least element An element a in A is called a least element of A if a ≤ x for all x in A. Note: an element a of (A, ≤ ) is a greatest (or least) element if and only if it is a least (or greatest) element of (A, ≥ ) Madneeta Singh ACSE0306 Discrete Structures Unit 28 11/05/2020 3  Isomorphic Ordered Sets Let (A, ≤) and (B, ≤) be two partially ordered sets then they are said to be isomorphic if their “structures” are entirely similar. Example – Let two POSETS, A = P({0, 1}) ordered by ≤ and B = {1, 2, 3, 6} ordered by division relation are Isomorphic Ordered Sets. Madneeta Singh ACSE0306 11/05/2020 29 Discrete Structures Unit 3  Isomorphic Ordered Sets Explanation : A = { Φ, {0}, {1}, {0, 1} } with subset relation. If we try to define a map. f( Φ ) = 1, f( {0} ) = 2, Hasse Diagram of POSET A f( {1} ) = 3 and f( {0, 1} ) = 6. So both the sets are isomorphic. Hence, they are Isomorphic Ordered Set. Hasse Diagram of POSET B Madneeta Singh ACSE0306 11/05/2020 30 Discrete Structures Unit 3  Well Ordered Set A partially ordered set is called a Well Ordered set if every non-empty subset has a least element. Example – A set of natural number and less than operation ([N, ≤]) then it is a Well ordered Set because firstly it is a POSET and if we take any two natural numbers e.g. n1 and n2 where n1≤n2. Here, n1 is the least element. So, it is a Well Ordered Note – Set. Any Well ordered set is totally ordered. Every subset of a Well ordered set is Well-ordered with the same ordering. Madneeta Singh ACSE0306 11/05/2020 31 Discrete Structures Unit 3  Hasse Diagram(CO3) Unit element The greatest element of a poset, if it exists, is denoted by 1 and is often called the unit element. Zero element The least element of a poset, if it exists, is denoted by 0 and is often called the zero element. Madneeta Singh ACSE0306 Discrete Structures Unit 32 11/05/2020 3  Hasse Diagram(CO3) If (A, ≤ ) be a poset, then 1. If greatest element exists, then it is unique. 2. If least element exists, then it is unique. Proof: Assume that there are two greatest elements of poset (A, ≤ ), say a and b. Therefore, x ≤ a and x ≤ b, ∀ x ∈ A. ∴a ≤ b (b is greatest element) and b ≤ a (a is greatest element) ∴by antisymmetric property, a = b. Similarly, for least element. Madneeta Singh ACSE0306 Discrete Structures Unit 33 11/05/2020 3  Hasse Diagram(CO3) Let (L,∨, ∧) be a lattice. 1. commutative law for join and meet: For a, b ∈ L, a ∨ b = b ∨ a; a ∧ b = b ∧ a 2. Associative law for join and meet: For a, b, c ∈ L, (a ∨ b) ∨ c = a ∨ (b ∨ c ); (a ∧ b) ∧ c = a ∧ (b ∧ c ) 3. Absorption law for join and meet: For a, b ∈ L, a ∨ (a ∧ b) = a ; a ∧ (a ∨ b) = a Madneeta Singh ACSE0306 Discrete Structures Unit 34 11/05/2020 3  Lattice Let a, b ∈ L, a ∨ b = l.u.b.{a,b} = l.u.b.{b,a} = b ∨ a a ∧ b = g.l.b.{a,b} = g.l.b.{b,a} = b ∧ a Proof of 2: Let a, b ∈ L, b ≤ (a ∨ b) ≤ (a ∨ b) ∨ c and c ≤ (a ∨ b) ∨ c By def. of l.u.b., b ∨ c ≤ (a ∨ b) ∨ c Also, a ≤ (a ∨ b) ≤ (a ∨ b) ∨ c ∴ a ∨ (b ∨ c ) ≤ (a ∨ b) ∨ c …(1) Madneeta Singh ACSE0306 Discrete Structures Unit 35 11/05/2020 3  Properties of Lattices 1. Idempotent Properties a) a v a = a b) a Λ a = a 2.Commutative Properties a) a v b = b v a b) a Λ b = b Λ a 3.Associative Properties a) a v (b v c)= (a v b) v c b) a Λ(b Λ c)= (a Λ b) Λc 4. Absorption Properties a) a v (a Λ b) = a b) a Λ (a v b) = a Madneeta Singh ACSE0306 11/05/2020 36 Discrete Structures Unit 3  Bounded Lattices(CO3) Bounded A lattice L is said to be bounded if it has a greatest element 1 and a least element 0 For instance: Example: The lattice P(S) of all subsets of a set S, with the relation containment is bounded. The greatest element is S and the least element is empty set. Example : The lattice Z+ under the partial order of divisibility is not bounded, since it has a least element 1, but no greatest element. Madneeta Singh ACSE0306 11/05/2020 37 Discrete Structures Unit 3  Distributive Lattices(CO3) Distributive A lattice (L, ≤) is called distributive if for any elements a, b and c in L we have the following distributive properties: 1. a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) 2. a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) If L is not distributive, we say that L is non distributive. Note: the distributive property holds when a. any two of the elements a, b and c are equal or b. when any one of the elements is 0 or I. Madneeta Singh ACSE0306 11/05/2020 38 Discrete Structures Unit 3  Distributive Lattices(CO3) Example For a set S, the lattice P(S) is distributive, since join and meet each satisfy the distributive property. Example The lattice whose Hasse diagram shown in adjacent diagram is distributive Madneeta Singh ACSE0306 11/05/2020 39 Discrete Structures Unit 3  Distributive Lattices(CO3) Example :Show that the lattices as follows are non- distributive. a ∧ ( b ∨ c) = a ∧ I = a (a∧ b) ∨(a ∧ c) = b ∨ 0 = b a ∧ ( b ∨ c) = a ∧ I = a (a∧ b) ∨ (a ∧ c) = 0 ∨ 0 = 0 Madneeta Singh ACSE0306 11/05/2020 40 Discrete Structures Unit 3  Complemented Lattices(CO3) Complement of an element: Let L be bounded lattice with greatest element 1 and least element 0, and let a in L. An element b in L is called a complement of a if a ∨ b = 1 and a ∧ b =0 Note: 0’ = 1 and 1’ = 0 Complemented Lattice: A lattice L is said to be complemented if it is bounded and every element in it has a complement. Madneeta Singh ACSE0306 11/05/2020 41 Discrete Structures Unit 3  Complemented Lattices(CO3) Example : The lattice L=P(S) is such that every element has a complement, since if A in L, then its set complement A has the properties A ∨ A = S and A ∧ A=ф. That is, the set complement is also the complement in L. Example : complemented lattices where complement of element is not unique Madneeta Singh ACSE0306 11/05/2020 42 Discrete Structures Unit 3  Faculty Video Links, Youtube & NPTEL Video Links and Online Courses Details (CO3) Youtube/other Video Links https://www.youtube.com/watch?v=qPtGlrb_sXg&list=PL0862 D1A947252D20&index=40 CO3 https://www.youtube.com/watch?v=WW7YO0b4QHs&list=PLE AYkSg4uSQ2Wfc_l4QEZUSRdx2ZcFziO CO3 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 43 3  Daily Quiz(CO3) In a poset (partially ordered set), which of the following statements is true? A) Every pair of elements is comparable. B) There exists a unique maximum element. C) Every subset has a least upper bound (supremum). D) Every element has a successor. Which of the following is a lattice? A) The set of all natural numbers with the relation "less than or equal to." B) The set of all integers with the relation "divides." C) The set of all subsets of a given set with the relation "subset." D) The set of all real numbers with the relation "less than or equal to." 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 44 3  Daily Quiz(CO3) Which property does not necessarily hold in a poset? A) Reflexivity B) Symmetry C) Transitivity D) Antisymmetry In a lattice, the greatest element is also known as: A) Lower bound B) Meet C) Join D) Top element Which of the following statements is true about a distributive lattice? A) Every pair of elements has a unique supremum. B) Every pair of elements has a unique infimum. C) The distributive property holds for all pairs of elements. D) It must contain a maximum element. 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 45 3  Weekly Assignment(CO3) 1. Define a lattice. Give an example of a finite lattice and explain why it satisfies the definition of a lattice. Include a description of its meet and join operations. 2. Discuss the concept of a distributive lattice. Provide an example of a distributive lattice and explain why it is distributive. Include a description of how meet and join operations behave in distributive lattices. 3.Consider a poset that consists of the set {a,b,c,d,e}\{a, b, c, d, e\}{a,b,c,d,e} with the relation {(a,b),(a,c),(a,d),(b,e),(c,e),(d,e)}\{ (a, b), (a, c), (a, d), (b, e), (c, e), (d, e) \}{(a,b),(a,c),(a,d),(b,e),(c,e),(d,e)}. Draw the Hasse diagram for this poset. Identify all maximal and minimal elements, and describe any chains and anti chains present in this poset. 4. Define a partially ordered set (poset) and provide an example that illustrates the concept. Explain how the order relation is defined in your example. 5. Describe the concept of a Hasse diagram 6. Explain what it means for a poset to have a maximum element. Provide an example of a poset that includes a maximum element and draw its Hasse diagram. 11/05/2020 Madneeta Singh ACSE0306 Discrete Structures Unit 46 3  MCQs(CO3) A sublattice(say, S) of a lattice(say, L) is a convex sublattice of L if _________ a) x>=z, where x in S implies z in S, for every element x, y in L b) x=y and y