In classical propositional logic (CPL) logical reasoning is formalised as logical entailment and can be computed by means of tableau and resolution proof procedures. Unfortunately CPL is not expressive enough and using first order logic (FOL) does not solve the problem either since proof procedures for these logics are not decidable. Modal propositional logics (MPL) on the other hand are both decidable and more expressive than CPL. It therefore seems reasonable to apply tableau and resolution proof systems to MPL in order to compute logical entailment in MPL. Although some of the principles in CPL are present in MPL, there are complexities in MPL that are not present in CPL. Tableau and resolution proof systems which address these issues and others will be surveyed here. In particular the work of Abadi & Manna (1986), Chan (1987), del Cerro & Herzig (1988), Fitting (1983, 1990) and Gore (1995) will be reviewed. / Computing / M. Sc. (Computer Science)

Partant des travaux séminaux de Boole, Frege et Russell, le mémoire cherche à clarifier l‟enjeu du pluralisme logique à l‟ère de la prolifération des logiques non-classiques et des développements en informatique théorique et en théorie des preuves. Deux chapitres plus « historiques » sont à l‟ordre du jour : (1) le premier chapitre articule l‟absolutisme de Frege et Russell en prenant soin de montrer comment il exclut la possibilité d‟envisager des structures et des logiques alternatives; (2) le quatrième chapitre expose le chemin qui mena Carnap à l‟adoption de la méthode syntaxique et du principe de tolérance, pour ensuite dégager l‟instrumentalisme carnapien en philosophie de la Logique et des mathématiques. Passant par l‟analyse d‟une interprétation intuitive de la logique linéaire, le deuxième chapitre se tourne ensuite vers l‟établissement d‟une forme logico-mathématique de pluralisme logique à l‟aide de la théorie des relations d‟ordre et la théorie des catégories. Le troisième chapitre délimite le terrain de jeu des positions entourant le débat entre monisme et pluralisme puis offre un argument contre la thèse qui veut que le conflit entre logiques rivales soit apparent, le tout grâce à l‟utilisation du point de vue des logiques sous-structurelles. Enfin, le cinquième chapitre démontre que chacune des trois grandes approches au concept de conséquence logique (modèle-théorétique, preuve-théorétique et dialogique) forme un cadre suffisamment général pour établir un pluralisme. Bref, le mémoire est une défense du pluralisme logique. / Starting from the seminal work of Boole, Frege and Russell, the dissertation seeks to clarify the issue of logical pluralism in the era of the proliferation of non-classical logics and the developments in theoretical computer science and proof theory. Two “historical” chapters are scheduled: the first chapter articulate the absolutism of Frege and Russell, taking care to show how it condemns the possibility to consider alternative structures and logics; the fourth chapter describes the path that led Carnap from the adoption of the syntactic method to the formulation of the principle of tolerance, then goes on to display Carnap‟s instrumentalism in philosophy of Logic and mathematics. Opening with the analysis of an intuitive interpretation of linear logic, the second chapter then turns to the establishment of a form of logico-mathematical pluralism with the help of order theory and category theory. The third chapter delineates the playground of revisionism (philosophical positions surrounding the debate between monism and pluralism) and then provides an argument against the thesis that denies the reality of the conflict between rival logics, all this being done by adopting the substructural logic point of view. The fifth chapter shows that each of the three main approaches to the concept of logical consequence (model-theoretic, proof-theoretic and dialogical) supplies a framework sufficiently general to establish pluralism. In short, the dissertation is a defence of logical pluralism.

Although proof has long been viewed as a cornerstone of mathematical activity, incorporating the mathematical practice of proving into classrooms is not a simple matter. In this dissertation I aim to advance research on proof by addressing this issue. In particular, I explore the role proof might play in promoting the learning of mathematics in the classroom. I do this in a series of three articles (organized as three chapters), which are preceded by an introductory chapter. The introductory chapter situates the remaining chapters in the context of mathematics education research. In the second chapter I explore what the literature on proof tells us about what role proof might play in the promotion of learning in the mathematics classroom. In this chapter I also compare the ways in which proof is purported to promote learning in the mathematics classroom with the roles it is purported to play in the field of research mathematics. In the third chapter I look at empirical data to explore ways engaging in proof and proving might create opportunities for student learning. In particular, my analysis led me to focus on how identifying and reflecting on the key idea of a proof can create opportunities for learning mathematics. The final chapter is an article for a practitioner journal and discusses implications for practice based on the two preceding articles.

[pt] Segerberg apresentou uma prova geral da completude para lógicas proposicionais. Para tal, um sistema de dedução foi definido de forma que suas regras sejam regras para um operador booleano arbitrário para uma dada lógica proposicional. Cada regra desse sistema corresponde a uma linha na tabela de verdade desse operador. Na primeira parte desse trabalho, mostramos uma extensão da ideia de Segerberg para lógicas proposicionais finito-valoradas e para lógicas não-determinísticas. Mantemos a ideia de definir um sistema de dedução cujas regras correspondam a linhas de tabelas verdade, mas ao invés de termos um tipo de regra para cada valor de verdade da lógica correspondente, usamos uma representação bivalente que usa a técnica de fórmulas separadoras definidas por Carlos Caleiro e João Marcos. O sistema definido possui tantas regras que pode ser difícil trabalhar com elas. Acreditamos que um sistema de cálculo de sequentes definido de forma análoga poderia ser mais intuitivo. Motivados por essa observação, a segunda parte dessa tese é dedicada à definição de uma tradução entre cálculo de sequentes e dedução natural, onde procuramos definir uma bijeção melhor do que as já existentes. / [en] Segerberg presented a general completeness proof for propositional logics. For this purpose, a Natural Deduction system was defined in a way that its rules were rules for an arbitrary boolean operator in a given propositional logic. Each of those rules corresponds to a row on the operator s truth-table. In the first part of this thesis we extend Segerbergs idea to finite-valued propositional logic and to non-deterministic logic. We maintain the idea of defining a deductive system whose rules correspond to rows of truth-tables, but instead of having n types of rules (one for each truth-value), we use a bivalent representation that makes use of the technique of separating formulas as defined by Carlos Caleiro and João Marcos. The system defined has so many rules it might be laborious to work with it. We believe that a sequent calculus system defined in a similar way would be more intuitive. Motivated by this observation, in the second part of this thesis we work out translations between Sequent Calculus and Natural Deduction, searching for a better bijective relationship than those already existing.

Made available in DSpace on 2016-04-26T20:22:14Z (GMT). No. of bitstreams: 1 Landolfo Andrade de Souza.pdf: 1706067 bytes, checksum: c3f41df8c866866f22a3fd11abb9cfa4 (MD5) Previous issue date: 2013-10-24 / There is no doubt that the modern civil procedure must be updated to cope with the substantive law needs and the new contemporary society dynamics. Likewise, such changes dispense legislative modifications, which often take a long time to be made. Thus, it s necessary to pursue the procedure s improvement by a more appropriate managing of the procedural techniques available for the judge, in the light of the constitutional guarantees. The rule for the burden of proof is within this perspective: it s one of the matters to which the doctrine devotes its attention in order to make the indispensable transformations in the procedural system to bring it closer to substantive law s reality. To this end, this work searched to examine how the burden of proof operates in the class actions, studying the reasons that authorize its change, since such possibility beyond the realm of consumer law - may correspond to a significant condition of effective protection of collective interests. For that purpose, one has used law doctrine, case law and deductive, inductive and analogical methods. The Federal Constitution and federal rules related to the burden of proof dogma and the collective interests protection have also been examined. The research has been split in for main parts. Firstly, some relevant aspects of the collective procedure have been studied. Then, the structural elements of the burden of proof have been analysed. The third part was dedicated to the conceptual elements, as well as the fundaments of applicability, including de lege lata, of the dynamic burden of proof theory in Brazilian law were outlined. In the fourth part, it has been demonstrated that the hipotheses that allow the flexibility of the general criteria for the distribution of the proof burdens are consistent with one of the most relevant preoccupations of procedural law jurists: the search for more effectiveness in the substantive field by the procedural technique refinement / Não há dúvidas de que o processo civil moderno deve atualizar-se para fazer frente às necessidades do direito material e da nova dinâmica da sociedade contemporânea. Tampouco se duvida que esta mudança prescinde de alterações legislativas, pois estas, muitas vezes, demoram a ocorrer. Impõe-se, então, buscar aprimorar o processo com o manejo mais adequado das técnicas processuais postas à disposição do juiz, à luz das garantias constitucionais. A regra sobre o ônus da prova se insere nesta perspectiva: constitui ela um dos pontos em que se debruça a doutrina para imprimir necessárias alterações no sistema processual, tornando-o mais próximo à realidade do direito material. Nesse propósito, este trabalho buscou apreciar como se comporta a regra do ônus da prova nas ações civis públicas, avaliando as razões que autorizariam a sua modificação, já que esta possibilidade para além dos campos do direito do consumidor pode importar significativa condição para a efetiva tutela dos interesses coletivos. Para tanto, valeu-se do estudo da doutrina e da jurisprudência, bem como se utilizaram os métodos dedutivo, indutivo e analógico. Examinaram-se a Constituição Federal e as normas federais pertinentes ao dogma do ônus da prova, bem como à defesa dos interesses coletivos. A pesquisa foi dividida em quatro partes principais. Na primeira, foram examinados alguns aspectos relevantes do direito processual coletivo. Na segunda, analisaram-se os principais aspectos do instituto do ônus da prova. Na terceira, foram fixados os elementos estruturais, bem como os fundamentos de aplicabilidade, inclusive de lege lata, da teoria do ônus dinâmico da prova no direito brasileiro. Na última parte, demonstrou-se que as hipóteses de flexibilização dos critérios gerais de repartição dos encargos probatórios encontram-se afinadas com uma das principais preocupações dos cultores do direito processual: buscar maior efetividade no plano material por meio do aprimoramento da técnica processual

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).

In this thesis I study several deductive systems for linear logic, its fragments, and some noncommutative extensions. All systems will be designed within the calculus of structures, which is a proof theoretical formalism for specifying logical systems, in the tradition of Hilbert's formalism, natural deduction, and the sequent calculus. Systems in the calculus of structures are based on two simple principles: deep inference and top-down symmetry. Together they have remarkable consequences for the properties of the logical systems. For example, for linear logic it is possible to design a deductive system, in which all rules are local. In particular, the contraction rule is reduced to an atomic version, and there is no global promotion rule. I will also show an extension of multiplicative exponential linear logic by a noncommutative, self-dual connective which is not representable in the sequent calculus. All systems enjoy the cut elimination property. Moreover, this can be proved independently from the sequent calculus via techniques that are based on the new top-down symmetry. Furthermore, for all systems, I will present several decomposition theorems which constitute a new type of normal form for derivations.

Partant des travaux séminaux de Boole, Frege et Russell, le mémoire cherche à clarifier l‟enjeu du pluralisme logique à l‟ère de la prolifération des logiques non-classiques et des développements en informatique théorique et en théorie des preuves. Deux chapitres plus « historiques » sont à l‟ordre du jour : (1) le premier chapitre articule l‟absolutisme de Frege et Russell en prenant soin de montrer comment il exclut la possibilité d‟envisager des structures et des logiques alternatives; (2) le quatrième chapitre expose le chemin qui mena Carnap à l‟adoption de la méthode syntaxique et du principe de tolérance, pour ensuite dégager l‟instrumentalisme carnapien en philosophie de la Logique et des mathématiques. Passant par l‟analyse d‟une interprétation intuitive de la logique linéaire, le deuxième chapitre se tourne ensuite vers l‟établissement d‟une forme logico-mathématique de pluralisme logique à l‟aide de la théorie des relations d‟ordre et la théorie des catégories. Le troisième chapitre délimite le terrain de jeu des positions entourant le débat entre monisme et pluralisme puis offre un argument contre la thèse qui veut que le conflit entre logiques rivales soit apparent, le tout grâce à l‟utilisation du point de vue des logiques sous-structurelles. Enfin, le cinquième chapitre démontre que chacune des trois grandes approches au concept de conséquence logique (modèle-théorétique, preuve-théorétique et dialogique) forme un cadre suffisamment général pour établir un pluralisme. Bref, le mémoire est une défense du pluralisme logique. / Starting from the seminal work of Boole, Frege and Russell, the dissertation seeks to clarify the issue of logical pluralism in the era of the proliferation of non-classical logics and the developments in theoretical computer science and proof theory. Two “historical” chapters are scheduled: the first chapter articulate the absolutism of Frege and Russell, taking care to show how it condemns the possibility to consider alternative structures and logics; the fourth chapter describes the path that led Carnap from the adoption of the syntactic method to the formulation of the principle of tolerance, then goes on to display Carnap‟s instrumentalism in philosophy of Logic and mathematics. Opening with the analysis of an intuitive interpretation of linear logic, the second chapter then turns to the establishment of a form of logico-mathematical pluralism with the help of order theory and category theory. The third chapter delineates the playground of revisionism (philosophical positions surrounding the debate between monism and pluralism) and then provides an argument against the thesis that denies the reality of the conflict between rival logics, all this being done by adopting the substructural logic point of view. The fifth chapter shows that each of the three main approaches to the concept of logical consequence (model-theoretic, proof-theoretic and dialogical) supplies a framework sufficiently general to establish pluralism. In short, the dissertation is a defence of logical pluralism.

[pt] A teoria da prova tradicional da lógica proposicional trata provas cujos tamanhos podem ser demasiado grandes. Estudos teóricos de prova descobriram diferenças exponenciais entre provas normais ou livres de corte e suas respectivas provas não-normais. Assim, o uso de grafos-de-prova, ao invés de árvores ou listas, para representar provas está se tornando mais popular entre teóricos da prova. Os grafos-de-prova servem como uma forma de proporcionar uma melhor simetria para a semântica de provas e uma maneira de estudar a complexidade das provas proposicionais. O objetivo deste trabalho é reduzir o peso/tamanho de deduções. Apresentamos formalismos de grafos de prova que visam capturar a estrutura lógica de uma dedução e uma forma de facilitar a visualização das propriedades. A vantagem destes formalismos é que as fórmulas e sub-deduções em dedução natural, preservadas na estrutura de grafo, podem ser compartilhadas eliminando sub-deduções desnecessárias resultando na prova reduzida. Neste trabalho, damos uma definição precisa de grafos de prova para a lógica puramente implicacional, logo estendemos esse resultado para a lógica proposicional completa e mostramos como reduzir (eliminando fórmulas máximas) essas representações de tal forma que um teorema de normalização pode ser provado através da contagem do número de fórmulas máximas na derivação original. A normalização forte será uma consequência direta desta normalização, uma vez que qualquer redução diminui as medidas correspondentes da complexidade da derivação. Continuando com o nosso objetivo de estudar a complexidade das provas, a abordagem atual também fornece representações de grafo para lógica de primeira ordem, a inferência profunda e lógica bi-intuitionista. / [en] Traditional proof theory of Propositional Logic deals with proofs which size can be huge. Proof theoretical studies discovered exponential gaps between normal or cut free proofs and their respective non-normal proofs. Thus, the use of proof-graphs, instead of trees or lists, for representing proofs is getting popular among proof-theoreticians. Proof-graphs serve as a way to provide a better symmetry to the semantics of proofs and a way to study complexity of propositional proofs and to provide more efficient theorem provers, concerning size of propositional proofs. The aim of this work is to reduce the weight/size of deductions. We present formalisms of proof-graphs that are intended to capture the logical structure of a deduction and a way to facilitate the visualization. The advantage of these formalisms is that formulas and subdeductions in Natural Deduction, preserved in the graph structure, can be shared deleting unnecessary sub-deductions resulting in the reduced proof. In this work, we give a precise definition of proof-graphs for purely implicational logic, then we extend this result to full propositional logic and show how to reduce (eliminating maximal formulas) these representations such that a normalization theorem can be proved by counting the number of maximal formulas in the original derivation. The strong normalization will be a direct consequence of such normalization, since that any reduction decreases the corresponding measures of derivation complexity. Continuing with our aim of studying the complexity of proofs, the current approach also give graph representations for first order logic, deep inference and bi-intuitionistic logic.

Logical pluralism from historical perspective - Abstract The plurality of logics is understood as a challenge to seek a deeper understanding of the na- ture and import of logic. Two basic approaches to demarcation of logic are considered, the model-theoretic and the proof-theoretic one. Investigation of the history which led to these two appraoches identifies the postion of logic in Kant's epistemology as crucial for the devel- opment. An analogical development from Kant's conception of geometry to the plurality of geometric theories leads to a holistic view both of geometry and of logic. It furthermore proves essential to understand the pragmatic import of logic. Given the problems tied to the attempts to demarcate logic, inferentialism and logical expressivism are arrived at as jointly provid- ing the most appropriate account. These approaches are developed into a conception which stresses, in line with the historical perspective of the work, the ability of logic to develop.