<p>Motivated by the need to develop trust in the use of machine learning (ML) systems, but also of artificial intelligence (AI) systems in general there has been massive interest in explaining the predictions of ML models. Logic-based formal explanations offer a rigorous alternative to existing non-formal explainability approaches. Recent work studied the computation of formal explanations for a growing range of classifiers. However, a number of additional explainability queries are of interest and have been studied in recent years. Two concrete examples are feature necessity and relevancy. Feature necessity asks whether a feature must occur in all explanations of a given prediction (FNP). In contrast, feature relevancy asks whether a feature occurs in some explanation of a given prediction (FRP). This paper investigates both the computational complexity of these problems, but also algorithms for their solution in practice. In terms of algorithms for feature relevancy, the paper studies algorithms for specific families of classifiers, but also general-purpose algorithms, which can be applied to families of classifiers used in most systems of AI and ML. The experimental results confirm that feature relevancy can be efficiently decided in practice, for a wide range of families of classifiers.</p>