On the Length of Boolean Functions in the Class of Exclusive-OR Sums of Pseudoproducts

摘要

Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L~(ESPP)(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L~(ESPP)(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions.