The design of efficient computer systems depends heavily on the ability to reduce the complexity of the underlying hardware. This is particularly important in the context of approximate computing, where Boolean circuits can be designed to produce approximate results with reduced hardware complexity, leading to smaller circuits with improved performance. One approach to achieving this is through the use of learning algorithms to automatically synthesize Boolean circuits from input-output examples. By integrating concepts from information theory and measure theory, it is possible to develop algorithms for learning Boolean circuits that are not only more accurate but also more efficient. This significance is amplified when immersed in the process of learning from examples, wherein the primary objective is to discern patterns and relationships within the data, laying the foundation for informed predictions or decisions. The work presented in this thesis aims to explore the application of mathematical quantifiers of information and uncertainty in datasets to improve the learning of corresponding Boolean circuits. In the first approach, mutual information is used to iteratively identify single output Boolean variables that optimize output information and reduce circuit area. The second approach focuses on simplifying Boolean circuits by removing logical gates using mutual information. This results in a significant reduction of 31% in area and 30% in delay for a 4% error rate, leading to more efficient circuits. In the third approach, the Wasserstein measure is used to learn Boolean circuits that leverage word-level information. These circuits can compete with machine learning techniques for MNIST classification while using 70 times less area. Moreover, for image processing filters, the learned Boolean circuit is 52% smaller than the exact model, while maintaining good accuracy.