Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
 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.

share|improve this question
6  
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) –  Joel David Hamkins Jan 21 '10 at 19:22
    
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. –  Joel David Hamkins Jan 22 '10 at 13:58
add comment

closed as not a real question by Joel David Hamkins, David Speyer, Mariano Suárez-Alvarez, Qiaochu Yuan, Reid Barton Jan 22 '10 at 15:50

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

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.

share|improve this answer
    
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. –  Joel David Hamkins Jan 22 '10 at 13:34
    
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. –  Darsh Ranjan Jan 22 '10 at 18:50
    
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. –  daniel pehoushek Jan 25 '10 at 15:13
    
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. –  daniel pehoushek Jan 25 '10 at 15:36
add comment

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