230
P. Kerntopf et al.
Example 10.6 Let us consider a 3-variable Boolean reversible function F(x 3 , x 2 ,
x 1 ) = (f 3 , f 2 , f 1 ) defined in such a manner that the only non-identical mappings of
variable assignments in F are as follows:
001 → 101
101 → 111
111 → 110
110 → 001
When we consider the reversible function F as a permutation of output assignments it is a single cycle of four elements:
< 001, 101, 111, 110 >
Notice that in the above mappings
– In the first row the leftmost bit is being negated,
– In the second row the second bit is being negated.
– In the third row the third bit is being negated.
– In the fourth row all bits are being negated.
This observation will be generalized later to functions of any number of variables.
Now let us note what changes have been done in the sets B i , 0 ≤ i ≤ 1, for
functions f 3 , f 2 , and f 1 , in comparison with the sets for the function in Example 10.5
(only assignments moved to another block are shown bolded and underlined):
B
0 (f 3 ) =
{000} , {010} ,
011, 110
, B
1 (f 3 ) =
001, 100
, {101} , {111}
,
B
0 (f 2 ) =
{000} , {001, 100} ,
110
, B
1 (f 2 ) =
{010} ,
011, 101
, {111}
,
B
0 (f 1 ) =
{000} , {010, 100} ,
111
, B
1 (f 1 ) =
{001} , {011, 101} ,
110
.
Let us summarize the above observations (notation from Example 10.5 is used
below).
The values of the function f 3 differ from the values of the projection function x 3
only for the assignments 001 and 110. Namely, we can notice that
f (0, 0, 1) = 0, f 3 (0, 0, 1) = 1,
f (1, 1, 0) = 1, f 3 (1, 1, 0) = 0.
As a result, the function f 3 can be obtained from the projection function x 3 by
swapping its values for variable assignments 001 and 110.