Logic functions and equations. Binary models for computer science.

Authors Christian Posthoff, Bernd Steinbach

Publication date 29 November 2005

Boolean derivative Boolean differential combinational circuit finite-state machine logic analysis logic design logic equation logic function

Mathematics Subject Classification ID

Boolean functions (06E30) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02)

Review text

The book under analysis has two main features which distinguish it from the numerous other books devoted to the applications of the two-element Boolean algebra to computer science and related fields. The first characteristic is the manner in which the beginner is introduced to the field. The authors adopt a strongly conversational style. Besides definitions, theorems (some of them with proofs) and algorithms, there are numerous examples (but no exercises left to the reader) worked out in (sometimes unusual) detail. The authors call the attention on several subtle points, offer alternative solutions to certain problems (for instance algebraic proofs and use of Karnaugh maps), explain the reason for choosing a certain strategy rather than another, or mention alternative terms for certain concepts. Briefly, one has the feeling of attending a very active class. The other main feature of this book is the crucial role played by the authors' own research on Boolean differential calculus and the handling of ternary vectors. So the book under review is both an introductory course and a research monograph. Whereas the former aspect addresses mainly computer engineering and computer science students rather than mathematicians, the advanced monograph part is certainly valuable to any researcher in the field. The contents are as follows. The first chapter introduces the Boolean algebraic and order theoretical structure of the set \(\{0,1\}\). From the very beginning the book is self-contained in the strict sense of the word: absolutely no previous knowledge is required, the reader only needs to have an open mind. Chapter 2 presents the more or less standard matter on logic functions, plus a short section on complete sets of functions. Ternary vectors and matrices appear in this chapter. The next chapter introduces logic equations: basic problems and definitions, reductions of any system of equations and inequalities to a single standard equation, solutions with regard to part of the variables. The subject matter of Chapter 4 is Boolean differential calculus. The differential \(dx\) of a Boolean variable \(x\) which varies in time is the Boolean variable which takes the value 1 if the variable \(x\) changes its value, otherwise is 0. With every logic function \(f({\mathbf x})\) of \(n\) variables are associated the total differential \(df({\mathbf x})=f({\mathbf x}\oplus d{\mathbf x})\), the total differential expansion \(F({\mathbf x},d{\mathbf x})=f({\mathbf x})\wedge \bigwedge_{i=1}^n(dx_i\vee\overline{dx_i})\), the total differential minimum Min\(f({\mathbf x})=f({\mathbf x})\wedge f({\mathbf x}\oplus d{\mathbf x})\) and the dually defined total differential maximum. Several relationships between these concepts are established and generalized to partial dfifferentials and \(m\)-fold differentials, which are defined in a natural way. The simple derivatives are defined by \[ \frac{\partial f({\mathbf x})}{\partial x_i}=f(x_1,\dots,x_n)\oplus f(x_1,\dots,\overline{x_i},\dots,x_n) \] and a somewhat parallel theory is constructed. Chapter 5 is devoted to the solution of logic equations and inequalities by a set of algorithms based on the following principles. 1) A complex equation is split into smaller problems that are easy to solve; 2) the solutions sets of these smaller problems are represented by ternary vectors and orthogonal lists of ternary vectors; 3) the logic operations are transferred to the solutions sets and implemented as set-theoretical operations, and 4) the parallel implementation of many parts of the algorithms is largely used, thus reducing the complexity. The last sections of the chapter deal with the inversion of equation systems, functional equations and Boolean differential equations, the latter subject being treated in some detail. Chapter 6 says a few words about propositions and predicates, then introduces the binary representation of integers and gives some elements of coding theory. After a section on application to programming languages, the chapter ends with a few elements of the theory of complexity, up to the definition of NP-completeness. Chapter 7 deals with combinational circuits: modern technology, the analysis and design of these circuits. The latter problem reduces to the problem of decomposing logic functions, for which several theorems are stated (and one of them is proved) and many examples are given. Chapter 8, dealing with sequential machines, has a somewhat parallel structure. Chapter 9 describes the family XBOOLE of computer programs devised by the authors for the solution of logic problems. For more details the reader is referred to a web page. The book includes a selective bibliography of about 50 items and an index of terms. The absence of an index of symbols is partially supplied by a list of figures and a list of tables. There are two invited prefaces and the author's foreword. Reviewer's remarks. 1) I completely agree with the terms ``logic function and ``switching function, which were used by switching theorists a few decades ago. The term ``Boolean function, which seems to prevail nowadays, should be reserved to polynomial functions over an arbitrary Boolean algebra. 2) The authors give credit to Stone for Theorem 2.19, i.e., the completeness theorem for logic functions, which is usually attributed to \textit{E. Post} [American J. 43, No. 4, 163--185 (1921; JFM 48.1122.01) and The two-valued iterative systems of mathematical logic, Ann. Math. Stud. 5 (1941; Zbl 0063.06326)]. 3) The references do not include the monograph by \textit{W. G. Schneeweiss} [Boolean Functions with Engineering Programs, Springer-Verlag (1989; Zbl 0686.94009)], which is much in the same spirit as the book under review. 4) The reference [Rudeanu, Ch.] on pages xxiv and 387 should be [Rudeanu, S.]. As a matter of fact, this reference follows an earlier monograph by the reviewer [Boolean functions and equations, North-Holland (1974; Zbl 0321.06013)], which is also highly theoretical but perhaps closer to the monograph under review, as it presents Boolean functions from the beginnning and contains two chapters on the Boolean algebra \(\{0,1\}\) and switching theory. 5) It would be interesting to compare XBOOLE to the algorithm BREL, devised by \textit{D. Bañeres, J. Cortadella} and \textit{M. Kisnevsky} [``A recursive paradigm to solve Boolean relations, DAC 2004, June 7--11, San Diego, Cal., 416--421]; these authors report also computational results.

Recommendations

Cited in

(22)

Describes a project that uses

Uses Software

XBOOLE

This page was built for publication: Logic functions and equations. Binary models for computer science.

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