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))`.