Towards a Unification of Logic and Information Theory
share
We examine the problem of efficient transmission of logical statements from a sender to a receiver under a diverse set of initial conditions for the sender and receiver's beliefs and on the goal for the communication. From the standpoint of our work, two different collections of logical statements are equivalent if there anything that can be proved from one collection can also be deduced from the other collection. Distinguishing between these two collections is thus unnecessary from the standpoint of our work and leads to communication cost efficiencies. In order to develop an example of an information theory for the transmission of logical statements, we focus on a simple logical system equivalent to propositional logic where a collection of logical statements can be alternately depicted as a collection of multivariate polynomial equations with coefficients and variables in a finite field. We then apply classical concepts from information theory, notably concepts for rate-distortion theory, to develop closed form expressions for the cost of communicating these logical statements. We additionally provide a theory of linear codes for implementing these communication systems that produces systems that are asymptotically bit-cost optimal in some settings. It is our belief that the scope for improving beyond our limited exploration is vast, including treating more sophisticated logical systems such as first order logic, studying different types of communication constraints and creating practical algorithms for attaining the Shannon limits.
READ FULL TEXT