# If in all satisfying assignments all pair of variables can take all possible values is this tautology?

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?

• $(x \lor y \lor z)$ is a counterexample. Don't know about a characterization. – Tyson Williams May 13 '15 at 11:40
• Your condition can be restated as: the VC dimension of the set of satisfying assignments is at least 2. – 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.
• For a concrete example, try $x_1 \lor \cdots \lor x_{d+1}$, whose solution set has VC dimension $d$. – Yuval Filmus May 14 '15 at 15:12