Deep connectionist models are characterized by many neurons grouped together in many successive layers. As a result, their data classifications are difficult to understand. We present two novel algorithms which explain the responses of several black-box machine learning models. The first is Fidex, which is local and thus applied to a single sample. The second, called FidexGlo, is global and uses Fidex. Both algorithms generate explanations by means of propositional rules. In our framework, the discriminative boundaries are parallel to the input variables and their location is precisely determined. Fidex is a heuristic algorithm that, at each step, establishes where the best hyperplane is that has increased fidelity the most. The algorithmic complexity of Fidex is proportional to the maximum number of steps, the number of possible hyperplanes, which is finite, and the number of samples. We first used FidexGlo with ensembles and support vector machines (SVMs) to show that its performance on three benchmark problems is competitive in terms of complexity, fidelity and accuracy. The most challenging part was then to apply it to convolutional neural networks. We achieved this with three classification problems based on images. We obtained accurate results and described the characteristics of the rules generated, as well as several examples of explanations illustrated with their corresponding images. To the best of our knowledge, this is one of the few works showing a global rule extraction technique applied to both ensembles, SVMs and deep neural networks.