cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.

2010-01-21T19:08:47Z

 Cardinal Equivalence Theorem

For each boolean formula, |quantifications| = |assignments|.

The set of valid quantifications has some cardinality, call that |Q(B)|. The set of satisfying assignments has some cardinality, call that |P(B)|. Those two numbers are equal, |Q(B)| = |P(B)|, range from 0 through 2^n.

Question one: Does anyone know the theorem by any other name?

++ Variable order

Changing the order of the variables of B changes the particulars of each set, but their cardinalities are still the same.
If we knew more precisely what swapping two variables does to the previously valid set of quantifications, then perhaps some form of Zipper Theorem could Be. However, my competency with quantifiers is less than necessary or sufficient to even compose any informally stated Zipper Theorem.

++ Question two:

Linear Corollary: Monotone QBFs are linearly decidable.

I only know this result as a followup to the Cardinal Equivalence. Is there a well known name for the Linear Corollary as a theorem?

thank you, daniel.
pehoushek1 at gee mail dot com.

Answer by Darsh Ranjan for cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.

2010-01-22T05:14:03Z

I think Daniel might be asking about the following proposition:

Let $f:\{0,1\}^n\to\{0,1\}$ be any function (i. e., an "n-ary boolean function"). The number of true formulas $$ Q_1 x_1 \ldots Q_n x_n : f(x_1,\ldots,x_n) = 1,$$ where each $Q_i$ is a quantifier $\forall$ or $\exists$, is equal to the number of $(x_1,\ldots,x_n)$ for which $f(x_1,\ldots,x_n) = 1$.

The proof is very easy (by induction on $n$). It's an amusing proposition, no doubt, but I don't know of any applications. It might make an interesting advanced exercise in a discrete mathematics course, though.

I've implicitly answered the question, but explicitly:

Does anyone know the theorem by any other name?

I'm not aware of such.

Have you or anyone you know ever heard of this equivalence?

I discovered it a few years ago, apparently about five years after you did. Nobody I tried to tell seemed interested by it, though.

Do you prefer any other name, for casting into stone? (imo This theorem belongs in at least one major book...)

I prefer no name, actually. I don't think it's important enough to have the status of "theorem" (which is why I've been calling it a "proposition"), but I'm willing to be convinced otherwise.

cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. - MathOverflow [closed]

cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.

Answer by Darsh Ranjan for cardinal equivalence: for each boolean formula, |quantifications| = |assignments|.