On the complexity of 2-output Boolean networks

AbstractThe complexity of 2-output combinational networks without feedback is explored. For monotone networks, which contain only and-gates and or-gates, if the two outputs can be expressed as Boolean functions having at most one variable in common, then the network obtained by adjoining optimal realizations of the individual functions is optimal. This property fails if the number of common input variables is greater than one or when not-gates are allowed