2019.1 FMC2, turmas de Thanos

Horários: 246T34 [14h55–16h35] @ B204 (U1; U2)
246N12 [18h45–20h25] @ A308 (U1; U2; U3)
Sala do prof:A225
Contato:thanos@imd.ufrn.br
Aulas gravadas: 2019.1; 2018.2
Study group: Telegram, atraves de link disponível em notícia do SIGAA [regras]
Monitoria/TA:fmc.imd.ufrn.br (logo)
Horário de atendimento:mande email para marcar (tente primeiro discutir tua dúvida no study group, e na monitoria)
Turmas anteriores: 2018.2; 2018.1; 2017.2; 2017.1; 2016.1

Prerequisitos

É prerequisito ter aprendido bem o conteudo transversal de FMC1. Sem aprender esses assuntos primeiro, não faz sentido se matricular em FMC2. (Obs.: aprenderpassar.)

Então—ANTES de começar—é bom estudar os:

  1. How to prove it, de Velleman (1, 2, 3, 6)
  2. Do fmcbook os capítulos:
    • Linguagens
    • Estratégias de provas
    • Os números naturais: recusão; indução
    • Combinatória enumerativa
    • Teoria elementar de números
    • Congrüências
  3. Mathematical Proofs, de Chartrand, Polimeni, Zhang (0, 2)
  4. Comments on style de James Munkres.
  5. A parte “Writing mathematics” do livro The tools of mathematical reasoning, de Lakins.

(Obs.: estudarler.)

Conteúdo

Conteúdo transversal (durante todas as unidades)
Lógica proposicional e de predicados (linguagem; sintaxe e semântica). Definições e provas. Demonstrações diretas e indiretas, refutações. Definições por recursão – provas por indução. A linguagem de conjuntos, funções, e relações.
Linguagem; Lógica; Recursão; Indução (U0)
Crash course!
Conjuntos, Funções, e Relações (U1)
Conjuntos, sua notação, suas operações, e seus leis. Uniões disjuntas, famílias e partições. Tuplas ordenadas e produto cartesiano. As operações unitárias de união e interseção. As relações de subconjunto, e de pertencer. Multiconjuntos e sequências. Funções, o conceito de função e suas propriedades. Intensão x extensão. Domínio, codomínio. Imagem, pre-imagem. Funções totais e parciais, injetivas, sobrejetivas, bijetivas. Aridade. Função constante, função identidade, projeções, funções características. Funções recursivas; recursão mutual. Funções de ordem superior. A notação de λ-calculus. Funções x predicados. Relações e suas propriedades. Relações de equivalência, clásses de equivalência. Operações em relações, inversão, composição, fechos.
Elementos de Álgebra abstrata (U2)
Conjuntos com estrutura. Operações. Teoria dos grupos. Demonstrações com o uso de identidades algébricas. Homomorfísmos. Outras estruturas: aneis, monoides, reticulados. Álgebras booleanas.
Elementos de Teoria de Conjuntos (U3)
Enumerações e conceito intuitivo de cardinalidade. Paradoxos e os axiomas Zermelo–Fraenkel. Representações de matemática (traduções). Os números naturais; axiomas Peano.
Elementos de Teoria de Ordem (U3)
Ordens parciais, totais, densas, bem-fundadas. Diagramas de Hasse. Elementos notáveis (majorantes, máximos, supremos). Conjuntos ordenados, reticulados, reticulados completos. Construções de conjutos ordenados. Dualidade. Ordens canônicas, ordens lexicográficas. Monotonicidade. Teoremas de ponto fixo. Conjuntos bem-ordenados.
Aplicações e assuntos auxiliares
Relações bem-fundadas e indução transfinita. Números ordinais. Limites de computação. Noções de decidibilidade e de semi-decidibilidade. λ-calculus, lógica combinatória. Elementos de teoria dos tipos. Noções de semántica de linguagens de programação. Y-combinator, fixpoints e recursão. Axiom of choice e suas conseqüências. Tipos de dados algébricos. Programação funcional. Programação lógica. Bancos de dados.

Bibliografia

(Conhece o libgen.io?)

Principal

Auxiliar

Para cada um dos assuntos que tratamos, procure a secção «Leitura complementar» no capítulo correspondente do fmcbook para mais referências.

  • Pierce et al: Software Foundations, Volume 1: Logical Foundations [SF1]
  • Velleman: How to prove it (1–3)
  • Pinter: A book of abstract algebra (2–5, 6, 12, 17)
  • Davey & Priestley: Introduction to lattices and order (1, 2)
  • Paul Halmos: Naïve set theory
  • Moschovakis: Notes on set theory (1, 2, 3–5, 6–7)
  • Goldrei: Classic set theory, for guided independent study (4, 7, 8)
  • Raymond Smullyan: Satan, Cantor, and Infinity
  • Raymond Smullyan: A beginner's guide to mathematical logic (Volume 1)
  • Paul Halmos: Linear Algebra Problem Book (1)
  • Birkhoff & Mac Lane: A survey of modern algebra (1.11; 1.1–1.5, 1.10, 1.12)
  • Aluffi: Algebra: Chapter 0
  • Mac Lane & Birkhoff: Algebra (1.1–1.3)
  • Herstein: Topics in Algebra (2.1–2.5 [skip # and *])
  • Simmons: Introduction to topology and modern analysis (1)
  • Munkres: Topology (1)
  • Loomis & Sternberg: Advanced Calculus (0)
  • João Marcos: Lógica Aplicada à Computação website (TdC, R&I)

Programação

Links

Dicas

Avaliação

Pontos

A disciplina é dividida em 3 unidades (vejá Conteudo). Em cada unidade o aluno vai receber de 0 a 100 pontos. As provas escritas de cada unidade terão 100 pontos em total. (Para pegar uma idéia dessas provas, olhe nos sites das minhas turmas de FMC2 de semestres passados.)

Alem desses pontos, um aluno pode ganhar pontos extra: por participação; por homework; ou por provas-surpresas. Esses pontos valem igualmente com os pontos de prova escrita. Estou tenando ao máximo ser justo com esses pontos, mas nenhuma justificativa será dada por ganhar (ou não ganhar, ou perder!) pontos extra. Umas regras: (1) nunca dê uma resposta que tu não pensou sozinho; (2) não tente “forçar a barra” dando respostas aleatórias nas minhas perguntas com objetivo único de ganhar pontos extra.

Umas provas escritas podem ter pontos bônus. Esses são pontos que são condicionalmente considerados: para considerá-los um aluno precisa ter pelo menos 50pts normais (não-bônus). As questões que valem pontos-bônus são em geral em assuntos auxiliares que, mesmo que merecem ser reconhecidos, não devem ser determinantes para aprovar na disciplina.

Presenças

Veja notícia no SIGAA para informações sobre presenças, chamadas, plickers, etc.

Provas

As provas principais serão avisadas com antecedência de pelo menos 48 horas.

Provinha 0

  • Provinha 0 (pts: 0; bônus: 0) (dia: 16/02/2019)
    { uncensored, answers }

Homework

Obs.: Estudar um assunto dum livro obviamente inclui resolver todos os exercícios e problemas. «Até» é sempre inclusivo.

09/01/2019

  1. Estude os ítens que tenho nos prerequisitos.
  2. Brinque com Haskell ou PureScript.
  3. Estude a (pouca) coisa que tá escrita no capítulo «Estratégias de provas» do fmcbook.
  4. Estude e resolve os exercícios/problemas do capítulo 3 de Velleman.
  5. Estude o capítulo «Linguagens» do fmcbook.
  6. Estude o capítulo «A linguagem de lógica proposicional» do fmcbook.
  7. Estude os capítulos 1–2 de Velleman.
  8. Estude brutalmente o capítulo «Os números naturais: recursão; indução» do fmcbook, e assista minhas aulas relevantes do FMC2/2018.2 (as 3 primeiras aulas).
  9. Installe o Coq; dê uma lida no «Preface» do SF1 (link na Bibliografia); estude o capítulo «Basics» do SF1.

04/02/2019

  1. Estude as «Prova 0» dos semestres passados (2017.1; 2017.2; 2018.1; 2018.2). Tente resolvê-las sozinho. Depois, leia bem todas as correções digitalizadas dos alunos dos semestres anteriores, para aproveitar dos comentários disponíveis. (Melhor estudar isso «por página».)

13/02/2019

  1. Estude as poucas coisas que estão escritas no Capítulo I
  2. Capítulo 3: até §24
  3. Problemas: Π3.1–Π3.5.

16/02/2019

  1. Capítulo 3
  2. Capítulos 4–5

Pontos extra

Nenhum ponto extra por enquanto.

Histórico de aulas

13/02/2019: Introdução [video]

  • Apresentação dos assuntos principais
  • Erros comuns:
    • Type error
    • Erro de lógica
    • Erro de matemática
    • Erro de semântica
  • Os típos principais: afirmações (tbm: proposições); objetos (tbm: individuais)
  • Diferença entre as duas frases:
    • «Se __A__, (então) __B__.»
    • «Como __A__, (logo) __B__.»
  • Os dois erros principais em definições:
    • Não aceitar objetos que deveriam ser aceitos
    • Aceitar objetos que não deveriam ser aceitos
  • →: ``somente se''; ←: ``se''
  • O significado da palavra «equivalente» em matemática
  • Noções primitivas – Definições
  • O contexto duma definição
  • Exemplos de definições na geometria euclideana.
  • Axiomas – Teoremas
  • Sinônimos de «teorema» e seus usos: lema, corolário
  • Hipótese; tese
  • Programando programas vs. provando teoremas
  • Lemmata como funções e bibliotecas de programação
  • Sintaxe vs. semântica
  • Uma linguagem para expressões aritméticas
  • Árvores de derivação
  • Parsing: de forma linear para arvore sintática

15/02/2019: Linguagens [video]

  • Números vs. numerais vs. dígitos
  • A notação BNF
  • Uma gramática em BNF para a linguagem de expressões aritmêticas
  • meta-: linguagens e metalinguagens; variáveis e metavariáveis
  • BNF para a linguagem de lógica proposicional
  • Limitações da linguagem da lógica proposicional
  • A linguagem de FOL

16/02/2019: Provinha 0

Futuro (fluido)

18/02/2019: Linguagens; Demonstrações

  • Igualdade sintáctica vs. denotacional
  • Açúcar sintáctico e abreviações
  • Prova (demonstração) vs. refutação
  • Não use nem «sendo» nem «com»!
  • Uma prova errada não quis dizer teorema errado
  • Conseqüência de teorema errado não quis dizer que a conclusão é errada
  • «A ⇒ B ⇒ ... ⇒ true» e daí?
  • Demonstrações: como atacar e como usar cada proposição

20/02/2019: Nats; recursão; indução

22/02/2019: Nats; recursão; indução

25/02/2019: Conjuntos

27/02/2019: Conjuntos

01/03/2019: Conjuntos

08/03/2019: Conjuntos

11/03/2019

13/03/2019

15/03/2019

18/03/2019

20/03/2019

22/03/2019

25/03/2019

27/03/2019

29/03/2019

01/04/2019

03/04/2019

05/04/2019

08/04/2019

10/04/2019

12/04/2019

15/04/2019

17/04/2019

22/04/2019

24/04/2019

26/04/2019

29/04/2019

03/05/2019

06/05/2019

08/05/2019

10/05/2019

13/05/2019

15/05/2019

17/05/2019

20/05/2019

22/05/2019

24/05/2019

27/05/2019

29/05/2019

31/05/2019

03/06/2019

05/06/2019

07/06/2019

10/06/2019

12/06/2019

14/06/2019

17/06/2019

19/06/2019

21/06/2019

26/06/2019

28/06/2019

Last update: Sat Feb 16 09:52:24 -03 2019