A 3n-lower bound on the network complexity of Boolean functions

AbstractLet fn:{0, 1}2⌜lgn⌝+1+n→{0, 1} be the Boolean function fn(a,b,q,z1…,zn)=q⋁j=1n zj(a=j∨b=j)∨ ⊕j=1n zj(a=j∨b=j) where a→a is any surjective map B⌜lgn⌝→{1, 2, …,n}.We prove C(fn)⩾3n−2 where C(fn) is the minimal size of a Boolean network which computes fn over the base of all 16 binary Boolean operations. This lower bound corresponds to an upper bound of 3n provided that we count only those gates that depend on some variable zj