Abstract
Given a positive Boolean function fand a subset δ of its variables, we give a combinatorial condition characterizing the existence of a prime implicant Dˆof the Boolean dual f
d
of f having the property that every variable in δ appears in Dˆ
We show that the recognition of this property is an NP-complete problem, suggesting an inherent computational difficulty of Boolean dualization, independently of the size of the dual function.
Finally it is shown that if the cardinality of δ is bounded by a constant, then the above recognition problem is polynomial. In particular, it follows that the co-ocurrence graph of the dual of a positive Boolean function can be always generated in time polynomial in the size of the function.