228
P. Kerntopf et al.
Proof. A function f is linear with respect to the variable x i iff negating x i is
equivalent to negating the function itself (see Lemma 10.1). It can be easily
shown that swapping two values (see Lemma 10.1) of component function f i of
the reversible function G n does not influence the property formulated in the first
sentence of this proof.
10.6 Component Functions Belonging to Different P-Classes
Now we are going to show that for n ≥ 3 there exist Boolean reversible functions
whose all component functions belong to different P-classes. Again, first we study
cycle structures of selected functions of small numbers of variables and next try to
apply extrapolation. We have checked in Table 2 of our paper [6] how many such
reversible functions exist for n = 3.
It was noted in Sect. 10.4 that there are 26 NPNP-classes of 3-variable functions
(R27–R52) that possess all component functions depending essentially on all three
variables. Among them there is only one class that consists of reversible functions
all whose component functions belong to different NPN-classes. It is shown below
in the same manner as previously 3-variable RevFunCFLVs.
NPNP Class R40 (Cardinality = 2304)
A = a ⊕ bc
B = b ⊕ ac ⊕ bc
C = a ⊕ c ⊕ ab ⊕ ac ⊕ bc
Its cycle structure is as follows:
< 0 >< 2 >< 3 >< 4 >< 1, 5, 7, 6 > .
Let us note that binary n-tuples in the unique cycle having more than one element
form a regular pattern:
001
101
111
110
P. Kerntopf et al.
Proof. A function f is linear with respect to the variable x i iff negating x i is
equivalent to negating the function itself (see Lemma 10.1). It can be easily
shown that swapping two values (see Lemma 10.1) of component function f i of
the reversible function G n does not influence the property formulated in the first
sentence of this proof.
10.6 Component Functions Belonging to Different P-Classes
Now we are going to show that for n ≥ 3 there exist Boolean reversible functions
whose all component functions belong to different P-classes. Again, first we study
cycle structures of selected functions of small numbers of variables and next try to
apply extrapolation. We have checked in Table 2 of our paper [6] how many such
reversible functions exist for n = 3.
It was noted in Sect. 10.4 that there are 26 NPNP-classes of 3-variable functions
(R27–R52) that possess all component functions depending essentially on all three
variables. Among them there is only one class that consists of reversible functions
all whose component functions belong to different NPN-classes. It is shown below
in the same manner as previously 3-variable RevFunCFLVs.
NPNP Class R40 (Cardinality = 2304)
A = a ⊕ bc
B = b ⊕ ac ⊕ bc
C = a ⊕ c ⊕ ab ⊕ ac ⊕ bc
Its cycle structure is as follows:
< 0 >< 2 >< 3 >< 4 >< 1, 5, 7, 6 > .
Let us note that binary n-tuples in the unique cycle having more than one element
form a regular pattern:
001
101
111
110