An Efficient Method for Converting Irregular Logical Formula into DNF/CNF with Graph Structure

Abstract In this paper, we introduce an effective technique that converts an irregular logical formula into a set of Disjunctive Normal Form (DNF) or a Conjunctive Normal Form (CNF) [1][3] using Graph structure. In a situation where we must evaluate complex conditions containing diverse factors, we develop a convoluted logical formula and evaluate the formula from the beginning to the end. As the complexity of the logical formula grows, the time complexity for evaluation computation increases exponentially. The most efficient evaluation will be achieved if we convert the complex propositional logic formula into a set of DNF or CNF expressions and then evaluate each DNF or CNF expressions one by one. The suggested method in this paper efficiently converts a convoluted logical formula into a set of DNF/CNF expressions with the time complexity of O (log N * 2log N). We employed Graph structure to develop the proposed DNF conversion method in this paper. A Tree structure with a root node and one or more sibling nodes is constructed to represent a local irregular logical formula. A branch in the Tree is a disjunctive literal and each branch in the Tree has a corresponding conjunctive relationship with another. To describe the global logical formula, a Graph structure includes every Tree connected in all logical sequence from the front literal to the end literal. All paths from the root node to a leaf node in the Graph represent a disjunctive iteral of conjunctive relationship with another path and the set of the disjunctive literals will be a full disjunctive normal form if we prune redundant nodes. A logical formula evaluation process is repeated operations following the rules of logical equivalences, such as double negative elimination, De Morgan’s law, and distributive law. The time complexity of the operations can exponentially increase as the length of logical formula grows. The conversion method we present in this paper can reduce the complexity of conversion operations and it can be used for not only DNF conversion, but also Conjunctive Normal Form (CNF) conversion with minor modification of relational representations.