Given $m, n, k$, how many of $k$-DNFs with $n$ variables and $m$ clauses are tautology? (or how many $k$-CNFs are unsatisfiable?)
How many tautologies are there?
co.combinatorics;lo.logic;sat
The answer depends on $k$, $m$, and $n$. Exact counts are generally not known, but there is a threshold phenomenon that for most settings of $k$, $m$, $n$, either nearly all $k$-SAT instances are satisfiable, or nearly all instances are unsatisfiable. For example, when $k=3$, it has been empirically observed that when $m < 4.27 n$, all but a $o(1)$ fraction of 3-SAT instances are satisfiable, and when $m > 4.27n$, all but a $o(1)$ fraction are unsatisfiable. (There are also rigorous proofs of bounds known.) One starting point is The Asymptotic Order of the k-SAT Threshold. Amin Coja-Oghlan has also done a lot of work on these satisfiability threshold problems.