2021.2 FMC1, turma de Thanos

Horários sincronizados: (quando tiver) será dentro dos 246N12 [18h45–20h25] 246N34 [20h35–22h15]
Contato:thanos@imd.ufrn.br
Playlists: FMC1 2019.2 (aulas gravadas)
TeX / LaTeX / ConTeXt (minicurso e sermões)
Monitoria/TA: fmc.imd.ufrn.br
Turmas anteriores: ..

Info

Pré-requisitos

É pré-requisito ter aprendido bem o conteudo das disciplinas de matemática do primeiro semestre., e (obviamente) do ensino médio também:

  • A Matemática do Ensino Médio, vol I de Lima, Carvalho, Wagner, Morgado (para esta disciplina os mais relevantes pré-requisitos são os Cap. 1–4)

(Obs.: aprenderpassar.)

Alem disso, é pré-requisito que os alunos matriculados tem tempo e vontade para estudar, fazer os trabalhos atribuídos, etc.

(Obs.: estudarler.)

ANTES de começar—é bom ler os:

  1. Comments on style de James Munkres.
  2. A parte “Writing mathematics” do livro The tools of mathematical reasoning, de Lakins.

Disclaimer. Eu suponho que os alunos desta turma verificaram os pré-requisitos da disciplina e assumam responsabilidade sobre o seu conhecimento. Lembrete:

pré-requisito

substantivo masculino

  1. condição prévia indispensável para se alcançar algo, seguir uma formação, fazer um curso, ocupar uma função etc.
  2. *(pedagogia)* num currículo, disciplina cursada obrigatoriamente antes de outra, por envolver conhecimentos prévios necessários ao estudo da segunda.

Conteúdo

Conteúdo transversal (durante todas as unidades)
Lógica proposicional e de predicados (linguagem; sintaxe e semântica). Definições e demonstrações. Demonstrações diretas e indiretas, refutações. Definições por recursão – provas por indução. Os números. A linguagem de funções.
Linguagem; Típos; (U0)
Crash course!
Logica, Demonstrações; Naturais, Recursão, Indução; (U1)
Teoria dos números; Análise combinatória (U2)
Teoria dos números (U3)

Bibliografia

(Conhece o libgen.rs?)

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.

Links

Dicas

Tecnologias e ferramentas necessárias

Obs.: As tecnologías/ferramentas seguintes podem mudar durante a disciplina—exceto a primeira.

  1. PAPEL (um caderno para dedicar à disciplina) e LAPIS/CANETA
  2. TeX / LaTeX / ConTeXt. (Online editor/compilador: Overleaf.)
  3. Um aparelho com câmera e uma ferramenta para escanear teu caderno
  4. Zulip: leia as instruções
  5. Google Meet
  6. O proof assistant Coq para algumas atividades. (Coq à la pastebin: CollaCoq.)
  7. Possivelmente usaremos outros proof assistants e linguagens de programação também.
  8. Git e uma conta no github ou gitlab.
  9. Muito recomendado mas não necessário: um sistema Unix (Minicurso Unix 2019.2)
  10. Muito recomendado mas não necessário: (neo)vim e Emacs

(Instalem e criem uma conta para usar onde necessário.)

Regras

  1. Nunca escreva algo que você mesmo não sabe explicar: (i) o que significa; (ii) seu papel na tua resolução. Por exemplo: um aluno escreveu a frase seguinte na sua demonstração: «Como f é cancelável pela esquerda temos que g=h». Ele deve saber o que significa ser cancelável pela esquerda é também explicar como isso foi usado e/ou o que isso tem a ver com essa parte da sua demonstração.
  2. Qualquer trabalho poderá ser questionado em forma de prova oral via videochamada, em modo privado ou aberto. Se um aluno não consegue explicar o que ele mesmo escreveu numa resolução, será considerado plágio e o aluno será reprovado imediatamente por nota e por faltas.
  3. Participando, nunca dê uma resposta que tu não pensou sozinho.
  4. Não tente “forçar a barra” perguntando ou respondendo coisas aleatórias com objetivo único de ganhar pontos. Os pontos de participação não correspondem em apenas perguntas ou dúvidas que mostram interesse. O interesse é implícito pelo fato que tu escolheu matricular nesta turma—não vale pontos.
  5. Não procurem resoluções em qualquer lugar fora dos indicados em cada homework. O único recurso aceitável para procurar ajuda é o nosso Zulip, especificamente seus canáis públicos (não DM).
  6. Proibido consultar o apêndice de resoluções do fmcbook durante a disciplina exceto quando for explicitamente permitido por mim. (Os apêndices de dicas são permitidos sim.)

Avaliação e faltas

Disclaimer. Eu suponho que os alunos desta turma escolheram se matricular por interesse em aprender seu conteudo. O ideal seria ignorar assuntos irrelevantes de avaliação, presenças, carga horária, etc., e se jogar nos estudos.

Avaliação

A nota final de cada aluno vai ser principalmente baseada em um ou mais dos: (i) provas orais com videochamada em modo privado e/ou aberto; (ii) sua participação (que inclue correação de trabalhos de outros alunos); (iii) suas resoluções de problem sets escritas e submetidas em TeX/LaTeX/ConTeXt; (iv) caderno escaneado com resoluções de homeworks; (v) resoluções em algum proof assistant, possivelmente publicadas em repositório git

Note que:

  • Os problem sets / homeworks podem envolver simular uma prova escrita em tempo real.
  • Cada aluno será responsável para manter organizado e bem escrito o seu caderno com todos os teoremas e exercícios que estudou durante a disciplina.

Presenças / Faltas

As presenças/faltas serão cadastradas baseadas na participação, na entrega dos trabalhos, e na entrega de caderno. Nenhuma dessas coisas é opcional, logo aluno que não as faz com a devida freqüência será reprovado por faltas.

FAQs

Dynamic content

Pontos

Pontos de participação

Problem Sets (PS)

Nenhum por enquanto.

Homework (HW)

Homeworks são atribuidos também: durante as aulas gravadas e no Zulip.

Obs.:

  • Estudar um assunto dum livro obviamente inclui resolver todos os exercícios e problemas.
  • «Até» é sempre inclusivo.
  • Homeworks marcados assim são opcionais; considero o resto obrigatório.
  • Depois de cada aula, um homework é sempre válido, obrigatório, e essencial: sem olhar para teu caderno, defina todas as noções e demonstre TODOS os teoremas da aula;
    while (não conseguiu) {
      estude o assunto;
      tente novamente;
    }
    
  • Exceto quando é explicitamente pedido, faça os homework sem consultar nenhum livro/texto/etc. auxiliar
  • Para os trabalhos de SF1 precisarás o arquivo lf-20210607.tgz. Baixe e abra o arquivo no teu computador; cria um repositorio git nele, e fique trabalhando aí. Se precisar ajuda, use o #tech.

18/10/2021

  1. Capítulo 1: todo

20/10/2021

  1. Capítulo 2: até o primeiro intervalo de problemas.
  2. Capítulo 3: até a «atacando a estrutura lógica duma proposição»

22/10/2021

  1. Capítulo 2: dê uma lida no resto do capítulo sem se preocupar com os detalhes, mas resolva mesmo os exercícios do «2.62: Não-limitações».
  2. Π2.7; Π2.8; Π2.9.
  3. Capítulo 3: até § «real-life exemplos: divisibilidade» (use no teu rascunho o tabuleiro de Dados/Alvos, mas escreva separadamente o texto mesmo (o código) das suas demonstrações.

24/10/2021

  1. Capítulo 3: até o primeiro intervalo de problemas

27/10/2021

  1. Se convença que os ataques e os usos que encontramos até agora fazem todos sentido.
  2. Θ. O √2 é irracional
  3. Discutimos como «passar a negação por dentro» para proposições das formas
    ¬(∀x)[φ(x)] e ¬(∃x)[φ(x)]
    mas não para proposições das formas
    ¬(∀x∈A)[φ(x)] e ¬(∃x∈A)[φ(x)]
    Trate essas também em duas maneiras: (i) malandramente, reduzindo em outros casos que já tratamos; (ii) coraçãomente, argumentando diretamente com o que cada proposição dessas afirma mesmo.
  4. Suponha que A denota uma proposição que tu não tens o direito de saber qual é. Mesmo assim tente demonstrar cada uma das direções, com as «regras do jogo» que temos encontrado até agora. Lembre-se que seguimos a idéia de considerar qualquer ¬P como sinônimo de (P⇒⊥)
    • A ⇒ ¬¬A
    • ¬¬A ⇒ A

29/10/2021

  1. Demonstre sem olhar em nada que √2 é irracional
  2. √6 é irracional?
  3. ³√2 é irracional?
  4. Existem irracionais a,b tal que, aᵇ é racional?
  5. Sem pensar sobre nenhuma idéia nova, enuncie e demonstre uma generalização dos teoremas que demonstramos (sobre o √2 e o √3).
  6. Capítulo 3: até o fim.

03/11/2021

  1. Investigue (demonstre ou refute): Cada número bonito tem raiz irracional.
  2. E o contrário? Cada número que tem raiz irracional é bonito?
  3. Tente demonstrar as duas conjecturas que encontramos na aula.
  4. para todo n natural, demonstre que existe número real √n construindo um segmento no plano cujo comprimento é √n.
  5. podes construir um segmento cujo comprimento é ³√2?

05/11/2021

  1. Jogue (até completar!) o jogo Natural Number Game
  2. [SF1]: Basics.v
  3. Capítulo «Os números naturais»: até §«Demonstrando propriedades de naturais sem indução».
  4. Podemos trocar o «S(n+m)» da (a2) por «Sn+m»?
  5. Proposições de dupla negaço:
    1. P ⇒ ¬¬P
    2. ¬¬P ⇒ P
  6. Comutatividade dos ∨,∧:
    1. (P ∨ Q) ⇒ (Q ∨ P)
    2. (P ∧ Q) ⇒ (Q ∧ P)
  7. Proposições de interdefinabilidade dos ⇒,∨:
    1. (P ⇒ Q) ⇒ (¬P ∨ Q)
    2. (P ⇒ Q) ⇐ (¬P ∨ Q)
    3. (P ∨ Q) ⇒ (¬P ⇒ Q)
    4. (P ∨ Q) ⇐ (¬P ⇒ Q)
  8. Proposições de contraposição:
    1. (P ⇒ Q) ⇒ (¬Q ⇒ ¬P)
    2. (¬Q ⇒ ¬P) ⇒ (P ⇒ Q)
  9. A irrefutabilidade do LEM:
    1. ¬¬(P∨¬P)
  10. A lei de Peirce e sua versão “fraca”:
    1. ((P ⇒ Q) ⇒ P) ⇒ P
    2. ((P ⇒ Q) ⇒ P) ⇒ ¬¬P
  11. Proposições de interdefinabilidade dos ∨,∧:
    1. P∨Q ⇒ ¬(¬P∧¬Q)
    2. P∨Q ⇐ ¬(¬P∧¬Q)
    3. P∧Q ⇒ ¬(¬P∨¬Q)
    4. P∧Q ⇐ ¬(¬P∨¬Q)
  12. As leis de De Morgan para ∨,∧:
    1. ¬(P∨Q) ⇒ (¬P ∧ ¬Q)
    2. ¬(P∨Q) ⇐ (¬P ∧ ¬Q)
    3. ¬(P∧Q) ⇒ (¬Q ∨ ¬P)
    4. ¬(P∧Q) ⇐ (¬Q ∨ ¬P)
  13. Proposições de distributividade dos ∨,∧:
    1. P∧(Q∨R) ⇒ (P∧Q)∨(P∧R)
    2. P∧(Q∨R) ⇐ (P∧Q)∨(P∧R)
    3. P∨(Q∧R) ⇒ (P∨Q)∧(P∨R)
    4. P∨(Q∧R) ⇐ (P∨Q)∧(P∨R)
  14. Currificação
    1. ((P∧Q)⇒R) ⇒ (P⇒(Q⇒R))
    2. ((P∧Q)⇒R) ⇐ (P⇒(Q⇒R))
  15. Reflexividade da ⇒:
    1. P ⇒ P
  16. Weakening and contraction:
    1. P ⇒ (P∨Q)
    2. Q ⇒ (P∨Q)
    3. (P∧Q) ⇒ P
    4. (P∧Q) ⇒ Q
    5. P ⇒ (P∧P)
    6. (P∨P) ⇒ P
  17. As leis de De Morgan para ∃,∀:
    1. ¬(∀x)[φ(x)] ⇒ (∃x)[¬φ(x)]
    2. ¬(∀x)[φ(x)] ⇐ (∃x)[¬φ(x)]
    3. ¬(∃x)[φ(x)] ⇒ (∀x)[¬φ(x)]
    4. ¬(∃x)[φ(x)] ⇐ (∀x)[¬φ(x)]
  18. Proposições de interdefinabilidade dos ∃,∀:
    1. (∃x)[φ(x)] ⇒ ¬(∀x)[¬φ(x)]
    2. (∃x)[φ(x)] ⇐ ¬(∀x)[¬φ(x)]
    3. (∀x)[φ(x)] ⇒ ¬(∃x)[¬φ(x)]
    4. (∀x)[φ(x)] ⇐ ¬(∃x)[¬φ(x)]
  19. Proposições de distributividade de quantificadores:
    1. (∃x)[φ(x) ∧ ψ(x)] ⇒ (∃x)[φ(x)] ∧ (∃x)[ψ(x)]
    2. (∃x)[φ(x) ∧ ψ(x)] ⇐ (∃x)[φ(x)] ∧ (∃x)[ψ(x)]
    3. (∃x)[φ(x) ∨ ψ(x)] ⇒ (∃x)[φ(x)] ∨ (∃x)[ψ(x)]
    4. (∃x)[φ(x) ∨ ψ(x)] ⇐ (∃x)[φ(x)] ∨ (∃x)[ψ(x)]
    5. (∀x)[φ(x) ∧ ψ(x)] ⇒ (∀x)[φ(x)] ∧ (∀x)[ψ(x)]
    6. (∀x)[φ(x) ∧ ψ(x)] ⇐ (∀x)[φ(x)] ∧ (∀x)[ψ(x)]
    7. (∀x)[φ(x) ∨ ψ(x)] ⇒ (∀x)[φ(x)] ∨ (∀x)[ψ(x)]
    8. (∀x)[φ(x) ∨ ψ(x)] ⇐ (∀x)[φ(x)] ∨ (∀x)[ψ(x)]

Para cada uma das proposições acima: (i) demonstre se for possível sem feitíços (lógica intuicionista); (ii) caso contrário demonstre se for possível com feitícos (lógica clássica); (iii) caso contrário refute dando um contraexemplo.

Sugestão: verifiquem os (i) e (ii) num proof assistant (Coq, Agda, ou Lean).

08/11/2021

  1. Na aula a primeira tentativa de descrever a indução foi reduzindo nosso alvo para a Base (φ(0)) e para o (∃n)[φ(n)⇒φ(Sn)]. Mostrei um exemplo para argumentar que seria errado permitir essa regra no jogo, pois assim a gente poderia demonstrar a proposição «todo número natural é menor ou igual a 1». A gente poderia demonstrar também a proposição «todo número natural é igual a 0»?
  2. §«Indução»
  3. §«Demonstrando propriedades de naturais com indução»

17/11/2021

  1. Problemas: Π4.1
  2. §«Ordem nos naturais»
  3. Problemas: Π4.11

18/11/2021

  1. Siga a sugestão do hw do dia 05/11/2021: (i) instale o Lean no teu computador; (ii) configure teu editor para ativar o modo Lean; (iii) numa pasta no teu computador use o comando leanpkg new fmclean; (iv) baixe o arquivo logic.lean que tem os enunciados prontos, e o coloca na pasta fmclean/src; (v) substitua todos os sorry, do arquivo com código que compila para demonstrar tudo. Dúvidas nos #proofassistants e #tech, obviamente!

19/11/2021

  1. Na aula definimos somatório (e produtório) para seqüências finitas de números x₁,…,xₙ em tal forma que a expressão x₁+x₂+x₃+x₄ acabou sendo definida como a (((x₁+x₂)+x₃)+x₄). Redefina somatório e produtório em tal forma que x₁+x₂+x₃+x₄ acabará sendo definida como a (x₁+(x₂+(x₃+x₄))).
  2. Na indução «alternativa» de Andreon/Erickson que aceitamos, parece que nem precisamos demonstrar a base. No outro lado, na nossa primeira idéia, pareceu necessário demonstrar a base φ(8). Cadê a base agora?
  3. Mostre que não podemos supor que k>0 no passo indutivo, escolhendo uma proposição absurda que vira demonstrável com essa regra de indução que nos permite considerar que k>0 no passo indutivo. Ou seja: precisa definir uma afirmação φ(–) que é obviamente errada, e escrever uma demonstração que para todo n, φ(n), usando essa regra.
  4. Até o primeiro segundo intervalo de problemas pulando a §53. «Somatórios e produtórios formalmente» (para este assunto consulte a aula #14).

23/11/2021

  1. Resolva sozinho e sem consultar nada toda a Prova 1.1 do 2019.2, simulando as escolhas e as limitações de tempo e de espaço, tudo isso no teu caderno.
  2. Resolva o resto (que não conseguiu resolver dentro do tempo em modo simulação-de-prova).

26/11/2021

  1. Na aula descobrimos que a regra de indução «a partir dum número b» não é algo que precisamos aceitar como princípio (axioma) mas podemos inferir a partir do princípio da indução «original e oficial». Faça a mesma coisa para justificar a indução com mais que uma base. Primeiramente enuncie formalmente esse princípio, e depois mostre como reduzí-lo para o princípio de indução.
  2. Novamente: existem irracionais a,b tal que, aᵇ é racional?
  3. Ache uma outra maneira para justificar o princípio de indução de «a partir dum número b»
  4. Podemos justificar («ganhar») o princípio da indução forte ou precisamos aceitar como princípio mesmo ?
  5. Podemos justificar («ganhar») o princípio da boa ordem ou precisamos aceitar como princípio mesmo?
  6. O 1/√2 é irracional?
  7. Escreva um programa copiando fielmente a definicao da função A que definimos no plicker. Use para calcular os valores A(3,2) e A(7,5). Modifique teu código para contar quantas vezes a função A foi chamada, e quantas delas foram com argumentos novos.
  8. Tente estabelecer implicações entre os princípios PBO, PIF, e PIFF.
  9. Onde robei na «demonstração» dos aniversários/cavalos?
  10. Demonstre que todas as potências de qualquer ímpar são números ímpares também.

29/11/2021

  1. Dado a (ir)racionalidade do α e/ou do β podemos concluir algo sobre a (ir)racionalidade dos αβ ou α+β?
  2. Termine as direcções PIF⇒PBO e PIF⇒PIFF

01/12/2021

  1. H. ∀n∀x[ Aₙ(Aₙ(x))<Aₙ₊₂(x) ]

Histórico

Vamos acompanhar as aulas gravadas de FMC1, e discutir no Zulip.

18/10/2021: Aula 1: Introdução [video]

  • Apresentação dos assuntos principais
  • Os típos principais: proposições (tbm: afirmações); objetos (tbm: individuais)
  • Erros comuns
  • Type error
  • Erro de semântica
  • Diferença entre as duas frases:
    • «Se A, (então) B
    • «Como A, (logo) B
  • O significado da palavra «equivalente» em matemática
  • Noções primitivas – Definições
  • 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
  • Árvores de derivação

20/10/2021: Aula 2: Introdução; Demonstrações [video]

  • Decepção e recap
  • implicação em matemática
  • «se» vs «somente se»
  • «necessário» vs «suficiente»
  • Erro: afirmação do conseqüente
  • Conjunção: como atacar e como usar
  • Um exemplo de demonstração e seu tabuleiro
  • Definições
  • contexto de definição
  • variáveis livres e ligadas
  • duas maneiras que uma definição pode ser errada
  • igualdade vs equivalência, com e sem «def»
  • declarar vs definir
  • Um exemplo de demonstração (cont.)
  • notação de conjuntos
  • Existência: como atacar e como usar

22/10/2021: Aula 3: Demonstrações [video]

  • Recap: açúcares sintácticos que já encontramos
  • (∃x∈A)[φ(x)] e (∀x∈A)[φ(x)] como açúcar sintáctico
  • Θ: todos os quadrados de ímpares são ímpares
  • «para algum» e CUIDADO: não use a «vírgula mágica», nem um «para» seco
  • propriedades de igualdade
  • «Calculamos»
  • D: divide
  • Θ: O 1 divide todos os inteiros
  • Θ: Cada inteiro divide ele mesmo

25/10/2021: Aula 4: Demonstrações [video]

  • Dois enunciados dum teorema: mesma coisa ou não?
  • Θ: (∀a∈ℤ)[a|0]
  • Demonstração errada: podemos inferir algo?
  • Θ: (∀a,b,x∈ℤ)[a|b ⇒ a|bx]
  • Como justificar uma coisa «obvia» de igualdade
  • Quantificadores consecutivos
  • Θ: (∀a,b∈ℤ)[a|b ⇒ (a|-b e -a|b)]
  • atacando conjunções
  • Utilizando teoremas demonstrados como lemmata
  • usando afirmações universais
  • Θ: (∀a,b,c∈ℤ)[(a|b e a|c) ⇒ a|b+c)]
  • mais uma justificação de algo «óbvio»
  • Θ: (∀a,b,c,x,y∈ℤ)[a|b e a|c ⇒ a|bx+cy]
  • usando implicações: modus ponens

27/10/2021: Aula 5: Demonstrações [video]

  • Θ: (∀a,b,c∈ℤ)[a|b e b|c ⇒ a|c]
  • Stocktaking/bookkeeping
  • Disjunção: como atacar
  • Separação em casos
  • LEM (Law of Excluded Middle)
  • Resumindo numa maneira mais humana
  • Disjunção: como usar
  • Uma resposta malandra
  • Uma resposta direta
  • Tratando negação
  • A ⇐?⇒ ¬¬A
  • Como usar
  • Θ: O √2 é irracional
  • D: (ir)racional
  • D: √2
  • «aquele … que …»

29/10/2021: Aula 6: irracionalidade [video]

  • Θ: O √2 é irracional
  • «aquele … tal …»
  • existência e unicidade
  • um enunciado errado de lemma
  • um enunciado dum lemma que não nos ajuda
  • um enunciado dum lemma que nos ajuda sim
  • implicação: outra maneira para atacar
  • a contrapositiva de implicação
  • uma demonstração com erros
  • não confunda «tal que» com «e»
  • a importância enorme do que demonstramos
  • Wason’s test

01/11/2021: Aula 7: irracionalidade [video]

  • Recap: Θ: O √2 é irracional
  • perguntando nossas próprias perguntas
  • Θ? O √3 é irracional
  • tentando copiar «mutatis mutandis» uma demonstração
  • dois teoremas fortes que não demonstramos ainda
  • dificuldade: demonstrar ou refutar?
  • demonstrado o lema que queremos
  • o que ganhamos brincando com o 4
  • separando números em «times» a partir dum número-guia
  • separando em casos
  • cadê o problema com o lemma sobre o 4?
  • esse √3 é um número mesmo?
  • para quais números x o √x é racional?
  • umas questões sobre primos e raizes racionais
  • Plicker: o √6 é irracional?

03/11/2021: Aulas 8 & 9a: demonstrações; linguagens

  • Aula 8 [video]
    • Demonstrações
      • perguntando nossas próprias perguntas
      • generalizando um teorema
      • generalizando uma definição
      • perguntando o contrário
      • Plicker: as conjecturas da aula passada são verdadeiras?
      • sobre a redução ao absurdo
    • Linguagens
      • sintaxe vs semântica
      • definindo linguagens
      • gramáticas e notação BNF
      • erro de ética: escolhe nomes bons e honestos
      • dígito vs numeral vs número
      • convenções e açúcar sintáctico
      • linguagens com variáveis
      • «arbitrariamente grande»
      • metalinguagem e metavariáveis
  • Aula 9a [video] (até o 00:36:59)
    • Demonstrações
      • Dupla negação
      • Como demonstrar que √n é definido para cada n natural
      • Plicker: o ³√2 é irracional?

05/11/2021: Aulas 9b & 10: naturais; recursão; indução

  • Aula 9b: [video] (a partir do 00:37:00)
    • Nat(urais): uma definição humana
    • um acordo sobre afirmações com (meta)variáveis não declaradas
    • voltando: variável vs metavariável
    • Nat(urais): uma definição com gramática
    • Nat(urais): uma definição com regras de inferência
    • Um açúcar sintáctico
    • os valores canônicos de Nats
    • função vs construtor
    • Numerais diferentes
    • Spoiler/trailer: seqüências, funções, FMC2
    • Igualdade
    • cuidado: os «para todo» e «existe»
    • Recursão
    • 2+3=5
    • Resumo: o que aconteceu
  • Aula 10: [video]
    • Recap: Nat(urais)
    • Recursão vs tijolo
    • Calculando a soma com recursão
    • onde focar para reduzir?
    • Multiplicação
    • 2 · 3 = 6
    • qual resultado incompleto é melhor?
    • precedência e associatividade de operadores
    • Θ. Associatividade da +
    • Plicker: tem como continuar a demonstração?
    • escolhendo variáveis com «linhas»: x’, x’’, etc.
    • o problema que temos demonstrando esse teorema

08/11/2021: Aula 11: Naturais, recursão, indução [video]

  • Recap: tentativa de demonstrar
  • a recursão foi no segundo argumento, então…
  • «para ALGUM»
  • Recursão – Indução
  • Indução
  • quando podemos usar indução
  • indução informalmente
  • indução expressa com conjunto
  • «conjunto fechado por…»
  • Esqueçam a receitinha de 3 passos!
  • Indução como regra de inferência
  • «Base» e «Passo indutivo»
  • a regra de indução na verdade é um esquema
  • indução para demonstrar nosso teorema atual
  • «hipótese indutiva»
  • Como podemos continuar agora?
  • Briga: poluição do estado com novos nomes novos «para abreviar»
  • Podemos continuar assim também!
  • continuando a demonstração
  • presente da recursão vs presente da indução
  • continuando a demonstração
  • Algo que NÃO é supor o próprio alvo!
  • Donde chegou essa paréntese?
  • continuando o cálculo
  • donde chegou essa paréntese?
  • propriedades de igualdade
  • o que aconteceu
  • E se eu nem precisei usar a hipótese indutiva?
  • Plicker: Faz diferença se escolher usar indução mais cedo?

10/11/2021: Aula 12 [2019-08-19]: Naturais, recursão, indução [video]

  • exponenciação
  • recap: associatividade da +
  • tentar começar «por indução»
  • Plicker: melhor, pior, ou mesma coisa?
  • «por indução no z»
  • podemos trocar quantificadores consecutivos da mesma forma
  • discussão: comparação das duas demonstrações
  • comparando as H.I.’s
  • com a regra errada podemos demonstrar que todo natural é igual a 0?
  • drinker’s paradox
  • o que ganhamos
  • Θ: + é comutativa
  • 0 + 0 = 0 + 0 sem nem calcular
  • lemmas em demonstrações
  • comparação com programação
  • subinduções
  • lendo as H.I. «com palavras da rua»
  • escopos e escolhas de variáveis

12/11/2021: Aula 13 [2019-08-21]: Naturais, recursão, indução [video]

  • Θ: + é comutativa: o esqueleto
  • escopos e as várias hipoteses indutivas
  • entender no coração, com palavras da rua
  • passo indutivo da segunda sub-indução
  • matemática é case-sensitive!
  • usando o ` ≟ ’
  • observações
  • adição, multiplicação, exponenciação, e depois?
  • Θ: · é associativa
  • lemmata em demonstrações
  • escolhendo nomes lindos para nossas variáveis
  • um erro no esboço da prova!

19/11/2021: Aula 14 [2019-08-26]: Naturais, recursão, indução [video]

  • associativa vs associativa-a-esquerda/direita
  • generalizando operação binária para n-ária, com n≥0
  • seqüências finitas e infinitas, convenções com os «…»
  • off-by-one error
  • definição formal (recursiva) de somatório e produtório
  • como definir a «próxima» operação depois da exponenciação
  • indução «a partir dum númer positivo»
  • «vacuamente verdade»
  • Plicker: Posso assumir k>8?
  • Cadê a base?

23/11/2021: Aula 15 [2019-08-28]: Naturais, recursão, indução [video]

  • justificando a regra de «indução a partir de» sem aceitar como princípio
  • o que significa ≤ ?
  • roubando usando língua, etimologia, notação, etc.
  • definindo relações recursivamente
  • programação declarativa: programação funcional e programação lógica
  • um lemma importante sobre a ≤
  • por que não podemos supor k>0 no passo indutivo?
  • descobrindo mais «princípios» relacionados
  • uns cuidados para tomar levantando de low-level para high-level
  • umas maneiras de definir a função fibonacci
  • definição dos números Lucas
  • como calcular valores dessas funções
  • exercício: L = ℓ
  • duas maneiras de organizar o passo indutivo
  • cuidado não escrever objetos não definidos!
  • quando uma base não é suficiente
  • Plicker: survey: tem irracionais a,b tais que aᵇ é racional?

24/11/2021: Aulas 16 [2019-08-30]: Naturais, recursão, indução [video]

  • tem irracionais a,b tais que aᵇ é racional?
  • NUNCA dê nenhum espaço desnecessário para teu inimigo!
  • 1/√2 é irracional? (fácil)
  • 2^(1/√2) é irracional? (difícil)
  • uma demonstração clássica
  • de SQL injection para lógica matemática
  • «abusando» o princípio da indução
  • ganhando a «indução a partir de»
  • maneiras diferentes de organizar uma demonstração por indução
  • princípio da indução original
  • princípio da indução com mais bases
  • ganhando a «indução com mais bases»
  • o que aconteceu?
  • dica: como começar sem saber se/qual indução vai precisar
  • indução forte
  • Plicker: tem base?
  • Q: podemos «ganhar» a partir da original?
  • dica de novo: como começar sem saber se/qual indução vai precisar
  • o princípio da boa ordem
  • Todos os naturais a partir de 8 podem ser escritos como somatório de 3s e 5s
  • uma dica seguindo um possível caminho

26/11/2021: Aula 17 [2019-09-02]: Naturais, recursão, indução [video]

  • indução forte
  • princípio da boa ordem (PBO)
  • como usar o PBO na prática
  • exemplo: não existem inteiros entre 0 e 1
  • entendendo o princípio da indução
  • indução e recursão: dois lados da mesma moeda
  • princípio da recursão
  • sobre implicação
  • Wason’s test com psicologia diferente
  • implicação material vs relevante
  • uma demonstração errada: cavalos e aniversários
  • triminôs: de prova por indução para um algoritmo
  • Plicker: uma recursão aninhada: quantas chamadas?

29/11/2021: Aula 18 [2019-09-04]: Naturais, recursão, indução [video]

  • o 1/√2 é racional?
  • soma e produto de (ir)racionais é (ir)racional?
  • Todas as potências de um ímpar são ímpares
  • escolhendo nomes de variáveis
  • podemos mexer com os quantificadores duma implicação?
  • onde roubei na «demonstração» dos aniversários
  • corolário simples do teorema dos triminôs
  • implicações entre PIF,PIFF,PBO
  • PBO ⇒ PIF
  • PIF ⇒ PIFF (dica)
  • PIF ⇒ PBO (dica)
  • Fortalecendo o enunciando: teorema de pontinhos
  • Plicker: de novo: quantas chamadas precisamos?

01/12/2021: Aulas 19 e 20: Resolução da Prova 1.1 [video] e [video]

  • Resolução da Prova 1.1 (A–E)
  • aridade
  • contexto de definição
  • não escreva: «sendo», «para x», «com»
  • português matemático
  • keywords low-level em demonstrações
  • «logo» vs «ou seja»
  • «existe» vs «seja»
  • «procuro …» vs sem nome
  • sobre cálculos e «calculamos»
  • proposição vs declaração
  • «suponha» vs «seja»
  • Reclamação: procurem usar seus recursos (compiladores humanos nesse caso)
  • onde e quando usar indução
  • uma resolução mais econômica
  • qual é a base?
  • somatório vazio
  • cuidado com indução: onde a quando?
  • essa vez o quando importa!
  • descreva tanto formalmente quanto com palavras de rua!
  • Plicker: Survey: ficou surpreso com tua nota?
  • F. ∀n[ Aₙ é estritamente crescente ]
  • Plicker: Como começaria a demonstração?
  • Demonstração do F
  • G1. Enuncie a G2 e demonstre.
  • G2. ∀n∀x[ Aₙ(x) é menor que Aₙ₊₁(x) ]
  • E sobre o A₄?

Futuro (fluido)

03/12/2021

06/12/2021

08/12/2021

10/12/2021

13/12/2021

15/12/2021

17/12/2021

20/12/2021

22/12/2021

27/12/2021

29/12/2021

03/01/2022

05/01/2022

07/01/2022

10/01/2022

12/01/2022

14/01/2022

17/01/2022

19/01/2022

21/01/2022

24/01/2022

26/01/2022

28/01/2022

31/01/2022

02/02/2022

04/02/2022

07/02/2022

09/02/2022

11/02/2022

14/02/2022

16/02/2022

18/02/2022

Last update: Wed Dec 1 17:46:17 -03 2021