With the rise of neural network approaches for machine learning problems, the focus has shifted to learning deep concepts across multiple layers. Although single-hidden-layer networks are sufficient to arbitrarily approximate any function, multilayer networks have proven to be superior in predictive performance for many applications. Unlike for neural networks, in symbolic machine learning approaches like decision tree or rule learning algorithms, the benefits of hidden layers of learned intermediate concepts remain uncertain. In this work, we empirically investigate the potential gains of deep concepts for symbolic approaches from three perspectives. First, we compare the number of possible flat and deep Boolean expressions with limited complexity, underlining the higher expressive power of deep models in such a setting. Second, we use logic minimization algorithms to generate minimal flat and deep Boolean formulas for artificial Boolean classification problems with different numbers of attributes and training examples, showing under which circumstances the use of deep concepts can lead to noticeably less complex models. Third, we compare the predictive performance of flat and deep models with a fixed maximum complexity on these datasets. We interpret these results as evidence that encourages further investigation of algorithms for learning complexity-bounded deep rule sets.