Redundancy testing in combinational networks

A simple, necessary and sufficient test is developed for testing whether a single connection in a tree-type NAND network is redundant. A procedure is presented for testing every connection in the network. The computational complexity of the procedure is m(i squared) where m = the number of gates and i = the average number of inputs per gate in the network. The redundancy test is generalized for multi-output tree-type NAND networks and such networks realizing partially specified functions. A dual test is developed for tree-type NOR networks, but NOR networks for partially specified functions are treated by a simpler test than the dual test. The test may be applied to AND-OR networks as well by converting them, at least conceptually, to an equivalent NAND form while preserving redundancy. (Modified author abstract).