| dc.description.abstract |
In this dissertation, the problem of calculating the number of equiva-
lence classes of Boolean functions is discussed. The difficulty of determining the
number of equivalence classes increases sharply with the number of variables n.
The motivation for choosing this topic lies in the fact that concrete numbers have
been known so far only for relatively small values of n, although the problem itself
was theoretically solved a long time ago.
Let G be the group of permutations of the set Bn = {0, 1}n. The effect of
the group G on scalar, Bn 7 → B1, that is, vectorial invertible Boolean functions,
Bn 7 → Bn. Two scalar Boolean functions f (x) and g(x), defined on Bn, are
considered equivalent with respect to the group G, i.e. f ∼ g, if for some σ ∈ G
for every x ∈ Bn f (x) = g(σ(x)) holds. Two vector invertible Boolean functions
f (x) and g(x), are considered equivalent with respect to the group G, i.e. f ∼ g,
if for some pair (σ, ρ) ∈ G × G for each x ∈ Bn holds g(x) = ρ(f (σ(x))). The
equivalence relation ∼ decomposes the set of all Boolean functions into equivalence
classes. Equivalence of Boolean functions has significant applications in the logical
synthesis of combinatorial circuits and in cryptography, especially in connection
with the design of S-boxes.
Let Un(G) and Vn(G) denote number of equivalence classes of scalar, i.e. vector
invertible Boolean functions of n variables in relation to the group G. The numbers
Un(G) and Vn(G) can be calculated relatively simply if the cycle index of the group
G is known. The dissertation considers four groups G of permutations of the set
Bn:
• group S′
n induced by group Sn permutations of coordinates elements x =
(x1, x2, . . . , xn) ∈ Bn,
• group Gn, induced by permutations and complementations of coordinates,
• group of GLn linear invertible transformations elements of the vector space
Bn, i
• group of AGLn affine invertible transformations elements Bn.
If the permutation σ ∈ G has ik cycles of length k ⩾ 1, its cycle structure is
i(σ) = (i1, i2, . . .). The cyclic index of the group G is the generatrix
ZG(f1, f2, . . .) = 1
|G|
X
σ∈G
Y
k⩾1
f ik
k
of cycle structures of all permutations σ ∈ G. General expressions for cycle indices
the four considered groups are known, but the cycle indices themselves, i.e. the
numbers Un(G) and Vn(G), are practically calculated only for relatively small
values, for e.g. n ⩽ 10.
The dissertation presents original results in the field of enumeration of equiv-
alence classes of Boolean functions in relation to these four groups of transfor-
mations. A similar expression was derived for all four groups of transformations
for the cycle index in the form of sum over partitions of the number n. Based
on that expression and previously calculated tables, the cycle index is calculated
much more efficiently. An overview of known results for relatively small n and
new results in the thesis for larger n is shown in the following table:
Number\ G S′
n Gn GLn AGLn
Un(G) 11 → 33 10 → 32 8 → 31 10 → 31
Vn(G) 6 → 30 7 → 27 6 → 26 6 → 26
Specially, in the case of the permutation group S′
n, an effective direct procedure
for calculating the number of equivalence classes that does not use a cycle index
is shown, and is described in the third paper from the introductory chapter.
The second part of the dissertation concerns monotone Boolean functions —
scalar Boolean functions which satisfy the monotonicity condition (from x ⩽ y
follows f (x) ⩽ f (y)). Let rn, i.e. dn (the n-th Dedekind number), denote the
number of equivalence classes of monotone Boolean functions in relation to the
group S′
n, that is, the total number of monotone Boolean functions of n variables.
The difficulty of calculating the number rn increases rapidly with n, so that
until recently the last calculated member of the sequence was r7. The procedure
described in the dissertation is based on the Frobenius theorem, by which it was
determined number r8. In doing so, the known value of the number d8 is used.
The dissertation consists of the first - introductory chapter and the following
three chapters. In the second chapter, theoretical terms related to the material
from chapters 3 and 4 are introduced, and they refer to discrete mathematics,
combinatorics and cycle indices of the considered four groups of transformations.
Chapter 3 describes the procedure for calculating the cycle indices for the
four considered groups of permutations, as well as numbers Un(G) and Vn(G)
equivalence classes of Boolean functions in relation to these groups. First, common
improvements for all four groups are considered, and then specific accelerations
related to individual groups. These results are published in the second paper
listed in the introductory chapter.
In chapter 4, the problem of finding the number of equivalence classes of
monotone Boolean functions is solved. First, a general expression for calculating
the number rn is given based on the Frobenius theorem in the form of the sum
(by partitions of the number n) of the number of fixed points of the permutation
corresponding to the partition. After that, depending on the graphs corresponding
to different partitions, different ways of calculating the number of fixed points for
n ⩽ 8 are shown. The procedure based on which the number r8 was calculated,
which also represents the original contribution of this dissertation is presented -
see the first paper from the list from the introductory chapter. Applying a similar
procedure, Pawelski [31] calculated r8 practically at the same time as the obtained
result described in the dissertation. |
en_US |