Augmenting Negation Normal Form with Irrelevant Variables

Irrelevant variables are always omitted in knowledge compilation languages since their assignments do not change the satisfiability of sentences. In order to identify new knowledge compilation languages and reduce the scale of compiling result of d-DNNF, we augment NNF with irrelevant variables in this paper. The NNF PNI , NNF PI , and NNF NI are proposed based on different combinations of positive literals, negative literals, and irrelevant variables. Each sentence in NNF, NNF PI , NNF NI , or NNF PNI can be translated to an equivalent sentence in another language in polynomial time. We also define d-DNNF NI , d-DNNF PI , and d-DNNF PNI based on decomposability and determinism in NNF, which are subclasses of NNF PI , NNF NI , and NNF PNI , respectively. A number of querying and transforming methods for d-DNNF PNI , d-DNNF PI , and d-DNNF PI are designed to solve relevant reasoning problems in knowledge compilation map. Overall, d-DNNF PI and d-DNNF NI do not reduce the tractability of d-DNNF, so we propose a compressing method for d-DNNF based on d-DNNF PI and d-DNNF NI . The experimentally, the compiling results of the d-DNNF PI and d-DNNF NI are better with respect to d-DNNF for most instances, and our compressing method is significantly effective for all instances.