220
P. Kerntopf et al.
Definition 10.6 A mapping F: {0, 1} n → {0, 1} n is called an n ∗ n reversible function
if it is bijective. It will also be considered as a vector of standard Boolean functions
that we will called component functions f i : {0, 1} n → {0, 1}, 1 ≤ i ≤ n. They are
defined at every x {0, 1} n by F(x) = (f 1 (x), . . . , f n (x)).
Since F is bijective hence component functions f i : {0, 1} n → {0, 1}, 1 ≤ i ≤ n,
are balanced Boolean functions.
By an analogy with the definition of NPN-equivalence classes for standard
Boolean functions, the following definition of equivalence classes for Boolean
reversible functions can be given.
Definition 10.7 Two reversible Boolean functions are NPNP-equivalent if they
can be transformed to each other by the following operations (including the
combinations that do not use all of these operations):
1. Negation of variables,
2. Permutation of variables,
3. Negation of component functions, and
4. Permutation of component functions.
Example 10.2 The component functions of a reversible Boolean function
F = ( f 1 , f 2 , f 3 ) are as follows:
f 1 (x, y, z) = x ⊕ yz
f 2 (x, y, z) = x ⊕ y ⊕ xz
f 3 (x, y, z) = x ⊕ y ⊕ z ⊕ xy
After negating variables x in F we obtain the reversible function
G = (g 1 , g 2 , g 3 ):
g 1 (x, y, z) = f 1
x
, y, z
= (1 ⊕ x) ⊕ yz = 1 ⊕ x ⊕ yz
g 2 (x, y, z) = f 2
x
, y, z
= (1 ⊕ x) ⊕ y ⊕ (1 ⊕ x) z = 1 ⊕ x ⊕ y ⊕ z ⊕ xz
g 3 (x, y, z) = f 3
x
, y, z
= (1 ⊕ x) ⊕ y ⊕ z ⊕ (1 ⊕ x) y
= 1 ⊕ x ⊕ y ⊕ z ⊕ y ⊕ xy = 1 ⊕ x ⊕ z ⊕ xy
The permutation of variables (x, y, z) → (x, z, y) in G leads to the function
H(h 1 , h 2 , h 3 ):
h 1 (x, y, z) = g 1 (x, z, y) = 1 ⊕ x ⊕ yz
h 2 (x, y, z) = g 2 (x, z, y) = 1 ⊕ x ⊕ z ⊕ y ⊕ xy
h 3 (x, y, z) = g 3 (x, z, y) = 1 ⊕ x ⊕ y ⊕ xz