Several queries and scores have recently been proposed to explain individualpredictions over ML models. Given the need for flexible, reliable, andeasy-to-apply interpretability methods for ML models, we foresee the need fordeveloping declarative languages to naturally specify different explainabilityqueries. We do this in a principled way by rooting such a language in a logic,called FOIL, that allows for expressing many simple but importantexplainability queries, and might serve as a core for more expressiveinterpretability languages. We study the computational complexity of FOILqueries over two classes of ML models often deemed to be easily interpretable:decision trees and OBDDs. Since the number of possible inputs for an ML modelis exponential in its dimension, the tractability of the FOIL evaluationproblem is delicate but can be achieved by either restricting the structure ofthe models or the fragment of FOIL being evaluated. We also present a prototypeimplementation of FOIL wrapped in a high-level declarative language and performexperiments showing that such a language can be used in practice.