# On Quantifying Literals in Boolean Logic and Its Applications to Explainable AI

arXiv: https://arxiv.org/abs/2108.09876 · HTML: https://mlsanity.com/paper/2108.09876/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 79 references that are in the map.
- First posted on arXiv 23 Aug 2021.

## Builds on (most cited first, 9 of 9)

- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Verifying Properties of Binarized Deep Neural Networks](https://mlsanity.com/paper/1709.06662/) (2017)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [On Symbolically Encoding the Behavior of Random Forests](https://mlsanity.com/paper/2007.01493/) (2020)
- [On the Relative Succinctness of Sentential Decision Diagrams](https://mlsanity.com/paper/1802.04544/) (2018)
- [New Limits for Knowledge Compilation and Applications to Exact Model Counting](https://mlsanity.com/paper/1506.02639/) (2015)

## Built on by (most cited first, 16 of 16)

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [On the Computation of Necessary and Sufficient Explanations](https://mlsanity.com/paper/2203.10451/) (2022)
- [Eliminating The Impossible, Whatever Remains Must Be True](https://mlsanity.com/paper/2206.09551/) (2022)
- [Feature Necessity & Relevancy in ML Classifier Explanations](https://mlsanity.com/paper/2210.15675/) (2022)
- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023)
- [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [On Formal Feature Attribution and Its Approximation](https://mlsanity.com/paper/2307.03380/) (2023)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [A New Class of Explanations for Classifiers with Non-Binary Features](https://mlsanity.com/paper/2304.14760/) (2023)
- [On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits](https://mlsanity.com/paper/2301.13328/) (2023)
- [Circuit Representations of Random Forests with Applications to XAI](https://mlsanity.com/paper/2602.08362/) (2026)
- [On Logic-Based Explainability with Partially Specified Inputs](https://mlsanity.com/paper/2306.15803/) (2023)
- [Scaling the Explanation of Multi-Class Bayesian Network Classifiers](https://mlsanity.com/paper/2603.14594/) (2026)
- [Explaining Reinforcement Learning Agents via Inductive Logic Programming](https://mlsanity.com/paper/2607.13655/) (2026)

## Abstract (arXiv)

Quantified Boolean logic results from adding operators to Boolean logic for existentially and universally quantifying variables. This extends the reach of Boolean logic by enabling a variety of applications that have been explored over the decades. The existential quantification of literals (variable states) and its applications have also been studied in the literature. In this paper, we complement this by studying universal literal quantification and its applications, particularly to explainable AI. We also provide a novel semantics for quantification, discuss the interplay between variable/literal and existential/universal quantification. We further identify some classes of Boolean formulas and circuits on which quantification can be done efficiently. Literal quantification is more fine-grained than variable quantification as the latter can be defined in terms of the former. This leads to a refinement of quantified Boolean logic with literal quantification as its primitive.