THE NUMBER OF BOOLEAN FUNCTIONS COMPUTED BY FORMULAS OF A GIVEN SIZE

Estimates are given of the number B(n, L) of distinct functions comput ed by propositional formulas of size L in n variables, constructed usi ng only Literals and boolean AND, boolean OR connectives. (L is the nu mber of occurrences of variables. L - 1 is the number of binary boolea n AND s and vs. B(n, L) is also the number of functions computed by tw o terminal series-parallel networks with L switches.) Enroute the read -once functions, which are closely related to Schroder numbers, are en umerated Writing B(n, L)= b(n, L)L, We find that if L and beta(n) go t o infinity with increasing n and L less than or equal to 2(n)/n (beta( n)), then b(n, L) similar to cn, where c = 2/(1n4 - 1). Making a compa rison with polynomial size Boolean circuits, this implies the followin g. For any constant alpha > 1, almost all Boolean functions with formu la complexity at most n(alpha) cannot be computed by any circuit const ructed from literals and fewer than alpha(-1)n(alpha) two-input boolea n AND, boolean OR gates. (C) 1998 John Wiley & Sons, Inc.