Easily Reconstructable Logic Functions

This paper shows that sum-of-product expression (SOP) minimization produces the generalization ability. We show this in three steps. First, various classes SOPs are generated. Second, minterms of SOP are randomly selected to generate partially defined functions. And, third, from the partially defined functions, original functions are reconstructed by SOP minimization. We consider Achilles heel functions, majority functions, monotone increasing cascade functions, functions generated from random SOPs, and monotone increasing random SOPs. As for generalization ability, the presented method is compared with Naive Bayes, multi-level perceptron, support vector machine, JRIP, J48, and random forest.