In the paper, finite two-valued check systems (information systems) are studied which are widely used in different applications related to pattern recognition, fault diagnosis, and discrete optimization. For an arbitrary finite two-valued check system which does not contains constant checks (attributes) we study the behavior of global Shannon function – unimprovable upper bound on minimum depth of decision trees which solve problems over given check system depending on the number of checks in problem description. The global approach to the study of decision trees is considered which allows us to use in decision trees arbitrary checks from the given system.

two-valued check systems, decision trees, Shannon functions

Mathematical problems and theory of numerical methods