We consider a set of binary random variables and address the open problems of inferring provable logical relations among these random variables, and prediction. We propose to solve these two problems by learning a Kolmogorov model (KM) for these random variables. Our proposed framework allows us to derive provable logical relations, i.e., mathematical relations among the outcomes of the random variables in the training set, and thus, extract valuable relations from that set. The proposed method to discover the logical relations is established using implication in mathematical logic, thereby offering a provable analytical basis for asserting these relations, unlike similar factorization methods. We also propose an efficient algorithm for learning the KM model and show its first-order optimality, despite the combinatorial nature of the learning problem. We illustrate our general framework by applying to recommendation systems and gene expression data. In recommendation systems, the proposed logical relations identify groups of items for which a user liking an item logically implies that he/she likes all items in that group. Our work is a significant step toward interpretable machine learning.