10 New Results on Reversible Boolean Functions Having Component. . .
233
Theorem 10.4 Any two component functions f r and f s of the Boolean reversible
function H n belong to different P-equivalence classes for n ≥ 3.
Proof. Let us write the cycle defining the function H n (x n , x n−1 , . . . , x 1 ) = ( f n ,
f n−1 , . . . , f 1 ) in the form: , where
u 1 = 000 . . . 001
u 2 = 100 . . . 001
u 3 = 110 . . . 001
. . .
u n−1 = 111 . . . 101
u n = 111 . . . 111
u n+1 = 111 . . . 110.
Thus the only non-identical mappings of variable assignments in H n are as
follows:
0, 0, . . . , 01 → 1, 0, . . . , 0, 1
1, 0, . . . , 01 → 1, 1, . . . , 0, 1
. . .
1, 1, . . . , 0, 1 → 1, 1, . . . , 1, 1
1, 1, . . . , 1, 1 → 1, 1, . . . , 1, 0
1, 1, . . . , 1, 0 → 0, 0, . . . , 0, 1.
Thus H n (u i ) = u i+1 for 1 ≤ i ≤ n and H n (u n+1 ) = u 0 . Notice that u i ∈ b n − i, i ,
1 ≤ i ≤ n and u n + 1 ∈ b 1, n − 1 . For any n the number of all assignments in the block
b n − i, i is equal
n!
(n−i)!i! and the block b 1, n − 1 contains exactly n assignments. For an
arbitrary selected k-th bit, 1 ≤ k ≤ n, there are
(n−1)!
(n−i−1)!(i)! assignments belonging to
b n − i, i and having this k-th bit equal 0. Similarly, there are
(n−1)!
(n−i)!(i−1)! assignments
belonging to b n − i, i and having the k-th bit equal 1. Also, f k (u) = 0 if the k-th bit
in the input assignment is 0 (e.g., for n > 3: f 2 (u 1 ) = 0; f 3 (u 1 ) = 0,..., f n−1 (u 1 ) = 0,
f n (u 1 ) = 1). For 1 < k ≤ n we have f k (u n−k+1 ) = 1 and f 1 (u n ) = 0.
Let us consider the following two cases with respect to i:
A. 1 ≤ i < n
• B 0 (f k = n−i+1 ) contains
(n−1)!
(n−i−1)!i! assignments from b n − i, i ,
• B 1 (f k = n−i+1 ) contains
(n−1)!
(n−i)!(i−1)! assignments from b n − i, i .
On the other hand, since f k = i (u i ) = 1, so
• B 0 (f k = n−i+1 ) contains
(n−1)!
(n−i−1)!i! − 1 assignments from b n − i, i ,
• B 1 (f k = n−i+1 ) contains
(n−1)!
(n−i)!(i−1)! + 1 assignments from b n − i, i .
233
Theorem 10.4 Any two component functions f r and f s of the Boolean reversible
function H n belong to different P-equivalence classes for n ≥ 3.
Proof. Let us write the cycle defining the function H n (x n , x n−1 , . . . , x 1 ) = ( f n ,
f n−1 , . . . , f 1 ) in the form: , where
u 1 = 000 . . . 001
u 2 = 100 . . . 001
u 3 = 110 . . . 001
. . .
u n−1 = 111 . . . 101
u n = 111 . . . 111
u n+1 = 111 . . . 110.
Thus the only non-identical mappings of variable assignments in H n are as
follows:
0, 0, . . . , 01 → 1, 0, . . . , 0, 1
1, 0, . . . , 01 → 1, 1, . . . , 0, 1
. . .
1, 1, . . . , 0, 1 → 1, 1, . . . , 1, 1
1, 1, . . . , 1, 1 → 1, 1, . . . , 1, 0
1, 1, . . . , 1, 0 → 0, 0, . . . , 0, 1.
Thus H n (u i ) = u i+1 for 1 ≤ i ≤ n and H n (u n+1 ) = u 0 . Notice that u i ∈ b n − i, i ,
1 ≤ i ≤ n and u n + 1 ∈ b 1, n − 1 . For any n the number of all assignments in the block
b n − i, i is equal
n!
(n−i)!i! and the block b 1, n − 1 contains exactly n assignments. For an
arbitrary selected k-th bit, 1 ≤ k ≤ n, there are
(n−1)!
(n−i−1)!(i)! assignments belonging to
b n − i, i and having this k-th bit equal 0. Similarly, there are
(n−1)!
(n−i)!(i−1)! assignments
belonging to b n − i, i and having the k-th bit equal 1. Also, f k (u) = 0 if the k-th bit
in the input assignment is 0 (e.g., for n > 3: f 2 (u 1 ) = 0; f 3 (u 1 ) = 0,..., f n−1 (u 1 ) = 0,
f n (u 1 ) = 1). For 1 < k ≤ n we have f k (u n−k+1 ) = 1 and f 1 (u n ) = 0.
Let us consider the following two cases with respect to i:
A. 1 ≤ i < n
• B 0 (f k = n−i+1 ) contains
(n−1)!
(n−i−1)!i! assignments from b n − i, i ,
• B 1 (f k = n−i+1 ) contains
(n−1)!
(n−i)!(i−1)! assignments from b n − i, i .
On the other hand, since f k = i (u i ) = 1, so
• B 0 (f k = n−i+1 ) contains
(n−1)!
(n−i−1)!i! − 1 assignments from b n − i, i ,
• B 1 (f k = n−i+1 ) contains
(n−1)!
(n−i)!(i−1)! + 1 assignments from b n − i, i .