Boolean and multiple-valued functions that include very many don't cares are becoming increasingly important in several areas of applications [14]. In this paper we introduce a new representation and decomposition method for such functions. The paper is organized as follows. In section 2 we introduce a new representation of Boolean and Multi-valued Functions - Cube Diagram Bundles (CDBs). This general-purpose representation combines Cube Calculus [7], Decision Diagrams [3] and Rough Partitions [10], and is especially efficient for very strongly unspecified functions. CDBs incorporate also a new concept of generalized don't cares for multiple-valued logic. This representation is next used to solve various decomposition problems that are important for Machine Learning and circuit design applications. Sections 3 to 6 introduce several types of decompositions based on patterns found in this representation. In section 3 general decomposition patterns with respect to EXOR, OR and AND gates are presented. Section 4 presents the Immediate Decompositions that happen rarely but are of a good quality: Strong Gate Decompositions, and the Ashenhurst Decomposition. A new approach to Ashenhurst Decomposition [1] is also presented - it is shown that contrary to the more general case of Curtis Decomposition [6], the column minimization problem is polynomially complete, and we give an efficient algorithm to solve it. Section 5 presents a new approach to Curtis Decomposition, which belongs to the Basic Decompositions of the system. Although in some respects similar to the approach from [16], we use the new representation, and several of its partial problems are significantly improved. For instance, a new very efficient algorithm for coloring of the Column Incompatibility Graph is proposed that utilizes the similarity of the graph coloring and the set covering problems, and thus gives an exact minimal coloring for any graph that corresponds to a non-cyclic set covering problem. Section 6 introduces another new concept in logic synthesis: goal-oriented reduction schemes, which generalize the EXOR transformation of Curtis-nondecomposable functions from [16]. Any function can serve as a goal function, and three reduction types (EXOR, OR and AND) of reducing to a goal function are presented. Section 7 presents the combined search strategy that uses all the decompositions, and section 8 presents numerical results and conclusions.