Recursive Boolean Formula Minimization Algorithms for Implication Logic

摘要

In this paper are given two novel algorithms for minimization of recursive Boolean formula (RBF), which is adequate for implementation of $N$-input 1-output Boolean functions (BFs) over basis ${{rm imply},~{rm false}}$ using two memristors. Both of our algorithms are direct consequence of necessary and sufficient conditions related to regular ordering of positive product terms within recursive formula. The results demonstrate how developed algorithms provide up to 26% gain in average number of implications and shorter recursive Boolean formula length in up to 77% of problem instances than previously published algorithms, tested on the set of all 4-input 1-output BFs.