Quantified Boolean Formulas
QBF (Quantified Boolean Formulas)
Vocabulary Propositional variables: Σ = {p, q, r, …}
Boolean connectives: ∨, ∧, ¬, →, Quantifiers: ∃, ∀
QBF (Quantified Boolean Formulas)
Vocabulary Propositional variables: Σ = {p, q, r, …}
Boolean connectives: ∨, ∧, ¬, →, Quantifiers: ∃, ∀
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p φ | ∀p φ | …
QBF (Quantified Boolean Formulas)
Vocabulary Propositional variables: Σ = {p, q, r, …}
Boolean connectives: ∨, ∧, ¬, →, Quantifiers: ∃, ∀
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p φ | ∀p φ | …
Semantics Requires a model M : FreeVar(φ) → {true, false}
Describes when φ holds on M (M ⊨ φ)
QBF (Quantified Boolean Formulas)
Vocabulary Propositional variables: Σ = {p, q, r, …}
Boolean connectives: ∨, ∧, ¬, →, Quantifiers: ∃, ∀
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p φ | ∀p φ | …
Semantics Requires a model M : FreeVar(φ) → {true, false}
Describes when φ holds on M (M ⊨ φ) iff
M ⊨ p M(p) = true
iff
M ⊨ φ1∨φ2 M ⊨ φ1 or M ⊨ φ2
…
iff
M ⊨ ∃p φ M’ ⊨ φ for some M’∈ {M[p:=true], M[p:=false]}
iff
M ⊨ ∀p φ M’ ⊨ φ for every M’∈ {M[p:=true], M[p:=false]}
Free variables and renaming
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p φ | ∀p φ | …
Free variables and renaming
Occurrence p is bound in φ if it appears under ∃p or ∀p is free in φ if it is not bound
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p φ | ∀p φ | …
Free variables and renaming
Occurrence p is bound in φ if it appears under ∃p or ∀p is free in φ if it is not bound
φ(p1,…,pk) means all free variables of φ are among p1,…,pk
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p φ | ∀p φ | …
Free variables and renaming
Occurrence p is bound in φ if it appears under ∃p or ∀p is free in φ if it is not bound
φ(p1,…,pk) means all free variables of φ are among p1,…,pk
φ[p/α] denotes the formula obtained by
replacing all free occurrences of p by α Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p φ | ∀p φ | …
Free variables and renaming
Occurrence p is bound in φ if it appears under ∃p or ∀p is free in φ if it is not bound
φ(p1,…,pk) means all free variables of φ are among p1,…,pk
φ[p/α] denotes the formula obtained by
replacing all free occurrences of p by α
Notation abuse: given φ(p) φ[q] is shorthand for φ[p/q]
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p φ | ∀p φ | …
Free variables and renaming
Occurrence p is bound in φ if it appears under ∃p or ∀p is free in φ if it is not bound
φ(p1,…,pk) means all free variables of φ are among p1,…,pk
φ[p/α] denotes the formula obtained by
replacing all free occurrences of p by α
Free variables and renaming
Occurrence p is bound in φ if it appears under ∃p or ∀p is free in φ if it is not bound
φ(p1,…,pk) means all free variables of φ are among p1,…,pk
φ[p/α] denotes the formula obtained by
replacing all free occurrences of p by α
Lemma (compositionality) Let φ, α be some QBF and p a variable Suppose that M ⊨ p iff M ⊨ α
Then M ⊨ φ iff M ⊨ φ[p/α]
provided no free variable of α occurs in φ
Free variables and renaming
Corollary (renaming) ∃p φ is equivalent to ∃q φ[p/q]
provided q does not occur in φ Occurrence p is bound in φ if it appears under ∃p or ∀p is free in φ if it is not bound
φ(p1,…,pk) means all free variables of φ are among p1,…,pk
φ[p/α] denotes the formula obtained by
replacing all free occurrences of p by α
Lemma (compositionality) Let φ, α be some QBF and p a variable Suppose that M ⊨ p iff M ⊨ α
Then M ⊨ φ iff M ⊨ φ[p/α]
provided no free variable of α occurs in φ
Economy of syntax
Lemma ∀ can be defined using ∃, ¬
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p | ∀p | …
Economy of syntax
Lemma ∀ can be defined using ∃, ¬
Syntax φ : p | … | φ ∨ φ | φ ∧ φ | ¬φ | φ → φ | φ φ ∃p | ∀p | …
is equivalent to
∀p φ ¬(∃p ¬φ)
namely:
Algorithms
Model-check(φ, M) if φ = p then
return M(p)
else if φ = φ1 ∨ φ2 then
return Model-check(φ1, M) OR Model-check(φ2, M)
else if …
…
else if φ = ∃p φ’ then
return Model-check(φ’, M[p:=true]) OR Model-check(φ’, M[p:=false])
else if φ = ∀p φ’ then
return Model-check(φ’, M[p:=true]) AND Model-check(φ’, M[p:=false])
Algorithms
Model-check(φ, M) if φ = p then
return M(p)
else if φ = φ1 ∨ φ2 then
return Model-check(φ1, M) OR Model-check(φ2, M)
else if …
…
else if φ = ∃p φ’ then
return Model-check(φ’, M[p:=true]) OR Model-check(φ’, M[p:=false])
else if φ = ∀p φ’ then
return Model-check(φ’, M[p:=true]) AND Model-check(φ’, M[p:=false])
Complexity: PSPACE-complete
Propositional satisfiability vs QBF model-checking
[∃p ∃q ∃r] φ(p,q,r)SAT QBF
∀p ∃q ∀r φ(p,q,r) p
q q
r r r r
0 0 1 1 1 1 0 1
p
q q
r r r r
0 0 1 1 1 1 0 1
Propositional satisfiability vs QBF model-checking
[∃p ∃q ∃r] φ(p,q,r)SAT QBF
∀p ∃q ∀r φ(p,q,r) p
q q
r r r r
0 0 1 1 1 1 0 1
p
q q
r r r r
0 0 1 1 1 1 0 1
Propositional satisfiability vs QBF model-checking
[∃p ∃q ∃r] φ(p,q,r)SAT QBF
∀p ∃q ∀r φ(p,q,r) p
q q
r r r r
0 0 1 1 1 1 0 1
p
q q
r r r r
0 0 1 1 1 1 0 1
Normal forms
Prenex φ : ∃p φ | ∀p φ | α
α : p | α ∨ α | α ∧ α | ¬α | ...
Normal forms
Prenex φ : ∃p φ | ∀p φ | α
α : p | α ∨ α | α ∧ α | ¬α | ...
Prenex-CNF/DNF when in addition α is in CNF/DNF
Normal forms
Prenex φ : ∃p φ | ∀p φ | α
α : p | α ∨ α | α ∧ α | ¬α | ...
Prenex-CNF/DNF when in addition α is in CNF/DNF
Lemma 1 Prenex normal form can be computed in polynomial time
Normal forms
Prenex φ : ∃p φ | ∀p φ | α
α : p | α ∨ α | α ∧ α | ¬α | ...
Prenex-CNF/DNF when in addition α is in CNF/DNF
Lemma 1 Prenex normal form can be computed in polynomial time
Lemma 2 Model-checking prenex QBFs with n quantifier alternations is in Σ = NP or ΠcoNP NP… … = coNP
Application example — compression
φreach = ∃p̅1,...,p̅n φinit[p̅1] ∧ φgoal[p̅n] ∧ Reachability in n = 2k steps:
⋀
i=2,...,n φtrans[p̅i-1,p̅i]0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
φinit(p̅) φtrans(p̅,p̅’) φgoal(p̅)
{
k bits
Application example — compression
φreach = ∃p̅1,...,p̅n φinit[p̅1] ∧ φgoal[p̅n] ∧
Size: |φ | ≈ |φ | + |φ | + can we do better?
Reachability in n = 2k steps:
⋀
i=2,...,n φtrans[p̅i-1,p̅i]k⋅2k |φ |
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
φinit(p̅) φtrans(p̅,p̅’) φgoal(p̅)
{
k bits
∀s̅,s̅’
(⋁ ⋀
i=2,...,i=2,…,nn φ s̅s̅’=p̅trans[p̅i-1i-1p̅,p̅i i)
] → φtrans[s̅,s̅’]Application example — compression
φreach = ∃p̅1,...,p̅n φinit[p̅1] ∧ φgoal[p̅n] ∧
Size: |φreach| ≈ |φinit| + |φgoal| + can we do better?
Reachability in n = 2k steps:
k⋅2k ⋅ |φtrans|
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
φinit(p̅) φtrans(p̅,p̅’) φgoal(p̅)
{
k bits
∀s̅,s̅’
(⋁
i=2,…,n s̅s̅’=p̅i-1p̅i)
→ φtrans[s̅,s̅’]k⋅2k |φ |
⋀
i=2,...,n φtrans[p̅i-1,p̅i]Application example — compression
φreach = ∃p̅1,...,p̅n φinit[p̅1] ∧ φgoal[p̅n] ∧
Size: |φ | ≈ |φ | + |φ | + can we do better?
Reachability in n = 2k steps:
k⋅2k + |φtrans|
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
φinit(p̅) φtrans(p̅,p̅’) φgoal(p̅)
{
k bits
∀s̅,s̅’
(⋁
i=2,…,n s̅s̅’=p̅i-1p̅i)
→ φtrans[s̅,s̅’]k⋅2k ⋅ |φtrans|
⋀
i=2,...,n φtrans[p̅i-1,p̅i]Application example — compression
φreach = ∃p̅1,...,p̅n φinit[p̅1] ∧ φgoal[p̅n] ∧
Size: |φreach| ≈ |φinit| + |φgoal| + can we do better?
Reachability in n = 2k steps:
k⋅2k + |φtrans| φk[p̅1,p̅n]
φ1(p̅,q̅) = φtrans[p̅,q̅]
φi+1(p̅,q̅) = ∃r̅ ∀s̅,s̅’
s̅s̅’=p̅r̅ ∨ s̅s̅’=r̅q̅ → φi[s̅,s̅’]
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
φinit(p̅) φtrans(p̅,p̅’) φgoal(p̅)
{
k bits
k⋅2k + |φtrans|
∀s̅,s̅’
(⋁
i=2,…,n s̅s̅’=p̅i-1p̅i)
→ φtrans[s̅,s̅’]k⋅2k |φ |
⋀
i=2,...,n φtrans[p̅i-1,p̅i]Application example — compression
φreach = ∃p̅1,...,p̅n φinit[p̅1] ∧ φgoal[p̅n] ∧
Size: |φ | ≈ |φ | + |φ | + can we do better?
Reachability in n = 2k steps:
φk[p̅1,p̅n] φ1(p̅,q̅) = φtrans[p̅,q̅]
φi+1(p̅,q̅) = ∃r̅ ∀s̅,s̅’
s̅s̅’=p̅r̅ ∨ s̅s̅’=r̅q̅ → φi[s̅,s̅’] k2 + |φtrans|
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
φinit(p̅) φtrans(p̅,p̅’) φgoal(p̅)
{
k bits
Things to remember
Things to remember
• QBF logic is still simple
• QBF model-checking generalises satisfiability & validity of prop. formulas (complexity is slightly higher and depends on quantifier alternation)
• There is a trick to succinctly describe a reachability property
