-2
$\begingroup$
 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.

$\endgroup$
2
  • 7
    $\begingroup$ Welcome to MO. However, your question is not clear. For example, the theorem you mentioned is not clear. In particular, I'm not sure what you mean by a "quantification" of a Boolean formula. Perhaps you could edit your question for clarity? But am I right to understand that your main question is: What name shall we all use to refer to your (unknown from google)'s theorem? If so, I think that this may not really be an appropriate MO question. (see the FAQ) $\endgroup$ Jan 21, 2010 at 19:22
  • $\begingroup$ I'm pleased to meet you now, Daniel. But I'm still not clear on what you mean by "quantification", unless you mean what Darsh says below. $\endgroup$ Jan 22, 2010 at 13:58

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This interpretation seems to miss some expressions that we would probably want to include as a "quantification". For example, we don't seem to get (forall x2)(exists x1)[f(x1,x2)=1] this way, since the variables are quantified in the wrong order. $\endgroup$ Jan 22, 2010 at 13:34
  • $\begingroup$ Good point, Joel. My interpretation is that once you pick an ordering of the variables, the number of true quantified formulas equals the number of satisfying assignments of the function. It may be that Daniel Pehoushek had something else in mind, but it's impossible to tell. $\endgroup$ Jan 22, 2010 at 18:50
  • $\begingroup$ thank you darsh. I editted the original; question Two: Linear Corollary: Quantified monotone boolean formulas are linearly decidable. (hunting for any previous name) On importance: Equivalence between complexity classes, where few equivalences are known, is important. After good names are given, identitys become easier to apply. Variable order area is where future research lays. The Cardinal Equivalenece provides that the number of valid quantifications remains invariant after shuffling variables; but details about valid quantifications after any swap are a mystery. $\endgroup$ Jan 25, 2010 at 15:13
  • $\begingroup$ Aside about answering qbfs: any boolean formula P, given an order, has a related monotone formula Q, for correctly answering all 2^n quantifications of P. The size of Q is only well understood for 2cnfs and formulas that are already monotone. For 2cnf Ps, the size is identical to the size of (P + all resolutions). When P is already monotone, that Is the Q formula. I have not yet looked at variable swapping, for either 2qbfs, or for monotone formulas. Those two solvable cases would be a good place to begin to study variable swaps. $\endgroup$ Jan 25, 2010 at 15:36

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