It is well known that mathematics students have to be able to understand and prove theorems. From our experience we know that engineering students should also be able to do the same, since a good theoretical knowledge of mathematics is essential for solving practical problems and constructing models. Proving theorems gives students a much better understanding of the subject, and helps them to develop mathematical thinking. The proof of a theorem consists of a logical chain of steps. Students should understand the need and the legitimacy of every step. Moreover, they have to comprehend the reasoning behind the order of the chain’s steps. For our research students were provided with proofs whose steps were either written in a random order or had missing parts. Students were asked to solve the \"puzzle\" – find the correct logical chain or complete the proof. These \"puzzles\" were meant to discourage students from simply memorizing the proof of a theorem. By using our examples students were encouraged to think independently and came to improve their understanding of the subject.

La sécurité des applications sur le web est totalement dépendante de leur design et de la robustesse de l'implémentation des algorithmes et protocoles cryptographiques sur lesquels elles s'appuient. Cette thèse présente une nouvelle approche, applicable à de larges projets, pour vérifier l'état de l'art des algorithmes de calculs sur les grands nombres, tel que rencontrés dans les implémentations de référence. Le code et les preuves sont réalisés en F*, un langage orienté preuve et qui offre un système de types riche et expressif. L'implémentation et la vérification dans un langage d'ordre supérieur permet de maximiser le partage de code mais nuit aux performances. Nous proposons donc un nouveau langage, Low*, qui encapsule un sous ensemble de C en F* et qui compile vers C de façon sûre. Low* conserve toute l'expressivité de F* pour les spécifications et les preuves et nous l'utilisons pour implémenter de la cryptographie, en y intégrant les optimisations des implémentations de référence. Nous vérifions ce code en termes de sûreté mémoire, de correction fonctionnelle et d'indépendance des traces d'exécution vis à vis des données sensibles. Ainsi, nous présentons HACL*, une bibliothèque cryptographique autonome et entièrement vérifiée, dont les performances sont comparables sinon meilleures que celles du code C de référence. Plusieurs algorithmes de HACL* font maintenant partie de la bibliothèque NSS de Mozilla, utilisée notamment dans Firefox et dans RedHat. Nous appliquons les mêmes concepts sur miTLS, une implémentation de TLS vérifiée et montrons comment étendre cette méthodologie à des preuves cryptographiques, du parsing de message et une machine à état. / The security of Internet applications relies crucially on the secure design and robust implementations of cryptographic algorithms and protocols. This thesis presents a new, scalable and extensible approach for verifying state-of-the-art bignum algorithms, found in popular cryptographic implementations. Our code and proofs are written in F∗, a proof-oriented language which offers a very rich and expressive type system. The natural way of writing and verifying higher-order functional code in F∗ prioritizes code sharing and proof composition, but this results in low performance for cryptographic code. We propose a new language, Low∗, a fragment of F∗ which can be seen as a shallow embedding of C in F∗ and safely compiled to C code. Nonetheless, Low∗ retains the full expressiveness and verification power of the F∗ system, at the specification and proof level. We use Low∗ to implement cryptographic code, incorporating state-of-the-art optimizations from existing C libraries. We use F∗ to verify this code for functional correctness, memory safety and secret in- dependence. We present HACL∗, a full-fledged and fully verified cryptographic library which boasts performance on par, if not better, with the reference C code. Several algorithms from HACL∗ are now part of NSS, Mozilla’s cryptographic library, notably used in the Firefox web browser and the Red Hat operating system. Eventually, we apply our techniques to miTLS, a verified implementation of the Transport Layer Security protocol. We show how they extend to cryptographic proofs, state-machine implementations and message parsing verification.

We study the problem of secure key establishment. We critically examine the security models of Bellare and Rogaway (1993) and Canetti and Krawczyk (2001) in the computational complexity approach, as these models are central in the understanding of the provable security paradigm. We show that the partnership definition used in the three-party key distribution (3PKD) protocol of Bellare and Rogaway (1995) is flawed, which invalidates the proof for the 3PKD protocol. We present an improved protocol with a new proof of security. We identify several variants of the key sharing requirement (i.e., two entities who have completed matching sessions, partners, are required to accept the same session key). We then present a brief discussion about the key sharing requirement. We identify several variants of the Bellare and Rogaway (1993) model. We present a comparative study of the relative strengths of security notions between the several variants of the Bellare-Rogaway model and the Canetti-Krawczyk model. In our comparative study, we reveal a drawback in the Bellare, Pointcheval, and Rogaway (2000) model with the protocol of Abdalla and Pointcheval (2005) as a case study. We prove a revised protocol of Boyd (1996) secure in the Bellare-Rogaway model. We then extend the model in order to allow more realistic adversary capabilities by incorporating the notion of resetting the long-term compromised key of some entity. This allows us to detect a known weakness of the protocol that cannot be captured in the original model. We also present an alternative protocol that is efficient in both messages and rounds. We prove the protocol secure in the extended model. We point out previously unknown flaws in several published protocols and a message authenticator of Bellare, Canetti, and Krawczyk (1998) by refuting claimed proofs of security. We also point out corresponding flaws in their existing proofs. We propose fixes to these protocols and their proofs. In some cases, we present new protocols with full proofs of security. We examine the role of session key construction in key establishment protocols, and demonstrate that a small change to the way that session keys are constructed can have significant benefits. Protocols that were proven secure in a restricted Bellare-Rogaway model can then be proven secure in the full model. We present a brief discussion on ways to construct session keys in key establishment protocols and also prove the protocol of Chen and Kudla (2003) secure in a less restrictive Bellare-Rogaway model. To complement the computational complexity approach, we provide a formal specification and machine analysis of the Bellare-Pointcheval-Rogaway model using an automated model checker, Simple Homomorphism Verification Tool (SHVT). We demonstrate that structural flaws in protocols can be revealed using our framework. We reveal previously unknown flaws in the unpublished preproceedings version of the protocol due to Jakobsson and Pointcheval (2001) and several published protocols with only heuristic security arguments. We conclude this thesis with a listing of some open problems that were encountered in the study.

The aim of this thesis is to present an extension to the string graphs of Dixon, Duncan and Kissinger that allows the finite representation of certain infinite families of graphs and graph rewrite rules, and to demonstrate that a logic can be built on this to allow the formalisation of inductive proofs in the string diagrams of compact closed and traced symmetric monoidal categories. String diagrams provide an intuitive method for reasoning about monoidal categories. However, this does not negate the ability for those using them to make mistakes in proofs. To this end, there is a project (Quantomatic) to build a proof assistant for string diagrams, at least for those based on categories with a notion of trace. The development of string graphs has provided a combinatorial formalisation of string diagrams, laying the foundations for this project. The prevalence of commutative Frobenius algebras (CFAs) in quantum information theory, a major application area of these diagrams, has led to the use of variable-arity nodes as a shorthand for normalised networks of Frobenius algebra morphisms, so-called "spider notation". This notation greatly eases reasoning with CFAs, but string graphs are inadequate to properly encode this reasoning. This dissertation firstly extends string graphs to allow for variable-arity nodes to be represented at all, and then introduces !-box notation – and structures to encode it – to represent string graph equations containing repeated subgraphs, where the number of repetitions is abitrary. This can be used to represent, for example, the "spider law" of CFAs, allowing two spiders to be merged, as well as the much more complex generalised bialgebra law that can arise from two interacting CFAs. This work then demonstrates how we can reason directly about !-graphs, viewed as (typically infinite) families of string graphs. Of particular note is the presentation of a form of graph-based induction, allowing the formal encoding of proofs that previously could only be represented as a mix of string diagrams and explanatory text.

Diese Arbeit nutzt und verfeinert Methoden der Komplexitätstheorie, um mit diesen die Komplexität dünner Instanzen zu untersuchen. Dazu gehören etwa Graphen mit wenigen Kanten oder Formeln mit wenigen Bedingungen beschränkter Weite. Dabei ergeben sich zwei natürliche Fragestellungen: (a) Gibt es einen effizienten Algorithmus, der beliebige Instanzen eines NP-schweren Problems auf äquivalente, dünne Instanzen reduziert? (b) Gibt es einen Algorithmus, der dünne Instanzen NP-schwerer Probleme bedeutend schneller löst als allgemeine Instanzen gelöst werden können? Wir formalisieren diese Fragen für verschiedene Probleme und zeigen, dass positive Antworten jeweils zu komplexitätstheoretischen Konsequenzen führen, die als unwahrscheinlich gelten. Frage (a) wird als Kommunikation modelliert, in der zwei Akteure kooperativ eine NP-schwere Sprache entscheiden möchten und dabei möglichst wenig kommunizieren. Unter der komplexitätstheoretischen Annahme, dass coNP keine Teilmenge von NP/poly ist, erhalten wir aus unseren Ergebnissen erstaunlich scharfe untere Schranken für interessante Parameter aus verschiedenen Teilgebieten der theoretischen Informatik. Im Speziellen betrifft das die Ausdünnung von Formeln, die Kernelisierung aus der parameterisierten Komplexitätstheorie, die verlustbehaftete Kompression von Entscheidungsproblemen, und die Theorie der probabilistisch verifizierbaren Beweise. Wir untersuchen Fragestellung (b) anhand der Exponentialzeitkomplexität von Zählproblemen. Unter (Varianten) der bekannten Exponentialzeithypothese (ETH) erhalten wir exponentielle untere Schranken für wichtige #P-schwere Probleme: das Berechnen der Zahl der erfüllenden Belegungen einer 2-KNF Formel, das Berechnen der Zahl aller unabhängigen Mengen in einem Graphen, das Berechnen der Permanente einer Matrix mit Einträgen 0 und 1, das Auswerten des Tuttepolynoms an festen Punkten. / In this thesis, we use and refine methods of computational complexity theory to analyze the complexity of sparse instances, such as graphs with few edges or formulas with few constraints of bounded width. Two natural questions arise in this context: (a) Is there an efficient algorithm that reduces arbitrary instances of an NP-hard problem to equivalent, sparse instances? (b) Is there an algorithm that solves sparse instances of an NP-hard problem significantly faster than general instances can be solved? We formalize these questions for different problems and show that positive answers for these formalizations would lead to consequences in complexity theory that are considered unlikely. Question (a) is modeled by a communication process, in which two players want to cooperatively decide an NP-hard language and at the same time communicate as few as possible. Under the complexity-theoretic hypothesis that coNP is not in NP/poly, our results imply surprisingly tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. We study the question (b) for counting problems in the exponential time setting. Assuming (variants of) the exponential time hypothesis (ETH), we obtain asymptotically tight, exponential lower bounds for well-studied #P-hard problems: Computing the number of satisfying assignments of a 2-CNF formula, computing the number of all independent sets in a graph, computing the permanent of a matrix with entries 0 and 1, evaluating the Tutte polynomial at fixed evaluation points.

A família sofreu, no século passado, séc. XX diversas mudanças. As próprias relações mudaram: industrialização e urbanização aceleradas, emancipação da mulher, duas Guerras Mundiais que alavancaram o tema dos direitos humanos, com evidente repercussão nos direitos da personalidade. Tudo isso alterou o perfil da família e das relações que ocorrem em seu seio. Na verdade, estabeleceu-se uma perspectiva limitadora do poder em geral, da ascendência sobre outrem, inclusive no âmbito do pátrio poder, hoje poder familiar. Sem embargo disso, passada a euforia inicial, é hora de buscar caminhos para a plena efetivação desses direitos. Isso dependerá, em grande medida, da própria interpretação judicial, já que na decisão jurisdicional o ordenamento convertido numa fórmula específica para a solução daquela lide atinge o seu ápice. Se a afetividade e a grita por justiça e ética nas relações familiares é inafastável, mais do que isso, é louvável, porque consagra a dignidade da pessoa humana, por outro lado, a ideologia e a patrulha moral em temas existenciais devem ser evitadas. Ativismo judicial não se confunde com invasividade. A intrujice do Estado na família pela função legislativa, executiva ou judiciária deve incentivar um repensar das próprias expectativas que os operadores do Direito, sobretudo do Direito de Família, possuem a respeito do potencial transformativo de seus saberes. Assim, sempre buscando o justo termo, a dissertação examina as hipóteses de intervenção judicial no exercício abusivo do poder familiar, tanto na dimensão patrimonial quanto na dimensão existencial. Na primeira, analisa-se a administração dos bens dos filhos, o usufruto que, por lei, lhe é correlato e sua interpretação à luz do princípio do melhor interesse da criança e do adolescente. Na segunda, o objeto da investigação é o ponto ótimo de equilíbrio entre a intervenção que concretiza os direitos e a intervenção invasiva, errônea. Surgem ponderações sobre a ideologia e sua influência na exegese judicial, em temas como alienação parental e abandono afetivo que habitam o novo léxico deste Direito de Família sequioso de substância o qual, entretanto, não pode abdicar de uma postura autocrítica sob pena de manietar as próprias possibilidades de realização pessoal que alega defender. / Family underwent several changes in the last century, the twentieth century. The very relationships did change: accelerated (rapid) industrialization and urbanization, women´s emancipation, two World Wars, levered the human rights subject, with obvious repercussion on the rights of personality. All of that has modified family profile and the relationships that occur within its core. Actually, in general, a limiting perspective of power was established on the ascendancy over the other, inclusively in the extent of parental power, currently said family, or parental authority. With no embargo of this, after leaving behind the initial euphoria, now is the moment to look for ways towards the thorough accomplishment of these rights. This will depend, largely, on the judicial interpretation, for in the jurisdictional decision converted into a specific formula aimed at the solution of that dispute, it reaches its climax. If, on one hand, affectivity and the outcry for justice and ethics within family relationships cannot be set apart, and, more than that, they are praiseworthy - for they consecrate dignity of the individual - on the other hand, when it comes to existential matters, ideology and moral patrolling ought to be avoided. Judicial activism does not confound with invasiveness. State intrusion on family through legislative, or executive, or judiciary activity, should encourage a review of the very expectations that Law operating professionals have particularly those in the Family Law field regarding the transformational potential of their knowledge. Therefore, looking always for the right boundary, the dissertation investigates the hypotheses for judicial intervening in abusive family authority, considering not only property dimension, but also the existential. On the first we analyze the administration of assets of sons, the usufruct that by force of law correlates to it, and its interpretation in the light of best interest for child and adolescent. On the second, the object of our investigation is the optimal balance point between intervention that makes rights concrete, and the invasive, erroneous interference. We ponder over ideology and its influence on the judicial exegesis, in subjects such as parental alienation and affective abandonment, which dwell in this Family Law new lexicon, avid for substance, but which, however, cannot waive from a self-criticism posture, under penalty of handcuffing the very own possibilities of personal fulfillment it alleges to defend.

Esta Tese aborda, de modo original e pioneiro, importantes aspectos da Engenharia de Fundações do Sul de Minas: a) sistematização de conhecimentos sobre a Geologia regional; b) identificação e caracterização da prática de fundações; c) definição (com a formação de um banco de dados) dos perfis mais representativos do subsolo de suas principais cidades; d) estudo dos parâmetros físicos, químicos e geomecânicos de um solo típico; e) implantação de campo experimental de fundações da Universidade Federal de Lavras, com a realização de provas de carga. Grande ênfase foi dada aos itens (a), (c) e (e). Priorizou-se o estudo das fundações de baixa capacidade de carga, no estudo do comportamento carga-recalque de ensaios de placa, de provas de carga a compressão em estacas-broca isoladas e de tubulões curtos instrumentados. Destacam-se as análises sobre os efeitos de forma, profundidade, melhoramento do terreno de fundação e de inundação nas fundações rasas e da variação L/d na resistência lateral unitária das estacas, sendo valorizadas as fórmulas empíricas com base no SPT. São apresentadas fórmulas de previsão de carga, em função do SPT, para sapatas, estacas de pequeno diâmetro e tubulões curtos e um estudo de custos, onde se mostra que a opção indiscriminada por tubulões é inadequada para certas faixas de carga de trabalho. Adicionalmente, são feitas recomendações para intensificar o uso de sondagens tendo em vista a grande variabilidade das propriedades dos solos regionais e para aumentar os fatores de segurança nestas fórmulas onde houver possibilidade de ocorrência de colapso no solo. / This work presents, at time, important aspects of Foundation Engineering at Southern Region of Minas Gerais State: a) systematization of the knowledge about regional geology; b) identification and characterization of practice in foundations; c) definition (though establishment of a data base) of most representative sub-soil profiles at main cities at the region; d) study of physical, chemical and geomechanical parameters of a typical soil; e) implementation of a experimental field for foundation studies at Federal University of Lavras, by execution of load tests. A large emphasis was given to items a, c and e. The study of foundations of low load capacity was prioritized when testing plates, isolated piles under compression and short drilled piers with sensors. Analysis such as form effects, depth, soil improvement and flooding on shallow foundations and variation of L/d on the lateral unity resistance by emphasizing the empiral equations based on SPT were all pointed out. Mathematical equations are presented for load estimation as function of SPT for small diameter piles and short drilled piers as well as a cost study where it can bem shown that the undistinguished alternative for piers is inadequate for some load values. In addition, due to soil spatial variability and safety factor increment on soils subject for colapse, recommendations on intensive use of SPT test are given.

Made available in DSpace on 2016-04-27T17:13:02Z (GMT). No. of bitstreams: 1 aguinaldo rama.pdf: 834376 bytes, checksum: 115c94033b3852d2fd9618f3cb19a427 (MD5) Previous issue date: 2005-11-08 / Made available in DSpace on 2016-08-25T17:25:34Z (GMT). No. of bitstreams: 2 aguinaldo rama.pdf.jpg: 1943 bytes, checksum: cc73c4c239a4c332d642ba1e7c7a9fb2 (MD5) aguinaldo rama.pdf: 834376 bytes, checksum: 115c94033b3852d2fd9618f3cb19a427 (MD5) Previous issue date: 2005-11-08 / We present an analysis of three collections of mathematics text books for primary school. The choice of the collections is oriented by the synthesis presented in the guidebook of the Plano Nacional do Livro Didático. The goal of the analysis is to investigate the way the authors approach the integers, mainly the concept of divisibility. Our main focus concerns proof strategies and the use of challenging problem situations. Two other aspects are considered: relations between integers and other mathematical subjects, particularly álgebra and geometry; articulations between old and new contents, and the resulting review of subjects, during which it is expectec that the learners growing maturity is taken into consideration. We verify that one of the collections presents good informal proofs, suitable for this learning level, using a variety of methods; it also properly explores the potencial of problems related to integers. The second collection presents some convincing proofs together with unsuitable ones, while the third one states several properties without exibiting explanation concerns. The last ones provide few problems demanding a greater sophistication of reasoning. The three collections present the subject in 5th and 6th grades, in the context of natural numbers, and no overview is provided after the introduction of negative numbers. The second part of the work is dedicated to middle school. We examine the eleven collections recomended by the guidebook of the Plano Nacional do Livro do Ensino Médio. We analyse the review of the integers at the beggining of the first books of the collections. Generally speaking, the review is superficial; divisibility concepts including negatives is explored only in the context of exercises. Few more elaborated problems are proposed Finally, we suggest actitities for middle scholl relating integers to a variety of themes, as geometry, complex number, polynomials, combinatorial analysis / Apresentamos uma análise de três coleções de livros de matemática do ensino fundamental. Tomamos como referência para a escolha dos livros as sínteses constantes no guia do Plano Nacional do Livro Didático. O objetivo dessa análise é verificar a forma como os autores abordam os números inteiros, em particular o conceito de divisibilidade. Damos maior atenção para dois aspectos: as estratégias adotadas para demonstrações referentes ao assunto, e o uso de situações-problema desafiadoras. Também consideramos dois outros aspectos: articulações entre números inteiros e as demais áreas da matemática, em particular a álgebra e a geometria; articulações entre conteúdos novos e já conhecidos, e as conseqüentes retomadas de temas, nas quais espera-se que o suposto amadurecimento dos estudantes seja considerado. Constatamos que uma das coleções apresenta boas provas informais, adequadas para esse estágio de aprendizagem, usando métodos variados; também explora de modo conveniente o potencial de problemas envolvendo números inteiros. A segunda coleção apresenta algumas demonstrações convincentes, e outras inadequadas; a terceira enuncia diversas propriedades sem preocupação com justificativas. Nessas duas últimas, poucos problemas exigem maior sofisticação de raciocínio. Nas três coleções o assunto é enfocado quase exclusivamente na 5º e na 6º série, no âmbito dos números naturais, não sendo retomado no contexto dos inteiros, após a introdução dos negativos. A segunda parte do trabalho é dedicada ao ensino médio. Consultamos as onze coleções recomendas pelo guia do Plano Nacional do Livro do Ensino Médio. Analisamos a revisão dos inteiros feita no início dos primeiros livros dessas coleções. De modo geral, essa retomada é superficial; o conceito de divisibilidade entre inteiros, incluindo os negativos, pode ser apreciado somente em uns poucos exercícios. Poucos problemas mais elaborados são propostos. Finalizamos com sugestões de atividades para o ensino médio envolvendo números inteiros, em conexão com assuntos variados, tais como: geometria, números complexos, polinômios, análise combinatória

Submitted by ROSEMEIRE DE FATIMA BATISTELA null (rosebatistela@hotmail.com) on 2017-02-11T02:22:43Z No. of bitstreams: 1 tese finalizada 10 fevereiro 2017 com a capa.pdf: 2263896 bytes, checksum: 413948c6a47fb47a21e1587275d29c03 (MD5) / Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2017-02-15T16:56:58Z (GMT) No. of bitstreams: 1 batistela_rf_dr_rcla.pdf: 2263896 bytes, checksum: 413948c6a47fb47a21e1587275d29c03 (MD5) / Made available in DSpace on 2017-02-15T16:56:58Z (GMT). No. of bitstreams: 1 batistela_rf_dr_rcla.pdf: 2263896 bytes, checksum: 413948c6a47fb47a21e1587275d29c03 (MD5) Previous issue date: 2017-02-02 / Apresentamos nesta tese uma proposta de inserção do tema teorema da incompletude de Gödel em cursos de Licenciatura em Matemática. A interrogação norteadora foi: como sentidos e significados do teorema da incompletude de Gödel podem ser atualizados em cursos de Licenciatura em Matemática? Na busca de elaborarmos uma resposta para essa questão, apresentamos o cenário matemático presente à época do surgimento deste teorema, expondo-o como a resposta negativa para o projeto do Formalismo que objetivava formalizar toda a Matemática a partir da aritmética de Peano. Além disso, trazemos no contexto, as outras duas correntes filosóficas, Logicismo e Intuicionismo, e os motivos que impossibilitaram o completamento de seus projetos, que semelhantemente ao Formalismo buscaram fundamentar a Matemática sob outras bases, a saber, a Lógica e os constructos finitistas, respectivamente. Assim, explicitamos que teorema da incompletude de Gödel aparece oferecendo resposta negativa à questão da consistência da aritmética, que era um problema para a Matemática na época, estabelecendo uma barreira intransponível para a demonstração dessa consistência, da qual dependia o sucesso do Formalismo e, consequentemente, a fundamentação completa da Matemática no ideal dos formalistas. Num segundo momento, focamos na demonstração deste teorema expondo-a em duas versões distintas, que para nós se nos mostraram apropriadas para serem trabalhadas em cursos de Licenciatura em Matemática. Uma, como possibilidade de conduzir o leitor pelos meandros da prova desenvolvida por Gödel em 1931, ilustrando-a, bem como, as ideias utilizadas nela, aclarando a sua compreensão. Outra, como opção que valida o teorema da incompletude apresentando-o de maneira formal, portanto, com endereçamentos e objetivos distintos, por um lado, a experiência com a numeração de Gödel e a construção da sentença indecidível, por outro, com a construção formal do conceito de método de decisão de uma teoria. Na sequência, apresentamos uma discussão focada na proposta de Bourbaki para a Matemática, por compreendermos que a atitude desse grupo revela a forma como o teorema da incompletude de Gödel foi acolhido nessa ciência e como ela continuou após este resultado. Nessa exposição aparece que o grupo Bourbaki assume que o teorema da incompletude não impossibilita que a Matemática prossiga em sua atividade, ele apenas sinaliza que o aparecimento de proposições indecidíveis, até mesmo na teoria dos números naturais, é inevitável. Finalmente, trazemos a proposta de como atualizar sentidos e significados do teorema da incompletude de Gödel em cursos de Licenciatura em Matemática, aproximando o tema de conteúdos agendados nas ementas, propondo discussão de aspectos desse teorema em diversos momentos, em disciplinas que julgamos apropriadas, culminando no trabalho com as duas demonstrações em disciplinas do último semestre do curso. A apresentação é feita tomando como exemplar um curso de Licenciatura em Matemática. Consideramos por fim, a importância do trabalho com um resultado tão significativo da Lógica Matemática que requer atenção da comunidade da Educação Matemática, dado que as consequências deste teorema se relacionam com a concepção de Matemática ensinada em todos os níveis escolares, que, muito embora não tenham relação com conteúdos específicos, expõem o alcance do método de produção da Matemática. / In this thesis we present a proposal to insert Gödel's incompleteness theorem in Mathematics Education undergraduate courses. The main research question guiding this investigation is: How can the senses and meanings of Gödel's incompleteness theorem be updated in Mathematics Education undergraduate courses? In answering the research question, we start by presenting the mathematical scenario from the time when the theorem emerged; this scenario proposed a negative response to the project of Formalism, which aimed to formalize all Mathematics based upon Peano’s arithmetic. We also describe Logicism and Intuitionism, focusing on reasons that prevented the completion of these two projects which, in similarly to Formalism, were sought to support mathematics under other bases of Logic and finitists constructs. Gödel's incompleteness theorem, which offers a negative answer to the issue of arithmetic consistency, was a problem for Mathematics at that time, as the Mathematical field was passing though the challenge of demonstrating its consistency by depending upon the success of Formalism and upon the Mathematics’ rationale grounded in formalists’ ideal. We present the proof of Gödel's theorem by focusing on its two different versions, both being accessible and appropriate to be explored in Mathematics Education undergraduate courses. In the first one, the reader will have a chance to follow the details of the proof as developed by Gödel in 1931. The intention here is to expose Gödel’ ideas used at the time, as well as to clarify understanding of the proof. In the second one, the reader will be familiarized with another proof that validates the incompleteness theorem, presenting it in its formal version. The intention here is to highlight Gödel’s numbering experience and the construction of undecidable sentence, and to present the formal construction of the decision method concept from a theory. We also present a brief discussion of Bourbaki’s proposal for Mathematics, highlighting Bourbaki’s group perspective which reveals how Gödel’s incompleteness theorem was important and welcome in science, and how the field has developed since its result. It seems to us that Bourbaki’s group assumes that the incompleteness theorem does not preclude Mathematics from continuing its activity. Thus, from Bourbaki’s perspective, Gödel’s incompleteness theorem only indicates the arising of undecidable propositions, which are inevitable, occurring even in the theory of natural numbers. We suggest updating the senses and the meanings of Gödel's incompleteness theorem in Mathematics Education undergraduate courses by aligning Gödel's theorem with secondary mathematics school curriculum. We also suggest including discussion of this theorem in different moments of the secondary mathematics school curriculum, in which students will have elements to build understanding of the two proofs as a final comprehensive project. This study contributes to the literature by setting light on the importance of working with results of Mathematical Logic such as Gödel's incompleteness theorem in secondary mathematics courses and teaching preparation. It calls the attention of the Mathematical Education community, since its consequences are directly related to the design of mathematics and how it is being taught at all grade levels. Although some of these mathematics contents may not be related specifically to the theorem, the understanding of the theorem shows the broad relevance of the method in making sense of Mathematics.

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