Information Technology Reference
In-Depth Information
A
finite function
is one whose domain and codomain are both finite sets. Finite functions
can be completely defined by tables of pairs
{
(
d
,
r
)
}
,where
d
is an element of its domain and
r
is the corresponding element of its codomain.
Binary functions
are complete finite functions whose domains and codomains are Carte-
sian products over the binary set
B
=
{
}
0, 1
.
Boolean functions
are binary functions whose
B
codomain is
. The tables below define three Boolean functions on two input variables and
one Boolean function on one input variable. They are called
truth tables
because the values 1
and 0 are often associated with the values
Tr u e
and
False
, respectively.
xyx
∧
y
xyx
∨
y
xyx
⊕
y
x
x
00 0
01 0
10 0
11 1
00 0
01 1
10 1
11 1
00 0
01 1
10 1
11 0
0
1
1
0
The above tables define the
AND
function
x
∧
y
(its value is
Tr u e
when
x
and
y
are
Tr u e
),
the
OR
function
x
∨
y
(its value is
Tr u e
when either
x
or
y
or both are
Tr u e
), the
EXCLUSIVE
OR
function
x
y
(its value is
Tr u e
only when either
x
or
y
is
Tr u e
,thatis,when
x
is
Tr u e
and
y
is
False
and vice versa), and the
NOT
function
x
(its value is
Tr u e
when
x
is
False
and vice versa). The notation
f
(
2,1
)
∧
⊕
,
f
(
2,1
)
∨
,
f
(
2,1
)
⊕
2
2
2
:
B
→B
:
B
→B
:
B
→B
,
f
(
1,1
)
for these functions makes explicit their number of input and output variables.
We generally suppress the second superscript when functions are Boolean. The physical devices
that compute the
AND
,
OR
,
NOT
,and
EXCLUSIVE OR
functions are called
gates
.
Many computational problems are described by functions
f
:
:
B →B
¬
A
∗
→C
∗
from the (un-
A
bounded) set of strings over an alphabet
to the set of strings over a potentially different
C
A
alphabet
. Since the letters in every finite alphabet
can be encoded as fixed-length strings
B
=
{
}
over the binary alphabet
0, 1
, there is no loss of generality in assuming that functions
B
∗
→B
∗
, that is, from strings over
are mappings
f
:
B
B
.
Functions with unbounded domains can be used to identify languages. A language
L
over
the alphabet
to strings over
A
∗
→B
A
is uniquely determined by a
characteristic function
f
:
with the
A
∗
such that
f
(
x
)=
1
property that
L
=
. This statement means that
L
is the set
of strings
x
in
A
∗
for which
f
on them, namely
f
(
x
)
, has value 1.
We often restrict a function
f
:
{
x
|
x
∈
}
B
∗
→B
∗
to input strings of length
n
,
n
arbitrary. The
n
. Its codomain consists of those strings into which strings of
length
n
map. This set may contain strings of many lengths. It is often convenient to map
strings of length
n
to strings of a fixed length containing the same information. This can be
done as follows. Let
h
(
n
)
be the length of a longest string that is the value of an input string
of length
n
. Encode letters in
B
domain of such a function is
by repeating them (replace 0 by 00 and 1 by 11) and then add
as a prefix as many instances of 01 as necessary to insure that each string in the codomain of
f
n
has 2
h
(
n
)
characters. For example, if
h
(
4
)=
3and
f
(
0110
)=
10, encode the value 10 as
011100. This encoding provides a function
f
n
:
B
n
2
h
(
n
)
containing all the information
B
→B
that is in the original version of
f
n
.
It is often useful to work with functions
f
:
whose domains and codomains are
real numbers
. Functions of this type include linear functions, polynomials, exponentials,
and logarithms. A
polynomial
p
(
x
):
→
1 in the variable
x
is specified
by a set of
k
real coefficients,
c
k−
1
,
...
,
c
1
,
c
0
,where
p
(
x
)=
c
k−
1
x
k−
1
+
→
of degree
k
−
+
c
1
x
1
+
c
0
.
···
Search WWH ::
Custom Search