A Quantified Boolean Formula
A quantified Boolean formula (QBF) is an extension of propositional logic that allows for quantification over boolean variables using the `universal (∀)` and `existential (∃)` quantifiers. Unlike regular Boolean formulas, which only consist of logical connectives like `AND (∧)`, `OR (∨)`, `NOT (¬)`, and parentheses, QBFs can also include these quantifiers at the beginning of the formula to specify whether all or some values of a particular variable must satisfy certain conditions.
Areas of application
- Computer Science
- Artificial Intelligence
- Formal Verification
- Logic Programming
- Mathematics
Example
For example, consider the following QBF: `∀x (H(x) ∧ ∃y (G(y) ∨ K(y))`. This formula asserts that every value of the variable `x` must be either happy (`H(x)`) or some value of the variable `y` must be either glad (`G(y)`) or knowledgeable (`K(y))`.