🗊 Презентация Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al

Категория: Английский язык
Нажмите для полного просмотра!
Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №1 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №2 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №3 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №4 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №5 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №6 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №7 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №8 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №9 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №10 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №11 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №12 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №13 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №14 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №15 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №16 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №17 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №18 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №19 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №20 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №21 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №22 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №23 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №24 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №25 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №26 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №27 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №28 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №29 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №30 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №31 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №32 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №33 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №34 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №35 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №36 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №37 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №38 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №39 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №40 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №41 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №42 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №43 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №44 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №45 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №46 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №47 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №48 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №49 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №50 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №51 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №52 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №53 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №54 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №55 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №56 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №57 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №58 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №59 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №60 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №61 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №62 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №63 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №64 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №65 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №66 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №67 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №68 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №69 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №70 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №71 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №72 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №73 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №74 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №75 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №76 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №77 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №78 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №79 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №80 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №81 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №82 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №83 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №84 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №85 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №86 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №87 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №88 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №89 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №90 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №91 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №92 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №93 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №94 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №95 Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al, слайд №96
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting al. Доклад-сообщение содержит 96 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting...
Описание слайда:
Relations Irina Prosvirnina Relations, properties of relations Equivalence relations Partial orderings Hasse diagrams The topological sorting algorithm

Слайд 2


Relations The Cartesian product of A and B, denoted by , is the set of all ordered pairs (a, b), where and . Hence,
Описание слайда:
Relations The Cartesian product of A and B, denoted by , is the set of all ordered pairs (a, b), where and . Hence,

Слайд 3


Relations Definition 1 A binary relation between two sets and is defined to be a subset R of the Cartesian product . We use the notation to denote...
Описание слайда:
Relations Definition 1 A binary relation between two sets and is defined to be a subset R of the Cartesian product . We use the notation to denote that . Moreover, when belongs to , is said to be related to by . In the special case when , we simply refer to as a relation on .

Слайд 4


Relations Example 1 Write down all ordered pairs belonging to the following binary relations between and }: Solution
Описание слайда:
Relations Example 1 Write down all ordered pairs belonging to the following binary relations between and }: Solution

Слайд 5


Relations Example 2 The following defines a relation on : is a divisor of Write down the ordered pairs belonging to . Solution
Описание слайда:
Relations Example 2 The following defines a relation on : is a divisor of Write down the ordered pairs belonging to . Solution

Слайд 6


Relations We can use the concept of a directed graph do describe the ordered pairs belonging to a given binary relation.
Описание слайда:
Relations We can use the concept of a directed graph do describe the ordered pairs belonging to a given binary relation.

Слайд 7


Relations Let and be two finite sets and let be a binary relation between these two sets. We represent the elements of these two sets as the vertices...
Описание слайда:
Relations Let and be two finite sets and let be a binary relation between these two sets. We represent the elements of these two sets as the vertices of a graph. For each of the ordered pairs in a relation , draw an arrow linking the related elements. This is called a directed graph or digraph.

Слайд 8


Example 3 Consider the relation between and given in example 1, b): . The corresponding directed graph is given in the figure below. 1 2 3 4 5 6 7
Описание слайда:
Example 3 Consider the relation between and given in example 1, b): . The corresponding directed graph is given in the figure below. 1 2 3 4 5 6 7

Слайд 9


Relations For a relation on a single set we use a directed graph in which a single set of vertices represents the elements of and arrows link the...
Описание слайда:
Relations For a relation on a single set we use a directed graph in which a single set of vertices represents the elements of and arrows link the related elements.

Слайд 10


Properties of relations We now restrict our attention to relations defined on a single set and define a number of properties which a given relation...
Описание слайда:
Properties of relations We now restrict our attention to relations defined on a single set and define a number of properties which a given relation on may or may not possess.

Слайд 11


Properties of relations Definition 2 A relation on a set is reflexive if for all in . In terms of ordered pairs a given relation is reflexive if...
Описание слайда:
Properties of relations Definition 2 A relation on a set is reflexive if for all in . In terms of ordered pairs a given relation is reflexive if belongs to for all possible values of .

Слайд 12


Properties of relations In terms of directed graph representation is reflexive if there is always an arrow from every vertex to itself.
Описание слайда:
Properties of relations In terms of directed graph representation is reflexive if there is always an arrow from every vertex to itself.

Слайд 13


Properties of relations Definition 3 A relation on a set is symmetric when implies for all and in . In terms of ordered pairs a given relation is...
Описание слайда:
Properties of relations Definition 3 A relation on a set is symmetric when implies for all and in . In terms of ordered pairs a given relation is symmetric if when belongs to then belongs to for all possible values of and .

Слайд 14


Properties of relations In terms of directed graph representation is symmetric if whenever there is an arc from to then there is also an arc from to .
Описание слайда:
Properties of relations In terms of directed graph representation is symmetric if whenever there is an arc from to then there is also an arc from to .

Слайд 15


Properties of relations Definition 4 A relation on a set is antisymmetric when and implies for all and in . In terms of ordered pairs a given...
Описание слайда:
Properties of relations Definition 4 A relation on a set is antisymmetric when and implies for all and in . In terms of ordered pairs a given relation is antisymmetric if when belongs to and belongs to then for all possible values of and .

Слайд 16


Properties of relations In terms of directed graph representation is antisymmetric if whenever there is an arc from to and is not equal to then there...
Описание слайда:
Properties of relations In terms of directed graph representation is antisymmetric if whenever there is an arc from to and is not equal to then there is no arc from to .

Слайд 17


Properties of relations Definition 5 A relation on a set is transitive when and implies for all and in . In terms of ordered pairs a given relation...
Описание слайда:
Properties of relations Definition 5 A relation on a set is transitive when and implies for all and in . In terms of ordered pairs a given relation is transitive if when belongs to and belongs to then belongs to for all possible values of and .

Слайд 18


Properties of relations In terms of directed graph representation is transitive if whenever there is an arc from to and there is an arc from to then...
Описание слайда:
Properties of relations In terms of directed graph representation is transitive if whenever there is an arc from to and there is an arc from to then there is no arc from to .

Слайд 19


Properties of relations Example 5 Which of the following define a relation that is reflexive, symmetric, antisymmetric or transitive? « divides » on...
Описание слайда:
Properties of relations Example 5 Which of the following define a relation that is reflexive, symmetric, antisymmetric or transitive? « divides » on the set of natural numbers; « » on the set of integers; « has the same age as » on the set of all people?

Слайд 20


Equivalence relation Definition 1 A relation on a set is called an equivalence relation if it is reflexive, symmetric, and transitive. Equivalence...
Описание слайда:
Equivalence relation Definition 1 A relation on a set is called an equivalence relation if it is reflexive, symmetric, and transitive. Equivalence relations are important throughout mathematics and computer science. One reason for this is that in an equivalence relation, when two elements are related it makes sense to say they are equivalent.

Слайд 21


Equivalence relation Definition 2 Two elements and that are related by an equivalence relation are called equivalent. The notation is often used to...
Описание слайда:
Equivalence relation Definition 2 Two elements and that are related by an equivalence relation are called equivalent. The notation is often used to denote that and are equivalent elements with respect to a particular equivalence relation.

Слайд 22


Equivalence relation Example 1 Let be the relation on the set of integers such that or . is reflexive, symmetric, and transitive. It follows that is...
Описание слайда:
Equivalence relation Example 1 Let be the relation on the set of integers such that or . is reflexive, symmetric, and transitive. It follows that is an equivalence relation.

Слайд 23


Equivalence relation Example 2 Let be the relation on the set of real numbers such that is an integer. is reflexive, symmetric, and transitive. It...
Описание слайда:
Equivalence relation Example 2 Let be the relation on the set of real numbers such that is an integer. is reflexive, symmetric, and transitive. It follows that is an equivalence relation.

Слайд 24


Equivalence relation Example 3 (Congruence modulo ) Let be an integer with . Let . is an equivalence relation on the set of integers. is reflexive :...
Описание слайда:
Equivalence relation Example 3 (Congruence modulo ) Let be an integer with . Let . is an equivalence relation on the set of integers. is reflexive : , is symmetric : ), is transitive :

Слайд 25


Equivalence relation Example 4 Suppose that is the relation on the set of strings of English letters such that if and only if , where is the length...
Описание слайда:
Equivalence relation Example 4 Suppose that is the relation on the set of strings of English letters such that if and only if , where is the length of the string : . is reflexive, symmetric, and transitive. It follows that is an equivalence relation.

Слайд 26


Equivalence relation Example 5 Let be a positive integer and a set of strings. Suppose that is the relation on such that if and only if , or both and...
Описание слайда:
Equivalence relation Example 5 Let be a positive integer and a set of strings. Suppose that is the relation on such that if and only if , or both and have at least characters and the first characters of and are the same. That is, a string of fewer than characters is related only to itself; a string with at least n characters is related to a string if and only if has at least characters and begins with the characters at the start of . is reflexive, symmetric, and transitive. It follows that is an equivalence relation.

Слайд 27


Equivalence relation Example 6 The “divides” relation in the set of positive integers is not an equivalence relation. This relation is not symmetric...
Описание слайда:
Equivalence relation Example 6 The “divides” relation in the set of positive integers is not an equivalence relation. This relation is not symmetric (for instance, 2|4 but 2).

Слайд 28


Equivalence relation Example 7 Let be the relation on the set of real numbers such that is not an equivalence relation because it is not transitive:
Описание слайда:
Equivalence relation Example 7 Let be the relation on the set of real numbers such that is not an equivalence relation because it is not transitive:

Слайд 29


Equivalence relation Definition 3 Let be an equivalence relation on a set . The set of all elements that are related to an element of is called the...
Описание слайда:
Equivalence relation Definition 3 Let be an equivalence relation on a set . The set of all elements that are related to an element of is called the equivalence class of . The equivalence class of a with respect to is denoted by : . When only one relation is under consideration, we can delete the subscript and write for this equivalence class.

Слайд 30


Equivalence relation Definition 3 If , then is called a representative of this equivalence class. Any element of a class can be used as a...
Описание слайда:
Equivalence relation Definition 3 If , then is called a representative of this equivalence class. Any element of a class can be used as a representative of this class. That is, there is nothing special about the particular element chosen as the representative of the class.

Слайд 31


Equivalence relation Example 8 Let be the relation on the set of real numbers such that or . Find . Solution For example, , , .
Описание слайда:
Equivalence relation Example 8 Let be the relation on the set of real numbers such that or . Find . Solution For example, , , .

Слайд 32


Equivalence relation Example 9 What are the equivalence classes of and for congruence modulo ? Solution
Описание слайда:
Equivalence relation Example 9 What are the equivalence classes of and for congruence modulo ? Solution

Слайд 33


Equivalence relation Example 10 What is the equivalence class of the string 0111 with respect to the equivalence relation from on the set of all bit...
Описание слайда:
Equivalence relation Example 10 What is the equivalence class of the string 0111 with respect to the equivalence relation from on the set of all bit strings? Solution

Слайд 34


Equivalence relation Theorem 1 Let be an equivalence relation on a set . These statements for elements and of are equivalent: ,
Описание слайда:
Equivalence relation Theorem 1 Let be an equivalence relation on a set . These statements for elements and of are equivalent: ,

Слайд 35


? Proof Assume that is symmetric , , is transitive This shows that . The proof that is similar.
Описание слайда:
? Proof Assume that is symmetric , , is transitive This shows that . The proof that is similar.

Слайд 36


? Proof Let , (because because is reflexive).
Описание слайда:
? Proof Let , (because because is reflexive).

Слайд 37


? Proof Assume that Then there is an element c with: . ∧  ∧ 
Описание слайда:
? Proof Assume that Then there is an element c with: . ∧  ∧ 

Слайд 38


Equivalence relation It follows that these equivalence classes are either equal or disjoint and that the equivalence classes form a partition of .
Описание слайда:
Equivalence relation It follows that these equivalence classes are either equal or disjoint and that the equivalence classes form a partition of .

Слайд 39


Equivalence relation Definition 4 A partition of a set is a collection of disjoint nonempty subsets of that have as their union.
Описание слайда:
Equivalence relation Definition 4 A partition of a set is a collection of disjoint nonempty subsets of that have as their union.

Слайд 40


Equivalence relation Example 11 What are the sets in the partition of the integers arising from congruence modulo 4? Solution There are four...
Описание слайда:
Equivalence relation Example 11 What are the sets in the partition of the integers arising from congruence modulo 4? Solution There are four congruence classes: These congruence classes are disjoint, and every integer is in exactly one of them. In other words these congruence classes form a partition.

Слайд 41


Equivalence relation Example 12 What are the sets in the partition of the set of all bit strings arising from the relation on the set of all bit...
Описание слайда:
Equivalence relation Example 12 What are the sets in the partition of the set of all bit strings arising from the relation on the set of all bit strings? Solution Note that every bit string of length less than three is equivalent only to itself. Every bit string of length three or more is equivalent to one of the eight bit strings and . We have , .

Слайд 42


Example 12What are the sets in the partition of the set of all bit strings arising from the relation on the set of all bit strings? Solution Note...
Описание слайда:
Example 12What are the sets in the partition of the set of all bit strings arising from the relation on the set of all bit strings? Solution Note that every bit string of length less than three is equivalent only to itself. Every bit string of length three or more is equivalent to one of the eight bit strings and . We have , . These 15 equivalence classes are disjoint and every bit string is in exactly one of them. These equivalence classes partition the set of all bit strings.

Слайд 43


Partial Orderings Definition 5 A relation on a set is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A...
Описание слайда:
Partial Orderings Definition 5 A relation on a set is called a partial ordering or partial order if it is reflexive, antisymmetric, and transitive. A set together with a partial ordering is called a partially ordered set, or poset, and is denoted by Members of are called elements of the poset.

Слайд 44


Partial Orderings Example 1 The “greater than or equal” relation is a partial ordering on the set of integers.
Описание слайда:
Partial Orderings Example 1 The “greater than or equal” relation is a partial ordering on the set of integers.

Слайд 45


Partial Orderings Example 2 The divisibility relation| is a partial ordering on the set of positive integers, because it is reflexive, antisymmetric,...
Описание слайда:
Partial Orderings Example 2 The divisibility relation| is a partial ordering on the set of positive integers, because it is reflexive, antisymmetric, and transitive.

Слайд 46


Partial Orderings Example 3 The inclusion relation is a partial ordering on the power set of a set .
Описание слайда:
Partial Orderings Example 3 The inclusion relation is a partial ordering on the power set of a set .

Слайд 47


Partial Orderings Example 4 Let be the relation on the set of people such that if and are people and is older than . is not reflexive, because no...
Описание слайда:
Partial Orderings Example 4 Let be the relation on the set of people such that if and are people and is older than . is not reflexive, because no person is older than himself or herself. It follows that is not a partial ordering.

Слайд 48


Partial Orderings Definition 6 The elements and of a poset are called comparable if either or . When and are elements of such that neither nor , and...
Описание слайда:
Partial Orderings Definition 6 The elements and of a poset are called comparable if either or . When and are elements of such that neither nor , and are called incomparable.

Слайд 49


Partial Orderings Definition 7 If is a poset and every two elements of are comparable, is called a totally ordered or linearly ordered set, and is...
Описание слайда:
Partial Orderings Definition 7 If is a poset and every two elements of are comparable, is called a totally ordered or linearly ordered set, and is called a total order or a linear order. A totally ordered set is also called a chain.

Слайд 50


Partial Orderings Example 5 The poset is totally ordered, because or whenever and are integers.
Описание слайда:
Partial Orderings Example 5 The poset is totally ordered, because or whenever and are integers.

Слайд 51


Partial Orderings Example 6 The poset is not totally ordered because it contains elements that are incomparable, such as 5 and 7.
Описание слайда:
Partial Orderings Example 6 The poset is not totally ordered because it contains elements that are incomparable, such as 5 and 7.

Слайд 52


Constructing the Hasse Diagram for
Описание слайда:
Constructing the Hasse Diagram for

Слайд 53


Constructing the Hasse Diagram for
Описание слайда:
Constructing the Hasse Diagram for

Слайд 54


Constructing the Hasse Diagram for
Описание слайда:
Constructing the Hasse Diagram for

Слайд 55


Constructing the Hasse Diagram for
Описание слайда:
Constructing the Hasse Diagram for

Слайд 56


Constructing the Hasse Diagram for
Описание слайда:
Constructing the Hasse Diagram for

Слайд 57


Constructing the Hasse Diagram for
Описание слайда:
Constructing the Hasse Diagram for

Слайд 58


Constructing the Hasse Diagram for
Описание слайда:
Constructing the Hasse Diagram for

Слайд 59


Draw the Hasse diagram representing the partial ordering o
Описание слайда:
Draw the Hasse diagram representing the partial ordering o

Слайд 60


Draw the Hasse diagram representing the partial ordering on
Описание слайда:
Draw the Hasse diagram representing the partial ordering on

Слайд 61


Maximal and minimal elements Definition 8 An element of a poset is called maximal if it is not less than any element of the poset. That is, a is...
Описание слайда:
Maximal and minimal elements Definition 8 An element of a poset is called maximal if it is not less than any element of the poset. That is, a is maximal in the poset if there is no such that . Similarly, an element of a poset is called minimal if it is not greater than any element of the poset. That is, a is minimal if there is no element such that .

Слайд 62


Maximal and minimal elements Maximal and minimal elements are easy to spot using a Hasse diagram. They are the “top” and “bottom” elements in the...
Описание слайда:
Maximal and minimal elements Maximal and minimal elements are easy to spot using a Hasse diagram. They are the “top” and “bottom” elements in the diagram.

Слайд 63


The Hasse diagram representing the partial ordering o
Описание слайда:
The Hasse diagram representing the partial ordering o

Слайд 64


The Hasse diagram representing the partial ordering on
Описание слайда:
The Hasse diagram representing the partial ordering on

Слайд 65


Topological sorting Suppose that a project is made up of 20 different tasks. Some tasks can be completed only after others have been finished. How...
Описание слайда:
Topological sorting Suppose that a project is made up of 20 different tasks. Some tasks can be completed only after others have been finished. How can an order be found for these tasks? To model this problem we set up a partial order on the set of tasks so that if and only if and are tasks where cannot be started until has been completed. To produce a schedule for the project, we need to produce an order for all 20 tasks that is compatible with this partial order. We will show how this can be done.

Слайд 66


Topological sorting Definition 9 A total ordering is said to be compatible with the partial ordering if whenever . Constructing a compatible total...
Описание слайда:
Topological sorting Definition 9 A total ordering is said to be compatible with the partial ordering if whenever . Constructing a compatible total ordering from a partial ordering is called topological sorting.

Слайд 67


Topological sorting Lemma Every finite nonempty poset has at least one minimal element. Proof Choose an element of . If is not minimal, then there is...
Описание слайда:
Topological sorting Lemma Every finite nonempty poset has at least one minimal element. Proof Choose an element of . If is not minimal, then there is an element in with . If is not minimal, then there is an element in with . Continue this process. Because there are only a finite number of elements in the poset , this process must end with a minimal element .

Слайд 68


The topological sorting algorithm Let be finite poset. First choose a minimal element in . Such an element exists by lemma. is also a poset. If...
Описание слайда:
The topological sorting algorithm Let be finite poset. First choose a minimal element in . Such an element exists by lemma. is also a poset. If choose a minimal element of this poset. Such an element exists by lemma. If choose a minimal element of this poset. Continue this process. Because is a finite set, this process must terminate.

Слайд 69


The topological sorting algorithm The desired total ordering is defined by: This total ordering is compatible with the original partial ordering.
Описание слайда:
The topological sorting algorithm The desired total ordering is defined by: This total ordering is compatible with the original partial ordering.

Слайд 70


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset

Слайд 71


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 72


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 73


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 74


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 75


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 76


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 77


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 78


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 79


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 80


The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the poset Solution

Слайд 81


The topological sorting algorithm Example 1 Find a compatible total ordering for the posetа Solution 12
Описание слайда:
The topological sorting algorithm Example 1 Find a compatible total ordering for the posetа Solution 12

Слайд 82


The topological sorting algorithm Example 2 A development project at a computer company requires the completion of seven tasks. Some of these tasks...
Описание слайда:
The topological sorting algorithm Example 2 A development project at a computer company requires the completion of seven tasks. Some of these tasks can be started only after other tasks are finished. A partial ordering on tasks is set up by considering if task cannot be started until task has been completed. The Hasse diagram for the seven tasks, with respect to this partial ordering, is shown in the figure. Find an order in which these tasks can be carried out to complete the project.

Слайд 83


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset.
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset.

Слайд 84


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 85


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 86


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 87


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution 
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution 

Слайд 88


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution  
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution  

Слайд 89


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution  
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution  

Слайд 90


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 91


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 92


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 93


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 94


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 95


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Слайд 96


The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution
Описание слайда:
The topological sorting algorithm Example 2 Find a compatible total ordering for the poset. Solution

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию