Non-deterministic Semantics in Polynomial Format

AbstractThe method for automatic theorem proving proposed in [Carnielli, W. A., Polynomial ring calculus for many-valued logics, Proceedings of the 35th International Symposium on Multiple-Valued Logic, IEEE Computer Society. Calgary, Canada (2005), 20–25], called Polynomial Ring Calculus, is an algebraic proof mechanism based on handling polynomials over finite fields. Although useful in general domains, as in first-order logic, certain non-truth-functional logics and even in modal logics (see [Agudelo, J. C., Carnielli, W. A., Polynomial Ring Calculus for Modal Logics: a new semantics and proof method for modalities, The Review of Symbolic Logic. 4 (2011), 150–170, URL: doi:10.1017/S1755020310000213]), the method is particularly apt for deterministic and non-deterministic many-valued logics, as shown here. The aim of the present paper is to show how the method can be extended to any finite-valued non-deterministic semantics, and also to explore the computational character of the method through the development of a software capable of translating provability in deterministic and non-deterministic finite-valued logical systems into operations on polynomial rings