# Explainability via Short Formulas: the Case of Propositional Logic with Implementation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 15 references that are in the map.
- First posted on arXiv 3 Sep 2022.

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

- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Stable-Unstable Semantics: Beyond NP with Normal Logic Programs](https://mlsanity.com/paper/1608.01835/) (2016)

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

- [Why this and not that? A Logic-based Framework for Contrastive Explanations](https://mlsanity.com/paper/2507.08454/) (2025)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [Short Boolean Formulas as Explanations in Practice](https://mlsanity.com/paper/2307.06971/) (2023)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)

## Abstract (arXiv)

We conceptualize explainability in terms of logic and formula size, giving a number of related definitions of explainability in a very general setting. Our main interest is the so-called special explanation problem which aims to explain the truth value of an input formula in an input model. The explanation is a formula of minimal size that (1) agrees with the input formula on the input model and (2) transmits the involved truth value to the input formula globally, i.e., on every model. As an important example case, we study propositional logic in this setting and show that the special explainability problem is complete for the second level of the polynomial hierarchy. We also provide an implementation of this problem in answer set programming and investigate its capacity in relation to explaining answers to the n-queens and dominating set problems.