Various perspectives of research emerge from this paper. Notably, in the present study, we have focused on representation languages which are complete for propositional logic.
In other words, such representation languages are expressive enough to cover the concept class \(\mathcal {F}_n\)  of all Boolean functions over \(n\)  variables.
From the viewpoint of computational learning theory, this means that the VC dimension [1]} of all families of Boolean classifiers considered in this paper is equal to \(2^n\) .
This in turn implies that these families are not efficiently PAC learnable [2]} because their sample complexity is exponential in \(n\) .
In fact, it is well-known that the minimal size of any Boolean multilayer neural network representing all \(n\) -dimensional Boolean functions must be exponential in \(n\)  [3]}.
So, in order to analyze the interpretability of common Boolean classifiers that can be trained using a reasonable amount of data samples, we need to
focus on representation languages for which the VC dimension of the corresponding concept class is polynomial in \(n\) .
As a prototypical example, for the class of decision lists defined over monomials of size at most \(r\) , the VC dimension is polynomial in \(n\)  when \(r\)  is constant; in fact, \(r\) -decision lists are efficiently PAC learnable [4]}.
Of course, not all representation classes with polynomial VC dimension admit a polynomial-time learning algorithm, but virtually all Boolean classifiers used in practice
are defined from concept classes with polynomial sample complexity. Thus, it is clear that the computational intelligibility of incomplete classes
is worth being studied.
