Boolean minors Original Research Article

We study the problem of characterizing monotonic Boolean functions and threshold Boolean functions by forbidden Boolean minors. Completely monotonic functions, k-monotonic functions and regular functions are characterized by forbidden minors. A bound on the number of minimal forbidden minors of k-comparable functions is obtained. We prove that there is a finite list of minimal forbidden minors for k-asummable functions and give a sharp bound on the dimension of minimal forbidden minors of k-asummable functions. We prove the conjecture that a Boolean function is (m, 2m)-asummable if and only if it has no parity function of dimension m+1 as minor for m=1, 2.