B70-1 Truth Functions and the Problem of Their Realization by Two-Terminal Graphs

This book consists of two parts, the first being a survey of the mathematical theory of Boolean functions. Chapter 1 introduces basic definitions, various normal forms, prime implicants, and symmetric functions. In an appendix to Chapter 1, an unpublished combinatorial and nontrivial theorem of Bakos is given. (This theorem yields a uniform construction of Gray codes as a consequence.) Chapter 2 gives the standard theory of minimality. Applications to special cases such as monotonic or symmetric functions are given. Chapter 3 discusses interrelationships between conjunctive and disjunctive normal forms. Chapter 4 deals with functional completeness and the Post–Yablonsky theorem is proven. Some applications to finite automata are given. Chapter 5 is concerned with the decomposition of truth functions. Chapter 6, on numerical problems, is particularly good. Groups are used to classify truth functions. A form of Pólya´s theorem is given and the work of Pólya, Slepian, and the reviewer is presented. A number of special cases are worked out, including some of the results of Povarov. Chapter 7, on linearly separable functions, gives a number of characterizations.