234
P. Kerntopf et al.
Thus for any i, 1 ≤ i < n, B 1 (f k = n−i + 1 ) and B 1 (f k = n−i + 1 ) have different
numbers of assignments from the block b n-i,i so the function f k = n−i+1 cannot be
transformed to f k = n−i+1 by permutation of variables, as it only changes assignments
within the block b n-i,i .
B. i = n (i.e., n–i + 1 = 1)
• B 1 (f k = 1 ) contains one assignment from b 0,n ,
• B 1 (f k = 1 ) contains no assignments from b 0,n ,
• B 0 (f k = 1 ) contains n assignments from b 1,n−1 ,
• B 0 (f k = 1 ) contains n + 1 assignments from b 1,n−1 .
Thus B 1 (f k = 1 ) and B 1 (f k = 1 ) as well as B 1 (f k = 1 ) and B 1 (f k = 1 ) have different
numbers of assignments from the blocks b 0,n and b 1,n−1 , respectively.
So the function f k = n−i + 1 cannot be transformed to f k = n−i + 1 , for any 1 ≤ i ≤ n,
by permutation of variables, as it changes assignments within the corresponding
blocks. Hence, if i = j, then f i and f j belong to different P-equivalence classes.
It is obvious that by Theorem 10.4 the following result holds.
Corollary 10.1 For any n ≥ 3 there exist ternary reversible functions having all
component functions that belong to different P-equivalence classes.
10.7 Conclusions and Future Work
The paper presents two new results on properties of component functions of Boolean
reversible functions. The main subject of the paper is showing that the solutions in
this area can be found by extrapolation of cycle structures for 3- and 4-variable
Boolean reversible functions obtained in the course of enumerative computations.
Namely, the solutions of the two problems have been discovered by using our
extrapolation approach. The solved problems are as follows: (1) for any n ≥ 3 there
exists a Boolean reversible function with all component functions having at least
one linear variable, (2) for any n ≥ 3 there exists a Boolean reversible function with
all component functions belonging to different P-equivalence classes. We plan using
the abovementioned results together with our previous results presented in [6, 7] to
construct a classification of reversible Boolean functions which would be useful in
the synthesis of reversible circuits.
Acknowledgements The authors acknowledge partial support of COST Action IC1405 on
“Reversible Computation - Extending Horizons of Computing.”
P. Kerntopf et al.
Thus for any i, 1 ≤ i < n, B 1 (f k = n−i + 1 ) and B 1 (f k = n−i + 1 ) have different
numbers of assignments from the block b n-i,i so the function f k = n−i+1 cannot be
transformed to f k = n−i+1 by permutation of variables, as it only changes assignments
within the block b n-i,i .
B. i = n (i.e., n–i + 1 = 1)
• B 1 (f k = 1 ) contains one assignment from b 0,n ,
• B 1 (f k = 1 ) contains no assignments from b 0,n ,
• B 0 (f k = 1 ) contains n assignments from b 1,n−1 ,
• B 0 (f k = 1 ) contains n + 1 assignments from b 1,n−1 .
Thus B 1 (f k = 1 ) and B 1 (f k = 1 ) as well as B 1 (f k = 1 ) and B 1 (f k = 1 ) have different
numbers of assignments from the blocks b 0,n and b 1,n−1 , respectively.
So the function f k = n−i + 1 cannot be transformed to f k = n−i + 1 , for any 1 ≤ i ≤ n,
by permutation of variables, as it changes assignments within the corresponding
blocks. Hence, if i = j, then f i and f j belong to different P-equivalence classes.
It is obvious that by Theorem 10.4 the following result holds.
Corollary 10.1 For any n ≥ 3 there exist ternary reversible functions having all
component functions that belong to different P-equivalence classes.
10.7 Conclusions and Future Work
The paper presents two new results on properties of component functions of Boolean
reversible functions. The main subject of the paper is showing that the solutions in
this area can be found by extrapolation of cycle structures for 3- and 4-variable
Boolean reversible functions obtained in the course of enumerative computations.
Namely, the solutions of the two problems have been discovered by using our
extrapolation approach. The solved problems are as follows: (1) for any n ≥ 3 there
exists a Boolean reversible function with all component functions having at least
one linear variable, (2) for any n ≥ 3 there exists a Boolean reversible function with
all component functions belonging to different P-equivalence classes. We plan using
the abovementioned results together with our previous results presented in [6, 7] to
construct a classification of reversible Boolean functions which would be useful in
the synthesis of reversible circuits.
Acknowledgements The authors acknowledge partial support of COST Action IC1405 on
“Reversible Computation - Extending Horizons of Computing.”