10 New Results on Reversible Boolean Functions Having Component. . .
231
Values of each of the other two component functions, f 2 and f 1 , also differ from
the values of the corresponding projection functions only for two assignments.
Swaps for f 2 in comparison with the projection function x 2 are as follows:
g (1, 0, 1) = 0, f 2 (1, 0, 1) = 1,
g (1, 1, 0) = 1, f 2 (1, 1, 0) = 0,
Swaps for f 1 in comparison with the projection function x 1 are as follows:
h (1, 1, 1) = 1, f 1 (1, 1, 1) = 0,
h (1, 1, 0) = 0, f 1 (1, 1, 0) = 1.
Let us show that component functions f 2 and f 1 belong to different P-equivalence
classes. Assume that f 2 and f 1 belong to the same P-equivalence class. Then, since
any permutation over the variable set {x 3 , x 2 , x 1 } does not change the assignment
111 there should be f 1 (1, 1, 1) = f 2 (1, 1, 1); however, f 1 (1, 1, 1) = 0 and f 2 (1, 1,
1) = 1. It is in contradiction with our assumption that f 2 and f 1 belong to the same
P-equivalence class. Thus f 2 and f 1 belong to different P-equivalence classes.
In a similar manner it can be shown that the other two pairs of component
functions of F, (f 3 , f 2 ) and (f 3 , f 1 ), belong to different P-equivalence classes. Let
us show that component functions f 3 and f 2 belong to different P-equivalence
classes. Assume that f 3 and f 2 belong to the same P-equivalence class. Then, any
permutation over the variable set {x 3 , x 2 , x 1 } changes variable assignments with
specified numbers of 0s and 1s only within one block. Let us consider the block
b 1,2 = {011, 101, 110} .
Note that f 2 (0, 1, 1) = f 2 (1, 0, 1) = 1, f 2 (1, 1, 0) = 0. However, f 3 (0, 1, 1) = f 3 (1,
0, 1) = f 3 (1, 1, 0) = 1. Hence f 2 cannot be transformed to f 3 by permutation of
variables. It is in contradiction with our assumption that f 3 and f 2 belong to the same
P-equivalence class. Thus f 3 and f 2 belong to different P-equivalence classes.
Now let us show that component functions f 3 and f 1 belong to different Pequivalence classes. Assume that f 3 and f 1 belong to the same P-equivalence class.
Consider the block
b 1,2 = {011, 101, 110} .
Note that f 1 (0, 1, 1) = f 1 (1, 0, 1) = f 1 (1, 1, 0) = 1. However, f 3 (0, 1, 1) = 0,
f 3 (1, 0, 1) = f 3 (1, 1, 0) = 1. Hence f 1 cannot be transformed to f 3 by permutation
of variables. It is in contradiction with our assumption that f 3 and f 1 belong to the
same P-equivalence class. Thus f 3 and f 1 belong to different P-equivalence classes.
231
Values of each of the other two component functions, f 2 and f 1 , also differ from
the values of the corresponding projection functions only for two assignments.
Swaps for f 2 in comparison with the projection function x 2 are as follows:
g (1, 0, 1) = 0, f 2 (1, 0, 1) = 1,
g (1, 1, 0) = 1, f 2 (1, 1, 0) = 0,
Swaps for f 1 in comparison with the projection function x 1 are as follows:
h (1, 1, 1) = 1, f 1 (1, 1, 1) = 0,
h (1, 1, 0) = 0, f 1 (1, 1, 0) = 1.
Let us show that component functions f 2 and f 1 belong to different P-equivalence
classes. Assume that f 2 and f 1 belong to the same P-equivalence class. Then, since
any permutation over the variable set {x 3 , x 2 , x 1 } does not change the assignment
111 there should be f 1 (1, 1, 1) = f 2 (1, 1, 1); however, f 1 (1, 1, 1) = 0 and f 2 (1, 1,
1) = 1. It is in contradiction with our assumption that f 2 and f 1 belong to the same
P-equivalence class. Thus f 2 and f 1 belong to different P-equivalence classes.
In a similar manner it can be shown that the other two pairs of component
functions of F, (f 3 , f 2 ) and (f 3 , f 1 ), belong to different P-equivalence classes. Let
us show that component functions f 3 and f 2 belong to different P-equivalence
classes. Assume that f 3 and f 2 belong to the same P-equivalence class. Then, any
permutation over the variable set {x 3 , x 2 , x 1 } changes variable assignments with
specified numbers of 0s and 1s only within one block. Let us consider the block
b 1,2 = {011, 101, 110} .
Note that f 2 (0, 1, 1) = f 2 (1, 0, 1) = 1, f 2 (1, 1, 0) = 0. However, f 3 (0, 1, 1) = f 3 (1,
0, 1) = f 3 (1, 1, 0) = 1. Hence f 2 cannot be transformed to f 3 by permutation of
variables. It is in contradiction with our assumption that f 3 and f 2 belong to the same
P-equivalence class. Thus f 3 and f 2 belong to different P-equivalence classes.
Now let us show that component functions f 3 and f 1 belong to different Pequivalence classes. Assume that f 3 and f 1 belong to the same P-equivalence class.
Consider the block
b 1,2 = {011, 101, 110} .
Note that f 1 (0, 1, 1) = f 1 (1, 0, 1) = f 1 (1, 1, 0) = 1. However, f 3 (0, 1, 1) = 0,
f 3 (1, 0, 1) = f 3 (1, 1, 0) = 1. Hence f 1 cannot be transformed to f 3 by permutation
of variables. It is in contradiction with our assumption that f 3 and f 1 belong to the
same P-equivalence class. Thus f 3 and f 1 belong to different P-equivalence classes.