Logical Networks

Logical Gates

Logical networks are built up from logical gates. The simplest logical gates are the two inputs and and or gates. The simplest and gate is a device with two inputs and a single output. The and gate output is on or true if both inputs are on or true. In other words, the and gate implements the elementary logic proposition or predicate: "The gate [output] is true if the first and the second inputs are true". This predicate is equivalent to the boolean algebra expression:

AB = C

Where A & B denote the two inputs to the gate and C is its output. All three being boolean variables which can only assume values of 1 & 0. 1 corresponding to true and 0 to false. The product AB works like ordinary multiplication except that all values are 0 or 1.

The simplest or gate is also a device with two inputs A & B and a single output C. The or gate implements the predicate: "The gate [output] is true if either A or B are true". This predicate is equivalent to the boolean algebra expression:

A+B = C

with all variables being boolean and with boolean addition being defined as follows:

0+0 = 0
0+1 = 1
1+0 = 1
1+1 = 1

Both the and and or gates can have an arbitrary number of inputs. The n input and gate implements a logical predicate equivalent to the boolean expression:

A1*A2*.....An = C
Similarly the n input or gate implements the boolean expression:

A1+A2+....+An = C
Where multiplication & additions are as previously defined.

Logical Networks

If we connect the output of a gate to the input of another we can construct arbitrarily complex networks which can express arbitrarily complex logic predicates equivalent to arbitrarily complex boolean algebra expressions. An example of such an expression is:

(A1 + (A2*A3))(A4(A5 + A6)) = C

This expression can be evaluated automatically by the circuitry of the logic gates, or by substituting the values 0 & 1 for all the variables. This can be done systematically by counting up the boolean state A1, A2, A3, A4, A5, A6 which can assume exactly 2 to the sixth power = 64 distinct states. If one arrays the 64 distinct input states from 000000 to 111111 and list the corresponding value of C one has computed the truth table of the expression. The first few rows of the truth table are:

000000 = 0
000001 = 0
000010 = 0
000011 = 0
000100 = 0
000101 = 0
000110 = 0
000111 = 0
etc..

Or more synthetically one observes that C =1 if both factors evaluate to 1, for the first factor this can be the case only if A1 = 1 or both A2 and A3 are = 1. For the second factor we have A4 = 1 and either A5 or A6 = 1. An even faster & simpler way is to execute algebraically all the multiplications obtaining the expression:

A1A4A5 + A1A4A6 + A2A3A4A5 + A2A3A4A6

This immediately tells us that this expression's truth table will evaluate to one or true in the following cases;

8 cases where A1 and A4 and A5 are all =1
8 cases where A1 and A4 and A6 are all =1
4 cases where A2 and A3 and A4 and A5 are all =1
4 cases where A2 and A3 and A4 and A6 are all =1

For a total of 24 cases out of 64. For the remaining 40 cases the truth function evaluates to false or zero.

Given an arbitrary boolean expression one can always rewrite it as either a sum of products or product of sums. The sum of products case is referred to as sum of minterms. In fact, the individual products define the minimal regions of the state space where the function evaluates to one. The fact that any arbitrary boolean function can be expressed as a sum of minterms is obvious since all one has to do is to resolve all the parenthesis by doing the indicated products. The dual of this theorem is that any arbitrary boolean expression can be represented as a product of sums, that is as expression of the type:

(A1 + A4+ ...)*(A3 + A7+ ...)* etc...

The product of sums form is referred to as the product of maxterms. In fact, a sum of boolean variables corresponds to the largest region [of the boolean state space] where the specific sum evaluates to one. The products of such maxterms correspond to their intersections when one or more evaluate to one. This result is easily obtained from the sum of products result. In fact, it is easy to see that the negation of a sums of products is:

~{(A1*A2*...)+(A3*A1*A5*...)} = (~A1 + ~A2 + ....)*(~A3 + ~A1 + ~A5 +....)

Where the symbol ~ represents negation of the proposition. The last expression is a product of maxterms.

Once an arbitrary boolean function is expressed as either a sum of minterms or a product of maxterms it is easy to see that it can be implemented as a network with only two layers of gates. In fact in the case of the sum of minterms the network will have a single OR gate with a number of inputs equal to the number of minterms. The minterms, in turn will be implemented as a set of AND gates one for each minterm. The opposite will be true in the case of product of maxterms. Each maxterm will be implemented by an OR gate. These in turn will be the inputs into an AND gate with as many inputs as there are maxterms. These canonical forms for logic networks maximize the speed of response, but they do not minimize the number of network components. Thus it is doubtful that the GeNets will be found out to be canonical. However, the existence of these canonical forms insures that it is possible to implement arbitrary switching patterns with gene cascades made-up by, as little as, two layers of genes.

Networks composed of just and and or gates are called combinatorial networks since all they can express is combination of logical inputs. If one adds any form of [state] memory to the nets they are referred to as sequential networks. Sequential networks can execute sequential processes or computations. It is highly likely that GeNets will be found to be sequential in nature. I.e. capable of executing genes choreographies and not just combinations.