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.