The Research Of Combinational Logic Optimization Algorithms Based On Granular Discernibility Matrix And Optimistic Concept

As an important content in logic circuit analysis and design,one of the main research contents of the optimization of combinational logic circuit is to simplify the truth table or the expression of logic function that describes the logic circuit.In industry,the method of electronic design automation is often used to optimize the logic circuit.However,with the arrival of the era of big data,the circuit integration degree is higher and the scale is larger,and the optimization of combinational logic circuit is also faced with new opportunities and challenges.With the increasing complexity of problems and the development of knowledge engineering methods,this paper tries to solve the optimization problem of combinatorial digital logic circuits by using the theory of Granular Computing and the theory of Formal Concept Analysis.Based on the previous work of our group,the simplification of truth table is transformed into a rule extraction problem of information system by using the Granular Discernibility Matrix and the optimistic concept.The main original works include:Firstly,the Granular Discernibility Matrix is constructed on the basis of equivalence relation and traditional Discernibility Matrix.The truth table is simplified by distinguishing the "0" from the "1" of the logical output.The Granular Discernibility Matrix is different from the traditional Discernibility Matrix in that it is neither symmetric nor square,but it contains all the information with the least equivalence class to identify all the output "1".In the process of finding rules,the concept of heuristic information is used to accelerate the convergence of the algorithm.A logic circuit optimization algorithm based on Granular Discernibility Matrix is designed.The equivalence between the proposed algorithm and the traditional Karnaugh method is proved.Secondly,the truth table is regarded as a logical information system,and the optimistic concept generated by the logical information system is defined directly from the perspective of equivalence class.The optimistic concept is generated in different granularity space,and the simplest rule in the truth table is obtained according to the relationship between the optimistic concept and the output attribute in the truth table.The calculation process of the above two algorithms is demonstrated by examples,and the correctness of the algorithm is proved by theoretical analysis.In this paper,based on the research work in the early stage of the research,proposed two algorithms for truth table appointment,expand the Granular Computing theory and scope of research and application of the theory of Formal Concept Analysis,enriched the logic circuit optimization of the optimization problem solving method,research results can be applied to the justification of propositional logic.The two reduction algorithms for truth table proposed in this paper expand the research field and application scope of the theory of Granular Computing and the theory of Formal Concept Analysis,and to some extent enrich the method of solving the optimization problem in the logic circuit optimization.The research results can be extended to the solution of SAT problem and the proof of propositional logic.