Orientador: Walter Alexandre Carnielli

Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciências Humanas

Resumo: O presente trabalho tem por objetivo explorar, em diversas vertentes, o caráter universal de uma ferramenta poderosa de prova, apta a ser utilizada em lógicas clássicas e não clássicas, em particular em lógicas multivaloradas proposicionais (determinísticas e não-determinísticas), em lógicas...

Resumo: O presente trabalho tem por objetivo explorar, em diversas vertentes, o caráter universal de uma ferramenta poderosa de prova, apta a ser utilizada em lógicas clássicas e não clássicas, em particular em lógicas multivaloradas proposicionais (determinísticas e não-determinísticas), em lógicas paraconsistentes, em lógicas modais e na Lógica de Primeira Ordem. Trata-se do Método de Prova de Anéis de Polinômios, que também pode, em princípio, ser visto do ponto de vista da semântica algébrica, desenvolvido inicialmente em (Carnielli 2005b). O método traduz fórmulas de uma lógica específica em polinômios (em geral finitos, mas podendo ser infinitos) com coeficientes em corpos finitos, e transforma o problema de se encontrar demonstrações no correlato algébrico da busca de soluções de sistemas de equações polinomiais. Esta universalidade do método possibilita a abertura de diversas linhas de pesquisa, sendo a questão da verofuncionalidade e suas generalizações uma delas. Outras linhas de pesquisa são: possibilidades de se investigar enfoques alternativos da complexidade computacional, prova automática de teoremas, métodos heurísticos em lógica e correlações entre álgebra e lógica. Este trabalho analisa e compara sistemas de anéis de polinômios para sistemas com verofuncionalidade generalizada, como no caso das semânticas não-determinísticas, e ainda em sistemas onde a verofuncionalidade é perdida, tais como em sistemas multivalorados reduzidos a bivalorados através da conhecida redução de Suszko. O método de anéis de polinômios, além de poderoso e elegante em sua aparente simplicidade, constitui ainda um ótimo instrumento pedagógico. Em relação á lógica clássica, definimos um anel de polinômios para a Lógica de Primeira Ordem, fundamentado em um novo domínio que opera com somas e produtos infinitos, o qual se denomina domínio de séries generalizadas fechado por produtos. Finalmente, procuramos avaliar todas as potencialidades do método, principalmente no aspecto inerente á questão de se poder pensar em uma característica unificadora na medida que utiliza o mesmo viés matemático para traduzir diferentes sistemas lógicos em variedades algébricas similares. Além disso, analisamos as interrelações do método com respeito a lógica algébrica (ou álgebra da lógica), e avaliamos suas perspectivas

Abstract: This investigation aims to explore, in various aspects, the universal character of a powerful proof method, able to be used in classical and non-classical logics, in particular in propositional many-valued logics (deterministic and non- deterministic) in paraconsistent logics, in modal...

Abstract: This investigation aims to explore, in various aspects, the universal character of a powerful proof method, able to be used in classical and non-classical logics, in particular in propositional many-valued logics (deterministic and non- deterministic) in paraconsistent logics, in modal logics and in First Order Logic. This is the Method of Polynomial Rings, which can also be considered as an algebraic semantics, initially developed in (Carnielli 2005b). The method translates logical formulas into specific polynomials (usually finite, but sometimes infinite) with coefficients infinite fields, and transforms the problem of finding proofs in the search for solutions of systems of polynomial equations. This universality of the method enables the opening of several research lines, in particular the issue of truth-functionality and its generalizations. Other lines of research are: the possibilities of investigating alternative approaches of computational complexity, automatic theorem proving, heuristic methods in logic and correlations between algebra and logic. This study compares and analyzes the polynomial ring systems for systems with generalized truth-functionality, as in the case of non- deterministic semantic and even in systems where truth-functionality is lost, such as those many-valued systems reduced to bivalued by means of the so-called Suszko reduction. The method of polynomial rings, besides being a powerful and elegant apparatus in its apparent simplicity, is still a great teaching tool. Regarding classical logic, we define the polynomial ring for First Order Logic , based on a new domain that operates on sums and infinite products, called domain of generalized series closed under products. Finally, we evaluate the full potential of the method, especially in what concerns the question of obtaining a unifying feature that uses the same mathematical basis to translate different logical systems on similar algebraic varieties. Furthermore, we address the connections of the method with respect to algebraic logic (algebra of logic), and evaluate their perspectives