Ì Exam ple 0.1.10: Given A= {1,2}, B = {x, y, z} and C = {3, 4}, find
A B C
× × and n A B C
(
)
× × .
Solu tion
n A B C
n A n B n C
(
)
( ) ( ) ( ) ( ) ( ) ( )
.
× ×
=
⋅
⋅
=
=
2 3 2 12.
0.1.2 Rela tions and Func tions
Definition of Relation: A relation on sets S and T is a set of ordered pairs (s, t),
where
(a) s S s
S
∈ ( is a member of )
(b) t T
∈
(c) S and T need not be different
(d) The set of all first elements in the “domain” of the relation, and
(e) The set of all second elements is the “range” of the relation.
Example:
Suppose S is the set {a, b, c, d, e} and set T is {w, x, y, z}.
8
Theory of Automata, Formal Languages and Computation
Set S
Set T
a
b
c
d
e
w
x
y
z
Fig. 1 Sets S and T are dis joint
y
z
x
y
x
z
3
4
3
4
3
4
3
4
3
4
3
4
(1, , 3)
x
(1, , 4)
x
(1, , 3)
y
(1, , 4)
y
(1, , 3)
z
(1, , 4)
z
(2, , 3)
x
(2, , 4)
x
(2, , 3)
y
(2, , 4)
y
(2, , 3)
z
(2, , 4)
z
1
2