232
P. Kerntopf et al.
Now the above presented methodology of proving that two component functions
of F belong to different P-equivalence classes will be extended to Boolean reversible
functions of any number of variables.
To prove that Boolean reversible functions with all component functions belonging to different P-equivalence classes exist for any number of variables n ≥ 3, we
will define the following infinite sequence of reversible functions.
Definition 10.11 The reversible Boolean function H n (x n , x n−1 , . . . , x 1 ) = ( f n ,
f n−1 , . . . , f 1 ), n ≥ 3, is defined in such a manner that the only non-identical mappings
of variable assignments in H n are as follows (N denotes negation):
a n , a n−1 , . . . , a 1 → Na n , a n−1 , . . . , a 1
Na n , a n−1 , . . . , a 1 → Na n , Na n−1 , . . . , a 1
. . .
Na n , Na n−1 , . . . , Na 2 , a 1 → Na n , Na n−1 , . . . , Na 2 , Na 1
Na n , Na n−1 , . . . , Na 2 , Na 1 → a n , a n−1 , . . . , a 1 ,
where the starting variable assignment is as follows:
a n a n−1 a n−2 . . . a 2 a 1 = 0 0 0 . . . 0 1.
Notice that in the ith row of the mappings in Definitions 10.1 and 10.11 ≤ i ≤ n,
the ith bit is being negated, and in the last mapping all bits are being negated.
When we consider the function H n as a permutation of variable assignments it is
a single cycle of n + 1 elements:
< a n , a n−1 , . . . , a 1 ,
Na n , a n−1 , . . . , a 1 ,
Na n , Na n−1 , . . . , a 1 ,
. . . ,
Na n , Na n−1 , . . . , Na 2 , a 1 ,
Na n , Na n−1 , . . . , Na 2 , Na 1 > .
Theorem 10.3 Each n ∗ n function H n is reversible for any n ≥ 3, where H n is
formulated in Definition 10.11.
Proof. Because non-identical mappings of variable assignments in H n form a single
cycle so this function is bijective for any n ≥ 3. Hence it is reversible.
Lemma 10.3 The values of the ith component function of the n ∗ n reversible
function H n differ from the values of the projection function x i only for two
assignments (it is a result of swapping two values).
Proof. This property follows from the manner in which the cycle for function H n
is constructed in Definition 10.11 (e.g., compare sets B 0 , B 1 in Examples 10.5 and
10.6).
P. Kerntopf et al.
Now the above presented methodology of proving that two component functions
of F belong to different P-equivalence classes will be extended to Boolean reversible
functions of any number of variables.
To prove that Boolean reversible functions with all component functions belonging to different P-equivalence classes exist for any number of variables n ≥ 3, we
will define the following infinite sequence of reversible functions.
Definition 10.11 The reversible Boolean function H n (x n , x n−1 , . . . , x 1 ) = ( f n ,
f n−1 , . . . , f 1 ), n ≥ 3, is defined in such a manner that the only non-identical mappings
of variable assignments in H n are as follows (N denotes negation):
a n , a n−1 , . . . , a 1 → Na n , a n−1 , . . . , a 1
Na n , a n−1 , . . . , a 1 → Na n , Na n−1 , . . . , a 1
. . .
Na n , Na n−1 , . . . , Na 2 , a 1 → Na n , Na n−1 , . . . , Na 2 , Na 1
Na n , Na n−1 , . . . , Na 2 , Na 1 → a n , a n−1 , . . . , a 1 ,
where the starting variable assignment is as follows:
a n a n−1 a n−2 . . . a 2 a 1 = 0 0 0 . . . 0 1.
Notice that in the ith row of the mappings in Definitions 10.1 and 10.11 ≤ i ≤ n,
the ith bit is being negated, and in the last mapping all bits are being negated.
When we consider the function H n as a permutation of variable assignments it is
a single cycle of n + 1 elements:
< a n , a n−1 , . . . , a 1 ,
Na n , a n−1 , . . . , a 1 ,
Na n , Na n−1 , . . . , a 1 ,
. . . ,
Na n , Na n−1 , . . . , Na 2 , a 1 ,
Na n , Na n−1 , . . . , Na 2 , Na 1 > .
Theorem 10.3 Each n ∗ n function H n is reversible for any n ≥ 3, where H n is
formulated in Definition 10.11.
Proof. Because non-identical mappings of variable assignments in H n form a single
cycle so this function is bijective for any n ≥ 3. Hence it is reversible.
Lemma 10.3 The values of the ith component function of the n ∗ n reversible
function H n differ from the values of the projection function x i only for two
assignments (it is a result of swapping two values).
Proof. This property follows from the manner in which the cycle for function H n
is constructed in Definition 10.11 (e.g., compare sets B 0 , B 1 in Examples 10.5 and
10.6).