Discrete Unit-3 M. Abdul Mateen Siddiqui PDF

Noida Institute of Engineering and Technology, Greater Noida Posets, Hasse Diagram and Lattices Unit: 3 Discrete Structures & M. Abdul Mateen Siddiqui Theory of Logic Assistant Professor (BCSE030...

Noida Institute of Engineering and Technology, Greater Noida Posets, Hasse Diagram and Lattices Unit: 3 Discrete Structures & M. Abdul Mateen Siddiqui Theory of Logic Assistant Professor (BCSE0306) Department of CSE (Cyber B Tech 3rd Security) Sem M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 1 11/05/2020 Unit 3  Faculty Introduction Name M. Abdul Mateen Siddiqui Qualification M. Tech. in CSE with specialization in CFIS Designation Assistant Professor Department Cyber Security 11/05/2020 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 2 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 3 Unit 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/13/24 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 4 Unit 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/13/24 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 5 Unit 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/13/24 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 6 Unit 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/13/24 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures Unit 3 7  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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 8 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 9 Unit 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 M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 10 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. M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 11 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. M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 12 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 ACSE0306 1.8 Discrete2.4 M. Abdul Mateen Siddiqui Structures 2.8 0.6 13 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 14 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 15 Unit 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 M. Abdul Mateen Siddiqui Discrete Structures Unit 5 11/13/24 16  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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 17 Unit 3  Content Video links Daily Quiz Weekly Assignment MCQ Old Question papers Expected Question for University Exam Summary References. 11/05/2020 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 18 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 19 Unit 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. M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 20 11/05/2020 Unit 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 co llection 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 21 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 22 11/05/2020 Unit 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 Mateen M. Abdul every element relates to Siddiqui 11/05/2020 ACSE0306 Discrete Structures 23 itself. 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. M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 24 11/05/2020 Unit 3  Terminologies M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 25 11/05/2020 Unit 3  POSET(Partially Ordered Set) M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 26 11/05/2020 Unit 3  Hasse Diagram Pictorial representation of POSET is called Hasse Diagram. Steps: 1.Draw Diagraphs. 2.Remove reflexive and transitive edges. 3.Draw diagraph in such a way that all edges are pointing upwards. 4.Remove directions and replace circle with dot. M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 27 11/05/2020 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. M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 28 11/05/2020 Unit 3  Hasse Diagram Example: Find the maximal and minimal elements in the following Hasse diagram M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 29 11/05/2020 Unit 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 1. Top elements or element not related to other element or having no successor 2. Bottom elements or having no predecessor M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 30 11/05/2020 Unit 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. Topper of subset and Topper of that topper Bottom and bottom of the bottom M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 31 11/05/2020 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 32 11/05/2020 Unit 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, ≥ ) M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 33 11/05/2020 Unit 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. M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 34 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 M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 35 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. M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 36 Unit 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) M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 37 11/05/2020 Unit 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 M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 38 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. M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 39 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. M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 40 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 M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 41 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 M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 42 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. M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 43 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 M. Abdul Mateen Siddiqui 11/05/2020 ACSE0306 Discrete Structures 44 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 45 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 46 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 47 Unit 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 M. Abdul Mateen Siddiqui ACSE0306 Discrete Structures 48 Unit 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