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$ – Tyson Williams May 13 '15 at 11:40
  • $\begingroup$ Your condition can be restated as: the VC dimension of the set of satisfying assignments is at least 2. $\endgroup$ – Yuval Filmus May 14 '15 at 15:02

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$ – Yuval Filmus May 14 '15 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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