Information Technology Reference
In-Depth Information
The following simple properties hold for arbitrary sets
A
and
B
and the operations of set
union, intersection, and difference:
A
∪
B
=
B
∪
A
A
∩
B
=
B
∩
A
A
∪∅
=
A
A
∩∅
=
∅
A
−∅
=
A
The
power set
of a set
A
, denoted 2
A
, is the set of all subsets of
A
including the empty
set. For example, 2
{
2,5,9
}
=
.Weuse2
A
to denote the power set
A
as a reminder that it has 2
|A|
elements. To see this, observe that
for each subset
B
of the set
A
there is a binary
n
-tuple
(
e
1
,
e
2
,
...
,
e
|A|
)
where
e
i
is 1 if the
i
th element of
A
is in
B
and 0 otherwise. Since there are 2
|A|
ways to assign 0's and 1's to
(
e
1
,
e
2
,
...
,
e
|A|
)
,2
A
has 2
|A|
elements.
The
Cartesian product
of two sets
A
and
B
, denoted
A
{∅
{
}
{
}
{
}
{
}
{
}
{
}
{
}}
,
2
,
5
,
9
,
2, 5
,
2, 9
,
5, 9
,
2, 5, 9
×
B
, is another set, the set of pairs
{
(
a
,
b
)
|
a
∈
A
,
b
∈
B
}
. For example, when
A
0
=
{
1, 2, 3
}
and
B
0
=
{
4, 3, 5
}
,
A
0
×
B
0
=
{
(
1, 4
)
,
(
1, 3
)
,
(
1, 5
)
,
(
2, 4
)
,
(
2, 3
)
,
(
2, 5
)
,
(
3, 4
)
,
(
3, 3
)
,
(
3, 5
)
}
. The Cartesian product of
k
sets
A
1
,
A
2
,
...
,
A
k
, denoted
A
1
×
A
2
×···×
A
k
,isthesetof
k
-tuples
{
(
a
1
,
a
2
,
...
,
a
k
)
|
a
1
∈
A
1
,
a
2
∈
A
2
,
...
,
a
k
∈
A
k
}
whose components are drawn from the respective sets. If for
≤
i
≤
k
,
A
i
=
A
,the
k
-fold Cartesian product
A
1
×
A
2
×···×
A
k
is denoted
each 1
A
k
.Anelementof
A
k
is a
k
-tuple
(
a
1
,
a
2
,
...
,
a
k
)
where
a
i
∈
A
.Thus,thebinary
n
-tuple
n
.
(
e
1
,
e
2
,
...
,
e
|A|
)
of the preceding paragraph is an element of
{
}
0, 1
1.2.2 Number Systems
Integers are widely used to describe problems. The infinite set
consisting of 0 and the
positive integers
is called the set of
natural numbers
. The set of positive and
negative integers and zero,
, consists of the integers
{
1, 2, 3,
...
}
.
In the
standard decimal representation
of the natural numbers, each integer
n
is repre-
sented as a sum of powers of 10. For example, 867
=
8
{
0, 1,
−
1, 2,
−
2,
...
}
10
0
.Since
computers today are binary machines, it is convenient to represent integers over base 2 instead
of 10. The
standard binary representation
for the natural numbers represents each integer as
a sum of powers of 2. That is, for some
k
10
2
+
6
10
1
+
7
×
×
×
0 each integer
n
can be represented as a
k
-tuple
x
=(
x
k−
1
,
x
k−
2
,
...
,
x
1
,
x
0
)
,whereeachof
x
k−
1
,
x
k−
2
,
...
,
x
1
,
x
0
has value 0 or 1 and
n
satisfies the following identity:
≥
n
=
x
k−
1
2
k−
1
+
x
k−
2
2
k−
2
+
+
x
1
2
1
+
x
0
2
0
···
The largest integer that can be represented with
k
bits is 2
k−
1
+
2
k−
2
+
+
2
1
+
2
0
···
=
2
k
1. (See Problem
1.1
.) Also, the
k
-tuple representation for
n
is unique; that is, two
different integers cannot have the same representation. When leading 0's are suppressed, the
standard binary representation for 1, 15, 32, and 97 are
(
1
)
,
(
1, 1, 1, 1
)
,
(
1, 0, 0, 0, 0, 0
)
,and
(
1, 1, 0, 0, 0, 0, 1
)
, respectively.
We denote with
x
+
y
,
x
−
−
y
,
x
∗
y
,and
x/y
the results of addition, subtraction, multi-
plication, and division of integers.
Search WWH ::
Custom Search