Binary Higher Order Neural Networks for Realizing Boolean Functions

In order to more efficiently realize Boolean func tions by using neural networks, we propose a binary product-unit neural network (BPUNN) and a binary pi-sigma neural network (BPSNN). The network weights can be determined by one-step training. It is shown that the addition "σ," the multiplication "π" and two kinds of special weighting operations in BPUNN and BPSNN can implement the logical operators "V," "Λ," and "¬" on Boolean algebra 〈Z₂, V, Λ, ¬, 0,1〉 (Z₂ = {0,1}), respec tively. The proposed two neural networks enjoy the following advantages over the existing networks: 1) for a complete truth table of N variables with both truth and false assignments, the corresponding Boolean function can be realized by accordingly choosing a BPUNN or a BPSNN such that at most 2^N-1 hidden nodes are needed, while O(2^N), precisely 2^N or at most 2 , hidden nodes are needed by existing networks; 2) a new network BPUPS based on a collaboration of BPUNN and BPSNN can be defined to deal with incomplete truth tables, while the existing networks can only deal with complete truth tables; and 3) the values of the weights are all simply -1 or 1, while the weights of all the existing networks are real numbers. Supporting numerical experiments are provided as well. Finally, we present the risk bounds of BPUNN, BPSNN, and BPUPS, and then analyze their probably approximately correct learnability.