Information Technology Reference
In-Depth Information
BINARY FUNCTIONS AND LOGIC CIRCUITS
2.4 a) Write a procedure EXOR in a language of your choice that
writes
the description
of the straight-line program given in equation (
2.2
).
b) Write a program in a language of your choice that
evaluates
an arbitrary straight-
line program given in the format of equation (
2.2
) in which each input value is
specified.
2.5 A set of Boolean functions forms a
complete basis
Ω
if a logic circuit can be constructed
for every Boolean function
f
:
n
using just functions in
Ω
.
a) Show that the basis consisting of one function, the
NAND
gate, a gate on two
inputs realizing the
NOT
of the
AND
of its inputs, is complete.
b) Determine whether or not the basis
B
→B
is complete.
2.6 Sh
ow
that the CNF of a Boolean function
f
is unique and is the negation of the DNF
of
f
.
2.7 Show that the RSE of a Boolean function is unique.
2.8 Show that any SOPE (POSE) of the parity function
f
(
n
)
⊕
{
AND
,
OR
}
has exponentially many terms.
Hint:
Show by contradiction that every term in a SOPE (every clause of a POSE)
of
f
(
n
)
⊕
contains every variable. Then use the fact that the DNF (CNF) of
f
(
n
)
⊕
has
exponentially many terms to complete the proof.
2.9 Demonstrate that the RSE of the
OR
of
n
variables,
f
(
n
)
, includes every product term
∨
except for the constant 1.
2.10 Consider the Boolean function
f
(
n
)
mod
3
on
n
variables, which has value 1 when the sum
of its variables is zero modulo 3 and value 0 otherwise. Show that it has exponential-size
DN F, CN F, a n d R S E n o r m a l f o r m s .
Hint:
Use the fact that the following sum is even:
3
k
3
j
0
≤j≤k
2.11 Show that every Boolean function
f
(
n
)
:
n
B
→B
can be expanded as follows:
f
(
x
1
,
x
2
,
...
,
x
n
)=
x
1
f
(
1,
x
2
,
...
,
x
n
)
∨
x
1
f
(
0,
x
2
,
...
,
x
n
)
Apply this expansion to each variable of
f
(
x
1
,
x
2
,
x
3
)=
x
1
x
2
∨
x
2
x
3
to obtain its
DNF.
2.12 In a
dual-rail logic
circuit 0 and 1 are represented
by
the pairs
(
0, 1
)
and
(
1, 0
)
,re-
spectively. A variable
x
is represented by the pair
(
x
,
x
)
.A
NOT
in this representation
(called a DRL-
NOT
) is a pair of twisted wires.
a) How are
AND
(DRL-
AND
)and
OR
(DRL-
OR
) realized in this representation? Use
standard
AND
and
OR
gates to construct circuits for gates in the new representa-
tion. Show that every function
f
:
m
can be realized by a
dual-rail logic
circuit in which the standard
NOT
gates are used only on input variables (to obtain
the pair
(
x
,
x
)
).
n
B
→B
Search WWH ::
Custom Search