Discernibility Matrix and Its Application in Logical Optimization

Abstract

The simplification of truth table is of great significance to the analysis and design of logic circuits. In this paper, the simplification of truth table is studied, and a method of GDM (granular discernibility matrix) that uses discernibility matrix is proposed to obtain the minimum Boolean expression from truth table, and its application in logic optimization is realized. Firstly, the truth table is regarded as a logical information system and the simplification of truth table is transformed into the problem of finding the simplest rules of the logical information system. Then, based on the traditional discernibility matrix, the equivalent relation model is used to construct the GDM, the information granular that can be organized into the minimum Boolean expression is found, and the minimum Boolean expression of the logical information system is obtained by using the disjunctive and conjunction operation of the information granular. In order to accelerate the convergence speed of the algorithm, the heuristic information is introduced, and the decision rule of organizing information granular is given to avoid the occurrence of redundant logic items in the acquisition of the minimum Boolean expression, making Boolean logic expression simplest. The acquisition efficiency of the minimum Boolean expression is improved, and the problem of large-scale logic circuit optimization is solved. Finally, the algorithm is described in detail through an example, and its correctness is proven mathematically. Finally, a detailed algorithm is given, and the correctness and effectiveness of the method are demonstrated through examples and theoretical proofs.

Keywords

• truth table
• rule discovery
• discernibility matrix
• minimal boolean expression