In this paper we propose the use of Information Theory as the basis of the fitness function for Boolean circuit design using Genetic Programming. Boolean functions are implemented by only replicating binary multiplexers. Entropy base d measures, such as Mutual Informa- tion and Normalized Mutual Information are investigated as tools for similarity measures between circuits. Three fitness functions are built over a primitive one. We show that the landscape of Normalized Mutual Information is more amenable for fitness functions than simple Mutual Information. A comparison of synthesized (through evolution) and min- imized circuits through other methods denotes the advantages of the Information-Theoretical approach.