10 New Results on Reversible Boolean Functions Having Component. . .
221
Negating all three functions h 1 , h 2 , and h 3 leads to the function K = (k 1 , k 2 , k 3 ):
k 1 (x, y, z) = h 1
(x, y, z) = 1 ⊕ (1 ⊕ x ⊕ yz) = x ⊕ yz
k 2 (x, y, z) = h 2
(x, y, z) = 1 ⊕ (1 ⊕ x ⊕ z ⊕ y ⊕ xy) = x ⊕ z ⊕ y ⊕ xy
k 3 (x, y, z) = h 3
(x, y, z) = 1 ⊕ (1 ⊕ x ⊕ y ⊕ xz) = x ⊕ y ⊕ xz
Finally, the following permutation of component functions (k 1 , k 2 , k 3 ) → (k 3 , k 1 ,
k 2 ) is performed leading to the function L(l 1 , l 2 , l 3 ):
l 1 (x, y, z) = k 3 (x, y, z) = x ⊕ y ⊕ xz
l 2 (x, y, z) = k 1 (x, y, z) = x ⊕ yz
l 3 (x, y, z) = k 2 (x, y, z) = x ⊕ z ⊕ y ⊕ xy
Thus the functions F = (f 1 , f 2 , f 3 ), G = (g 1 , g 2 , g 3 ), H = (h 1 , h 2 , h 3 ), K = (k 1 ,
k 2 , k 3 ), and L = (l 1 , l 2 , l 3 ) are pairwise NPNP-equivalent.
Each reversible function can be treated as a permutation. This is why we also
recall basic notions connected with permutations. Let A be any set of numbers. A
permutation on a set A is a bijective mapping from A to itself. Every permutation
can be considered as collection of disjoint cycles. Here such a collection will be
called a cycle structure. We will write a cycle in the form , meaning
that a 1 is mapped onto a 2 , ..., a k is mapped onto a 1 . It could be written in different
ways, e.g., . The number of elements in a cycle is called the
length of the cycle. A cycle with the length k is called a k-cycle. A 2-cycle is also
called a transposition.
10.3 Previous Work
The motivation for our studies of reversible functions toward constructing their classifications is borrowed from the classical logic synthesis by referring to an analogy
with related problems. For example, in classical logic synthesis, the equivalence of
two functions under permutation of the variables is an important problem due to
applications in the synthesis of multiplexer-based field-programmable gate arrays
[11, 12]. The problem is called Boolean matching, and two functions match if they
have the same P-representative. The extension to NP-representatives is done in [13,
14] in solving the Boolean matching problem in cell-library binding.
Classification of Boolean functions is a classical problem in logic synthesis
due to its various applications, with fast prototyping and unification of testing
procedures being just two of them [15]. However, a considerably smaller amount
221
Negating all three functions h 1 , h 2 , and h 3 leads to the function K = (k 1 , k 2 , k 3 ):
k 1 (x, y, z) = h 1
(x, y, z) = 1 ⊕ (1 ⊕ x ⊕ yz) = x ⊕ yz
k 2 (x, y, z) = h 2
(x, y, z) = 1 ⊕ (1 ⊕ x ⊕ z ⊕ y ⊕ xy) = x ⊕ z ⊕ y ⊕ xy
k 3 (x, y, z) = h 3
(x, y, z) = 1 ⊕ (1 ⊕ x ⊕ y ⊕ xz) = x ⊕ y ⊕ xz
Finally, the following permutation of component functions (k 1 , k 2 , k 3 ) → (k 3 , k 1 ,
k 2 ) is performed leading to the function L(l 1 , l 2 , l 3 ):
l 1 (x, y, z) = k 3 (x, y, z) = x ⊕ y ⊕ xz
l 2 (x, y, z) = k 1 (x, y, z) = x ⊕ yz
l 3 (x, y, z) = k 2 (x, y, z) = x ⊕ z ⊕ y ⊕ xy
Thus the functions F = (f 1 , f 2 , f 3 ), G = (g 1 , g 2 , g 3 ), H = (h 1 , h 2 , h 3 ), K = (k 1 ,
k 2 , k 3 ), and L = (l 1 , l 2 , l 3 ) are pairwise NPNP-equivalent.
Each reversible function can be treated as a permutation. This is why we also
recall basic notions connected with permutations. Let A be any set of numbers. A
permutation on a set A is a bijective mapping from A to itself. Every permutation
can be considered as collection of disjoint cycles. Here such a collection will be
called a cycle structure. We will write a cycle in the form , meaning
that a 1 is mapped onto a 2 , ..., a k is mapped onto a 1 . It could be written in different
ways, e.g., . The number of elements in a cycle is called the
length of the cycle. A cycle with the length k is called a k-cycle. A 2-cycle is also
called a transposition.
10.3 Previous Work
The motivation for our studies of reversible functions toward constructing their classifications is borrowed from the classical logic synthesis by referring to an analogy
with related problems. For example, in classical logic synthesis, the equivalence of
two functions under permutation of the variables is an important problem due to
applications in the synthesis of multiplexer-based field-programmable gate arrays
[11, 12]. The problem is called Boolean matching, and two functions match if they
have the same P-representative. The extension to NP-representatives is done in [13,
14] in solving the Boolean matching problem in cell-library binding.
Classification of Boolean functions is a classical problem in logic synthesis
due to its various applications, with fast prototyping and unification of testing
procedures being just two of them [15]. However, a considerably smaller amount