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.