On the OBDD-representation of general Boolean functions

摘要

The behavior of ordered binary decision diagrams (OBDD) for general Boolean functions is studied. A tight upper bound of (2/sup n/)(2+ epsilon ) for the worst case OBDD size is derived. Although the size of an OBDD is dependent on the ordering of decision variables, it is shown that almost all functions are not sensitive to variable ordering.