scientific article; zbMATH DE number 107561

From MaRDI portal
Publication:4023151





The solution of many problems involving Boolean functions of the form \(f: \{0,1\}^ n\to \{0,1\}\) is based on the fact that every such Boolean function can be represented in disjunctive normal form (d.n.f.), i.e., \(f= k_ 1\lor\cdots\lor k_ m\), where \(k_ 1,\dots,k_ m\) are elementary conjunctions. However, in many cases this requires complex computations; sometimes the complexity becomes prohibitive. An attempt to overcome this difficulty is based on the idea, apparently due to Yu. I. Zhuravlev, of enlarging the class of d.n.f. representations. To be specific, a linearized disjunctive normal form (l.d.n.f.) of a Boolean function \(f\) is a representation of the form \(f= f_ 1\lor\cdots\lor f_ p\), where each \(f_ j\in\prod L(n)\), i.e., \(f_ j\) is a product of linear functions; the latter term designates those functions which can be represented as linear polynomials over GF(2). Since every literal \(x_ i\) or \(\bar x_ i= x_ i+ 1\) is a linear function, it follows that every d.n.f. is an l.d.n.f. (in spite of this terminology, which may suggest the converse inclusion). The aim of this book is to develop a theory of l.d.n.f.'s and to argue the increased efficiency of the new theory. The book contains an introduction, five chapters and bibliography (but no subject index, author index or list of symbols). Below we do not follow closely the order of the chapters. The concepts of implicant and prime implicant are defined naturally in the new theory. The Blake and Nelson algorithms for the determination of the conventional prime implicants of a Boolean function are extended to the new framework. (The author correctly gives credit to Blake for the algorithm which was rediscovered by Quine and McCluskey.) Every Boolean function \(f\) equals the disjunction of its prime implicants, called the reduced l.d.n.f. of the function. The shortest l.d.n.f. representation (i.e., involving the fewest disjunctive terms) of a function \(f\) is obtained from its reduced l.d.n.f. by appropriate deletion of terms (possibly none). On the other hand, the fact that the length (i.e., number of disjunctive terms) of an l.d.n.f. is invariant with respect to the affine group of transformations of the \(n\)-dimensional unit cube enables one to apply algebraic methods in the study of the set \(\prod L(n)\) and of the l.d.n.f. representations. Thus, let \(L(n)\) be the vector space of all linear functions and, for each \(f\in \prod L(n)\), let \(M_ f\) be the subspace of those \(g\in L(n)\) for which \(fg=0\). Then \(f\) is related to \(M_ f\) in many ways, e.g., \(f=\prod_{g\in B}(g+ 1)\), where \(B\) is any basis of \(M_ f\), the dimension of \(M_ f\) equals the degree of the polynomial \(f\) provided \(f\neq 0\), etc. On the other hand, \(\prod L(n)\) is a complete and complemented modular lattice with respect to the pointwise ordering of functions. Special attention is paid to certain particular classes of functions, among which are the symmetric functions, the Boolean functions with a small number of zeros and the quadratic functions (i.e., quadratic polynomials over GF(2)). For instance, the study of the last class of functions is facilitated by the existence of three canonical forms to which they can be reduced by affine transformations. Besides the algebraic aspect, another important concern of the book is the study of various numerical characteristics such as the number of prime implicants of a function, the shortest length of an l.d.n.f. representation and many others, for which lower bounds, upper bounds, asymptotic evaluations or exact formulas are given. Finally, the author turns to algorithmic aspects. The problems treated here include the approximate realization of an l.d.n.f. representation of a Boolean function and of a partially defined Boolean function, the solution of systems of quadratic Boolean equations, the decodification of linear Reed-Muller codes of first order and some problems of pattern recognition. The complexity of the algorithms is analyzed and some computational experience is reported. The bibliography contains 46 items, of which 36 are by Soviet mathematicians; 10 items are by the present author. There is no reference to the extensive literature on the general theory of Boolean equations; see, e.g., a book by the reviewer [Boolean functions and equations (1974; Zbl 0321.06013)]. The book is clearly written and self-contained. It has the peculiarity that in most cases the theorems are preceded by their proofs. In the reviewer's opinion, a monograph like this requires many illustrative examples, while there are actually only three (on pages 20, 132 and 137). One might say that the author's aim was to prove the following metatheorem: The class of l.d.n.f.'s is a natural generalization of the class of d.n.f.'s and it is suitable for applications. The reviewer feels that this important monograph should be translated into English.












This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4023151)