# Logic for Explainable AI

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 60 references that are in the map.
- First posted on arXiv 9 May 2023.

## Builds on (most cited first, 30 of 38)

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Counterfactual Visual Explanations](https://mlsanity.com/paper/1904.07451/) (2019)
- [Counterfactual Explanations and Algorithmic Recourses for Machine Learning: A Review](https://mlsanity.com/paper/2010.10596/) (2020)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [Explaining Explanations in AI](https://mlsanity.com/paper/1811.01439/) (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)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [Quantitative Verification of Neural Networks And its Security Applications](https://mlsanity.com/paper/1906.10395/) (2019)
- [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [Contrastive Explanations with Local Foil Trees](https://mlsanity.com/paper/1806.07470/) (2018)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [Efficient Exact Verification of Binarized Neural Networks](https://mlsanity.com/paper/2005.03597/) (2020)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [Scalable Verification of Quantized Neural Networks (Technical Report)](https://mlsanity.com/paper/2012.08185/) (2020)
- [On the Computation of Necessary and Sufficient Explanations](https://mlsanity.com/paper/2203.10451/) (2022)
- [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022)
- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)
- [BDD4BNN: A BDD-based Quantitative Analysis Framework for Binarized Neural Networks](https://mlsanity.com/paper/2103.07224/) (2021)
- [On Quantifying Literals in Boolean Logic and Its Applications to Explainable AI](https://mlsanity.com/paper/2108.09876/) (2021)

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

- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [Most General Explanations of Tree Ensembles (Extended Version)](https://mlsanity.com/paper/2505.10991/) (2025)
- [On the Complexity of Global Necessary Reasons to Explain Classification](https://mlsanity.com/paper/2501.06766/) (2025)
- [Why this and not that? A Logic-based Framework for Contrastive Explanations](https://mlsanity.com/paper/2507.08454/) (2025)
- [When is the Computation of a Feature Attribution Method Tractable?](https://mlsanity.com/paper/2501.02356/) (2025)
- [Circuit Representations of Random Forests with Applications to XAI](https://mlsanity.com/paper/2602.08362/) (2026)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [The Pros and Cons of Adversarial Robustness](https://mlsanity.com/paper/2312.10911/) (2023)
- [Explanations are a Means to an End: Decision Theoretic Explanation Evaluation](https://mlsanity.com/paper/2506.22740/) (2025)
- [Database Views as Explanations for Relational Deep Learning](https://mlsanity.com/paper/2509.09482/) (2025)
- [Uncovering Bugs in Formal Explainers: A Case Study with PyXAI](https://mlsanity.com/paper/2511.03169/) (2025)
- [Sufficient Explanations in Databases and their Connections to Database Repairs](https://mlsanity.com/paper/2511.15623/) (2025)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)
- [On Trustworthy Rule-Based Models and Explanations](https://mlsanity.com/paper/2507.07576/) (2025)
- [Rigorous Feature Importance Scores based on Shapley Value and Banzhaf Index](https://mlsanity.com/paper/2508.11959/) (2025)
- [Efficient & Correct Predictive Equivalence for Decision Trees](https://mlsanity.com/paper/2509.17774/) (2025)
- [A Formal Framework for the Explanation of Finite Automata Decisions](https://mlsanity.com/paper/2602.13351/) (2026)
- [Scaling the Explanation of Multi-Class Bayesian Network Classifiers](https://mlsanity.com/paper/2603.14594/) (2026)
- [Towards Rigorous Explainability by Feature Attribution](https://mlsanity.com/paper/2604.15898/) (2026)
- [Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations](https://mlsanity.com/paper/2605.08688/) (2026)
- [Dsat: A Native SAT Solver for Discrete Logic](https://mlsanity.com/paper/2605.09347/) (2026)
- [Enhancing Query Efficiency for d-DNNF Representations Through Preprocessing](https://mlsanity.com/paper/2607.11492/) (2026)

## Abstract (arXiv)

A central quest in explainable AI relates to understanding the decisions made by (learned) classifiers. There are three dimensions of this understanding that have been receiving significant attention in recent years. The first dimension relates to characterizing conditions on instances that are necessary and sufficient for decisions, therefore providing abstractions of instances that can be viewed as the "reasons behind decisions." The next dimension relates to characterizing minimal conditions that are sufficient for a decision, therefore identifying maximal aspects of the instance that are irrelevant to the decision. The last dimension relates to characterizing minimal conditions that are necessary for a decision, therefore identifying minimal perturbations to the instance that yield alternate decisions. We discuss in this tutorial a comprehensive, semantical and computational theory of explainability along these dimensions which is based on some recent developments in symbolic logic. The tutorial will also discuss how this theory is particularly applicable to non-symbolic classifiers such as those based on Bayesian networks, decision trees, random forests and some types of neural networks.