# Could we know what's the total number of unsatisfiable 3SAT formulas for a given n variables?

given some $$n$$ variables I would be interested to know what is the count of all 3SAT formulas under $$n$$ that are unsatisfiable.

An example of all 3SAT forumlas under $$n=3$$ is the following: $$( x \lor y \lor z) = Satisfiable \\ ... \\ ( x \lor y \lor z)\land ( \neg x \lor \neg y \lor z)= Satisfiable \\ ... \\ ( x \lor y \lor z)\land( x \lor y \lor \neg z).....( \neg x \lor \neg y \lor \neg z) = Unsatisfiable$$ The total count of $$n=3$$ would be 1, because only the last formula is actually unsatisfiable

as you can see, even with a small number such as $$n=3$$ there are 256 different formulas, going even a single digit up to $$n=4$$ will result in $$2^{32}$$ different formulas, so it cannot be simulated.

Therefor I was wondering, is there any way of knowing just the count without having to check it one by one?

• are you interested in exact answers, or approximate is sufficient? Jul 8, 2022 at 23:11
• There are some interesting asymptotic bounds: If you draw a 3SAT formula randomly with $n$ variables and $m$ clauses, almost all with $\frac{m}{n}> 4.267$ are unsatisfiable, and almost all with $\frac{m}{n}<4.267$ are satisfiable. You can easily calculate the number of these. See cs.stackexchange.com/a/86544/44709 Jul 9, 2022 at 15:43
• What does it mean for a formula to be "under $n$"?
– D.W.
Jul 9, 2022 at 18:28
• Have you checked oeis.org?
– D.W.
Jul 9, 2022 at 18:28
• @AmeerJewdaki although not exactly answering it does provide interesting and valuable insight, thank you Jul 9, 2022 at 19:07