2020.1 FMC1, turma de Thanos

Homework

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.

24/02/2020

1. Estude o capítulo «Estratégias de provas».
2. Estude o capítulo «Linguagens».
3. Estude o capítulo «A linguagem de lógica proposicional».
4. Estude brutalmente o capítulo «Os números naturais: recursão; indução».
5. Estude os capítulos 1–3 de Velleman.
6. Brinque com Haskell ou PureScript.
7. Installe o Coq; estude o seu tutorial.
8. Podemos ler o « ⇔ » como «se e somente se». Qual das duas partes dele (⇐ e ⇒) corresponde no «se» e qual no «somente se»?
9. Podemos ler o « ⇔ » como «é suficiente e necessário para». Qual das duas partes dele (⇐ e ⇒) corresponde no «é suficiente para» e qual no «é necessário para»?

28/02/2020

1. Para cada um dos 7 conectivos pense: como usar? como atacar?
2. Deixamos uma demonstração no meio: sejam a,b,c inteiros tais que a|b e b|c. Demonstre que a|c.

02/03/2020

1. Defina (∃!x)[φ(x)] e (∃!x∈A)[φ(x)] como açúcar sintáctico
2. Duas definições diferentes de ser ímpar:
   D1. n ímpar ⇐def⇒ existe inteiro k tal que n = 2k+1
   D2. n ímpar ⇐def⇒ n não é par
   onde
   n par ⇐def⇒ existe inteiro k tal que n = 2k
   Demonstre ou refute: as definições D1 e D2 são equivalentes.
3. Demonstre ou refute: todos os impares tem quadrado ímpar
4. Demonstre ou refute: todos os inteiros cujo quadrado é ímpar são ímpares

04/03/2020

1. Se convença que os ataques e os usos que encontramos até agora fazem todos sentido.
2. Discutimos como «passar a negação por dentro» para proposições das formas
   • ¬(∀x)[φ(x)]
   • ¬(∃x)[φ(x)]
   mas não para proposições das formas
   • ¬(∀x∈A)[φ(x)]
   • ¬(∃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.
3. 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
4. Dado que cada número que não é ímpar é par, demonstre que: todos os inteiros cujo quadrado é ímpar são ímpares.
5. Demonstre sozinho todas os teoremas que temos demonstrado até agora, especificando claramente cada «linha de código» e atualizando o tabuleiro de dados/alvos.

06/03/2020

1. Estude bem todos os conectivos, seus usos e seus ataques se convencendo que cada uma dessas 12 coisas faz sentido.
2. Definimos como açúcar sintáctico: ∃!x)[φ(x)] ⇔ (∃x)[φ(x)]&(∀u)(∀v)[φ(u)&φ(v) ⇒ u=v]
   Demonstre/refute: (∃!x)[φ(x)] ⇐?⇒ (∃z)(∀x)[φ(x)⇔x=z]
3. Teu inimigo não aceita a (LEM) ou seja, não te permite supor do nada P∨¬P. Obviamente não a lei de dupla negação, então nem redução ao absurdo podes usar. Mesmo assim, sem supor nada mais sobre a proposição P, demonstre que:
   ¬¬(P∨¬P)

07/03/2020

1. Estude brutalmente o capítulo «Os números naturais: recursão; indução». (Foi hw desde 24/02/2020.)
2. Resolva as questões de recursão/indução de FMC1 dos semestres passados, especialmente do 2019.2.

14/03/2020

1. Tente terminar a demonstração da irracionalidade do √2
2. Justifique os outros princípios de indução usando a original

16/03/2020

1. todos os naturais a partir de 8 podem ser escritos como somatório de 3s e 5s
2. 3 é legal? Ou seja: é verdade que para todo natural n, se 3|n² então 3| n?
3. O 1/√2 é irracional?
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?
6. Dado a (ir)racionalidade do α e/ou do β podemos concluir algo sobre a (ir)racionalidade dos αβ ou α+β?
7. Investigue (demonstre ou refute): Cada número legal tem raiz irracional.
8. E o contrário? Cada número que tem raiz irracional é legal?

31/03/2020

1. Estude o capítulo «Introduções» (que atualizei esses dias).
2. Faça os homeworks anteriores que tem deixado pra lá!

Histórico de aulas

17/02/2020: aula com prof Felipe

19/02/2020: aula com prof Felipe

21/02/2020: aula com prof Felipe

28/02/2020: Demonstrações

• Tipos (objeto vs proposição)
• atômicas vs compostas
• definições e teoremas
• noções primitivas e axiomas
• teorema, lemma, corolários, conjectura
• demonstrações como jogos e programação
• dados – alvos
• linhas de código vs comentários
• conectivos: como atacar e como usar
• Type error
• igualdade vs equivalência, com e sem «def»
• igualdade intensional vs extensional, sintáctica vs semântica
• Erro de semântica
• Diferença entre as duas frases:
  • «Se __A__, (então) __B__.»
  • «Como __A__, (logo) __B__.»
• Existência: como atacar
• Existência: como usar
• Três enunciados dum teorema: mesma coisa ou não?
• O significado da palavra «equivalente» em matemática
• Um exemplo de demonstração e seu tabuleiro
• REPL
• linha de código vs comentário
• variáveis livres e ligadas
• linguagem e metalinguagem, variáveis e metavariáveis

02/03/2020: Demonstrações

• «se» vs «somente se»
• «necessário» vs «suficiente»
• açúcar sintáctico
• « ⇐ » e « ⇔ » como açúcar sintáctico
• (∃x∈A)[φ(x)] e (∀x∈A)[φ(x)] como açúcar sintáctico
• Conjunção: como atacar e como usar
• contexto de definição
• Θ: (∀a,b,c∈ℤ)[(a|b & b|c) ⇒ a|c)]
• Θ: O 1 divide todos os inteiros
• Θ: Cada inteiro divide ele mesmo
• Θ: (∀a∈ℤ)[a|0]
• Implicação: como atacar
• Universal: como atacar
• «a|b» vs. «a/b»
• D: ímpar
• duas definições de ímpar: equivalentes ou não?
• uma primeira treta sobre «reductio ad absurdum»
• propriedades de igualdade

04/03/2020: Demonstrações

• Negação como implicação
• Negação: como atacar (de graça pois foi reduzida para uma implicação)
• A ⇐?⇒ ¬¬A
• lei da dupla negação e LEM (lei do terceiro excluido)
• Conjunção: como atacar e como usar
• Implicação: como usar
• Modus Ponens
• Universal: como usar
• justificação de uso de universal mostrando as substituições: «com x := ...»
• Como justificar uma coisa «obvia» de igualdade
• por que podemos «multiplicar os dois lados por o mesmo número»?
• Contrapositiva de implicação
• Θ: (∀a,b,c∈ℤ)[a|b e a|c ⇒ (∀u,v∈ℤ)[a|bu+cv]]
• Melhor usar lemmas
• L1: (∀a,b∈ℤ)[a|b ⇒ (∀x∈ℤ)[a|bx]]
• L2: (∀a,b,c∈ℤ)[(a|b e a|c) ⇒ a|b+c)]
• Resumindo numa maneira mais humana
• Θ: todos os quadrados de ímpares são ímpares

06/03/2020: Demonstrações

• Como usar e como atacar diretamente cada conectivo!
• LEM e Dupla negação
• A ⇒ ¬¬A
• Contrapositiva
• Disjunção: umas regras que parecem injustas para o jogador
• Separação em casos
• Tabelas de verdade (evitem!!)
• Trocar proposições equivalentes por equivalentes

07/03/2020, 09h15–13h45: Naturais; Recursão; Indução

aulas gravadas correspondentes:

1. [12/08/2019]
2. [14/08/2019]
3. [16/08/2019]
4. [19/08/2019]
5. [21/08/2019]

• Números vs numerais
• Linguagens: sintaxe e semântica
• 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
• os valores canônicos de Nats
• função/operação vs construtor
• Igualdade
• cuidado: os «para todo» e «existe»
• Recursão
• 2+3=5
• 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 +
• tem como continuar a demonstração?
• escolhendo variáveis com «linhas»: x', x'', etc.
• o problema que temos demonstrando esse teorema
• a recursão foi no segundo argumento, então...
• «para ALGUM»
• Recursão – Indução: dois lados da mesma moeda
• Indução
• quando podemos usar indução
• indução informalmente
• 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?
• presente da recursão vs presente da indução
• E se eu nem precisei usar a hipótese indutiva?
• Faz diferença se escolher usar indução mais cedo?
• recap: associatividade da +
• tentar começar «por indução»
• «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
• o que ganhamos
• Θ: + é comutativa
• 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
• escopos e as várias hipoteses indutivas
• entender no coração, com palavras da rua
• passo indutivo da segunda sub-indução
• usando o ` ≟ '
• adição, multiplicação, exponenciação, e depois?
• escolhendo nomes lindos para nossas variáveis

09/03/2020: Nats; recursão; indução

• Θ: + é comutativa
• associativa vs associativa-a-esquerda/direita
• L/R-identidade de operaçãï
• L/R-distributividade
• indução «aninhada»
• escopos e as várias hipoteses indutivas
• entender no coração, com palavras da rua
• passo indutivo da segunda sub-indução
• posso assumir k>1?
• lemmas: quando usar?
• indução «a partir dum númer positivo»
• justificando a regra de «indução a partir de» sem aceitar como princípio

11/03/2020: Nats; recursão; indução

• Equivalência de duas definições diferentes de exponenciação
• 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
• cadê a base?

13/03/2020: Nats; indução; recursão; números

• Prop: O √2 é irracional
• Quem é √2?
• o que significa ser irracional?
• «aquele ... que ...»
• existência e unicidade
• seqüências finitas e infinitas, convenções com os «...»
• off-by-one error
• indução forte
• exemplo de abuso: SQL injection
• indução «a partir de»: duas maneiras de justificar
• uma demonstração errada: cavalos e aniversários
• onde roubei na «demonstração» dos aniversários
• O √2 é irracional: tentativa para demonstrar

16/03/2020: Números

• um lemma útil e umas variações dele
• a contrapositiva de implicação
• a importância enorme do que demonstramos: existência de irracionais!
• uma demonstração com erros sobre a irracionalidade do √3
• generalizando o teorema
• todos os naturais a partir de 8 podem ser escritos como somatório de 3s e 5s

Futuro (fluido)