Bollobas Brightwell and Leader [2] showed that there are at most 2((2n) + o(n2)) 2-SAT functions on n variable, and conjectured that in fact the number of 2-SAT functions on n variables is 2((2n) + n) (1 + o(1)). We prove their conjecture. As a corollary of this, we also find the expected number of satisfying assignments of a random 2-SAT function on n variables. We also find the next largest class of 2-SAT functions and show that if k = k(n) is any function with k(n) < n(1/4) for all sufficiently large n, then the class of 2-SAT functions on n variables which cannot be made unate by removing 25k variables is smaller than 2((2n) + n - kn) for all sufficiently large n.
展开▼
