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

An Efficient Method for Converting Irregular Logical Formula into DNF/CNF with Graph Structure | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article An Efficient Method for Converting Irregular Logical Formula into DNF/CNF with Graph Structure Sangmork Park This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4442842/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version 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 * 2 log 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. Conjunctive Normal Form Disjunctive Normal Form Logical Formula Graph Theory Figures Figure 1 Figure 2 Figure 3 Figure 4 1. Research Motivation The original problem that motivated this research was to find an optimal combination of attributes for access control in a distributed computing environment, which exposes the least accumulated privacy information. It is like a decision Tree problem; however, this method pursues a different approach. We employed a Graph structure instead of Tree structure. An attribute or a combination of attributes can be evaluated by the privacy information exposure grades that come from the attributes delivered for access control. To determine the optimal combination of attributes with the least privacy information, we need to investigate combinations of attributes which satisfy access conditions for a computer security system. The conditional requirements required by the security systems can be represented in a logical formula which is composed of polynomial literals and logical connectives such as negation, conjunction, and disjunction. Each literal can be considered the required attributes, and a conjunctive clause in the logical formula can represent the required combination of attributes for access control assessment. Any irregular logical formulae can be converted into an equivalent DNF or CNF. The DNF conversion method introduced in this paper supported a mechanism that can produce an efficient access control conditions assessment. The method can be employed for CNF conversion with minor modifications. We considered only three logical connectives -AND(∧), OR(∨), NOT(¬) because the objective of the original research is to verify an optimal combination of attributes to submit to an access control system. The required attributes that can afford accessibility to a distributed computing services and resources are expressed in a propositional formula such as: ¬p ∨ q ∧ r ∨ ( s ∧ t ∨ u ) ∨ ( ( p ∧ v ∨ w) ∧ ( x ∨ y)) – (1) where p, q, r, s, t, u, v, w, x, y stand for the name of attributes. Each attribute has a unique property that indicates the degree of privacy information. To efficiently assemble an optimal combination of attributes effectively that ensures accessibility while containing the least amount of privacy information, the propositional logic formula must be converted to complete DNF. The original propositional logic formula’s transformed DNF is as follows: ( ¬p ∧ r ) ∨ ( q ∧ r ) ∨ ( s ∧ t ) ∨ u ∨ ( p ∧ v ∧ x ) ∨ ( p ∧ v ∧ y) ∨ (w ∧ x ) ∨ (w ∧ y ) - (2) The computing service and resource providers determine the accessibility of their services and resources by the submitted attributes in an attribute-based access control system. The resource users will present a composite of attributes expressed in a conjunctive clause in DNF which marks the level of privacy and will select a set of attributes disclosing least privacy information while ensuring the access to the resources and services. We studied an efficient technique that converts any type of propositional formula into full DNF to create an optimal combination of attributes that satisfies accessibility conditions with the least amount of privacy information. 2. Research Background 2.1. Terminology The terminologies used in this paper follow the definitions in “Lecture Notes in Computer Science vol.679” [ 5 ]. 2.2. Conjunctive and Disjunctive Normal Form Diverse methods for fast and easy validity testing of propositional formula have been introduced [ 2 ] [ 3 ] [ 6 ]. The introduced methods in the research depend on testing conjunctive or disjunctive clauses, which are components of DNF or CNF logically equivalent to the propositional formula. All the propositional logic forms are to be converted into logically and semantically equivalent Conjunctive Normal Forms or Disjunctive Normal Form. Which of the normal form is preferred depends on the characteristics of applications [ 3 ]. The size of CNF and DNF can be expressed by the maximum number of literals in a conjunctive or disjunctive clause in the CNF or DNF. Ronald Revest et al. defined k -CNF and k -DNF to be the set of Boolean formulae in conjunctive or disjunctive normal form where each clause has k-literals at most. They showed k -CNF is converted into k -DNF and k -DNF is converted into k -CNF by applying De Morgan’s Rules [ 6 ]. Both CNF and DNF are convenient formats for evaluating the validity of a propositional formula with the same complexity. While DNF and CNF have the same level of complexity, there could be a more efficient normal form for different problems. When we evaluate the validity of a propositional formula to find an optimal combination of literals, converting the propositional formula to DNF will be preferable because it allows simultaneous validation of formula and calculation of each literal set’s property values. The previous DNF example (2) is 3-DNF with eight conjunctive clauses. It is converted into 3-CNF with eight disjunctive clauses such as: (p ∨ ¬r ) ∧ (¬q ∨ ¬r ) ∧ (¬s ∨ ¬t ) ∧ ¬u ∧ (¬p ∨ ¬v ∨ ¬x ) ∧ (¬w ∨ ¬x ) ∧ (¬p ∨ ¬v ∨ ¬y) ∧ (¬w ∨ ¬y ) - (3) If we evaluate only the validity of a propositional formula following traditional process on distribute, associative and De Morgan’s law, it is not feasible to assess which combination of literals produce an optimal result (least privacy information). However, if we evaluate the validity of a propositional formula in a DNF, it is the more efficient because we can evaluate the validity of the formula and calculate the score of each literals’ combination simultaneously by visiting every conjunctive clause in DNF. 2.3. Graph Data Structure The traditional conversion procedure that transforms a propositional formula into a logically equivalent Conjunctive or Disjunctive Normal Form involves repeated operations of transforms with Distributive Law, Associative Law, and De Morgan’s Law. We propose a DNF conversion method which employs a Graph structure for efficient and effective DNF conversion from a complex propositional formula. A propositional formula can be represented by a Tree structure for fast DNF conversion also, and the cost for traversing nodes for DNF expression in a Tree structure is the same as the Graph representation proposed in this paper. However, the Graph structure has advantages in simplicity of programming and the space complexity of data storage for computation. The Tree structure requires exponential increase in space complexity; however, the Graph structure requires linear increase of the space complexity as the size of propositional formula grows. If we use a Tree structure, we must build a sub-Graph containing the same number of leaf nodes in the Tree for every parenthesis clause. However, if we use Graph structure, we need to build a sub-Graph and connect the sub-Graph to each leaf node in the Graph. ( p ∨ q ) ∧ ( r ∨ s ) -(4) Figure-1 illustrates a representation of propositional formula of (4), framed in Tree and Graph structure. Every node in the Tree/Graph, with exception of ROOT and pseudo nodes, represents a literal in a propositional formula. In the illustration, the sibling relationship represents the disjunctive connective, and the parent-child relationship represents the conjunctive connective. The benefit of using a Graph structure for DNF conversion is illustrated in Fig. 1 . This advantage also can be applied for CNF conversion from any propositional formula with minor modifications. 3. Proposed Method DNF is a standard normal form of a logical formula composed of a disjunction of conjunctions. The first step for full DNF conversion proposed in this paper is to construct a Graph structure and crop a set of conjunctive clauses in the DNF. The conjunctive clauses may contain redundant literals or mutually contradictive literals. The second phase is to eliminate the redundancies and contradictions from the candidate conjunctions. If there are the same multiple literals in a conjunctive clause, we keep only one literal in the conjunctive clause since only one of the literals is valid. If there are mutually contradictive literals in a conjunctive clause, we discard the clause from DNF because it is invalid clause. After individual conjunction of literals is pruned, we investigated the entire DNF to eliminate redundancies. If a conjunctive clause of literals is a subset of another conjunctive clause, we remove the superset conjunction of literals from the DNF because we only need to evaluate the conjunctive clause with the smallest number of literals, which satisfies the conditional requirements. The third phase is to evaluate every conjunctive clause based on its properties of literals (attributes) for determining the optimal combination of attributes that exposes the least privacy information. We considered only the privacy level of attributes for simplicity in this paper. However, the scores may change by different problem sets and policies. We considered only three logical connectives -AND(∧), OR(∨), NOT(¬) in this research because the objective of this research is to find an optimal combination of attributes. 3.1. Convert Propositional Formula into a Graph Each literal in the propositional formula is represented in a node that contains several properties. Figure-2 illustrates a node’s data structure which contains properties of parent node, flag, child node(s), and property values, such as the name and privacy level of the attribute node. The property of parent and child node is the link pointing to its parent and child nodes, and the flag is used for Graph traversal, and the value represents the respective property value of the literal, such as privacy level. To build a Graph representing a propositional formula, we have to consider two connectives: conjunctive connective(∧) and disjunctive connective(∨), and parenthesis that describe the precedence of conversion operations. The Graph starts from a root node which has null value of parent, and property values. When a parenthesis is met, a pseudo node is created to build a sub-Graph with the literals in the parenthesis. The procedure for building a DNF conversion Graph follows the algorithms as below: Start from ROOT node Read Next If ‘(‘ : Create a pseudo root node and follow recursion procedure of Graph creation until ‘)’ appears. Else if ‘literal’ : Create a node and connect it to ROOT node. Read Next If ‘∨’ : Create a node with next literal/clause and assign the node to sibling node of the current node. Else if ‘∧’ : Create a node with next literal/clause and assign the node to every leaf node as a child node in current Graph Else if ‘(‘ : Create a pseudo root node and follow recursion procedure of Graph creation until ‘)’ appears. Repeat If we construct a Graph with Formula-(1) following algorithm above, the Graph will be constructed as below: ¬p ∨ q ∧ r ∨ ( s ∧ t ∨ u ) ∨ ( ( p ∧ v ∨ w) ∧ ( x ∨ y)) 3.2. Graph Traversal for Conjunctive Clause Retrieval Every depth-first search traversal path from ROOT node to a leaf node provides a possible conjunctive clause in DNF. The visited node’s properties are recorded to build conjunctive clauses and assess property values. The procedures for collecting conjunctive clauses for DNF construction follow the algorithm as below: Start from ROOT node Visit 1st Child node Record properties: name, value … If ‘Pseudo node’ Visit Child nodes recursively Else if ‘Leaf node‘ Add disjunctive relationship Return to parent node Else if ‘Child node exist’ Add conjunctive relationship Visit 1st Child node Record node properties Execute recursive visit procedures Visit next Child node Record node properties Execute recursive visit procedures If ‘No more Child node’ node Return to Parent node Visit next Child node Execute recursive visit procedures If ‘No more Child node’ Return to Parent node In Fignre-3, there are two paths from ROOT node to leaf node ‘x’. To reach ‘x’ from ROOT, we traverse either ‘R-R-p-v-R-x’ or ‘R-R-w-R-x’ in order. If we remove pseudo nodes represented by ‘R’ from the path, we can have ‘p-v-x’ path and ‘w-x’ path. Since the relationship between nodes in the same path is a parent-child relationship, they are conjunctive connective relationship, and each sibling node’s traversal paths from ROOT node have disjunctive relationship. The set of conjunctive clauses with disjunctive relationship composes a DNF. If we retrieve all the paths from the ROOT node to each leaf node following the rules given previously, the possible DNF will be the same as Formula-(2). 3.3. Prune Redundancy and Remove Contradiction The original propositional formula may have redundant conditional terms or contradicting conditional terms. We considered two different layers of redundancy pruning and one layer of contradiction removal. The first level of redundancy pruning, and contradiction removal considers any redundancies and contradictions in a conjunctive clause. When we deal with a complex propositional formula, we may find redundant literals such as: ( p ∧ q ∧ r ∧ s ∧ p ∧ r ∧ s ) -(5) In Formula-(5) there are two ‘r’s and ‘s’s which are redundant literals. The redundant literals must be removed and only one of the same literals is kept because (r ∧ r) is the same with ‘r’ and (s ∧ s) is the same with ‘s.’ There can be contradicting literals in a conjunctive clause such as: ( p ∧ q ∧ r ∧ s ∧ p ∧ ¬r ∧ t ) -(6) In Formula-(6), the two literals of ‘r’ and ‘¬r’ are contradicting which makes the whole conjunctive clause invalid. We investigate every conjunctive clause and discard the clause if there are any contradictory literals in the clause from DNF because it never will be satisfied. The higher-level of redundancy pruning is same as the lower-level redundancy pruning. It deals with different conjunctive clauses instead of literals in a clause. ( p ∧ q ∧ r ) ∨ (p ∧ q ∧ r ∧ s ∧ p) -(7) In Formula-(7), the conjunctive clause of ‘(p ∧ q ∧ r ∧ s ∧ p)’ is redundant clause because the extra literals in the longer conjunctive clause are meaningless. { p, q, r } ⊂ { p, q, r, s, p} -(8) If a set of literals in a conjunctive clause is a subset of another set of literals, the longer conjunctive clause must be removed from DNF. In Formula-(7), the clause of ‘(p ∧ q ∧ r ∧ s ∧ p)’ is removed because there is a subset literals clause in the DNF. Finding the subset-superset relationship between multiple sets of literals is achieved by using bit operation of respective sets. The literals in each conjunctive clause are sorted and the existence of a specific literal is in each set was recorded in the corresponding row and column of literals checking table. The bit-sum of bit-operation between multiple clauses presents the number of matching literals in the different clauses. If the bit-sum of bit-operation is the same as the bit-sum of a clause, the other clause is a redundant clause which needs to be removed from DNF. Figure 4. Literals Checking Table 3.4. Selecting Optimal Literals Combination The redundancy pruning and contradiction removal from a DNF is a full disjunctive normal form in which a literal appears exactly once in each clause. To identify the optimal conjunctive clause of literals, we evaluated the sum of property values from every conjunctive clause. The set of literals within a conjunctive clause presenting the best property values is the optimal literals combination. 3.5. Performance Issue Converting a propositional form into a normal form can involve an exponential increase of its size [ 4 ]. There have been many research that can reduce storage complexity and time complexity of normal form conversion processes [ 6 ] [ 7 ] [ 9 ]. They introduced efficient methods and techniques for efficient normal conversion. However, they focused on finding methods for efficient validity testing of propositional formulas with the normal forms, which makes it difficult to be applied to an optimal condition selection problem. The time complexity of this method is O (log N * 2 log N ) where ‘N’ is the number of literals in given propositional formula. The most complex step in this method is at the traversal step for finding paths within the Graph structure. If the propositional formula is divided by multiple sub-Graphs with constant number of ‘ k ’ literals, the number of paths from the ROOT node to each leaf node will be k N/k , and it is multiplied by (log k N) to count the number of nodes visited. The worst number of k = 2. 4. Conclusion DNF is a disjunction of conjunctive clauses. When we identify the validity of a propositional formula and verify an optimal combination of literals that makes the propositional formula valid while ensuring the best property values of the literals, converting the formula into logically equivalent DNF allows faster validity evaluation and optimal literals set selection. We introduced an efficient DNF conversion method by employing Graph structure to aggregate literals of an optimal combination of attributes. When we evaluate the validity of a propositional formula, converting the formula into CNF may also ensure the best solution. The method converting propositional formula to DNF using Graph structure can be applied to convert the logical formula into CNF by changing the relationship of literals. In DNF conversion method, we translated conjunctive connective into a parent-child relationship and disjunctive connective into a sibling relationship. To convert the propositional formula into CNF, the relationship between parent-child nodes, and sibling nodes are defined the opposite way of DNF conversion process, and the redundancy pruning, and contradiction removal procedures will be the same. Declarations Author Contribution Sangmork Park executed the research, developed the whole manuscript and figures, and reviewed. Statements and Declarations The author did not receive support from any organization for the submitted work. References Doets, K. Conjunctive Normal Form, From Logic to Logic Programming , The MIT, pp.17–18. Huth, M., & Ryan, M. Semantics of Propositional Logic, Logic in Computer Science: Modeling and Reasoning about Systems , Cambridge University Press, pp.45–68. Huth, M., & Ryan, M. Normal Forms, Logic in Computer Science: Modeling and Reasoning about Systems , Cambridge University Press, pp.69–89. Peter Bro Miltersen, Radhakrishnan, J., & Wegener, I. On Converting CNF to DNF, Mathematical Foundations of Computer Science 2003 , Springer Berlin/Heidelberg, pp. 612–621. Chapter 2 Terminology, Resolution Methods for the Decision Problem 1993 , Springer Berlin/Heidelberg, pp. 6–16. Rivest, R. L. Learning Decision List, Machine Learning vol.2 No.3, Springer Nethelands, pp. 229–246. Panagiotis Manolios, & Vroon, D. Efficient Circuit to CNF Conversion, Theory and Applications of Satisfiability Testing-SAT 2007 , Springer Berlin/Heidelberg, pp. 4–9. Lang, B. Ian Foster et al. Attribute Based Access Control for Grid Computing, ftp://info.mcs.anl.gov/pub/tech_reports/reports/P1367.pdf . Daniel Sheridan The optimality of a Fast CNF Conversion ant its Use with SAT, Proc. of SAT-2004, http://www.satisfiability.org/SAT04/programme/114.pdf . Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4442842","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":304400649,"identity":"5b8649e7-d76e-42e7-b5be-28096c6c2531","order_by":0,"name":"Sangmork Park","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAApklEQVRIiWNgGAWjYHACZgaGCgYGNiBLggQtZ0jWwtgGYRGnxZz97GPDn/MOR/MxMB+8zUOMFsuedONk3m2Hc9sY2JKtidJicCCN+TDjtjSgFh4zaeK0nH/GfPDnHJAW/m9EarmRxpzA22ADsoWNOC2WM54xG/McA2phZjO2nEOMFnP+NGbJHzUSufPbmx/eeEOUw+AsZmKUo2oZBaNgFIyCUYALAACxWikw5Yy1ewAAAABJRU5ErkJggg==","orcid":"","institution":"Virginia Military Institute","correspondingAuthor":true,"prefix":"","firstName":"Sangmork","middleName":"","lastName":"Park","suffix":""}],"badges":[],"createdAt":"2024-05-19 03:38:21","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4442842/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4442842/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":57408898,"identity":"1b763f30-3a5f-4222-861a-2bea629a6225","added_by":"auto","created_at":"2024-05-30 10:03:23","extension":"jpeg","order_by":1,"title":"Figure 1","display":"","copyAsset":false,"role":"figure","size":81482,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eTree vs Graph Structure\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"floatimage1.jpeg","url":"https://assets-eu.researchsquare.com/files/rs-4442842/v1/187b49e9ccc9457a3d81ca2d.jpeg"},{"id":57408896,"identity":"ee3b4ce0-0c8a-4bec-b59a-136f50dd7da4","added_by":"auto","created_at":"2024-05-30 10:03:23","extension":"png","order_by":2,"title":"Figure 2","display":"","copyAsset":false,"role":"figure","size":1875,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eNode Representation\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"Onlinefloatimage2.png","url":"https://assets-eu.researchsquare.com/files/rs-4442842/v1/69e76f561ee89e00117a64b4.png"},{"id":57408899,"identity":"6e7412e5-3264-4364-8d31-f1ac2b9e6282","added_by":"auto","created_at":"2024-05-30 10:03:23","extension":"jpeg","order_by":3,"title":"Figure 3","display":"","copyAsset":false,"role":"figure","size":120323,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eGraph Representation of Propositional Formula\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"floatimage3.jpeg","url":"https://assets-eu.researchsquare.com/files/rs-4442842/v1/c74ba50c10ff8973c4c157f7.jpeg"},{"id":57408897,"identity":"9827159f-48c0-402c-8b43-f31d3e878e2d","added_by":"auto","created_at":"2024-05-30 10:03:23","extension":"png","order_by":4,"title":"Figure 4","display":"","copyAsset":false,"role":"figure","size":3660,"visible":true,"origin":"","legend":"\u003cp\u003e\u003cstrong\u003eLiterals Checking Table\u003c/strong\u003e\u003c/p\u003e","description":"","filename":"F4.png","url":"https://assets-eu.researchsquare.com/files/rs-4442842/v1/ae1b7a20e5f32f0943e2200b.png"},{"id":59487837,"identity":"3e8d05c7-0e2c-45a0-9613-d3aaf4043aef","added_by":"auto","created_at":"2024-07-02 11:26:50","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":588312,"visible":true,"origin":"","legend":"","description":"","filename":"manuscript.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4442842/v1/016a8214-354f-4dc1-b693-77b3c3d92878.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"An Efficient Method for Converting Irregular Logical Formula into DNF/CNF with Graph Structure","fulltext":[{"header":"1. Research Motivation","content":"\u003cp\u003eThe original problem that motivated this research was to find an optimal combination of attributes for access control in a distributed computing environment, which exposes the least accumulated privacy information. It is like a decision Tree problem; however, this method pursues a different approach. We employed a Graph structure instead of Tree structure. An attribute or a combination of attributes can be evaluated by the privacy information exposure grades that come from the attributes delivered for access control. To determine the optimal combination of attributes with the least privacy information, we need to investigate combinations of attributes which satisfy access conditions for a computer security system.\u003c/p\u003e \u003cp\u003eThe conditional requirements required by the security systems can be represented in a logical formula which is composed of polynomial literals and logical connectives such as negation, conjunction, and disjunction. Each literal can be considered the required attributes, and a conjunctive clause in the logical formula can represent the required combination of attributes for access control assessment. Any irregular logical formulae can be converted into an equivalent DNF or CNF. The DNF conversion method introduced in this paper supported a mechanism that can produce an efficient access control conditions assessment. The method can be employed for CNF conversion with minor modifications.\u003c/p\u003e \u003cp\u003eWe considered only three logical connectives -AND(\u0026and;), OR(\u0026or;), NOT(\u0026not;) because the objective of the original research is to verify an optimal combination of attributes to submit to an access control system. The required attributes that can afford accessibility to a distributed computing services and resources are expressed in a propositional formula such as:\u003c/p\u003e \u003cp\u003e\u0026not;p \u0026or; q \u0026and; r \u0026or; ( s \u0026and; t \u0026or; u ) \u0026or; ( ( p \u0026and; v \u0026or; w) \u0026and; ( x \u0026or; y))\u003c/p\u003e \u003cp\u003e\u0026ndash; (1)\u003c/p\u003e \u003cp\u003ewhere p, q, r, s, t, u, v, w, x, y stand for the name of attributes. Each attribute has a unique property that indicates the degree of privacy information. To efficiently assemble an optimal combination of attributes effectively that ensures accessibility while containing the least amount of privacy information, the propositional logic formula must be converted to complete DNF. The original propositional logic formula\u0026rsquo;s transformed DNF is as follows:\u003c/p\u003e \u003cp\u003e( \u0026not;p \u0026and; r ) \u0026or; ( q \u0026and; r ) \u0026or; ( s \u0026and; t ) \u0026or; u \u0026or; ( p \u0026and; v \u0026and; x )\u003c/p\u003e \u003cp\u003e\u0026or; ( p \u0026and; v \u0026and; y) \u0026or; (w \u0026and; x ) \u0026or; (w \u0026and; y ) - (2)\u003c/p\u003e \u003cp\u003eThe computing service and resource providers determine the accessibility of their services and resources by the submitted attributes in an attribute-based access control system. The resource users will present a composite of attributes expressed in a conjunctive clause in DNF which marks the level of privacy and will select a set of attributes disclosing least privacy information while ensuring the access to the resources and services.\u003c/p\u003e \u003cp\u003eWe studied an efficient technique that converts any type of propositional formula into full DNF to create an optimal combination of attributes that satisfies accessibility conditions with the least amount of privacy information.\u003c/p\u003e"},{"header":"2. Research Background","content":"\u003cdiv id=\"Sec3\" class=\"Section2\"\u003e \u003ch2\u003e2.1. Terminology\u003c/h2\u003e \u003cp\u003eThe terminologies used in this paper follow the definitions in \u0026ldquo;Lecture Notes in Computer Science vol.679\u0026rdquo; [\u003cspan citationid=\"CR5\" class=\"CitationRef\"\u003e5\u003c/span\u003e].\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec4\" class=\"Section2\"\u003e \u003ch2\u003e2.2. Conjunctive and Disjunctive Normal Form\u003c/h2\u003e \u003cp\u003eDiverse methods for fast and easy validity testing of propositional formula have been introduced [\u003cspan citationid=\"CR2\" class=\"CitationRef\"\u003e2\u003c/span\u003e] [\u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e3\u003c/span\u003e] [\u003cspan citationid=\"CR6\" class=\"CitationRef\"\u003e6\u003c/span\u003e]. The introduced methods in the research depend on testing conjunctive or disjunctive clauses, which are components of DNF or CNF logically equivalent to the propositional formula.\u003c/p\u003e \u003cp\u003eAll the propositional logic forms are to be converted into logically and semantically equivalent Conjunctive Normal Forms or Disjunctive Normal Form. Which of the normal form is preferred depends on the characteristics of applications [\u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e3\u003c/span\u003e]. The size of CNF and DNF can be expressed by the maximum number of literals in a conjunctive or disjunctive clause in the CNF or DNF. Ronald Revest et al. defined \u003cem\u003ek\u003c/em\u003e-CNF and \u003cem\u003ek\u003c/em\u003e-DNF to be the set of Boolean formulae in conjunctive or disjunctive normal form where each clause has k-literals at most. They showed \u003cem\u003ek\u003c/em\u003e-CNF is converted into \u003cem\u003ek\u003c/em\u003e-DNF and \u003cem\u003ek\u003c/em\u003e-DNF is converted into \u003cem\u003ek\u003c/em\u003e-CNF by applying De Morgan\u0026rsquo;s Rules [\u003cspan citationid=\"CR6\" class=\"CitationRef\"\u003e6\u003c/span\u003e]. Both CNF and DNF are convenient formats for evaluating the validity of a propositional formula with the same complexity. While DNF and CNF have the same level of complexity, there could be a more efficient normal form for different problems.\u003c/p\u003e \u003cp\u003eWhen we evaluate the validity of a propositional formula to find an optimal combination of literals, converting the propositional formula to DNF will be preferable because it allows simultaneous validation of formula and calculation of each literal set\u0026rsquo;s property values.\u003c/p\u003e \u003cp\u003eThe previous DNF example (2) is 3-DNF with eight conjunctive clauses. It is converted into 3-CNF with eight disjunctive clauses such as:\u003c/p\u003e \u003cp\u003e(p \u0026or; \u0026not;r ) \u0026and; (\u0026not;q \u0026or; \u0026not;r ) \u0026and; (\u0026not;s \u0026or; \u0026not;t ) \u0026and; \u0026not;u \u0026and; (\u0026not;p \u0026or; \u0026not;v \u0026or; \u0026not;x )\u003c/p\u003e \u003cp\u003e\u0026and; (\u0026not;w \u0026or; \u0026not;x ) \u0026and; (\u0026not;p \u0026or; \u0026not;v \u0026or; \u0026not;y) \u0026and; (\u0026not;w \u0026or; \u0026not;y ) - (3)\u003c/p\u003e \u003cp\u003eIf we evaluate only the validity of a propositional formula following traditional process on distribute, associative and De Morgan\u0026rsquo;s law, it is not feasible to assess which combination of literals produce an optimal result (least privacy information). However, if we evaluate the validity of a propositional formula in a DNF, it is the more efficient because we can evaluate the validity of the formula and calculate the score of each literals\u0026rsquo; combination simultaneously by visiting every conjunctive clause in DNF.\u003c/p\u003e \u003c/div\u003e \u003cdiv id=\"Sec5\" class=\"Section2\"\u003e \u003ch2\u003e2.3. Graph Data Structure\u003c/h2\u003e \u003cp\u003eThe traditional conversion procedure that transforms a propositional formula into a logically equivalent Conjunctive or Disjunctive Normal Form involves repeated operations of transforms with Distributive Law, Associative Law, and De Morgan\u0026rsquo;s Law. We propose a DNF conversion method which employs a Graph structure for efficient and effective DNF conversion from a complex propositional formula.\u003c/p\u003e \u003cp\u003eA propositional formula can be represented by a Tree structure for fast DNF conversion also, and the cost for traversing nodes for DNF expression in a Tree structure is the same as the Graph representation proposed in this paper. However, the Graph structure has advantages in simplicity of programming and the space complexity of data storage for computation. The Tree structure requires exponential increase in space complexity; however, the Graph structure requires linear increase of the space complexity as the size of propositional formula grows. If we use a Tree structure, we must build a sub-Graph containing the same number of leaf nodes in the Tree for every parenthesis clause. However, if we use Graph structure, we need to build a sub-Graph and connect the sub-Graph to each leaf node in the Graph.\u003c/p\u003e \u003cp\u003e( p \u0026or; q ) \u0026and; ( r \u0026or; s ) -(4)\u003c/p\u003e \u003cp\u003e \u003c/p\u003e \u003cp\u003eFigure-1 illustrates a representation of propositional formula of (4), framed in Tree and Graph structure. Every node in the Tree/Graph, with exception of ROOT and pseudo nodes, represents a literal in a propositional formula. In the illustration, the sibling relationship represents the disjunctive connective, and the parent-child relationship represents the conjunctive connective. The benefit of using a Graph structure for DNF conversion is illustrated in Fig.\u0026nbsp;\u003cspan refid=\"Fig1\" class=\"InternalRef\"\u003e1\u003c/span\u003e. This advantage also can be applied for CNF conversion from any propositional formula with minor modifications.\u003c/p\u003e \u003c/div\u003e"},{"header":"3. Proposed Method","content":"\u003cp\u003eDNF is a standard normal form of a logical formula composed of a disjunction of conjunctions.\u003c/p\u003e\n\u003cp\u003eThe first step for full DNF conversion proposed in this paper is to construct a Graph structure and crop a set of conjunctive clauses in the DNF. The conjunctive clauses may contain redundant literals or mutually contradictive literals.\u003c/p\u003e\n\u003cp\u003eThe second phase is to eliminate the redundancies and contradictions from the candidate conjunctions. If there are the same multiple literals in a conjunctive clause, we keep only one literal in the conjunctive clause since only one of the literals is valid. If there are mutually contradictive literals in a conjunctive clause, we discard the clause from DNF because it is invalid clause. After individual conjunction of literals is pruned, we investigated the entire DNF to eliminate redundancies. If a conjunctive clause of literals is a subset of another conjunctive clause, we remove the superset conjunction of literals from the DNF because we only need to evaluate the conjunctive clause with the smallest number of literals, which satisfies the conditional requirements.\u003c/p\u003e\n\u003cp\u003eThe third phase is to evaluate every conjunctive clause based on its properties of literals (attributes) for determining the optimal combination of attributes that exposes the least privacy information. We considered only the privacy level of attributes for simplicity in this paper. However, the scores may change by different problem sets and policies. We considered only three logical connectives -AND(\u0026and;), OR(\u0026or;), NOT(\u0026not;) in this research because the objective of this research is to find an optimal combination of attributes.\u003c/p\u003e\n\u003cdiv id=\"Sec7\"\u003e\n \u003ch2\u003e3.1. Convert Propositional Formula into a Graph\u003c/h2\u003e\n \u003cp\u003eEach literal in the propositional formula is represented in a node that contains several properties. Figure-2 illustrates a node\u0026rsquo;s data structure which contains properties of parent node, flag, child node(s), and property values, such as the name and privacy level of the attribute node.\u003c/p\u003e\n \u003cp\u003eThe property of parent and child node is the link pointing to its parent and child nodes, and the flag is used for Graph traversal, and the value represents the respective property value of the literal, such as privacy level.\u003c/p\u003e\n \u003cp\u003eTo build a Graph representing a propositional formula, we have to consider two connectives: conjunctive connective(\u0026and;) and disjunctive connective(\u0026or;), and parenthesis that describe the precedence of conversion operations. The Graph starts from a root node which has null value of parent, and property values. When a parenthesis is met, a pseudo node is created to build a sub-Graph with the literals in the parenthesis. The procedure for building a DNF conversion Graph follows the algorithms as below:\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eStart from ROOT node\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eRead Next\u003c/em\u003e\u003c/p\u003e\n \u003cdiv\u003e\n \u003cp\u003e\u003cem\u003eIf \u0026lsquo;(\u0026lsquo; : Create a pseudo root node and follow recursion procedure of Graph creation until \u0026lsquo;)\u0026rsquo; appears.\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eElse if \u0026lsquo;literal\u0026rsquo; : Create a node and connect it to ROOT node.\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eRead Next\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eIf \u0026lsquo;\u0026or;\u0026rsquo; : Create a node with next literal/clause and assign the node to sibling node of the current node.\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eElse if \u0026lsquo;\u0026and;\u0026rsquo; : Create a node with next literal/clause and assign the node to every leaf node as a child node in current Graph\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eElse if \u0026lsquo;(\u0026lsquo; : Create a pseudo root node and follow recursion procedure of Graph creation until \u0026lsquo;)\u0026rsquo; appears.\u003c/em\u003e\u003c/p\u003e\n \u003c/div\u003e\n \u003cp\u003e\u003cem\u003eRepeat\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003eIf we construct a Graph with Formula-(1) following algorithm above, the Graph will be constructed as below:\u003c/p\u003e\n \u003cp\u003e\u0026not;p \u0026or; q \u0026and; r \u0026or; ( s \u0026and; t \u0026or; u ) \u0026or; ( ( p \u0026and; v \u0026or; w) \u0026and; ( x \u0026or; y))\u003c/p\u003e\n\u003c/div\u003e\n\u003cdiv id=\"Sec8\"\u003e\n \u003ch2\u003e3.2. Graph Traversal for Conjunctive Clause Retrieval\u003c/h2\u003e\n \u003cp\u003eEvery depth-first search traversal path from ROOT node to a leaf node provides a possible conjunctive clause in DNF. The visited node\u0026rsquo;s properties are recorded to build conjunctive clauses and assess property values.\u003c/p\u003e\n \u003cp\u003eThe procedures for collecting conjunctive clauses for DNF construction follow the algorithm as below:\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eStart from ROOT node\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eVisit 1st Child node\u003c/em\u003e\u003c/p\u003e\n \u003cdiv\u003e\n \u003cp\u003e\u003cem\u003eRecord properties: name, value \u0026hellip;\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eIf \u0026lsquo;Pseudo node\u0026rsquo;\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eVisit Child nodes recursively\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eElse if \u0026lsquo;Leaf node\u0026lsquo;\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eAdd disjunctive relationship\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eReturn to parent node\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eElse if \u0026lsquo;Child node exist\u0026rsquo;\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eAdd conjunctive relationship\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eVisit 1st Child node\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eRecord node properties\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eExecute recursive visit procedures\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eVisit next Child node\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eRecord node properties\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eExecute recursive visit procedures\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eIf \u0026lsquo;No more Child node\u0026rsquo; node\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eReturn to Parent node\u003c/em\u003e\u003c/p\u003e\n \u003c/div\u003e\n \u003cp\u003e\u003cem\u003eVisit next Child node\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eExecute recursive visit procedures\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eIf \u0026lsquo;No more Child node\u0026rsquo;\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003e\u003cem\u003eReturn to Parent node\u003c/em\u003e\u003c/p\u003e\n \u003cp\u003eIn Fignre-3, there are two paths from ROOT node to leaf node \u0026lsquo;x\u0026rsquo;. To reach \u0026lsquo;x\u0026rsquo; from ROOT, we traverse either \u0026lsquo;R-R-p-v-R-x\u0026rsquo; or \u0026lsquo;R-R-w-R-x\u0026rsquo; in order. If we remove pseudo nodes represented by \u0026lsquo;R\u0026rsquo; from the path, we can have \u0026lsquo;p-v-x\u0026rsquo; path and \u0026lsquo;w-x\u0026rsquo; path. Since the relationship between nodes in the same path is a parent-child relationship, they are conjunctive connective relationship, and each sibling node\u0026rsquo;s traversal paths from ROOT node have disjunctive relationship. The set of conjunctive clauses with disjunctive relationship composes a DNF.\u003c/p\u003e\n \u003cp\u003eIf we retrieve all the paths from the ROOT node to each leaf node following the rules given previously, the possible DNF will be the same as Formula-(2).\u003c/p\u003e\n\u003c/div\u003e\n\u003cdiv id=\"Sec9\"\u003e\n \u003ch2\u003e3.3. Prune Redundancy and Remove Contradiction\u003c/h2\u003e\n \u003cp\u003eThe original propositional formula may have redundant conditional terms or contradicting conditional terms. We considered two different layers of redundancy pruning and one layer of contradiction removal.\u003c/p\u003e\n \u003cp\u003eThe first level of redundancy pruning, and contradiction removal considers any redundancies and contradictions in a conjunctive clause. When we deal with a complex propositional formula, we may find redundant literals such as:\u003c/p\u003e\n \u003cp\u003e( p \u0026and; q \u0026and; r \u0026and; s \u0026and; p \u0026and; r \u0026and; s ) -(5)\u003c/p\u003e\n \u003cp\u003eIn Formula-(5) there are two \u0026lsquo;r\u0026rsquo;s and \u0026lsquo;s\u0026rsquo;s which are redundant literals. The redundant literals must be removed and only one of the same literals is kept because (r \u0026and; r) is the same with \u0026lsquo;r\u0026rsquo; and (s \u0026and; s) is the same with \u0026lsquo;s.\u0026rsquo;\u003c/p\u003e\n \u003cp\u003eThere can be contradicting literals in a conjunctive clause such as:\u003c/p\u003e\n \u003cp\u003e( p \u0026and; q \u0026and; r \u0026and; s \u0026and; p \u0026and; \u0026not;r \u0026and; t ) -(6)\u003c/p\u003e\n \u003cp\u003eIn Formula-(6), the two literals of \u0026lsquo;r\u0026rsquo; and \u0026lsquo;\u0026not;r\u0026rsquo; are contradicting which makes the whole conjunctive clause invalid. We investigate every conjunctive clause and discard the clause if there are any contradictory literals in the clause from DNF because it never will be satisfied.\u003c/p\u003e\n \u003cp\u003eThe higher-level of redundancy pruning is same as the lower-level redundancy pruning. It deals with different conjunctive clauses instead of literals in a clause.\u003c/p\u003e\n \u003cp\u003e( p \u0026and; q \u0026and; r ) \u0026or; (p \u0026and; q \u0026and; r \u0026and; s \u0026and; p) -(7)\u003c/p\u003e\n \u003cp\u003eIn Formula-(7), the conjunctive clause of \u0026lsquo;(p \u0026and; q \u0026and; r \u0026and; s \u0026and; p)\u0026rsquo; is redundant clause because the extra literals in the longer conjunctive clause are meaningless.\u003c/p\u003e\n \u003cp\u003e{ p, q, r } \u0026sub; { p, q, r, s, p} -(8)\u003c/p\u003e\n \u003cp\u003eIf a set of literals in a conjunctive clause is a subset of another set of literals, the longer conjunctive clause must be removed from DNF. In Formula-(7), the clause of \u0026lsquo;(p \u0026and; q \u0026and; r \u0026and; s \u0026and; p)\u0026rsquo; is removed because there is a subset literals clause in the DNF.\u003c/p\u003e\n \u003cp\u003eFinding the subset-superset relationship between multiple sets of literals is achieved by using bit operation of respective sets. The literals in each conjunctive clause are sorted and the existence of a specific literal is in each set was recorded in the corresponding row and column of literals checking table. The bit-sum of bit-operation between multiple clauses presents the number of matching literals in the different clauses. If the bit-sum of bit-operation is the same as the bit-sum of a clause, the other clause is a redundant clause which needs to be removed from DNF.\u003c/p\u003e\n \u003cdiv\u003e\n \u003cp\u003e\u003cstrong\u003eFigure 4. Literals Checking Table\u003c/strong\u003e\u003c/p\u003e\n \u003c/div\u003e\n\u003c/div\u003e\n\u003cdiv id=\"Sec10\"\u003e\n \u003ch2\u003e3.4. Selecting Optimal Literals Combination\u003c/h2\u003e\n \u003cp\u003eThe redundancy pruning and contradiction removal from a DNF is a full disjunctive normal form in which a literal appears exactly once in each clause. To identify the optimal conjunctive clause of literals, we evaluated the sum of property values from every conjunctive clause. The set of literals within a conjunctive clause presenting the best property values is the optimal literals combination.\u003c/p\u003e\n\u003c/div\u003e\n\u003cdiv id=\"Sec11\"\u003e\n \u003ch2\u003e3.5. Performance Issue\u003c/h2\u003e\n \u003cp\u003eConverting a propositional form into a normal form can involve an exponential increase of its size [\u003cspan\u003e4\u003c/span\u003e]. There have been many research that can reduce storage complexity and time complexity of normal form conversion processes [\u003cspan\u003e6\u003c/span\u003e] [\u003cspan\u003e7\u003c/span\u003e] [\u003cspan\u003e9\u003c/span\u003e]. They introduced efficient methods and techniques for efficient normal conversion. However, they focused on finding methods for efficient validity testing of propositional formulas with the normal forms, which makes it difficult to be applied to an optimal condition selection problem.\u003c/p\u003e\n \u003cp\u003eThe time complexity of this method is O (log N * 2\u003csup\u003e\u003cem\u003elog N\u003c/em\u003e\u003c/sup\u003e) where \u0026lsquo;N\u0026rsquo; is the number of literals in given propositional formula. The most complex step in this method is at the traversal step for finding paths within the Graph structure. If the propositional formula is divided by multiple sub-Graphs with constant number of \u0026lsquo;\u003cem\u003ek\u003c/em\u003e\u0026rsquo; literals, the number of paths from the ROOT node to each leaf node will be \u003cem\u003ek\u003c/em\u003e \u003csup\u003e\u003cem\u003eN/k\u003c/em\u003e\u003c/sup\u003e, and it is multiplied by (log \u003csub\u003ek\u003c/sub\u003e N) to count the number of nodes visited. The worst number of \u003cem\u003ek\u003c/em\u003e\u0026thinsp;=\u0026thinsp;2.\u003c/p\u003e\n\u003c/div\u003e"},{"header":"4. Conclusion","content":"\u003cp\u003eDNF is a disjunction of conjunctive clauses. When we identify the validity of a propositional formula and verify an optimal combination of literals that makes the propositional formula valid while ensuring the best property values of the literals, converting the formula into logically equivalent DNF allows faster validity evaluation and optimal literals set selection.\u003c/p\u003e \u003cp\u003eWe introduced an efficient DNF conversion method by employing Graph structure to aggregate literals of an optimal combination of attributes. When we evaluate the validity of a propositional formula, converting the formula into CNF may also ensure the best solution. The method converting propositional formula to DNF using Graph structure can be applied to convert the logical formula into CNF by changing the relationship of literals. In DNF conversion method, we translated conjunctive connective into a parent-child relationship and disjunctive connective into a sibling relationship. To convert the propositional formula into CNF, the relationship between parent-child nodes, and sibling nodes are defined the opposite way of DNF conversion process, and the redundancy pruning, and contradiction removal procedures will be the same.\u003c/p\u003e"},{"header":"Declarations","content":"\u003ch2\u003eAuthor Contribution\u003c/h2\u003e\u003cp\u003eSangmork Park executed the research, developed the whole manuscript and figures, and reviewed.\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003eStatements and Declarations\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003eThe author did not receive support from any organization for the submitted work.\u003c/p\u003e"},{"header":"References","content":"\u003col\u003e\u003cli\u003e\u003cspan\u003eDoets, K. Conjunctive Normal Form, \u003cem\u003eFrom Logic to Logic Programming\u003c/em\u003e, The MIT, pp.17\u0026ndash;18.\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eHuth, M., \u0026amp; Ryan, M. Semantics of Propositional Logic, \u003cem\u003eLogic in Computer Science: Modeling and Reasoning about Systems\u003c/em\u003e, Cambridge University Press, pp.45\u0026ndash;68.\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eHuth, M., \u0026amp; Ryan, M. Normal Forms, \u003cem\u003eLogic in Computer Science: Modeling and Reasoning about Systems\u003c/em\u003e, Cambridge University Press, pp.69\u0026ndash;89.\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003ePeter Bro Miltersen, Radhakrishnan, J., \u0026amp; Wegener, I. On Converting CNF to DNF, \u003cem\u003eMathematical Foundations of Computer Science 2003\u003c/em\u003e, Springer Berlin/Heidelberg, pp. 612\u0026ndash;621.\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eChapter 2 Terminology, \u003cem\u003eResolution Methods for the Decision Problem 1993\u003c/em\u003e, Springer Berlin/Heidelberg, pp. 6\u0026ndash;16.\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eRivest, R. L. Learning Decision List, Machine Learning vol.2 No.3, Springer Nethelands, pp. 229\u0026ndash;246.\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003ePanagiotis Manolios, \u0026amp; Vroon, D. Efficient Circuit to CNF Conversion, \u003cem\u003eTheory and Applications of Satisfiability Testing-SAT 2007\u003c/em\u003e, Springer Berlin/Heidelberg, pp. 4\u0026ndash;9.\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eLang, B. Ian Foster et al. Attribute Based Access Control for Grid Computing, \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003eftp://info.mcs.anl.gov/pub/tech_reports/reports/P1367.pdf\u003c/span\u003e\u003cspan address=\"http://ftp://info.mcs.anl.gov/pub/tech_reports/reports/P1367.pdf\" targettype=\"URL\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e.\u003c/span\u003e\u003c/li\u003e \u003cli\u003e\u003cspan\u003eDaniel Sheridan The optimality of a Fast CNF Conversion ant its Use with SAT, Proc. of SAT-2004, \u003cspan class=\"ExternalRef\"\u003e\u003cspan class=\"RefSource\"\u003ehttp://www.satisfiability.org/SAT04/programme/114.pdf\u003c/span\u003e\u003cspan address=\"http://www.satisfiability.org/SAT04/programme/114.pdf\" targettype=\"URL\" class=\"RefTarget\"\u003e\u003c/span\u003e\u003c/span\u003e.\u003c/span\u003e\u003c/li\u003e\u003c/ol\u003e"}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":true,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":false,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Conjunctive Normal Form, Disjunctive Normal Form, Logical Formula, Graph Theory","lastPublishedDoi":"10.21203/rs.3.rs-4442842/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4442842/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003eIn 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) [\u003cspan citationid=\"CR1\" class=\"CitationRef\"\u003e1\u003c/span\u003e][\u003cspan citationid=\"CR3\" class=\"CitationRef\"\u003e3\u003c/span\u003e] 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.\u003c/p\u003e \u003cp\u003eThe 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 * 2\u003csup\u003e\u003cem\u003elog N\u003c/em\u003e\u003c/sup\u003e).\u003c/p\u003e \u003cp\u003eWe 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.\u003c/p\u003e \u003cp\u003eA logical formula evaluation process is repeated operations following the rules of logical equivalences, such as double negative elimination, De Morgan\u0026rsquo;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.\u003c/p\u003e","manuscriptTitle":"An Efficient Method for Converting Irregular Logical Formula into DNF/CNF with Graph Structure","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-05-30 10:03:18","doi":"10.21203/rs.3.rs-4442842/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"ce9cb4e6-6b7f-4bd2-b2b5-1e4f5fe9e26a","owner":[],"postedDate":"May 30th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-07-02T11:18:43+00:00","versionOfRecord":[],"versionCreatedAt":"2024-05-30 10:03:18","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-4442842","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4442842","identity":"rs-4442842","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}