No description available.

No description available.

Made available in DSpace on 2014-06-12T15:49:50Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O presente trabalho é baseada em dois aspectos fundamentais: (i) o estudo de procedimentos de normalização para sistemas de provas, especialmente para a lógica clássica com dedução natural; e (ii) a investigação de técnicas da perspectiva geométrica aplicadas em propriedades da teoria da prova. Com isso, a motivação específica deste trabalho reside principalmente na análise daqueles trabalhos que estão voltados à definição de técnicas da normalização através de mecanismos da perspectiva geométrica. Destaca-se que técnicas da perspectiva geométrica trazem o uso de arcabouços gráficos e/ou topológicos com a finalidade de representar sistemas formais de provas e suas propriedades. Dessa forma, a primeira parte do documento apresenta o uso de técnicas e arcabouços topológicos para estabelecer algumas propriedades, como, por exemplo, o critério de corretude e a normalização de sistemas de prova. Ao passo que a segunda parte do documento é inicialmente direcionada à descrição de algumas abordagens de normalização (principalmente) para a lógica clássica com dedução natural. E o complemento da segunda parte é dedicado à definição do principal objetivo do trabalho, i.e., desenvolver um procedimento de normalização para o conjunto completo de operadores dos N-Grafos, através do auxílio de algumas técnicas de perspectiva geométrica. (Destaca-se que as técnicas de perspectiva geométrica, aplicadas à normalização dos N-Grafos, não fazem uso de arcabouços topológicos). N-Grafos é um sistema de prova com múltipla conclusão definido para lógica clássica proposicional com dedução natural. Ademais, os N-Grafos possuem tanto regras lógicas como estruturais, estruturas cíclicas são permitidas e além disso as derivações são representadas como grafos direcionados. De fato, a princpal característica do procedimento de normalização aqui apresentado é fornecer um tratamento completo para as estruturas cíclicas. Ou seja, são definidas classes de ciclos válidos, critério de corretude, propriedades e ainda um algoritmo específico para normalizar os ciclos nos N-Grafos. Destaca-se que esses elementos são construídos através do auxílio de arcabouços gráficos. Além disso, o mecanismo de normalização é capaz de lidar com os diferentes papéis executados pelos operadores ?/>. Adicionalmente, apresenta-se uma prova direta da normalização fraca para os N-Grafos, bem como, a determinação das propriedades da subfórmula e da separação

[pt] Dedução Natural para a lógica intuicionista tem sido relacionada à Teoria das Categorias através do que agora é conhecido por Lógica Categórica. Essa relação é fortemente baseada no isomorfismo de Curry-Howard entre Dedução Natural e (lambda)-Cálculo Tipado. Esta dissertação descreve alguns aspectos dessa relação com o objetivo de propor uma visão 2-categórica da Lógica Categórica. Mostramos que mesmo numa visão 2-cateórica algumas desvantagens conhecidas na Teoria das Categorias continuam valendo. Concluímos essa dissertação discutindo as vantagens de uma visão 2-categórica a partir de premissas mais fracas. / [en] Natural Deduction for intuitionistic logic has been related to Category Theory by what now is known as Categorical Logic. This relationship is strongly based on the Curry-Howard Isomorphism between Natural Deduction and typed (lambda)-Calculus. This dissertation describes some aspects of these relationship with the aim of proposing a 2-categorical view of categorical logic. We show that even under this 2-categorical view some of the drawbacks already known in ordinary Category Theory remain holding. We conclude this dissertation discussing the advantages of 2-categorical view under some weaker assumptions.

[pt] Garantir que programas são implementados de forma a cumprir uma especificação é uma questão fundamental em computação, por isso, têm sido propostos vários métodos que almejam provar a correção dos programas. Este trabalho apresenta um método, baseado no isomorfismo de Curry-Howard, que extrai conteúdos computacionais de provas intuicionistas, conhecido como síntese construtiva ou proofs-as-programs. É proposto um processo de síntese construtiva de programas, onde a extração do conteúdo computacional gera um programa em linguagem imperativa a partir de uma prova em lógica intuicionista poli-sortida, cujos axiomas definem os tipos abstratos de dados, sendo utilizado como sistema dedutivo a Dedução Natural. Também é apresentada uma prova de correção, bem como uma prova de completude do método atráves do uso de um sistema com regra ômega (computacional) para a aritmética de Heyting, concluindo com uma demonstração da relação entre o uso da indução finita no lugar da regra ômega computacional no processo de síntese. / [en] One of the main problems in computer science is to assure that programs are implemented in such a way that they satisfy a given specification. There are many studies about methods to prove correctness of programs. This work presents a method, belonging to the constructive synthesis or proofs-as-programs paradigm, that comes from the Curry- Howard isomorphism and extracts the computational contents of intuitionist proofs. The synthesis process proposed produces a program in an imperative language from a proof in many-sorted intuitionist logic, where the axioms define the abstract data types using Natural Deduction as deductive system. It is proved the correctness, as well as the completeness of the method regarding the Heyting arithmetic with ômega-rule(in its computational version). A discussion about the use of the finitary induction instead of computational ômega-rule concludes the work.

[pt] Apresentamos uma lógica para a compreensão de condicionais a partir da proximidade (PUC-Logic) que unifica as lógicas Contrafactual e Deôntica propostas por David Lewis. Propomos também um sistema de dedução natural (PUC-ND) associado a essa nova lógica. Esse sistema de inferência é correto, completo, normalizável e decidível. A completude relativa para as lógicas V e CO é apresentada para dar ênfase à abordagem unificada sobre o trabalho de Lewis. Depois disso, apresentamos uma perspectiva construtivista para mostrar que a abstração contrafactual de Lewis não exige a regra do absurdo clássico. / [en] We present a logic for Proximity-based Understanding of Conditionals (PUC-Logic) that unifies the Counterfactual and Deontic logics proposed by David Lewis. We also propose a natural deduction system (PUC-ND) associated to this new logic. This inference system is proven to be sound, complete, normalizing and decidable. The relative completeness for the V and CO logics is shown to emphasize the unified approach over the work of Lewis. We, then, present a constructive approach to counterfactuals to show that the Lewis counterfactual abstraction does not require the classical absurd rule.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / 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 esquematicas, 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ÃÃoo Fraca e Forte para sistemas esquemÃticos definidos em funÃÃoo 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. / 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.

[pt] Neste trabalho propomos um framework lógico para sistemas de Dedução Natural rotulados. Sua meta-linguagem é baseada numa generalização dos esquemas de regras propostos por Prawitz, e o uso de rótulos permite a definição de lógicas intencionais como lógicas modais e de descrição, bem como a definição uniforme de quantificadores como o para um número não-renumerável de indivíduos vale a propriedade P (lógica de Keisler), ou para quase todos os indivíduos vale P (lógica de ultra-filtros), sem mencionar os quantificadores padrões de lógica de primeira-ordem. Mostramos também a implementação deste framework em um assistente de prova virtual disponível livremente na web, e comparamos a definição de sistemas lógicos nele com o mesmo feito em outros assistentes — Agda, Isabelle, Lean, Metamath. Como subproduto deste experimento comparativo, também contribuímos uma prova formal em Lean do postulado de Zolt em três dimensões usando o sistema Zp proposto por Giovaninni et al. / [en] We propose a Logical Framework for labelled Natural Deduction systems. Its meta-language is based on a generalization of the rule schemas proposed by Prawitz, and the use of labels allows the definition of intentional logics, such as Modal Logic and Description Logic, as well as some quantifiers, such as Keisler s for non-denumerable-many individuals property P, or for almost all individuals P holds, or generally P holds, not to mention standard first-order logic quantifiers, all in a uniform way. We also show an implementation of this framework as a freely-available web-based proof assistant. We then compare the definition of logical systems in our implementation and in other proof assistants — Agda, Isabelle, Lean, Metamath. As a sub-product of this comparison experiment, we contribute a formal proof (in Lean) of De Zolt s postulate for three dimensions, using the Zp system proposed by Giovaninni et al.

[pt] É um fato conhecido que provas clássicas podem ser demasiadamente grandes. Estudos em teoria da prova descobriram diferenças exponenciais entre provas normais (ou provas livres do corte) e suas respectivas provas não normais. Por outro lado, provadores automáticos de teorema usualmente se baseiam na construção de provas normais, livres de corte ou provas de corte atômico, pois tais procedimento envolvem menos escolhas. Provas de algumas tautologias são conhecidamente grandes quanto realizadas sem a regra do corte e curtas quando a utilizam. Queremos com este trabalho apresentar procedimentos para reduzir o tamanho de provas proposicionais. Neste sentido, apresentamos dois métodos. O primeiro, denominado método vertical, faz uso de axiomas de extensão e alguns casos é possível uma redução considerável no tamanho da prova. Apresentamos um procedimento que gera tais axiomas de extensão. O segundo, denominado método horizontal, adiciona fórmulas máximas por meio de unificação via substituição de variáveis proposicionais. Também apresentamos um método que gera tal unificação durante o processo de construção da prova. O primeiro método é aplicado a dedução natural enquanto o segundo à Dedução Natural e Cálculo de Seqüentes. As provas produzidas correspondem de certo modo a provas não normais (com a regra do corte). / [en] It is well-known that the size of propositional classical proofs can be huge. Proof theoretical studies discovered exponential gaps between normal or cut-free proofs and their respective non-normal proofs. The task of automatic theorem proving is, on the other hand, usually based on the construction of normal, cut-free or only-atomic-cuts proofs, since this procedure produces less alternative choices. There are familiar tautologies such that the cut-free proof is huge while the non-cut-free is small. The aim of this work is to reduce the weight of proposicional deductions. In this sense we present two methods. The fi first, namely vertical method, uses the extension axioms. We present a method that generates a such extension axiom. The second, namely horizontal method, adds suitable (propositional) unifi fications modulo variable substitutions.We also present a method that generates a such unifi fication during the proving process. The proofs produced correspond in a certain way to non normal proofs (non cut-free proofs).

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.