2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 9
    $\begingroup$ $(x \lor y \lor z)$ is a counterexample. Don't know about a characterization. $\endgroup$
    – Tyson Williams
    Commented 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$
    – Yuval Filmus
    Commented May 14, 2015 at 15:02

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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
    Commented 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.