bilangan 5

CHAPTER 5: SETS AND FUNCTIONS
5.1: Naїve Set Theory
5.2: Set Operations
5.3: Functions and Their Algebra
5.4: Relations

5.1 NAїVE SET THEORY

 A set is an unordered collection of objects, things or symbols, etc.

 The objects in a set are also called the elements or members of the set.

 Two sets are equal if and only if they have the same elements. For instance,
A={1,2,3} B= {3,1,2} C= {2,2,3,1,1,1,2} D={-2,3,1}
- A=B, the order in which the elements are listed does not matter.
- A=B=C, it does not matter if an element is listed more than once.
- A D, because set A and set D do not have same elements. Similarly, BD, and C D.

 2 types of set notation :
 listing the elements
 specifying the main characteristics of the set

  ~ “ is a member of “

 ~ “ is not a member of “

Venn Diagram
Sets can be represented graphically using Venn diagram. For example, a Venn diagram for the set A= {a, b, c, d } is as follows.



 Universal set , U
 Contains all the objects under consideration

 Null or empty set ,  or {}
 Has no elements
 Note that the set {} is not empty. It has one element which is . A set with one element is called a singleton set.
 Example: Odd numbers divisible by 2.

 Finite set
 Contains exactly n distinct elements where n is a nonnegative integer

 Infinite set
 It is not finite (has infinite number of elements)

 Power set , P(S)
 Def: Given a set S, the power set of S is the set of all subsets of the set S.
The power set of S is denoted by P(S).
 Number of elements in power set denoted as n [P(S)].
 n [P(S)] = 2n where n is the number of elements in set S.

Eg.: If A = {0, 1, 2}, find the power set of set A .



Eg.: What is the power set of set J if the number of elements in set J is 10?


 Subset
 The A  B if and only if every elements of A is also an element of B
 A  B ~ “ A is a proper subset of B ( A  B but A  B )
 For any set A,    and   .


 Let S be a set. If there are exactly n distinct elements in S where n is a nonnegative integer, then n is the cardinality of S, .
Example: (a) A= {2, 4, 6, 8, 10} then A= 5 and n(A)= 5.
(b) B= {2, 3, 3, 4, 5, 5, 6, 7} then B=6 and n(B)= 8.
(c) C= { } then C=0 and n(C)= 0

5.2 SET OPERATIONS

Cartesian Products
What is a Cartesian product of two sets? Let A and B be two sets. The Cartesian product of A and B, denoted by A x B, is the set of all ordered pairs (a, b) where aA and bB. Hence,
A x B = {(a, b) aA  b B}

Example 1:
Let A ={a, b, c} and B={1, 2}, find the Cartesian product A x B.
Solution:





Example 2:
Let A = {1, 2, 3}, B = {x, y}, and C = {a, b}. Find
(a) A x B x C
(b) C x B x A
Solution:









We define the subset R of the Cartesian product A x B a relation from the set A to set B. The elements of the set R are ordered pairs, where the first element belongs to A and the second element belongs to B.
For example,
Let A = {1, 2, 3} and B = {a, b, c}
Then, the relation, R = {(1, a ), (2, a ), (3, a ), (2, b), (3, c)} is a subset of A x B

NOTE
A x B  B x A.








Set Operations

 Complement of set, A or A’ = {x | x A}
 The complement of the set A is the set of elements which are not in A
 ( ) = A

 Union, A  B = {x | x A or x B}
 Contains those elements that are either in A or in B, or in both.

 Intersection, A  B = {x | x A and x B}
 Containing those elements in both A and B.

 Two sets are called disjoint if their intersection is the empty set.
 A  B = {}

 Difference, A – B or A \ B or A ~ B = {x | x A and x B}
 Containing those elements that are in A but not in B
 Also called the complement of B with respect to A

Eg: A = {1, 3, 5}, B = {1, 2, 3}. Find A – B.



 Symmetric difference, A B = {x | (x A and x B) or (x B and x A)}
 All elements that belong to A or B, but not to both A and B.

Eg.: A = {a, b, c, d}, B = {a, c, e, f, g}. Find A B.


Example 3:
Given U = { x : 10 30 , x is positive integer }
A = { x : x is prime number }
B = { x : x is the number which is greater than 14 }
C = { x : x is odd number }

A , B and C are the subsets of universal set , U . List down the elements in
( i ) A – C
( ii ) ( A – B )’
(iii) A C
Solution:






Example 4:
Given that U = {x| x is an integer and 1 10}
A = {x| x }
B = {x| x2 64}
C = {x| x is an even integer}
(i) List the elements of A and B.
(ii) Represent the relationships between these sets (A, B and C) on a clearly labeled Venn diagram (List down all the elements in each set).
(iii) List in full the elements of P =
Solution:














Example 5:
Given that
U = {x: 10 50, x is an integer}
P = {x: x, when divided by 12, leaves a remainder of 4}
Q = {x: x is prime number}
R = {x: x is a multiple of 7}

List all the elements of sets
(i) P, Q and R.
(ii) P .
(iii) (P .
Solution :










Set Identities

o Identity laws
A   = A
A  U = A

o Domination laws
A  U = U
A   = 

o Idempotent laws


o Complementation law
( ) = A

o Commutative laws
A  B = B  A
A  B = B  A

o Associative laws
A  ( B  C ) = ( A  B )  C
A  ( B  C ) = ( A  B )  C

o Distributive laws
A  ( B  C ) = ( A  B )  ( A  C )
A  ( B  C ) = ( A  B )  ( A  C )

o De Morgan’s laws
=
=

o Absorption laws
A  ( A  B ) = A
A  ( A  B ) = A

o Complement laws
A  = U
A  = 




Example 6:

Solution :









Example 7:

Solution :










Example 8:

Solution :


















Computer Representation of Sets

Def: Let A = {a, b, c, …, r}, U = {x1, x2, …, xn} and A is a subset of U. Then assigns 1 to an
element that belong to A and 0 to an element that does not belong to A.

Example 9:
Let Y = {0, 1, 2, …, 15}.
(a) Find the representation of {2, 4, 5, 7, 11, 14} as a bit string.
(b) Write down the set represented by the bit string 1010011011101001.
(c) If A and B are represented by the bit strings 0011010001101101 and 1010100100010111,
find the representation as bit strings of A B, A B, and .
Solution:










Example 10:
Let the bit strings of A and B is 1100101010 and 0010100100 respectively. Find the bit strings of A B and A B.
Solution:









Example 11:
Let the bit strings of A and B is 00101110 and 10100101 respectively. Find the bit strings of
A  B, A  B and .
Solution:







Problem Solving Using Formulae
n ( A B ) = n ( A ) + n ( B ) – n ( A B )


Example 12:
76 pupils were asked if they had visited Thailand , Brunei or Indonesia before . 8 of them have been to all three countries , 16 have been to Thailand and Brunei , 30 have been to Brunei and Indonesia and 22 have been to Thailand and Indonesia . Given that 36 had been to Thailand , 38 to Brunei and 52 to Indonesia , illustrate the above information on a clearly labeled Venn diagram . Hence , find out how many pupils have visited
( i ) one of the three countries only ;
( ii ) more than one of the three countries ;
( iii ) Thailand or Indonesia ;
( iv ) none of the three counties .
Solution :










Example 13:
Three sets P , Q and R are subsets of universal set , U , and satisfy the following conditions :
P  Q = Q , P R =  and n( R Q ) = n( R )
Represent these sets on a clearly labeled Venn diagram .
Solution :







Example 14:
Draw a Venn diagram and shaded the region to show the following combinations.

Solution :





Example 15:
A biology teacher instructed his 84 students to collect some hibiscus, sunflower and orchid. On
the next day, the students brought the plants to the class. Here is the summary:

39 of them brought hibiscus
54 of them brought sunflower
39 of them brought orchid
15 of them brought hibiscus and orchid
18 of them brought hibiscus and sunflower
27 of them brought orchid and sunflower

(i) Assume that there are x of them who brought all the three plants. There are y of them
who brought orchid and sunflower but not hibiscus. Draw a Venn diagram to illustrate
the above information.
(ii) Find the value of x and y.
Solution :






























Example 16:
A bank surveyed 55 of its customers account and categorizes them as either Current,
Fixed or Over 10K (over 10 thousand). All these categories are mutually exclusive and
each customer can be classified as single category or two or all.
Eg : A customer can be current and fixed .

The survey has the following details:

Total number of customers classified as all categories = 11
Total number of customers classified as only Current = 8
Total number of customers classified as only Fixed = 9
Total number of customers classified as only Over 10K = 6
Total number of customers classified as Current and Fixed = 16
The number of Current and Over 10K customers is more than the number of Fixed and Over 10K customers by 8.

(a) Let x denote the number of Current and Over 10K customers only and y denote the number of Fixed and Over 10K customers only . Draw a Venn diagram representing the above data.
(b) Write down two equations representing x and y.
(c) Solve for x and y.
Solution :
























Example 17:
A computer school has 33 students each of whom is sitting for examinations in at least one of the
following: Physics, Mathematics and Chemistry. 12 students take all three subjects, 16 take
Mathematics and Chemistry, 14 take Mathematics and Physics, 17 take Physics and Chemistry
and 22 take Chemistry. The number of students who sit for Physics is the same as Mathematics.
(i) Put all this information into a Venn diagram denoting ‘x’ and ‘y’ respectively the number of students who takes Mathematics only and Physics only.
(ii) Find the value of x and y.
(iii) How many students are sitting for only one subject?
Solution:




































Example 18:
From a survey on 40 students, it was found that 12 liked pineapple, 19 liked durian, 17 liked
apple, 6 liked durian and apple, 2 liked all the three flavors and 2 students do not like any of
these fruits. Given that x number of students liked apple and pineapple but not durian whereas y
number of students liked pineapple and durian but not apple.
(i) Draw a Venn diagram to represent the above information.
(ii) If the number of students who liked pineapple and durian is the same as the number of students who liked apple and pineapple, find x and y.
Solution:





































5.3 FUNCTIONS AND THEIR ALGEBRA

 Definition function:
A relation in which every element in the domain has a unique image in the codomain.

 Notation of functions :
A function f from x to y : f : x y or y = f ( x )



f(x )




domain codomain / range

 Domain – set of input values for a function
 Range – set of all images of a function
– is a subset of codomain
 c is the image of a and a is a pre-image of c .

Example 1 :
Let f be the function from Z to Z that assigns the square of an integer to this integer . Then ,
f(x) = x2 , where the domain of f is the set of all integers , the codomain of f can be chosen to be the set of all integers , and the range of f is the set of all nonnegative integers that are perfect squares , namely , { 0 , 1 , 4 , 9 , … }.



















Algebra of Function

 Let f and g be two functions and x
 Sum : ( f + g ) ( x ) = f ( x ) + g ( x )
 Difference : ( f – g ) ( x ) = f ( x ) – g ( x )
 Product : ( fg ) ( x ) = f ( x ) g ( x )
 Quotient : (

Example 2:
f ( x ) = and g ( x ) = , find the following functions and the domain of each function.
( a ) ( f + g )(x ) ( b ) ( f – g )(x ) ( c ) ( fg )(x ) ( d ) ( )( x )
Solutions:






























One-To-One and Onto Functions

 Some functions have distinct images at distinct members of their domain . These functions are said to be one-to-one , or injective.

Example 3:
Determine whether the function f = {(1, b), (3, a), (2, c)} from X = {1, 2, 3} to Y = {a, b, c} is one-to-one.
Solution:


Example 4:
Determine whether the function f = {(1, a), (2, b), (3, a)} from X = {1, 2, 3} to Y = {a, b, c} is one-to-one.
Solution:


Example 5:
Determine whether the function f(x) = x2 from the set of integers to the set of integers is
one-to-one .
Solution :





Example 6:
Determine whether the function f(x) = x + 1 is one-to-one .
Solution :







 When every member of the codomain is the image of some element of the domain (range and codomain are equal), this property is called onto, or surjective.

Example 7:
Determine whether the function f = {(1, a), (2, c), (3, b)} from X = {1, 2, 3} to Y = {a, b, c} is onto.
Solution:



Example 8:
Determine whether the function f = {(1, b), (3, a), (2, c)} from X = {1, 2, 3} to Y = {a, b, c, d} is onto.
Solution:


Example 9:
Is the function f(x) = x2 from the set of integers to the set of integers onto ?
Solution :




Example 10:
Is the function f(x) = x + 1 from the set of integers to the set of integers onto ?
Solution :






 The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto.

Example 11:
Let f be the function from { a , b , c , d } to { 1 , 2 , 3 , 4 } with f(a) = 4 , f(b) = 2 , f(c) = 1 , and f(d) = 3 . Is f a bijection?
Solution:

















Inverse Functions And Compositions Of Functions:

 Inverse functions
If f is a one – to – one correspondence (invertible) function with domain X and range Y, then f –1, called inverse function of f, has domain Y and range X. Hence, f –1(y) = x when f (x) = y for all y in Y.

 Compositions of functions
 Let g be a function from the set A to the set B and let f be a function from the set B to the set C . The composition of the functions f and g , denoted by f g , is defined by
( f g )(a) = f (g(a)) .

 Not commutative , f g g f

Example 12:
Given that and , find
(i) ,
(ii) .
Solution:









Example 13:
Let f(x) = 9x + 2 and g(x) = . Find
(i) ,
(ii) ,
(iii) g –1.
Solution:









Example 14:
The function g is defined by g(x) = 8 – 3x . Find:
( a ) expressions for g – 1(x) and g2(x) ;
( b ) the value of x for which g – 1(x) = g2(x) .
Solution :















Example 15:
Let h and k be functions from {1, 2, 3} to {a, b, c} and from {a, b, c} to {1, 2, 3} respectively,
such that h(1)=c, h(2)=b, h(3)=a, and k(a)=2, k(b)=1, k(c)=1.
(i) Is h or k one-to-one?
(ii) Is h or k onto?
(iii) Does either h or k have inverse? If so, find this inverse.
(iv) Find and
Solution:













 When the composition of a function and its inverse is formed , in either order , an identity function is obtained .
( f –1 f )(a) = f –1(f (a)) = f –1(b) = a ,
and
( f f –1)(b) = f (f –1(b)) = f (a) = b .
Special Types of Relations
 Let f be a relation from A to B. Then we say that f is everywhere defined if domain of relation f = A.

Example 15:
Given A = {1, 2, 3, 4}, B = {a, b, c, d} and let f = {(1, a), (2, a), (3, d), (4, c)}. Determine whether the relation f is one-to-one, onto and / or everywhere defined.
Solution:









Example 16:
Given A = {a1, a2, a3}, B = {b1, b2, b3}, C = {c1, c2} and D = {d1, d2, d3, d4}. For each of the following relations, determine whether it is one-to-one, onto and / or everywhere defined.
(a) f1 : A B {(a1, b2), (a2, b3), (a3, b1)}
(b) f2 : A D {(a1, d2), (a2, d1), (a3, d4)}
(c) f3 : B C {(b1, c2), (b2, c2), (b3, c1)}
(d) f4 : D B {(d1, b1), (d2, b2), (d3, b1)}
Solution:





















5.4 RELATIONS

The most direct way to express a relationship between elements of two sets is to use ordered pairs made up of two related elements. For this reason, sets of ordered pairs are called binary relations.

 Let A and B be sets. A binary relation from A to B is a subset of A x B.

In other words, a binary relation from A to B is a set R of ordered pairs where the first element of each ordered pair comes from A and the second element comes from B . We use the notation a R b to denote that ( a , b )  R and a b to denote that ( a , b )  R .

Example 1:
Let A = { 0 , 1 , 2 } and B = { a , b } . Then { ( 0 , a ) , ( 0 , b ) , ( 1 , a ) , ( 2 , b ) } is a relation from A to B . This means , for instance , that 0 R a , but that 1 b .

Relations on A Set
 A relation on the set A is a relation from A to A .

Example 2:
A relation R is defined on a set A = {0, 1, 2, 3}. List the elements of R if
R = {(x, y) | x y, x A and y A}.
Solution :







Example 3:
Consider the following relations on the set of integers :
R1 = { ( a , b )  a  b }
R2 = { ( a , b )  a > b }
R3 = { ( a , b )  a = b or a = -b }
R4 = { ( a , b )  a = b }
R5 = { ( a , b )  a = b + 1 }
R6 = { ( a , b )  a + b  3 }
Which of these relations contain each of the pairs (1, 1), (1, 2) , ( 2 , 1 ) , ( 1 , -1 ) , and ( 2 , 2 ) ?
Solution :






Properties of Relations
 A relation R on a set A is called reflexive if ( a , a )  R for every element a  A .

Example 4:
Consider the following relations on { 1 , 2 , 3 , 4 } :
R1 = {( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 4 ) , ( 4 , 1 ) , ( 4 , 4 )}
R2 = {( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 1 )}
R3 = {( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 4 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) , ( 4 , 1 ) , ( 4 , 4 )}
R4 = {( 2 , 1 ) , ( 3 , 1 ) ( 3 , 2 ) ( 4 , 1 ) , ( 4 , 2 ) , ( 4 , 3 )}
R5 = {(1, 1), (1, 2), (1, 3), ( 1 , 4 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 3 ) , ( 3 , 4 ) , ( 4 , 4 )}
R6 = {( 3 , 4 )}
Which of these relations are reflexive ?
Solution :





Example 5:
Consider the following relations on the set of integers:
R1 = { ( a , b )  a  b }
R2 = { ( a , b )  a > b }
R3 = { ( a , b )  a = b or a = -b }
R4 = { ( a , b )  a = b }
R5 = { ( a , b )  a = b + 1 }
R6 = { ( a , b )  a + b  3 }
Which of these relations are reflexive ?
Solution :





Example 6:
Is the “divides” relation on the set of positive integers reflexive ?
Solution :









 A relation R on a set A is called symmetric if ( b , a )  R whenever ( a , b )  R , for a , b  A . A relation R on a set A such that ( a , b )  R and ( b , a )  R only if a = b , for a , b  A , is called anti-symmetric .

Example 7:
Which of the following relations are symmetric and which are anti-symmetric ?
R1 = {( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 4 ) , ( 4 , 1 ) , ( 4 , 4 )}
R2 = {( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 1 )}
R3 = {( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 4 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) , ( 4 , 1 ) , ( 4 , 4 )}
R4 = {( 2 , 1 ) , ( 3 , 1 ) ( 3 , 2 ) ( 4 , 1 ) , ( 4 , 2 ) , ( 4 , 3 )}
R5 = {(1, 1), (1, 2), (1, 3), ( 1 , 4 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 3 ) , ( 3 , 4 ) , ( 4 , 4 )}
R6 = {( 3 , 4 )}
Solution :





Example 8:
Consider the following relations on the set of integers:
R1 = { ( a , b )  a  b }
R2 = { ( a , b )  a > b }
R3 = { ( a , b )  a = b or a = -b }
R4 = { ( a , b )  a = b }
R5 = { ( a , b )  a = b + 1 }
R6 = { ( a , b )  a + b  3 }
Which of these relations are symmetric and which are anti-symmetric?
Solution :





Example 9 :
Is the “divides” relation on the set of positive integers symmetric ? Is it anti-symmetric ?
Solution :










 A relation R on a set A is called transitive if whenever ( a , b )  R and
( b , c )  R , then ( a , c )  R , for a , b , c  A .

Example 10:
For each of the following relations on the set { 1 , 2 , 3 , 4 } , decide whether it is reflexive ,
symmetric , anti-symmetric , and / or transitive .
( i ) { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) }
( ii ) { ( 1 , 1 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) , ( 4 , 4 ) }
Solution :







Example 11:
For each of the following relations on the set { 1 , 2 , 3 , 4 } , decide whether it is reflexive , symmetric , antisymmetric , and / or transitive .
( i ) { ( 2 , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 2 ) , ( 3 , 3 ) , ( 3 , 4 ) }
( ii ) { ( 1 , 1 ) , ( 1 , 2 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) , ( 4 , 4 ) }
( iii ) { ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 1 ) , ( 3 , 4 ) }
Solution :







Example 12:
For each of the following relations on the set { 1 , 2 , 3 , 4 } , decide whether it is reflexive ,
symmetric , anti-symmetric , and / or transitive .
( i ) { ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 4 ) }
( ii ) { ( 1 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) , ( 4 , 4 ) }
Solution :










Combining Relations

 Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S is the relation consisting of ordered pairs (a, c), where a A, c C, and for which there exists an element b B such that (a, b) R and (b, c) S. We denote the composite of R and S by S R

Example 13:
Let R1 = {(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)} and R2 = {(1, 2), ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } be relations on the set { 1 , 2 , 3 , 4 } . Find
( i ) R1 R2 . ( ii ) R1 R2 . ( iii ) R2 – R1
( iv ) R1 R2 (v) R1 R2
Solution:





















Example 14:
Given A = {1, 2, 3, 4}, B = {a, b, c, d}, C = {x, y, z}, and let
R = {(1, a), (2, d), (3, a), (3, b), (3, d)} & S = {(b, x), (b, z), (c, y), (d, z)}. Find S R.
Solution:







Inverse Relation

Let R be any relation from a set A to a set B. Inverse of R, R-1 = {(b, a) : (a, b) R}.

Example 15:
Given R1 = {(1, 1), (2, 2), (3, 3)} and R2 = {(1, 1), (1, 2), (1, 3), (1, 4)}. Suppose that R1
and R2 are relations from {1, 2, 3} to {1, 2, 3, 4}, find:
(a) R1 R2
(b) R1 R2
(c) R1 – R¬2
(d) R1 R2
(e) and
Solution:













Representing Relations

There are many ways to represent a relation between finite sets . As we have seen , one way is to list its ordered pairs . In this section we will discuss two alternative methods for representing relations . One method uses zero-one matrices . The other method uses directed graphs .

Representing relations using matrices

A relation between finite sets can be represented using a zero-one matrix . Suppose that R is a relation from A = { a1 , a2 , … , am } to B = { b1 , b2 , … , bn } . The relation R can be represented by the matrix MR = [ mij ] , where

mij =




Example 16:
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 if a1 = 1 , a2 = 2 , and a3 = 3 , and b1 = 1 and b2 = 2 ?
Solution :




Example 17:
Represent each of the following relations on {1, 2, 3} with a matrix (with the elements of this set listed in increasing order) .
( i ) { ( 1 , 2 ) , ( 2 , 1 ) , ( 2 , 2 ) , ( 3 , 3 ) }
( ii ) { ( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) , ( 2 , 2 ) , ( 2 , 3 ) , ( 3 , 3 ) }
Solution :





Example 18:
Let A = { a1 , a2 , a3 } and B = { b1 , b2 , b3 , b4 , b5 }. Which ordered pairs are in the relation R represented by the matrix

MR = ?
Solution :



Example 19:
Given A = {1, 2, 3, 4}, B = {x, y, z} and R = {(1, y), (1, z), (3, y), (4, x), (4, z)}.
(a) Determine the matrix of the relation.
(b) Find R-1.
Solution:








The matrix of a relation on a set , which is a square matrix , can be used to determine whether the relation has certain properties .

The relation R is reflexive if all the elements on the main diagonal of MR are equal to 1 .
MR =

The relation R is symmetric if and only if mji = 1 whenever mij = 1 .
MR =

The relation R is antisymmetric if mij = 1 with i j , then mji = 0 .
MR =

Example 20:
Suppose that the relation R on a set is represented by the matrix
MR =
Is R reflexive , symmetric , and / or antisymmetric ?
Solution :





Suppose that R1 and R2 are relations on a set A represented by the matrices MR1 and MR2 , respectively . The matrix representing the union of these relations has a 1 in the positions where either MR1 or MR2 has a 1 . The matrix representing the intersection of these relations has a 1 in the positions where both MR1 and MR2 have a 1 . Thus , the matrices representing the union and intersection of these relations are
MR1 R2 = MR1 MR2 and MR1 R2 = MR1 MR2

Example 21:
Suppose that the relations R1 and R2 on a set A are represented by the matrices
MR1 = and MR2 = .
What are the matrices representing R1 R2 and R1 R2 ?
Solution :







Example 22:
Let A = B = {1, 2, 3, 4}, R = {(1, 1), (1, 3), (2, 3), (3, 1), (4, 2), (4, 4)}, and
S = {(1, 2), (2, 3), (3, 1), (3, 2), (4, 3)}. Compute
(a) M
(b) M
(c) M
(d) M
Solution:















The matrix for the composite of relations can be found using the Boolean product of the matrices for these relations . In particular , suppose that R is a relation from A to B and S is a relation from B to C . Let the zero-one matrices for SoR , R , and S be MSoR = [tij] , M¬R = [rij] , and MS = [sij] , respectively . The ordered pair ( ai , cj ) belongs to SoR if and only if there is an element bk such that ( a¬i , bk ) belongs to R and ( bk , cj ) belongs to S . It follows that tij = 1 if and only if rik = skj = 1 for some k .
MSoR = MR  MS

Example 23:
Let R1 and R2 be relations on a set A represented by the matrices

= and = .
Find the matrices that represent
( i ) R1 R2
( ii ) R1 R2
( iii ) R1 R2
Solution :













Example 24:
Find the matrix representing the relations S R where the matrices representing R and S are
MR = , Ms = .
Solution:





The matrix representing the composite of two relations can be used to find the matrix for M . In particular ,
M = M

Example 25:
Find the matrix representing the relation R2 where the matrix representing R is
MR =
Solution :








Representing relations using digraphs

• 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 represented using an arc from the vertex a back to itself . Such an edge is called a loop .

• Note that relations from a set A to a set B cannot be represented by directed graphs unless A = B .

Example 26:
Let A = {1, 2, 3, 4, 5}, and let R be the relation on A defined as follows:
R = {(1, 3), (1, 4), (2, 1), (2, 2), (2, 4), (3, 5), (5, 2), (5, 5)}
(a) Write down the matrix representation of R.
(b) Draw the graphical representation of R.
Solution:







Example 27:
Show the directed graph of the relation
R = { ( 1 , 1 ) , ( 1 , 3 ) , ( 2 , 1 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 1 ) , ( 3 , 2 ) , ( 4 , 1 ) }
on the set { 1 , 2 , 3 , 4 } .
Solution :













Example 28:
What are the ordered pairs in the relation R represented by the directed graph shown in figure?
1 2
• •





• •
4 3
Solution :
















Example 29:
A = {1, 2, 3, 4, 6}, R be the relation on A defined by “x divides y” or x | y.
(a) Write R as a set of ordered pairs.
(b) Draw its directed graph.
(c) Find the inverse R-1.
Solution:





















• A relation is reflexive if and only if there is a loop at every vertex of the directed graph .

• A relation is symmetric if and only if for every edge between distinct vertices in its digraph there is an edge in the opposite direction .

• A relation is anti symmetric if and only if there are never two edges in opposite directions between distinct vertices .

• A relation is transitive if and only if whenever there is an edge from a vertex x to a vertex y and an edge from a vertex y to a vertex z , there is an edge from x to z .









Example 30:
Determine whether the relations for the directed graphs shown in ( a ) and ( b ) are reflexive , symmetric , anti symmetric , and / or transitive .
(a)
• a



• •
b c

(b) a b
• •





• •
c d

Solution :






















Example 31:
Let R and S be the relations on the set A = {1, 2, 3, 4} such that
R = {(1, 1), (1, 2), (1, 4), (2, 2), (3, 3), (4, 2), (4, 4)}
S = {(1, 3), (1, 4), (3, 1), (3, 4), (4, 1), (4, 3), (4, 4)}
Find
(i) R S,
(ii) S R,
(iii) R – S.
(iv) Represent each of the relations R and S with a directed graph.
(v) Determine for each of the relations R and S whether it is reflexive, symmetric,
anti-symmetric and / or transitive.
Solution:


















Equivalence Relations

 A relation on a set A is called an equivalence relation if it is reflexive , symmetric , and transitive .

 Two elements that are related by an equivalence relation are called equivalent .

Example 32:
Which of the following relations on {1, 2, 3} are equivalence relations? Determine the properties
of an equivalence relation that the others lack.
(i) {(1, 1), (1, 2), (1, 3), (2, 2)}
(ii) {(1, 2), (2, 1)}
(iii) {(1, 1), (2, 2), (2, 3), (3, 2), (3, 3)}
Solution:


Example 33:
Which of the following relations on {1, 2, 3, 4, 5} are equivalence relations? Determine the
properties of an equivalence relation that the others lack.
(i) {(1, 1), (1, 3), (2, 2), (3, 1), (3, 3), (4, 4), (5, 5)}
(ii) {(1, 1), (1, 3), (2, 2), (3, 1), (3, 3), (3, 4), (4, 4), (5, 5)}
Solution:




Example 34:
Let R1 and R2 be the relations on the set {1, 2, 3, 4} given by

R1 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 2), (4, 3), (4, 4)}.

(i) Decide whether R1 is reflexive, symmetric, anti-symmetric and / or transitive.
(ii) List the elements of R2 – R1, R1 R2 and R1 R2.
(iii) Represent R2 with a zero-one matrix.
(iv) Draw the directed graph of R1.
(v) Decide whether R2 is an equivalence relation. Determine the properties of an equivalence relation that the others lack.
Solution:























2.5 QUANTIFIERS

 The universal quantification of P( x ) [ P(x), is called the universal quantifier ] is the proposition
“P (x) is true for all values of x in the universe of discourse.”

 When all of the elements in the universe of discourse can be listed – say , x1 , x2 , … , xn – it follows that the universal quantification P(x) is the same as the conjunction
P(x1) P(x2) … P(xn) ,
Since this conjunction is true if and only if P(x1) , P(x2) , … , P(xn) are all true .

 The existential quantification of P(x) [ P(x) , is called the existential quantifier ] is the proposition
“There exists an element x in the universe of discourse such that P(x) is true.”

 When all of the elements in the universe of discourse can be listed – say , x1 , x2 , … , xn – the existential quantification P(x) is the same as the disjunction
P(x1) P(x2) … P(xn) ,

Since this disjunction is true if and only if at least one of P(x1) , P(x2) , … , P(xn) is true .

Example 1:
Let P(x) be the statement “x + 1 > x.” What is the truth value of the quantification P(x), where the universe of discourse is the set of real numbers?
Solution:



Example 2:
What is the truth value of P(x), where P(x) is the statement “x2 < 10” and the universe of discourse consists of the positive integers not exceeding 4?
Solution:



Example 3:
Let Q(x) denote the statement “x = x + 1.” What is the truth value of the quantification Q(x), where the universe of discourse is the set of real numbers?
Solution:




Example 4:
What is the truth value of P(x) where P(x) is the statement “x2 > 10” and the universe of discourse consists of the positive integers not exceeding 4?
Solution:





Negation

