10 New Results on Reversible Boolean Functions Having Component. . .
223
10.4 Extrapolation Based on Cycle Structures
In [29, 30] it has been demonstrated that it is possible to extrapolate some properties
of reversible functions by considering their cycle structures. This is why we tried to
exploit the same approach to discover infinite sequences of reversible functions with
all their component functions having at least one linear variable. First, we were able
to check how many such reversible functions exist for n = 3. Namely, in Table 2
of our earlier paper [6] there are 52 NPNP classes of 3-variable reversible functions
(denoted R1-R52) and 26 out of these 52 classes of functions possess all component
functions depending essentially on all these variables. Among them three classes
consist of reversible functions F(c, b, a) all whose component functions have at
least one linear variable (let us call such functions in short RevFunCFLVs). Below
PPRMs expressions for representatives of these three classes are listed together with
the following information:
– Sets of linear variables for all component functions.
– Cardinality of a class.
NPNP Class R28 (Cardinality = 384)
A = a ⊕ bc (the set of linear variables = {a})
B = a ⊕ b ⊕ ac (the set of linear variables = {b})
C = a ⊕ b ⊕ c ⊕ ab (the set of linear variables = {c})
NPNP Class R29 (Cardinality = 1152)
A = a ⊕ bc (the set of linear variables = {a})
B = a ⊕ b ⊕ ac (the set of linear variables = {b})
C = a ⊕ b ⊕ c ⊕ ac (the set of linear variables = {b})
NPNP Class R32 (Cardinality = 576)
A = a ⊕ bc (the set of linear variables = {a})
B = a ⊕ b ⊕ bc (the set of linear variables = {a})
C = a ⊕ c ⊕ bc (the set of linear variables = {a})