Tree-shellability of Boolean functions

In this paper, we define tree-shellable and ordered tree-shellable Boolean functions. A tree-shellable function is a positive Boolean function such th at the number of prime implicants equals the number of paths from the root node to a I-node in its binary decision tree representation. A tree-shellab le function is easy to dualize and good for a kind of reliability computati on. We show their basic properties and clarify the relations between severa l shellable functions, i.e. shellable, tree-shellable, ordered tree-shellab le, aligned and lexico-exchange functions. We also discuss on tree-shellabl e quadratic functions. (C) 2001 Elsevier Science B.V. All rights reserved.