Chapter 15 - Relations. In this chapter, the following content will be discussed: Basic concepts of relation, types of relations, relation on a set, the inverse of a relation, representing relations using digraphs, N-ary relations. | (CSC 102) Lecture 15 Discrete Structures Previous Lectures Summary Procedural Versions Properties of Sets Empty Set Properties Difference Properties Set Identities Boolean Algebra and Set theory Puzzles Relations Today's Lecture Basic concepts of relation Types of relations Relation on a set The inverse of a relation Representing relations using Digraphs N-ary Relations Relations Example: Let P be a set of people, C be a set of cars, and R be the relation describing which person drives which car(s). P = {Carl, Suzanne, Peter, Carla}, C = {Mercedes, BMW, tricycle} R = {(Carl, Mercedes), (Suzanne, Mercedes), (Suzanne, BMW), (Peter, tricycle)} This means that Carl drives a Mercedes, Suzanne drives a Mercedes and a BMW, Peter drives a tricycle, and Carla does not drive any of these vehicles. Relations If we want to describe a relationship between elements of two sets A and B, we can use ordered pairs with their first element taken from A and their second element taken from B. Since this is a relation between two sets, it is called a binary relation. Definition: Let A and B be sets. A binary relation R from A to B is a subset of A B. In other words, for a binary relation R we have R A B. We use the notation aRb to denote that (a, b) R and aRb to denote that (a, b) R. Relations If we have two sets A={1,2,3,4,5} and B={5,6,7,8,9} The cartesian product of A and B is A × B = { (1,5), (1,6), (1,7), (1,8), (1,9), (2,5), (2,6), (2,7), (2,8), (2,9), (3,5), (3,6), (3,7), (3,8), (3,9), (4,5), (4,6), (4,7), (4,8), (4,9), (5,5), (5,6), (5,7), (5,8), (5,9) }. The rule is to add 4: R = { (1,5), (2,6), (3,7), (4,8), (5,9) }. R is subset of A × B. Relations 5 6 7 8 9 1 2 3 4 5 The Rule is ‘ADD 4’ One to One Relations Relations Many to Many relation If we have two sets A={Ahmad, Peter, Ali, Jaweria, Hamad} and B={Paris, London, Dubai, New York, Cyprus} The cartesian product of A and B is A × B = { (Ahmad,Paris), ., (Hamad,Cyprus) }. The rule is “Has visited”: R = { (Ahmad,Paris), . | (CSC 102) Lecture 15 Discrete Structures Previous Lectures Summary Procedural Versions Properties of Sets Empty Set Properties Difference Properties Set Identities Boolean Algebra and Set theory Puzzles Relations Today's Lecture Basic concepts of relation Types of relations Relation on a set The inverse of a relation Representing relations using Digraphs N-ary Relations Relations Example: Let P be a set of people, C be a set of cars, and R be the relation describing which person drives which car(s). P = {Carl, Suzanne, Peter, Carla}, C = {Mercedes, BMW, tricycle} R = {(Carl, Mercedes), (Suzanne, Mercedes), (Suzanne, BMW), (Peter, tricycle)} This means that Carl drives a Mercedes, Suzanne drives a Mercedes and a BMW, Peter drives a tricycle, and Carla does not drive any of these vehicles. Relations If we want to describe a relationship between elements of two sets A and B, we can use ordered pairs with their first element taken from A and their second element taken from B. Since this
