I suppose this is both easy and false.

Let $\phi$ be propositional boolean formula on variables $x_1 \ldots x_n$.

Suppose in all satisfying assignments of $\phi$, all pairs of variables $(x_i,x_j),i \ne j$ can take all possible values, i.e. any of $\{(F,F),(F,T),(T,F),(T,T)\}$.

Is $\phi$ tautology?

In case the answer is negative, is there simple characterization of those $\phi$ which are not tautologies?

  • 9
    $\begingroup$ $(x \lor y \lor z)$ is a counterexample. Don't know about a characterization. $\endgroup$ May 13, 2015 at 11:40
  • $\begingroup$ Your condition can be restated as: the VC dimension of the set of satisfying assignments is at least 2. $\endgroup$ May 14, 2015 at 15:02

1 Answer 1


The VC dimension of a set $S \in \{0,1\}^n$ is the maximal $d$ such that for all $i_1 < \cdots < i_d \in \{1,\ldots,n\}$ and all $b_1,\ldots,b_d \in \{0,1\}$, there is a point $x \in S$ such that $x_{i_1} = b_1,\ldots,x_{i_d} = b_d$. Your condition states that the VC dimension of the set of satisfying assignment of a formula is at least $2$. The formula is a tautology if the VC dimension is $n$. There are sets of arbitrary VC dimension, so even if you replace pairs by larger tuples, your conclusion would still be wrong.

  • 1
    $\begingroup$ For a concrete example, try $x_1 \lor \cdots \lor x_{d+1}$, whose solution set has VC dimension $d$. $\endgroup$ May 14, 2015 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.