# Upper bound for #Monotone k-SAT

(I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.)

Consider a collection of $n$ Boolean variables, $x_1,\ldots,x_n$ and a function $F$ on this collection of variables, $F(x_1,\ldots,x_n)$. An assignment of true and false values to each Boolean variable is called a satisfying assignment if $F(x_1,\ldots,x_n)$ is true.

I'm interested in functions $F$ that take the form $(x_{i_1}\vee x_{j_1} \vee \cdots \vee x_{k_1})\wedge \cdots \wedge (x_{i_m}\vee x_{j_m} \vee \cdots \vee x_{k_m})$ where indices are allowed to repeat, a so-called Monotone k-SAT function. Perhaps something worth noting is that not all of the clauses contain $k$ variables, but it is known that $k$ is the most number of variables in all clauses.

Question: What sort of bounds on the number of satisfying assignments for $F$ are known? The worst bound is $2^n$; I'm hoping there is something better.

(Note: this builds on an original question graciously answered by Yuval Filmus here: Number of states in an AND-OR DAG)

• A bound in terms of what? If you want an upper bound that depends only on $n$ and $k$, there is no upper bound better than $2^n$: it is easy to construct a formula that has satisfying assignments, so the upper bound $2^n$ is tight. The same for lower bounds (the lower bound of 0 is tight). – D.W. Apr 5 '16 at 21:16

A $k$-SAT instance over $n$ variables, monotone or otherwise, has at most $2^n - 2^{n-k}$ solutions. This is simply the number of possible settings of the $n$ variables minus the least number of settings a single $k$-CNF clause can exclude, assuming all the variables in the clause are distinct. You only have to consider the case of a formula with a single clause because adding more clauses can never increase the number of satisfying assignments.
• Thanks for the response. Do you have a reference for this? Also, a comment above says that $2^n$ is tight, why is this not the case here? – jonem Apr 6 '16 at 22:28
• $2^n$ is a tight upper bound if an empty formula is considered valid, as the convention is that any assignment of the variables satisfies such a formula. There's no reference; the logic of the answer should be straightforward enough that you can verify the truth of it yourself. – Kyle Jones Apr 7 '16 at 2:29