A condition for uniqueness of linear decomposition of a boolean function into disjunctive sum of indecomposable functions

Let n ^ 1, К = [GF(2)]ⁿ, that is, V_n is the n-dimensional vector space over the field GF(2), and H_n be the group of shifts : Vn ^ Vn of the space Vn defined as a_a(x) = a ф x. Let F_n be the set of all Boolean functions f : Vn ^GF(2) in n variables and, for integer t ^ 0, let U_t be the set of all functions in F_n of degree not more than t. Let, at last, (H^f = {a_a : G H_n,f (a ф x) ф f (x) G U_t}. We say that functions g and h in F_n are equivalent modulo U_t and write g = h (mod U_t) if g ф h G U_t. Also, we say that a function f G F_n is linearly decomposable into disjunctive sum modulo U_t if there exist a linear transformation A of the vector space Vn, an integer k G {1, 2,...,n - 1}, and some Boolean functions f₁ and f₂ such that, for any x = x₁x₂ ... x_n G Vn, f (xA) = f₁(x₁,... ,x_k) ф f₂(x_k+1, ... ,x_n) (mod U_t). In this case, the right part of the last equivalence is called a linear decomposition of the function f into disjunctive sum modulo U_t and f ₁, f₂ are the components of the decomposition. By the principle of mathematical induction, these notions are defined for every number m ^ 2 of components in the sum and, further, just this definition of the linear decomposition of f into disjunctive sum modulo U_t is meant. The main result is the following: if s ^ 2, (H_n)f ¹⁾ is trivial (consists only of the identical shift of Vn), and f is linearly decomposable into disjunctive sum modulo then there exists an unique linear decomposition D of f into disjunctive sum modulo of linearly indecomposable (into disjunctive sum modulo U_s) components. The term "uniqueness" of the decomposition D means that any other similar decomposition of f gives the same decomposition of Vn into the direct sum of subspaces induced by its components that are, in turn, linearly equivalent modulo to components in D.

Keywords

Authors

References