Second-Order Quantified Boolean Logic

Jie-Hong R. JiangAAAI 2023 · DOI

Introduction

Computational logic often follows a hierarchy of complexity. While standard Boolean Satisfiability (SAT) is NP-complete and Quantified Boolean Formulas (QBF) are PSPACE-complete, certain high-level problems in hardware verification and multi-agent planning demand even greater expressive power. This research establishes a formal logical framework for Second-Order Quantified Boolean Formulas (SOQBFs), a logic that allows quantification over functions rather than just individual variables, corresponding to the Exponential-Time Hierarchy (EXPH).

The SOQBF Formalism

SOQBFs offer a significant advantage in succinctness. Problems that would require an exponentially large QBF can often be encoded as a compact SOQBF. While a theoretical bridge exists via quantifier elimination—which converts SOQBFs to standard QBFs—this process typically results in an exponential blowup in formula size. Until now, the field lacked the practical "machinery" available for simpler logics—specifically, formal proof systems and methods to extract strategies (models) when a formula is found to be true or false.

Methodology: The SOQ-res Proof System

The core contribution of this work is the SOQ-res system, a sound and complete refutation-proof system based on resolution. To manage the inherent complexity of second-order logic, the system employs a lazy instantiation strategy. Rather than "grounding" every possible function input—which would lead to immediate memory exhaustion—the system treats function variables as "bundles" of potential values, instantiating them only as needed during resolution.

Representation of a function strategy using a tree-based decision structure.

The system introduces two primary rules:

  1. $\exists_F$-Resolve: Combines clauses by unifying partially instantiated function variables.
  2. $\forall_F$-Reduce: Simplifies clauses by removing universal function variables under specific conditions.

Countermodel Extraction

When a formula is proven false, the SOQ-res system allows for the extraction of "countermodels"—winning strategies for the universal ("forall") player. The paper provides an algorithm that traverses the proof's Directed Acyclic Graph (DAG) to construct Decision Lists. These lists represent the Herbrand functionals, providing a concrete blueprint for how a defender can defeat any attempt to satisfy the formula.

Applications in Synthesis and Planning

The paper demonstrates the utility of SOQBF in modeling complex systems. For instance, System Synthesis involves designing components that function correctly regardless of environmental behavior. This can be naturally formulated as an SOQBF where the component's behavior is a quantified function.

Conceptual model of a system with quantified function variables.

Theoretical Foundations and Results

As a theoretical work, this research focuses on mathematical proofs of soundness and completeness rather than empirical benchmarks. The author demonstrates that the SOQ-res system will never produce a false proof and will always be able to prove a false formula is indeed false. Furthermore, the paper reinforces that SOQBF is $\Sigma^{EXP}_k$-complete, providing a clear hierarchy for categorizing computational problems.

Conclusion and Future Directions

This research establishes the theoretical foundation for SOQBF solvers. While the mathematical framework of soundness, completeness, and strategy extraction is now in place, the development of practical, high-performance "SOQBF-SAT" solvers remains the next major challenge. Future work will also explore "killer apps" for this logic, such as checking memory consistency models in modern processor architectures.

Summary updated

BibTeX
@inproceedings{jiang2023second,
  author = {Jie-Hong R. Jiang},
  title = {{Second-Order Quantified Boolean Logic}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25515},
}
Figure