Abstract—This paper investigates various aspects of functional and structural complexity in Boolean polyfunctional nets. These are nets each of whose constituent elements are capable of performing any single function from a prescribed set of functions assigned to the element. Such nets are characterized in the paper as functionally redundant, universal, ultrastable, perfect, imperfect, etc. These descriptors are measures of net function complexity and describe, in general, the range over which net function varies as the function of each element varies over its assigned set of functions. For example, in a net which is functionally ultrastable, any allowable variation in element function produces no variation in net function. In a net which is functionally perfect, every variation in element function produces a corresponding variation in net function; furthermore, every possible net function is obtained. All nets which are not perfect are called imperfect.

In a previous paper by this author, the problem of achieving arbitrary reliability for combinatorial nets from arbitrarily unreliable elements was reduced to the study of the convergence properties of an associated polynomial system. In this paper simple criteria which specify the convergence of such a system to a nodal fixed point are obtained from known results in matrix theory. (Convergence to a nodal fixed point implies that the corresponding net approaches reliability arbitrarily near 1 for a particular function.) Theorems are also given which show that it is possible to obtain, from a single system converging to a nodal fixed point, many systems having this property. In a recent paper by this author [1] the organization and reliability of large combinatorial nets were investigated. In that paper several theorems were proved whose ultimate purpose was to delineate conditions under which arbitrarily reliable homogeneous nets could be obtained from arbitrarily unreliable elements. It is the main purpose of the present note to amplify these results as well as prove certain new theorems from which arbitrary reliability for a particular net may be tested by making use of easily applied theorems and associated algorithms. We begin by reviewing certain necessary concepts from the aforementioned paper. This paper should be consulted for a more detailed treatment of these ideas.

The properties of m×1 homogeneous polyfunctional nets under iteration (a growth process in which each element is replaced by a copy of the original net) are explored in considerable detail. Theorems are proved which relate the sequence of sets of output functions of a net to its structure as well as to the set of functions performed by the elements of the net. A complete characterization with respect to convergence of the 2×1 bordered net is given. Many new results on the oscillation properties of these nets are obtained, including methods for constructing nets which oscillate with prescribed period. The reliability properties of nets whose initial function assignments contain sum, product, and majority functions are studied. For the class of m×1 bordered nets (nets only slightly less general than the m×1 nets) it is shown that arbitrary reliability for these functions can be obtained under extremely broad conditions.

The organization and reliability of large redundant nets of formal neurons are investigated. Each neuron has m inputs and n outputs and is capable of performing at any one time any member of any prescribed subset of the total possible set of 22m·nfunctions. Various methods for obtaining large nets of predictable structure and function through the medium of element reproduction are discussed. In the principal reproduction scheme considered, called ``complete iteration,'' each element ``grows'' a copy of the net of which it is a part and each new element does likewise, ad infinitum. The output or net function is studied as the number of ``iterations'' or ``reproductions'' increases. The concept of net convergence (or oscillation) which is equivalent to the condition achieved by the net when its set of net functions becomes stable (or oscillatory) is precisely defined. Theorems are proved which predict this behavior for various nets of general interest. A polynomial system is associated with each net which completely describes its probabilistic behavior. This system produces the Moore-Shannon h(p) function in the special case where the net stabilizes (converges) on only two functions. Conditions are given under which a net may be made arbitrarily reliable even though its constituent elements are arbitrarily unreliable.

The functional states of a neural (combinational) net of prescribed interconnection geometry and over-all net function are characterized and enumerated. The problem is formalized for a class of nets having an arbitrary number of inputs and outputs by introducing the notion of a Boolean matrix. The concept of stability of neural nets (which is closely related to the set of functional states over which the input-output function is invariant) is precisely defined and evaluated for certain general classes of nets.

The topology of the n-dimensional cube is used to reduce the problem of determining the minimal forms of a Boolean function of n variables to that of finding the minimal coverings of the essential vertices of the basic cell system associated with the given function. The proof of this statement is contained in the central Theorem 4. A numerical easily programmed procedure is given with which it is possible to treat problems with a greater number of variables than has heretofore been practical. The procedure by-passes the determination of the basic cells (the prime implicants of W. V. Quine) and locates the essential vertices, from which in turn the irredundant and minimal forms are obtained.