PSPACE — Quantified Boolean Formula: Worked examples

Everything here uses only three moves from the parent:

$\exists x ψ^{'}$ is TRUE $⟺ ψ^{'} [x = 0] OR ψ^{'} [x = 1]$ is TRUE.
$\forall x ψ^{'}$ is TRUE $⟺ ψ^{'} [x = 0] AND ψ^{'} [x = 1]$ is TRUE.
No quantifiers left $\Rightarrow$ plug in the fixed bits and compute.

Here $x = 1$ means "true", $x = 0$ means "false". $\lor$ is OR, $\land$ is AND, $\neg$ is NOT, $\leftrightarrow$ is "equal" (both same), $\Rightarrow$ is "if… then…".

The scenario matrix

Every QBF differs along a handful of axes. This table names each cell — every worked example below is tagged with the cell(s) it covers.

Cell	What varies	Why it's a distinct case	Covered by
A	Pure $\exists \dots \exists$	This is just SAT — one player	Ex 1
B	Pure $\forall \dots \forall$	One failing branch kills it	Ex 2
C	$\exists$ then $\forall$	$\exists$ commits before seeing $\forall$ 's reply	Ex 3
D	$\forall$ then $\exists$	$\exists$ answers after seeing $\forall$ 's move (dependence!)	Ex 4
E	Order swap $\exists\forall$ vs $\forall\exists$	Same body, different truth value	Ex 5
F	A false QBF (early $\forall$ -failure)	Short-circuit / spoiler wins	Ex 6
G	Degenerate: variable absent from body	Quantifier over an unused variable	Ex 7
H	Real-world word problem (a game)	Reading a game as a QBF	Ex 8
I	Exam twist: nested 3-alternation	Depth-3 game tree, prune early	Ex 9

We solve them so that every cell is hit at least once.

$\forall x \exists y (x \leftrightarrow y)$ vs $\exists y \forall x (x \leftrightarrow y)$ Forecast: Ex 4 showed the first is TRUE. In the swapped one, $\exists$ must fix one $y$ before seeing $x$ . Guess: FALSE?

First formula $\forall x \exists y$ : TRUE (proved in Ex 4 — $y$ trails $x$ ). Why this step? Establish the reference value.
Swapped $\exists y \forall x (x \leftrightarrow y)$ : $\exists$ commits $y$ first. Try $y = 0$ : need $\forall x (x \leftrightarrow 0)$ ; at $x = 1$ : $1 \leftrightarrow 0 = 0$ . Fails. Why this step? $\forall x$ = AND; the mismatched $x$ breaks it.
Try $y = 1$ : need $\forall x (x \leftrightarrow 1)$ ; at $x = 0$ : $0 \leftrightarrow 1 = 0$ . Fails. Why this step? The other fixed $y$ is broken by the other $x$ .
Both fixed choices of $y$ fail $\Rightarrow$ swapped formula FALSE.

Verify: $TRUE \neq = FALSE$ : swapping $\exists\forall$ genuinely changed the answer. This is the concrete witness for the parent's "order matters" mistake and mirrors $\forall y \exists x (x > y)$ true / $\exists x \forall y (x > y)$ false. ✔ See Two-Player Games and Game Trees.

Ex 6 — Cell F: a FALSE QBF via early $\forall$ -failure

Ex 7 — Cell G: degenerate — a quantifier over an unused variable

Ex 8 — Cell H: real-world word problem (a tiny game)

Worked example The 2-move coin game

Two players share a light bulb. Alice ( $\exists$ , wants bulb ON) flips switch $a$ ; then Bob ( $\forall$ , wants it OFF) flips switch $b$ . The bulb is ON exactly when the switches disagree ( $a \neq = b$ ). Does Alice have a winning strategy?

Forecast: Alice moves first; Bob then flips to match her, forcing agreement. Guess: FALSE?

Model it: bulb-ON $= (a \neq = b) = \neg (a \leftrightarrow b)$ . The question is the QBF $\exists a \forall b \neg (a \leftrightarrow b)$ . Why this step? " $\exists$ has a strategy" = the QBF with Alice's move first is TRUE (parent's game interpretation).
Alice tries $a = 0$ : Bob plays $\forall b \neg (0 \leftrightarrow b)$ . At $b = 0$ : $\neg (0 \leftrightarrow 0) = \neg1 = 0$ . Bob wins by copying. Why this step? $\forall b$ = AND; Bob's matching move $b = a$ turns the bulb off.
Alice tries $a = 1$ : Bob plays $b = 1$ : $\neg (1 \leftrightarrow 1) = 0$ . Bob wins again. Why this step? Every first move of Alice has a Bob-reply, because Bob moves second (dependence favours Bob here — mirror of Ex 4).
No $a$ works $\Rightarrow$ QBF FALSE $\Rightarrow$ Alice has no winning strategy; Bob does.

Verify: Bob's strategy $b = a$ always forces $a \neq = b$ false, i.e. bulb OFF. Since the second-mover can react, the "disagree" goal is unwinnable for the first mover. FALSE. ✔

Ex 9 — Cell I: exam twist — depth-3 alternation

Worked example

$\exists x \forall y \exists z [(x \lor y) \land (y \lor z)]$ Forecast: A 3-move game. $\exists$ picks $x$ , $\forall$ picks $y$ , then $\exists$ patches with $z$ . If $\exists$ opens $x = 1$ , the first clause is satisfied no matter what; $z$ then only has to fix the second clause. Guess: TRUE?

Outer $\exists x$ : try $x = 1$ . Body becomes $(1 \lor y) \land (y \lor z) = (y \lor z)$ . Why this step? $\exists$ plays the value that simplifies the hardest clause away; $1 \lor y = 1$ .
$\forall y$ : must hold for both $y$ values, so check $y = 0$ and $y = 1$ . Why this step? $\forall y$ = AND over $y$ ; both sub-games must be won by the inner $\exists z$ .
Branch $y = 1$ : inner $\exists z (1 \lor z)$ — pick any $z$ , say $z = 0$ : $1 \lor 0 = 1$ . Won. Why this step? $\exists z$ needs one good $z$ ; $1 \lor z$ is already true.
Branch $y = 0$ : inner $\exists z (0 \lor z)$ — pick $z = 1$ : $0 \lor 1 = 1$ . Won. Here $z$ depends on $y$ . Why this step? $z$ is chosen after $y$ , so it can react to $y = 0$ by supplying the missing $1$ .
Both $\forall y$ -branches won $\Rightarrow$ the $x = 1$ line succeeds $\Rightarrow$ whole formula TRUE.

Verify: $\exists$ -strategy: $x = 1$ , and $z = \neg y$ (or $z = 1$ always). Then $(x \lor y) = 1$ and $(y \lor z) \geq (y \lor \neg y) = 1$ . Wins for both $y$ . TRUE. ✔ This is the full game-tree evaluated by the parent's recursion.

Which cell did each example fill?

Recall Map back to the matrix

A → Ex 1 (pure $\exists$ = SAT) — SAT and NP-completeness
B → Ex 2 (pure $\forall$ )
C → Ex 3 ( $\exists\forall$ , $\exists$ commits first)
D → Ex 4 ( $\forall\exists$ , dependence)
E → Ex 5 (order swap flips truth)
F → Ex 6 (false via early $\forall$ -fail)
G → Ex 7 (vacuous quantifier)
H → Ex 8 (word-problem game)
I → Ex 9 (depth-3, prune with $x = 1$ )

Self-check

Which quantifier short-circuits on the first TRUE branch?

\exists

(it is an OR).

Which quantifier short-circuits on the first FALSE branch?

\forall

(it is an AND).

\forall y \exists x ϕ

, may

x

depend on

y

Yes —

x

is chosen after

y

is revealed.

Why did Ex 5's swapped formula become false?

\exists

had to fix one

y

before seeing

x

, so no single

y

matched both

x

values.

What happens to

\forall y

\exists y

when

y

is absent from the body?

The quantifier is vacuous — delete it, truth is unchanged.

Related: PSPACE — Quantified Boolean Formula · NP vs PSPACE · Polynomial Hierarchy · Savitch's Theorem · PSPACE and Polynomial Space

Worked examples — PSPACE — Quantified Boolean Formula

The scenario matrix

The examples

Ex 1 — Cell A: pure $\exists$ (this is SAT)

Ex 2 — Cell B: pure $\forall$

Ex 3 — Cell C: $\exists$ then $\forall$

Ex 4 — Cell D: $\forall$ then $\exists$ (dependence!)

Ex 5 — Cell E: order matters (the swap)