Boolean Matrices and the Design of Combinational Relay Switching Circuits

Matrices over a Boolean algebra, or simply Boolean matrices, are rectangular arrays of elements from a Boolean algebra. These arrays are subject to appropriate rules of operation, some of which are analogous to the rules of operation for ordinary matrices, whereas others reflect the 177 178 T H E BELL SYSTEM TECHNICAL J O U R N A L , JANUARY 1 9 5 5 Boolean character of the elements. The purpose of this paper is to present those properties of Boolean matrices which have application to the design of combination relay logic circuits, and to develop fundamental aspects of this application. In this paper, we shall assume a knowledge of the elementary aspects of Boolean algebra and of its application to the design of switching circuits. 1, 2 We shall use the following notations for the Boolean operations: + denotes the Boolean sum or union, · denotes the Boolean product or intersection, ^ denotes inclusion. In order to he able to operate most naturally with Boolean matrices, we use the system in which the parallel connection of contacts x and y is represented by x + y while their series connection is represented by x -y or just xy. We use 0 to denote an open circuit or contact and 1 to denote a closed circuit or contact. The Boolean algebra from which the elements of our Boolean matrices are selected is the s e t " $ " of 2 Boolean or switching functions of n variables Xi, x*, · · · , .r,, . 2. MATRICES ASSOCIATED W I T H COMBINATIONAL CIRCUITS