Induction and recursion - Engineering

Induction and recursion - Engineering

Relations Chapter 9 1 Chapter Summary Relations and Their Properties n-ary Relations and Their Applications (not currently included in overheads) Representing Relations Closures of Relations (not currently included in overheads) Equivalence Relations Partial Orderings

2 Representing Relations Section 9.3 3 Section Summary Representing Relations using Matrices Representing Relations using Digraphs 4 Representing Relations Using Matrices

A relation between finite sets can be represented using a zero-one matrix. Suppose R is a relation from A = {a1, a2, , am} to B = {b1, b2, , bn}. The elements of the two sets can be listed in any particular arbitrary order. When A = B, we use the same ordering. The relation R is represented by the matrix MR = [mij], where The matrix representing R has a 1 as its (i,j) entry when ai is

related to bj and a 0 if ai is not related to bj. 5 Examples of Representing Relations Using Matrices Example 1: Suppose that A = {1,2,3} and B = {1,2}. Let R be the relation from A to B containing (a,b) if a A, b B, and a > b. What is the matrix representing R (assuming the ordering of elements is the same as the increasing numerical order)? Solution: Because R = {(2,1), (3,1),(3,2)}, the matrix is 6

Examples of Representing Relations Using Matrices (cont.) Example 2: Let A = {a1,a2, a3} and B = {b1,b2, b3,b4, b5}. Which ordered pairs are in the relation R represented by the matrix Solution: Because R consists of those ordered pairs (ai,bj) with mij = 1, it follows that: R = {(a1, b2), (a2, b1),(a2, b3), (a2, b4),(a3, b1), {(a3, b3), (a3, b5)}. 7 Matrices of Relations on Sets If R is a reflexive relation, all the elements on

the main diagonal of MR are equal to 1. R is a symmetric relation, if and only if mij = 1 whenever mji = 1. R is an antisymmetric relation, if and only if mij = 0 or mji = 0 when i j. 8 Example of a Relation on a Set Example 3: Suppose that the relation R on a set is represented by the matrix

Is R reflexive, symmetric, and/or antisymmetric? Solution: Because all the diagonal elements are equal to 1, R is reflexive. Because MR is symmetric, R is symmetric and not antisymmetric because both m1,2 and m2,1 are 1. 9 Representing Relations Using Digraphs Definition: A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a,b), and the vertex b is called the terminal vertex of this

edge. An edge of the form (a,a) is called a loop. Example 7: A drawing of the directed graph with vertices a, b, c, and d, and edges (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), and (d, b) is shown here. 10 Examples of Digraphs Representing Relations Example 8: What are the ordered pairs in the relation represented by this directed graph?

Solution: The ordered pairs in the relation are (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), and (4, 3) 11 Determining which Properties a Relation has from its Digraph Reflexivity: A loop must be present at all vertices in the graph. Symmetry: If (x,y) is an edge, then so is (y,x).

Antisymmetry: If (x,y) with x y is an edge, then (y,x) is not an edge. Transitivity: If (x,y) and (y,z) are edges, then so is (x,z). 12 Determining which Properties a Relation has from its Digraph Example 1 a c b d

Reflexive? No, not every vertex has a loop Symmetric? Yes (trivially), there is no edge from one vertex to another Antisymmetric? Yes (trivially), there is no edge from one vertex to another Transitive? Yes, (trivially) since there is no edge from one vertex 13 Determining which Properties a Relation has from its Digraph Example 2 a c

b d Reflexive? No, there are no loops Symmetric? No, there is an edge from a to b, but not from b to a Antisymmetric? No, there is an edge from d to b and b to d Transitive? No, there are edges from a to c and from c to b, but there is no edge from a to d 14 Determining which Properties a Relation has from its Digraph Example 3 a

c b d Reflexive? No, there are no loops Symmetric? No, for example, there is no edge from c to a Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back Transitive? No, there is no edge from a to b 15

Determining which Properties a Relation has from its Digraph Example 4 a c b d Reflexive? No, there are no loops Symmetric? No, for example, there is no edge from d to a Antisymmetric? Yes, whenever there is an edge from one vertex to another, there is not one going back

Transitive? Yes (trivially), there are no two edges where the first 16 Example of the Powers of a Relation a b a d R

d c b a d R4 c b c

R2 b a d R 3 c The pair (x,y) is in Rn if there is a path of length n from x to y in R

17 (following the direction of the arrows). Partial Orderings Section 9.6 18 Section Summary Partial Orderings and Partially-ordered Sets Lexicographic Orderings Hasse Diagrams Lattices (not currently in overheads) Topological Sorting (not currently in

overheads) 19 Partial Orderings Definition 1: A relation R on a set S is called a partial ordering, or partial order, if it is reflexive, antisymmetric, and transitive. A set together with a partial ordering R is called a partially ordered set, or poset, and is denoted by (S, R). Members of S are called elements of the poset. 20

Partial Orderings (continued) Example 1: Show that the greater than or equal relation () is a partial ordering on the set of integers. Reflexivity: a a for every integer a. Antisymmetry: If a b and b a , then a = b. Transitivity: If a b and b c , then a c. These properties all follow from the order axioms for the integers. (See Appendix 1). 21 Partial Orderings (continued) Example 2: Show that the divisibility relation () is a partial ordering on the set of integers.

Reflexivity: a a for all integers a. (see Example 9 in Section 9.1) Antisymmetry: If a and b are positive integers with a | b and b | a, then a = b. (see Example 12 in Section 9.1) Transitivity: Suppose that a divides b and b divides c. Then there are positive integers k and l such that b = ak and c = bl. Hence, c = a(kl), so a divides c. Therefore, the relation is transitive. (Z+, ) is a poset. 22 Partial Orderings (continued)

Example 3: Show that the inclusion relation () is a partial ordering on the power set of a set S. Reflexivity: A A whenever A is a subset of S. Antisymmetry: If A and B are positive integers with A B and B A, then A = B. Transitivity: If A B and B C, then A C. The properties all follow from the definition of set inclusion. 23 Comparability

Definition 2: The elements a and b of a poset (S, ) are comparable if either a b or b a. When a and b are elements of S so that neither a b nor b a, then a and b are called incomparable. The symbol is used to denote the relation in any poset. Definition 3: If (S, ) is a poset and every two elements of S are comparable, S 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. Definition 4: (S, ) is a well-ordered set if it is a poset such that is a total ordering and every nonempty subset of S has a least element. 24

Lexicographic Order Definition: Given two posets (A1,1) and (A2,2), the lexicographic ordering on A1 A2 is defined by specifying that (a1, a2) is less than (b1,b2), that is, (a1, a2) (b1,b2), either if a1 1 b1 or if a1 = b1 and a2 2 b2. This definition can be easily extended to a lexicographic ordering on strings (see text). Example: Consider strings of lowercase English letters. A lexicographic ordering can be defined using the ordering of the letters in the alphabet. This is the same ordering as that used in dictionaries. discreet discrete, because these strings differ in the seventh position and e t.

discreet discreetness, because the first eight letters agree, but the second string is longer. 25 Hasse Diagrams Definition: A Hasse diagram is a visual representation of a partial ordering that leaves out edges that must be present because of the reflexive and transitive properties. A partial ordering is shown in (a) of the figure above. The loops due to the reflexive property are deleted in (b). The edges that must be present due to the transitive property are deleted in (c). The Hasse diagram for the partial ordering (a), is depicted in (c). 26

Procedure for Constructing a Hasse Diagram To represent a finite poset (S, ) using a Hasse diagram, start with the directed graph of the relation: Remove the loops (a, a) present at every vertex due to the reflexive property. Remove all edges (x, y) for which there is an element z S such that x z and z y. These are the edges that must be present due to the transitive property.

Arrange each edge so that its initial vertex is below the terminal vertex. Remove all the arrows, because all edges point upwards 27

Recently Viewed Presentations

  • Proximity Sensor

    Proximity Sensor

    อ่านค่าบนหน้าจอ NXT. Light Sensor. Light Sensor ทำหน้าที่ตรวจจับความมืดและแสงสว่าง ... โดย Light Sensor จะวัดแสงโดยรอบของมันเท่านั้น ...
  • Chapter 13 - Weather Analysis and Forecasting

    Chapter 13 - Weather Analysis and Forecasting

    Chapter 13 - Weather Analysis and Forecasting The National Weather Service Different weather forecast offices (WFOs) are responsible for their specific region
  • yackaninaothsscience.weebly.com

    yackaninaothsscience.weebly.com

    Define the vocabulary listed in the title on page 699 (vertebrate, invertebrate, phylum, bilateral symmetry, radial symmetry, protostome, & deuterostome) & answer questions 1-5 on pg 704. Read pg 714-715 of 23.4 (READ COMPLETELY as we are dissecting an annelid):
  • Global TB Drug Facility

    Global TB Drug Facility

    Sélection des produits 2. Prévisions 3. Approvisionnement (incluant prix le plus bas et qualité garantie) 4. Soutien pour la gestion des médicaments 10 étapes d'approche pratique pour sécuriser la livraison des médicaments antituberculeux au travers du mécanisme d'achat direct (Direct...
  • Pythagorean Theorem Word Problems

    Pythagorean Theorem Word Problems

    2. c 5 12 40 24 b C = 13 B = 32 PYTHAGOREAN THEOREM WORD PROBLEMS OBJECTIVE: Students will solve for missing values using the Pythagorean theorem for word problems RECALL THE PYTHAGOREAN THEOREM THE PYTHAGOREAN THEOREM STATES THAT...
  • HUMR5140 Introduction to Human Rights Law Autumn 2011

    HUMR5140 Introduction to Human Rights Law Autumn 2011

    Golder v. UK (1975), para. 29: "The Court is prepared to consider … that it should be guided by Articles 31 to 33 of the Vienna Convention of 23 May 1969 on the Law of Treaties." Banković (2001), para. 55:...
  • J.L Peyraud INRA Perspective of Livestock production 2050

    J.L Peyraud INRA Perspective of Livestock production 2050

    ariation. according to local contexts. Comprehensive framework and methods to assess the sustainability of livestock system. Synergies and trade off between services (+ and -) Levers that can improve delivery of services .
  • What does replicable real world evidence from real

    What does replicable real world evidence from real

    Disclosures. This work was funded by the Laura and John Arnold Foundation. At the time that this work was conducted, Dr. Wang was principal investigator on other grants from: Agen