Abstract <p>The complexity of correct training of supervised classification procedures that utilize methods of logical data analysis is studied. The research focuses on the metric (quantitative) properties of informative fragments within feature descriptions of precedents particularly where the number of features significantly exceeds the number of precedents. An asymptotic estimate is provided for the typical number of frequently occurring fragments in precedent descriptions that distinguish between objects of different classes. These fragments are referred to as regular representative elementary classifiers. The typical length of such fragments is also indicated. The technical foundation of the presented estimates relies on a methodology developed for obtaining similar evaluations in the context of an intractable discrete problem—enumeration of irredundant coverings of an integer matrix—which is formulated in this work as the problem of finding minimal infrequent elementary classifiers. New results regarding the complexity of implementing logical classifiers provide a theoretical justification for the efficiency of a training procedure based on the search for regular representative elementary classifiers, and they confirm the prospects of this approach in terms of computational time.</p>