In this thesis we see deductive systems for classical propositional and predicate logic which use deep inference, i.e. inference rules apply arbitrarily deep inside formulas, and a certain symmetry, which provides an involution on derivations. Like sequent systems, they have a cut rule which is admissible. Unlike sequent systems, they enjoy various new interesting properties. Not only the identity axiom, but also cut, weakening and even contraction are reducible to atomic form. This leads to inference rules that are local, meaning that the effort of applying them is bounded, and finitary, meaning that, given a conclusion, there is only a finite number of premises to choose from. The systems also enjoy new normal forms for derivations and, in the propositional case, a cut elimination procedure that is drastically simpler than the ones for sequent systems.

Em Engenharia de Produção, os processos de decisão constituem um dos temas centrais e envolvem fatores de naturezas diversas, que os cercam de dificuldades. Nesses processos, não raramente, estão presentes fatores de natureza subjetiva, informações imprecisas, quando não vagas e mesmo conflitantes, que podem levar a decisões distorcidas, comprometendo a clareza e a objetividade de uma análise. Para manipular logicamente um conjunto de informações vagas, subjetivas, inconsistentes ou paracompletas, são necessárias lógicas alternativas da clássica, pois esta não pode, ao menos diretamente, ser empregada para tal fim. Assim, a lógica paraconsistente pode, em princípio, ser uma ferramenta adequada para a tarefa. No presente trabalho será apresentado um processo de auxílio às tomadas de decisão, denominado de Método de Análise pelo Baricentro (MAB), que se baseia na lógica paraconsistente anotada evidencial Et e no algoritmo para-analisador, introduzidos em (DA COSTA et al., 1999) e (DA SILVA FILHO; ABE, 2001). Esse método permite, de modo não trivial, o tratamento de informações com aquelas características e evidencia a possibilidade de aplicações da lógica Et em Administração, Marketing, Engenharia de Produção, previsão de diagnósticos, aplicações financeiras, entre outros temas. Um estudo de caso real, com resultados plenamente satisfatórios, mostra sua aplicabilidade na prática. Além disso, o MAB abre, entre outras, a perspectiva de se transformarem análises qualitativas em quantitativas. / In Production Engineering, decision making processes represent one of the most important topics and involve factors of various natures, which are, in turn, surrounded by difficulties. Quite often in these processes, there are factors of subjective nature, inaccurate data, sometimes even vague or conflicting information, which may lead to distorted decisions that eventually compromise the clarity and objectiveness of the analysis. In order to logically handle a set of vague, subjective, inconsistent or paracomplete information, logic other than classic is required, once the latter cannot, at least directly, be applied for such purpose. Hence, paraconsistent logic can, in principle, be an adequate tool for the task. In this paper, we will present an auxiliary process in decision making called Baricenter Analysis Method (BAM), which is based in Paraconsistent Annotated Evidential Logic Et and in a para-analyzer algorithm, introduced in (DA COSTA et al., 1999) and (DA SILVA FILHO; ABE, 2001). This methodology allows, in quite an unusual way, the treatment of information containing those characteristics and points out the possibility of applications of logic Et in Business Administration, Marketing, Production Engineering, anticipation of diagnosis, financial applications, among other subjects. Furthermore, BAM opens the possibility of transforming qualitative into quantitative analysis.

<p>In this thesis we use the syntactic-semantic method of constructive type theory to give meaning to classical logic, in particular Gentzen's LK.</p><p>We interpret a derivation of a classical sequent as a derivation of a contradiction from the assumptions that the antecedent formulas are true and that the succedent formulas are false, where the concepts of truth and falsity are taken to conform to the corresponding constructive concepts, using function types to encode falsity. This representation brings LK to a manageable form that allows us to split the succedent rules into parts. In this way, every succedent rule gives rise to a natural deduction style introduction rule. These introduction rules, taken together with the antecedent rules adapted to natural deduction, yield a natural deduction calculus whose subsequent interpretation in constructive type theory gives meaning to classical logic.</p><p>The Gentzen-Prawitz inversion principle holds for the introduction and elimination rules of the natural deduction calculus and allows for a corresponding notion of convertibility. We take the introduction rules to determine the meanings of the logical constants of classical logic and use the induced type-theoretic elimination rules to interpret the elimination rules of the natural deduction calculus. This produces an interpretation injective with respect to convertibility, contrary to an analogous translation into intuitionistic predicate logic.</p><p>From the interpretation in constructive type theory and the interpretation of cut by explicit substitution, we derive a full precision contraction relation for a natural deduction version of LK. We use a term notation to formalize the contraction relation and the corresponding cut-elimination procedure.</p><p>The interpretation can be read as a Brouwer-Heyting-Kolmogorov (BHK) semantics that justifies classical logic. The BHK semantics utilizes a notion of classical proof and a corresponding notion of classical truth akin to Kolmogorov's notion of pseudotruth. We also consider a second BHK semantics, more closely connected with Kolmogorov's double-negation translation.</p><p>The first interpretation reinterprets the consequence relation while keeping the constructive interpretation of truth, whereas the second interpretation reinterprets the notion of truth while keeping the constructive interpretation of the consequence relation. The first and second interpretations act on derivations in much the same way as Plotkin's call-by-value and call-by-name continuation-passing-style translations, respectively.</p><p>We conclude that classical logic can be given a constructive semantics by laying down introduction rules for the classical logical constants. This semantics constitutes a proof interpretation of classical logic.</p>

In this thesis we use the syntactic-semantic method of constructive type theory to give meaning to classical logic, in particular Gentzen's LK. We interpret a derivation of a classical sequent as a derivation of a contradiction from the assumptions that the antecedent formulas are true and that the succedent formulas are false, where the concepts of truth and falsity are taken to conform to the corresponding constructive concepts, using function types to encode falsity. This representation brings LK to a manageable form that allows us to split the succedent rules into parts. In this way, every succedent rule gives rise to a natural deduction style introduction rule. These introduction rules, taken together with the antecedent rules adapted to natural deduction, yield a natural deduction calculus whose subsequent interpretation in constructive type theory gives meaning to classical logic. The Gentzen-Prawitz inversion principle holds for the introduction and elimination rules of the natural deduction calculus and allows for a corresponding notion of convertibility. We take the introduction rules to determine the meanings of the logical constants of classical logic and use the induced type-theoretic elimination rules to interpret the elimination rules of the natural deduction calculus. This produces an interpretation injective with respect to convertibility, contrary to an analogous translation into intuitionistic predicate logic. From the interpretation in constructive type theory and the interpretation of cut by explicit substitution, we derive a full precision contraction relation for a natural deduction version of LK. We use a term notation to formalize the contraction relation and the corresponding cut-elimination procedure. The interpretation can be read as a Brouwer-Heyting-Kolmogorov (BHK) semantics that justifies classical logic. The BHK semantics utilizes a notion of classical proof and a corresponding notion of classical truth akin to Kolmogorov's notion of pseudotruth. We also consider a second BHK semantics, more closely connected with Kolmogorov's double-negation translation. The first interpretation reinterprets the consequence relation while keeping the constructive interpretation of truth, whereas the second interpretation reinterprets the notion of truth while keeping the constructive interpretation of the consequence relation. The first and second interpretations act on derivations in much the same way as Plotkin's call-by-value and call-by-name continuation-passing-style translations, respectively. We conclude that classical logic can be given a constructive semantics by laying down introduction rules for the classical logical constants. This semantics constitutes a proof interpretation of classical logic.

Les questions <EM>"Qu'est-ce qu'une preuve?"</EM> et <EM>"Quand deux preuves sont-elles identiques?"</EM> sont fondamentales pour la théorie de la preuve. Mais pour la logique classique propositionnelle --- la logique la plus répandue --- nous n'avons pas encore de réponse satisfaisante. C'est embarrassant non seulement pour la théorie de la preuve, mais aussi pour l'informatique, où la logique classique joue un rôle majeur dans le raisonnement automatique et dans la programmation logique. De même, l'architecture des processeurs est fondée sur la logique classique. Tous les domaines dans lesquels la recherche de preuve est employée peuvent bénéficier d'une meilleure compréhension de la notion de preuve en logique classique, et le célèbre problème NP-vs-coNP peut être réduit à la question de savoir s'il existe une preuve courte (c'est-à-dire, de taille polynomiale) pour chaque tautologie booléenne. Normalement, les preuves sont étudiées comme des objets syntaxiques au sein de systèmes déductifs (par exemple, les tableaux, le calcul des séquents, la résolution, ...). Ici, nous prenons le point de vue que ces objets syntaxiques (également connus sous le nom d'arbres de preuve) doivent être considérés comme des représentations concrètes des objets abstraits que sont les preuves, et qu'un tel objet abstrait peut être représenté par un arbre en résolution ou dans le calcul des séquents. Le thème principal de ce travail est d'améliorer notre compréhension des objets abstraits que sont les preuves, et cela se fera sous trois angles différents, étudiés dans les trois parties de ce mémoire: l'algèbre abstraite (chapitre 2), la combinatoire (chapitres 3 et 4), et la complexité (chapitre 5).

Cette thèse étudie deux modèles de réalisabilité pour la logique classique construits sur la sémantique des jeux HO, interprétant la logique, l'arithmétique et l'analyse classiques directement par des programmes manipulant un espace de stockage d'ordre supérieur.La non-innocence en jeux HO autorise les références d'ordre supérieur, et le non parenthésage révèle la CPS des jeux HO et fournit une catégorie de continuations dans laquelle interpréter le lambda-mu calcul de Parigot. Deux modèles de réalisabilité sont construits sur cette interprétation calculatoire directe des preuves classiques.Le premier repose sur l'orthogonalité, comme celui de Krivine, mais il est simplement typé et au premier ordre. En l'absence de codage de l'absurdité au second ordre, une mu-variable libre dans les réaliseurs permet l'extraction. Nous définissons un bar-récurseur et prouvons qu'il réalise l'axiome du choix dépendant, utilisant deux conséquences de la structure de CPO du modèle de jeux: toute fonction sur les entiers (même non calculable) existe dans le modèle, et toute fonctionnelle sur des séquences est Scott-continue. La bar-récursion est habituellement utilisée pour réaliser intuitionnistiquement le « double negation shift » et en déduire la traduction négative de l'axiome du choix. Ici, nous réalisons directement l'axiome du choix dans un cadre classique.Le second, très spécifique au modèle de jeux, repose sur des conditions de gain: des ensembles de positions d'un jeu munis de propriétés de cohérence. Un réaliseur est alors une stratégie dont les positions sont toutes gagnantes. / This thesis investigates two realizability models for classical logic built on HO game semantics. The main motivation is to have a direct computational interpretation of classical logic, arithmetic and analysis with programs manipulating a higher-order store.Relaxing the innocence condition in HO games provides higher-order references, and dropping the well-bracketing of strategies reveals the CPS of HO games and gives a category of continuations in which we can interpret Parigot's lambda-mu calculus. This permits a direct computational interpretation of classical proofs from which we build two realizability models.The first model is orthogonality-based, as the one of Krivine. However, it is simply-typed and first-order. This means that we do not use a second-order coding of falsity, and extraction is handled by considering realizers with a free mu-variable. We provide a bar-recursor in this model and prove that it realizes the axiom of dependent choice, relying on two consequences of the CPO structure of the games model: every function on natural numbers (possibly non computable) exists in the model, and every functional on sequences is Scott-continuous. Usually, bar-recursion is used to intuitionistically realize the double negation shift and consequently the negative translation of the axiom of choice. Here, we directly realize the axiom of choice in a classical setting.The second model relies on winning conditions and is very specific to the games model. A winning condition is a set of positions in a game which satisfies some coherence properties, and a realizer of a formula is then a strategy which positions are all winning.

Em Engenharia de Produção, os processos de decisão constituem um dos temas centrais e envolvem fatores de naturezas diversas, que os cercam de dificuldades. Nesses processos, não raramente, estão presentes fatores de natureza subjetiva, informações imprecisas, quando não vagas e mesmo conflitantes, que podem levar a decisões distorcidas, comprometendo a clareza e a objetividade de uma análise. Para manipular logicamente um conjunto de informações vagas, subjetivas, inconsistentes ou paracompletas, são necessárias lógicas alternativas da clássica, pois esta não pode, ao menos diretamente, ser empregada para tal fim. Assim, a lógica paraconsistente pode, em princípio, ser uma ferramenta adequada para a tarefa. No presente trabalho será apresentado um processo de auxílio às tomadas de decisão, denominado de Método de Análise pelo Baricentro (MAB), que se baseia na lógica paraconsistente anotada evidencial Et e no algoritmo para-analisador, introduzidos em (DA COSTA et al., 1999) e (DA SILVA FILHO; ABE, 2001). Esse método permite, de modo não trivial, o tratamento de informações com aquelas características e evidencia a possibilidade de aplicações da lógica Et em Administração, Marketing, Engenharia de Produção, previsão de diagnósticos, aplicações financeiras, entre outros temas. Um estudo de caso real, com resultados plenamente satisfatórios, mostra sua aplicabilidade na prática. Além disso, o MAB abre, entre outras, a perspectiva de se transformarem análises qualitativas em quantitativas. / In Production Engineering, decision making processes represent one of the most important topics and involve factors of various natures, which are, in turn, surrounded by difficulties. Quite often in these processes, there are factors of subjective nature, inaccurate data, sometimes even vague or conflicting information, which may lead to distorted decisions that eventually compromise the clarity and objectiveness of the analysis. In order to logically handle a set of vague, subjective, inconsistent or paracomplete information, logic other than classic is required, once the latter cannot, at least directly, be applied for such purpose. Hence, paraconsistent logic can, in principle, be an adequate tool for the task. In this paper, we will present an auxiliary process in decision making called Baricenter Analysis Method (BAM), which is based in Paraconsistent Annotated Evidential Logic Et and in a para-analyzer algorithm, introduced in (DA COSTA et al., 1999) and (DA SILVA FILHO; ABE, 2001). This methodology allows, in quite an unusual way, the treatment of information containing those characteristics and points out the possibility of applications of logic Et in Business Administration, Marketing, Production Engineering, anticipation of diagnosis, financial applications, among other subjects. Furthermore, BAM opens the possibility of transforming qualitative into quantitative analysis.