Lecture Discrete structures: Chapter 16 - Amer Rasheed

In this chapter, the following content will be discussed: Properties of relations; reflexive, symmetric and transitive relations; properties of “less than” relations; properties of congruence modulo 3; transitive closure of a relations. | (CSC 102) Lecture 16 Discrete Structures Previous Lecture Summery Basic concepts of relation Types of relations Relation on a set The inverse of a relation Representing relations using Digraphs N-ary Relations Today’s Lecture Properties of relations Reflexive, Symmetric and Transitive Relations Properties of “Less than” relations Properties of Congruence Modulo 3 Transitive closure of a relations 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. We can use arrows to display graphs. Example: Display the digraph with V = {a, b, c, d} and E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}. a b c d An edge of the form (b, b) is called a loop. Representing Relations Using Digraphs Representing Relations Using Digraphs Let A = {3, 4, 5, 6, 7, 8} and define a relation R on A as follows: For all x, y ∈ A, x R y ⇔ 2 | (x − y). Draw the directed graph of R. Note that 3 R 3 because 3 − 3 = 0 and 2 | 0 since 0 = 2 · 0. Thus there is a loop from 3 to itself. Similarly, there is a loop from 4 to itself, from 5 to itself, and so forth, since the difference of each integer with itself is 0, and 2 | 0. Note also that 3 R 5 because 3 − 5 = −2 = 2 · (−1). And 5 R 3 because 5 − 3 = 2 = 2 · 1. Hence there is an arrow from 3 to 5 and also an arrow from 5 to 3. The other arrows in the directed graph, are obtained by similar reasoning. Directed Graph of a Relation Let A = {3, 4, 5, 6, 7, 8} and define a relation R on A as follows: For all x, y ∈ A, x R y ⇔ 2 | (x − y). Draw the directed graph of R. N-ary Relations A binary relation is a subset of a Cartesian product of two sets, similarly, an n-ary relation is a subset of a Cartesian product of n sets. Definition Given sets A1, A2, . . . , An, an n-ary . | (CSC 102) Lecture 16 Discrete Structures Previous Lecture Summery Basic concepts of relation Types of relations Relation on a set The inverse of a relation Representing relations using Digraphs N-ary Relations Today’s Lecture Properties of relations Reflexive, Symmetric and Transitive Relations Properties of “Less than” relations Properties of Congruence Modulo 3 Transitive closure of a relations 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. We can use arrows to display graphs. Example: Display the digraph with V = {a, b, c, d} and E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}. a b c d An edge of the form (b, b) is called a loop. Representing Relations Using Digraphs Representing Relations Using

Bấm vào đây để xem trước nội dung
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.