<p>In the context of machine learning, classification is the procedure of predicting the class to which each element of a population belongs to. Most classification functions, for real world problems, are imperfect and thus require rigorous analysis for use in safety-critical applications such as health care. This paper proposes a software architecture for improving the trustworthiness and explainability of AI-based classifiers. The architecture combines a search-based approach with machine-learned explanations and satisfiability solving, to provide an indication of classification confidence and counterfactual explanation rules that are deductively verified to be consistent with the classifier. An implementation of the proposed architecture is evaluated on a medical case study of prognosis of Acute Coronary Syndrome (ACS). The evaluation shows that the proposed architecture is consistently able to complement each individual classification with an indication of confidence and an explanation, which is formally verified for consistency with the classifier. This contributes to foster trustworthy and explainable classification.</p>