Selected problems in the theory of Boolean functions. Ed. by S. F. Vinokurov and N. A. Peryazev. (Q2748260)

From the introductions to the four chapters of the book:NEWLINENEWLINENEWLINEI. ``In this chapter we introduce the prerequisites necessary for the understanding of the results of the following chapters.''NEWLINENEWLINENEWLINEII. ``The repetition-free [Boolean] functions are an important class of functions which, beside the theoretical value, are applied in the mathematical modeling of discrete information processors. This chapter is devoted to the characterization of repetition-free Boolean functions, to the determination of the number of repetition-free Boolean functions and to the determination of repetition-free representations of the functions in binary basic sets.'' Here ``repetition-free'' means that no variable has more than one occurrence.NEWLINENEWLINENEWLINEIII. ``The basic idea in the construction of operator polynomial forms consists in the representation of the basic functions by canonical forms as images of a certain function by operators from a specified set (basic sheaf) of operators. The existence of at least one such function and of such sheaves guarantees the obtainment of canonical forms: the Zhegalkin polynomial and its generalizations \([\dots]\). The operators are a very convenient tool for the description of decompositions of Boolean functions. The operator approach enabled us to obtain an overview of polynomial expansions, to construct classes of polynomials including all known polynomials, starting with the Zhegalkin polynomials and the complete polynomial normal forms. \([\dots]\) We also apply to decompositions those classes of operators that generalize the operators which distribute negations, taking partial derivatives and substitution operators. The expansions using partial derivatives have technical applications and, besides, they provide elementary proofs of certain known results.''NEWLINENEWLINENEWLINEIV. ``In this chapter we study algorithms which enable one to represent a Boolean function as a cascade of terms, and also in polynomial normal forms, the representations having the least complexity in these classes. The complexity in the former class is understood as the number of involved variables, while in the latter class it is the number of terms.''NEWLINENEWLINENEWLINEThe bibliography contains 52 items, of which 46 are Russian papers and books. The monograph by \textit{M. Davio}, \textit{J.-P. Deschamps} and \textit{A. Thayse} [Discrete and switching functions (1978; Zbl 0385.94020)], closely related to the subject matter of the book under review, is missing. There is no index.NEWLINENEWLINENEWLINEReviewer's remarks: I could not understand some of the basic concepts of this book. Thus, e.g., it is not clear whether the terms, as defined on page 13, are formal expressions or functions. The concept of binary basic set is defined on page 15 by the condition that the set consists of all binary functions; the authors probably meant that it contains only binary functions, otherwise the binary basic set would be unique and distinct from \(B_0\). A similar remark holds for elementary basic sets. I understood the operators given on pages 70-71 as examples, but I could not understand the general definition on pages 69-70.