Submitted by Luiz Felipe Barbosa (luiz.fbabreu2@ufpe.br) on 2015-03-12T14:54:25Z No. of bitstreams: 2 Dissertacao Ruan Carvalho.pdf: 760651 bytes, checksum: 11973d9d0a63868703fa87f2c9daf83b (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Approved for entry into archive by Daniella Sodre (daniella.sodre@ufpe.br) on 2015-03-13T13:14:37Z (GMT) No. of bitstreams: 2 Dissertacao Ruan Carvalho.pdf: 760651 bytes, checksum: 11973d9d0a63868703fa87f2c9daf83b (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-13T13:14:37Z (GMT). No. of bitstreams: 2 Dissertacao Ruan Carvalho.pdf: 760651 bytes, checksum: 11973d9d0a63868703fa87f2c9daf83b (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2013-10-03 / Desde que proof-nets para MLL− foram introduzidas por Girard, vários estudos foram realizados na prova de corretude desse sistema. O primeiro critério foi o no shorttrip condition: Girard usou a noção de trips para definir impérios e provou que se todas as fórmulas terminais numa proof-net R forem conclusões de links ou de axiomas, então pelo menos um link terminal divide R em duas partes (a conclusão deste link é chamada de “nó split”). Outro avanço na prova de corretude de proof-nets foi obtido pela introdução de um novo tipo de subnets. Uma vez que a noção de reinos foi introduzida, Bellin & van de Wiele produziram uma elegante prova do teorema de sequentização utilizando propriedades simples das subnets e mostrando como encontrar o nó split. Todavia, estas abordagens não se aplicam integralmente aos N-Grafos, uma vez que a noção de reinos não é possível de ser empregada. Não obstante, a necessidade de identificar o nó split está no coração da prova da sequentização. Então, usamos alguns resultados obtidos para as proof-nets e apresentamos uma outra abordagem para chegar à prova da sequentização para os N-Grafos. Usando a noção de subprovas, definimos o império do norte, o do sul e o total (whole empire) de uma ocorrência de fórmula A. Com isso, além da apresentação de uma nova prova de corretude para os N-Grafos (sem o conectivo !), também é dado um método generalizado para realizar cortes precisos em provas.

CAVALCANTE, Alexandre Silva. Sistemas esquemáticos de dedução natural: um estudo prova-teórico. 2010. 201 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2010. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T19:23:49Z No. of bitstreams: 1 2010_tese_ascavalcante.pdf: 842091 bytes, checksum: 559c5a97b93d42e7b0bb2d0c9b1d1520 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T11:32:56Z (GMT) No. of bitstreams: 1 2010_tese_ascavalcante.pdf: 842091 bytes, checksum: 559c5a97b93d42e7b0bb2d0c9b1d1520 (MD5) / Made available in DSpace on 2016-07-25T11:32:56Z (GMT). No. of bitstreams: 1 2010_tese_ascavalcante.pdf: 842091 bytes, checksum: 559c5a97b93d42e7b0bb2d0c9b1d1520 (MD5) Previous issue date: 2010 / The term Theory Test was introduced by Hilbert to identify the study of formal proofs. Research in this area can be classified into: a) Proof Theory of reductive or interpretational, whose goal is to demonstrate, among other things, the consistency of mathematics using only methods finitistas, b) Structural Proof Theory, where the structural characteristics of the formal proofs are investigated by means of deductive systems as Natural Deduction and Sequent Calculus. Prawitz through Theory Proof set a Theory of Meaning for constants logics and proposed schematic introduction rules and elimination to characterize the propositional connectives. Schroeder-Heister settings Prawitz extended and formalized the use of rules as hypotheses, making possible the use of separate calculations for assumptions of calculations for logical constants. We are not interested in the investigation of schematic rules to give meaning to the logical constants. We intend to actually set schematic standardization procedures, based on such schematic rules? Attic, in order to identify sufficient conditions for a system to be normalizável. These results are relevant to the Abstract Theory of Evidence, a term used to identify the study of the conditions abstract and general to the proof-theoretical analysis of formal systems. Abstract Theory of Evidence do not study specific logical calculations, but families of calculations instances of rules schematic. Our proposal is therefore based on rules schematic rules can be instantiated for concrete, in particular, by introducing rules modal operators. We prove also theorems Normalizaçãoo Weak and Strong systems defined in schematic funçãoo schematic of our rules, we obtain sufficient conditions for a system instance is normalizável these rules, we define a procedure that normalizes deductions concrete evidence and compare our standards with evidence schematic standards for systems defined in the literature. / O termo Teoria da Prova foi introduzido por Hilbert para identificar o estudo sobre provas formais. Pesquisas nessa área podem ser classificadas em: a) Teoria da Prova Redutiva ou Interpretacional, cujo objetivo é demonstrar, entre outras coisas, a consistência da matemática utilizando somente métodos finitistas, e b) Teoria da Prova Estrutural, onde características estruturais das provas formais são investigadas por meio de sistemas dedutivos como Dedução Natural e Cálculo de Sequentes. Prawitz, por meio da Teoria da Prova, definiu uma Teoria dos Significados para constantes logicas e propôs regras esquemáticas de introdução e de eliminação para caracterizar os conectivos proposicionais. Schroeder-Heister estendeu as definições de Prawitz e formalizou o uso de regras como hipóteses, tornando possível a utilização de cálculos para suposições separados de cálculos para constantes lógicas. Não estamos interessados na investigação de regras esquemáticas para dar significado a constantes lógicas. Pretendemos, na verdade, definir procedimentos de normalização esquemáticos, baseados em tais regras esquemáticas, com objetivo de identificar condições suficientes para um sistema ser normalizável. Tais resultados são pertinentes à Teoria Abstrata da Prova, termo usado para identificar o estudo das condições abstratas e gerais para a análise prova-teórica de sistemas formais. Teoria Abstrata da Prova não estuda cálculos lógicos específicos, mas famílias de cálculos instâncias de regras esquemáticas. A nossa proposta, portanto, baseia-se em regras esquemáticas que podem ser instanciadas por regras concretas, em particular, por regras que introduzem operadores modais. Provamos, também, Teoremas de Normalização Fraca e Forte para sistemas esquemáticos definidos em função de nossas regras esquemáticas, obtemos condições suficientes para que um sistema instância destas regras seja normalizável, definimos um procedimento que normaliza deduções concretas e comparamos nossas provas de normalização esquemática com provas de normalização para sistemas definidos na literatura.

Orientador: Marcelo Esteban Coniglio / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-08-07T00:21:55Z (GMT). No. of bitstreams: 1 Sanz_WagnerdeCampos_D.pdf: 2570437 bytes, checksum: 15352759879927665653f4fc165c3703 (MD5) Previous issue date: 2006 / Resumo: O objetivo desta tese é o de propor uma elucidação da negação e do absurdo no âmbito dos sistemas de dedução natural para as lógicas intuicionista e clássica. Nossa investigação pode ser vista como um desenvolvimento de uma proposta apresentada por Russell há mais de cem anos e a qual ele parece ter abandonado posteriormente. Focaremos a atenção, em primeiro lugar, sobre a negação e, depois, como conseqüência das propostas para a negação, sobre a constante de absurdo. Nosso ponto de partida é, na verdade, um problema de natureza conceitual. Questionaremos a correção e a adequação da análise da negação e do absurdo atualmente predominante no meio-ambiente de dedução natural de estilo gentzeniano. O questionamento dessas análises adota como ponto focal o conceito de hipótese. O conceito de hipótese é uma noção central para os sistemas de dedução natural e a nossa proposta de análise desse conceito servirá de esteio para a formulação das propostas elucidatórias para a negação e o absurdo dentro dos sistemas de dedução natural / Abstract: The purpose of this thesis is to present an elucidation of negation and absurd for intuitionist and classical logics in the range of natural deduction systems. Our study could be seen as a development of a proposal presented by Russell over a hundred years ago, which he presumably abandoned later on. First, we will focus on negation and then on the absurd constant, as a consequence of the claims we are making for negation. As a matter of fact, our starting point is a problem of a conceptual nature. We will question the correctness and the adequacy of the analysis of negation and absurd, prevailing nowadays in the Gentzen-style natural deduction circle. The concept of hypothesis is the focus point in questioning these analyses. The concept of hypothesis is a central notion for natural deduction systems and the purpose of our analysis of this concept is to support the formulation of elucidative propositions for negation and absurd in natural deduction systems / Doutorado / Doutor em Filosofia

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-04-24T14:03:12Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao-mestrado.pdf: 2772669 bytes, checksum: 25b575026c012270168ca5a4c397d063 (MD5) / Made available in DSpace on 2017-04-24T14:03:12Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao-mestrado.pdf: 2772669 bytes, checksum: 25b575026c012270168ca5a4c397d063 (MD5) Previous issue date: 2015-07-29 / CNPQ / N-Graphs is a multiple conclusion natural deduction with proofs as directed graphs, motivated by the idea of proofs as geometric objects and aimed towards the study of the geometry of Natural Deduction systems. Following that line of research, this work revisits the system under a purely combinatorial perspective, determining geometrical conditions on the graphs of proofs to explain its soundness criterion and proof growth during normalization. Applying recent developments in the fields of proof graphs, proof-nets and N-Graphs itself, we propose a linear time algorithm for proof verification of the full system, a result that can be related to proof-nets solutions from Murawski (2000) and Guerrini (2011), and a normalization procedure based on the notion of sub-N-Graphs, introduced by Carvalho, in 2014. We first present a new soundness criterion for meta-edges, along with the extension of Carvalho’s sequentization proof for the full system. For this criterion we define an algorithm for proof verification that uses a DFS-like search to find invalid cycles in a proof-graph. Since the soundness criterion in proof graphs is analogous to the proof-nets procedure, the algorithm can also be extended to check proofs in the multiplicative linear logic without units (MLL−) with linear time complexity. The new normalization proposed here combines a modified version of Alves’ (2009) original beta and permutative reductions with an adaptation of Carbone’s duplication operation on sub-N-Graphs. The procedure is simpler than the original one and works as an extension of both the normalization defined by Prawitz and the combinatorial study developed by Carbone, i.e. normal proofs enjoy the separation and subformula properties and have a structure that can represent how patterns lying in normal proofs can be recovered from the graph of the original proof with cuts. / N-Grafos é uma dedução natural de múltiplas conclusões onde provas são representadas como grafos direcionados, motivado pela idéia de provas como objetos geométricos e com o objetivo de estudar a geometria de sistemas de Dedução Natural. Seguindo esta linha de pesquisa, este trabalho revisita o sistema sob uma perpectiva puramente combinatorial, determinando condições geométricas nos grafos de prova para explicar seu critério de corretude e crescimento da prova durante a normalização. Aplicando desenvolvimentos recentes nos campos de grafos de prova, proof-nets e dos próprios N-Grafos, propomos um algoritmo linear para verificação de provas para o sistema completo, um resultado que pode ser comparado com soluções para roof-nets desenvolvidas por Murawski (2000) e Guerrini (2011), e um procedimento de normalização baseado na noção de sub-N-Grafos, introduzidas por Carvalho, em 2014. Apresentamos primeiramente um novo critério de corretude para meta-arestas, juntamente com a extensão para todo o sistema da prova da sequentização desenvolvida por Carvalho. Para este critério definimos um algoritmo para verificação de provas que utiliza uma busca parecida com a DFS (Busca em Profundidade) para encontrar ciclos inválidos em um grafo de prova. Como o critério de corretude para grafos de provas é análogo ao procedimento para proof-nets, o algoritmo pode também ser estendido para validar provas em Lógica Linear multiplicativa sem units (MLL−) com complexidade de tempo linear. A nova normalização proposta aqui combina uma versão modificada das reduções beta e permutativas originais de Alves com uma adaptação da operação de duplicação proposta por Carbone para ser aplicada a sub-N-Grafos. O procedimento é mais simples do que o original e funciona como uma extensão da normalização definida por Prawitz e do estudo combinatorial desenvolvido por Carbone, i.e. provas em forma normal desfrutam das propriedades da separação e subformula e possuem uma estrutura que pode representar como padrões existentes em provas na forma normal poderiam ser recuperados a partir do grafo da prova original com cortes.

ARRUDA, Alexandre Matos. Um sistema infinitário para a lógica de menor ponto fixo. 2007. 91 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T15:28:27Z No. of bitstreams: 1 2007_dis_amarruda.pdf: 427889 bytes, checksum: b0a54f14f17ff89b515a4101e02f5b58 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T15:29:23Z (GMT) No. of bitstreams: 1 2007_dis_amarruda.pdf: 427889 bytes, checksum: b0a54f14f17ff89b515a4101e02f5b58 (MD5) / Made available in DSpace on 2016-05-20T15:29:23Z (GMT). No. of bitstreams: 1 2007_dis_amarruda.pdf: 427889 bytes, checksum: b0a54f14f17ff89b515a4101e02f5b58 (MD5) Previous issue date: 2007 / The notion of the least fixed-point of an operator is widely applied in computer science as, for instance, in the context of query languages for relational databases. Some extensions of FOL with _xed-point operators on finite structures, as the least fixed-point logic (LFP), were proposed to deal with problem problems related to the expressivity of FOL. LFP captures the complexity class PTIME over the class of _nite ordered structures. The descriptive characterization of computational classes is a central issue within _nite model theory (FMT). Trakhtenbrot's theorem, considered the starting point of FMT, states that validity over finite models is not recursively enumerable, that is, completeness fails over finite models. This result is based on an underlying assumption that any deductive system is of finite nature. However, we can relax such assumption as done in the scope of proof theory for arithmetic. Proof theory has roots in the Hilbert's programme. Proof theoretical consequences are, for instance, related to normalization theorems, consistency, decidability, and complexity results. The proof theory for arithmetic is also motivated by Godel incompleteness theorems. It aims to o_er an example of a true mathematically meaningful principle not derivable in first-order arithmetic. One way of presenting this proof is based on a definition of a proof system with an infinitary rule, the w-rule, that establishes the consistency of first-order arithmetic through a proof-theoretical perspective. Motivated by this proof, here we will propose an in_nitary proof system for LFP that will allow us to investigate proof theoretical properties. With such in_nitary deductive system, we aim to present a proof theory for a logic traditionally defined within the scope of FMT. It opens up an alternative way of proving results already obtained within FMT and also new results through a proof theoretical perspective. Moreover, we will propose a normalization procedure with some restrictions on the rules, such this deductive system can be used in a theorem prover to compute queries on relational databases. / A noção de menor ponto-fixo de um operador é amplamente aplicada na ciência da computação como, por exemplo, no contexto das linguagens de consulta para bancos de dados relacionais. Algumas extensões da Lógica de Primeira-Ordem (FOL)1 com operadores de ponto-fixo em estruturas finitas, como a lógica de menor ponto-fixo (LFP)2, foram propostas para lidar com problemas relacionados á expressividade de FOL. A LFP captura as classes de complexidade PTIME sobre a classe das estruturas finitas ordenadas. A caracterização descritiva de classes computacionais é uma abordagem central em Teoria do Modelos Finitos (FMT)3. O teorema de Trakhtenbrot, considerado o ponto de partida para FMT, estabelece que a validade sobre modelos finitos não é recursivamente enumerável, isto é, a completude falha sobre modelos finitos. Este resultado é baseado na hipótese de que qualquer sistema dedutivo é de natureza finita. Entretanto, nos podemos relaxar tal hipótese como foi feito no escopo da teoria da prova para aritmética. A teoria da prova tem raízes no programa de Hilbert. Conseqüências teóricas da noção de prova são, por exemplo, relacionadas a teoremas de normalização, consistência, decidibilidade, e resultados de complexidade. A teoria da prova para aritmética também é motivada pelos teoremas de incompletude de Gödel, cujo alvo foi fornecer um exemplo de um princípio matemático verdadeiro e significativo que não é derivável na aritmética de primeira-ordem. Um meio de apresentar esta prova é baseado na definição de um sistema de prova com uma regra infinitária, a w-rule, que estabiliza a consistência da aritmética de primeira-ordem através de uma perspectiva de teoria da prova. Motivados por esta prova, iremos propor aqui um sistema infinitário de prova para LFP que nos permitirá investigar propriedades em teoria da prova. Com tal sistema dedutivo infinito, pretendemos apresentar uma teoria da prova para uma lógica tradicionalmente definida no escopo de FMT. Permanece aberto um caminho alternativo de provar resultados já obtidos com FMT e também novos resultados do ponto de vista da teoria da prova. Além disso, iremos propor um procedimento de normalização com restrições para este sistema dedutivo, que pode ser usado em um provador de teoremas para computar consultas em banco de dados relacionais