Boolean normal forms, shellability, and reliability computations

Orthogonal forms of positive Boolean functions play an important role in re liability theory, since the probability that they take value 1 can be easil y computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs ). In this paper, we present some new results about shellability. We establ ish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable D NF, and we prove that testing the so-called lexico-exchange (LE) property ( a strengthening of shellability) is NP-complete.