A binary complete decision table with many-valued decisions is a table with n columns (attributes) and \(2^{n}\) pairwise distinct rows filled with numbers from the set \(\{0,1\}\) . Each row of this table is labeled with a nonempty finite set of decisions. For a given row of the table, the task is to find a decision from the set of decisions attached to the row. Such tables are generalizations of Boolean functions. They can also be viewed as representations of various problems related to systems of decision rules. In this chapter, we consider three types of classes of binary complete decision tables with many-valued decisions, closed with respect to removal of columns and changing of decisions. For tables from these classes, we study the relationships between the minimum weighted depth of deterministic, nondeterministic, and (for one type of classes) strongly nondeterministic decision trees and the total weight of attributes attached to columns. The obtained results can be used for the analysis of decision trees derived from decision rule systems.