Information Technology Reference
In-Depth Information
Logic circuits
are DAGs in which all vertices except input vertices carry the labels of gates.
Input vertices carry the labels of
Boolean variables
, variables assuming values over the set
B
=
{
}
.ThegraphofFig.
1.2
(a) is the logic circuit of Fig.
1.3
(c), whereas the graph
of Fig.
1.2
(b) is the logic circuit of Fig.
1.4
. (The figures are shown in Section
1.4.1
,Logic
Circuits.) The set of labels of logic gates used in a DAG is called the
basis
Ω
for the DAG. The
size
of a circuit is the number of non-input vertices that it contains. Its
depth
is the length of
the longest directed path from an input vertex to an output vertex.
0, 1
1.2.6 Matrices
An
m
n
matrix
is an array of elements containing
m
rows and
n
columns. (See Chapter
6
.)
The
adjacency matrix
of a graph
G
with
n
vertices is an
n
×
n
matrix whose entries are 0 or
1. The entry in the
i
th row and
j
th column is 1 if there is an edge from vertex
i
to vertex
j
and 0 otherwise. The adjacency matrix
A
for the graph in Fig.
1.2
(a) is
×
⎡
⎣
⎤
⎦
00100
00100
00001
00001
00000
A
=
1.2.7 Functions
The engineering component of computer science is concerned with the design, development,
and testing of hardware and software. The theoretical component is concerned with questions
of feasibility and optimality. For example, one might ask if there exists a program H that can
determine whether an arbitrary program P on an arbitrary input I will halt or not. This is
an example of an unsolvable computational problem. While it is a fascinating topic, practice
often demands answers to less ethereal questions, such as “Can a particular problem be solved
on a general-purpose computer with storage space
S
in
T
steps?”
To address feasibility and optimality it is important to have a precise definition of the tasks
under examination. Functions serve this purpose. A
function
(or
mapping
)
f
:
D →R
is
arelation
f
on the Cartesian product
D×R
subject to the requirement that for each
d
∈D
there is at most one pair
(
d
,
r
)
in
f
.If
(
d
,
r
)
f
, we say that the value of
f
on
d
is
r
, denoted
f
(
d
)=
r
.The
domain
and
codomain
of
f
are
∈
D
R
D
R
and
, respectively. The sets
and
can
be finite or infinite. For example, let
f
mult
:
2
=
2
and codomain
→
of domain
D
R
=
map a pair of natural numbers
x
and
y
(
=
{
0, 1, 2, 3,
...
}
)intotheirproduct
z
;
that is,
f
(
x
,
y
)=
z
=
x
∗
y
.A
function
f
:
D →R
is partial
if for some
d
∈D
no value
in
is assigned to
f
(
d
)
.Otherwise,a
function is complete
.
If the domain of a function is the Cartesian product of
n
sets, the function is said to have
n
input variables
. If the codomain of a function is the Cartesian product of
m
sets, the
function is said to have
m
output variables
. If the input variables of such a function are all
drawn from the set
A
and the output variables are all drawn from the set
B
, this information
is often captured by the notation
f
(
n
,
m
)
R
B
m
. However, we frequently do not use
exponents or we use only one exponent to parametrize a class of problems.
:
A
n
→
Search WWH ::
Custom Search