Quick
index
main
eev
maths
blogme
dednat4
littlelangs
PURO
(GAC2,
λ, etc)
(Chapa 1)

emacs
lua
(la)tex
fvwm
tcl
forth
icon
debian
irc
contact

Matemática Discreta - 2011.1

Todas as folhas manuscritas de curso de 2011.1:
  http://angg.twu.net/MD/MD-2011.1-tudo.pdf
  http://angg.twu.net/MD/MD-2011.1-tudo.djvu
Todas as folhas manuscritas de curso de 2010.2:
  http://angg.twu.net/MD/MD-2010.2-tudo.pdf
  http://angg.twu.net/MD/MD-2010.2-tudo.djvu

O livro principal do curso é Scheinerman: "Matemática Discreta, uma introdução". A biblioteca tem vários exemplares; o código dele na biblioteca é 510/S316.

Vamos usar o Hopcroft/Motwani/Ullman, "Introdução à teoria de autômatos, linguagens e computação", como livro auxiliar (mas praticamente só vamos usar o primeiro capítulo dele). O código dele na biblioteca é 005.73/H791.

Veja o horário da monitoria aqui.

Veja a página do semestre passado!

Plano de aulas / resumo do que já aconteceu:

1ª aula (16/mar): Introdução às operações "e", "ou" e "não". Durante a
  maior parte da aula usamos 0 e 1 como valores de verdade; no final
  mudamos para F e V (em negrito). Mencionei que números, valores de
  verdade e conjuntos são objetos de tipos diferentes.
2ª aula (18/mar): Distribuí uma folha sobre operações e circuitos
    http://angg.twu.net/MD/MD_circuitos_2011mar18.pdf
    http://angg.twu.net/MD/MD_circuitos_2011mar18.djvu
  Pus um aviso enorme no quadro, com três caveirinhas embaixo,
  enfatizando a importância do exercício 1a; ele dizia mais ou menos o
  seguinte:
    No exercício 1a eu peço pra vocês _definirem_ certas operações.
    Reparem que definições são feitas em "matematiquês", que tem
    pedaços em português, pedaços em símbolos matemáticos, e às vezes
    diagramas e exemplos.
    Vocês estão aprendendo uma língua nova, e o 1a é como uma
    "redação" nessa língua nova.
    Não existem redações "certas" e "erradas" - só melhores e piores.
    Alguns critérios: clareza, não ter erros de sintaxe, tem que
    convencer quem a lê (não pode ter argumentos errados), etc.
    Programar é fazer definições - numa língua que o computador
    entenda. Às vezes basta o computador entender o que vocês escreveu
    - mas se o seu programa der um bug uma semana depois de ter sido
    escrito você vai ter que entender o que escreveu uma semana antes
    pra consertá-lo.
    Em geral _vocês_ vão ter que entender o que escreveram...
    Mas muitas vezes vocês vão ter que escrever coisas que _outras
    pessoas_ entendam - por exemplo, nas matérias da faculdade.
    Outro exemplo: quando a gente manda dúvidas pra listas de
    discussão as dúvidas bem explicadas são bem respondidas, as outras
    não.
    Além disso vocês vão precisar fazer definições (claras) em
    praticamente todas as matérias do curso.
  Passamos a aula quase toda discutindo o 1a. No final lemos um pedaço
  da seção 1 do Scheinerman ("Definições").

3ª aula (23/mar): D_n = conjunto dos divisores de n.
  Conjuntos de objetos com uma certa propriedade.
  Quantificadores e regras de redução para quantificadores.
4ª aula (25/mar):
  http://angg.twu.net/MD/MD_exercicios_2010mar29.pdf
  http://angg.twu.net/MD/MD_exercicios_2010mar29_gabarito.pdf
  Até a simplificação do E_4.
  Construímos a tabela com 8 simplificações

5ª aula (30/mar): Avisei que antes da gente continuar com a história
  das expressões equivalentes era melhor a gente aprender mais sobre
  modos de construir conjuntos e sobre como calcular o valor de
  expressões envolvendo conjuntos. Calculamos:
    C_1 = { (a,b) | a∈{0,1,2}, b∈{0,1,2}, a+b<=2}
    C_2 = {(a,b-a)| a∈{0,1,2}, b∈{0,1,2}, a+b<=2}
    C_3 = { {a,b} | a∈{0,1,2}, b∈{0,1,2}, a+b<=2}
  E ficaram umas dúvidas: {1,0}={0,1}? {0,0}={0}?
  Mostrei as definições do "contido ou igual", "contido e diferente",
  "não contido-ou-igual", "=" para conjuntos, etc, e a regra de
  redução do "∈". Passei um exercício pra casa, avisando que era MUITO
  importante e razoavelmente difícil (uma caveira - "precisa de
  perseverança"):
    Mostre que {0}={0,0} por uma série de reduções, e encontre um modo
    de explicar cada redução - por exemplo:
      {0}={0,0}
         \
         / pela regra A=B ~~~> A<=B ∧ B<=A 
         \ com A={0,0} e B={0}
         v
      {0}<={0,0}∧{0,0}<={0}
    Tente encontrar um modo de fazer isto que fique MUITO claro.
    Obs: a solução ocupa uma página inteira.
  (Estou escrevendo "contido ou igual" como "<=").
6ª aula (01/abr): *** completar ***

  Exercícios:

  Representem estes grafos direcionados "formalmente", isto é, com a
  notação de conjuntos e listas:
  (1) 1 --> 2 --\
      ^    |^^--/
      |    v|
      4 <-- 3
  (2) {1,2} --> {1} --\
        |          ^--/
        v
       {2}       {}
  e represente estes grafos direcionados "graficamente":
  (3) ({1,2,3}, {(2,1),(2,3),(2,1)})
  (4) ({1,...,4}, {(a,b)∈{1,...,4}^2 | a<b})
  (5) Calcule e represente graficamente:
      ({1,...,9},
       {(a,b) ∈ {1,...,9}^2 | a|b})
  Dica importante: dá pra fazer esta "conta" explicitamente desde que
  a gente use reticências ns lugares certos. Treinem usar reticências
  de um modo claro! (Obs: levem esta recomendação a sério! A gente
  leva anos pra aprender a user reticências bem, e é muito útil -
  comecem a treinar o mais rápido possível!)

7ª aula (06/abr): Definimos este grafo direcionado:
    D9 = ({1,...,9}, {(a,b) ∈ (1,...,9}^2 | a|b})
  e um outro, com menos setas:
             9		     
             ^		   
	     |		   
	     3--->6	   
    D9-  =   ^    ^	   
	     |    |	   
             1--->2--->4--->8
             |\		   
             | v		   
             5  7            
  Vimos as definições formais de reflexividade, simetria e
  transitividade para relações R \subseteq A^2, e as interpretações
  gráficas para reflexividade/simetria/transitividade. Contei que
  sempre existe um modo "mínimo" de acrescentar setas a uma relação
  para obter uma relação reflexiva/simétrica/transitiva. Definimos um
  outro grafo direcionado, D9', acrescentando a D9- as setas
  correspondentes a "acessibilidade em dois passos". Passei um
  problema (importante, duas caveirinhas, pra ser terminado em casa):
      Mostre que no grafo direcionado D9' esta
      sentença é falsa: ∀a,b,c∈A.aRb∧bRc->aRc.
  As dicas eram:
    1) Quem é A?
    2) Quem é R?
    3) Qual é a relação entre D9' e (A,R)?
    4) Como calcular o valor de ∀a,b,c∈A.aRb∧bRc->aRc?
    5) Como mostrar que ∀a,b,c∈A.aRb∧bRc->aRc é falso?
    6) Depois que a gente cria um conjunto C a gente não pode mudá-lo
       acrescentando mais elementos... mas podemos criar um conjunto
       C' contendo todos os elementos de C e mais alguns.
    7) Não escrevam ∀{1,...9}∈A.____! {1,...9} é constante.
    8) Dá pra cacular o valor de ∀a,b,c∈A.aRb∧bRc->aRc fazendo uma
       tabela com uma linha para cada valor "interessante" de a, b, c
       -- mas a tabela vai ter 9^3 linhas.
8ª aula (08/abr): Começamos com um grafo direcionado mais simples que
  os da aula passada: E=(A,R)=({1,...,7}, {(1,2),(3,2),(3,4),(5,6)}).
  A gente viu na aula passada como calcular os fechos reflexivo,
  simétrico e transitivo de uma relação graficamente, então introduzi
  uma notação - R^refl, R^sim, R^trans - e pedi pros alunos calcularem
  R^refl, R^sim, R^trans, (R^sim)^trans, ((R^sim)^trans)^refl, para a
  relação R do grafo direcionado E. A minha idéia era usar a relação
  S:=((R^sim)^trans)^refl para começar a discutir relações de
  equivalência, mas a gente acabou parando antes disso - os alunos não
  chegaram a um acordo sobre o resultado de (R^sim)^trans, e ficaram
  discutindo métodos possíveis.
    Uma definição "formalizável" de R^trans é a seguinte:
    se R <= A×A, então R^trans é a _menor relação transitiva_
    obedecendo R <= R^trans <= A×A (obs: aqui o "<=" é \subseteq).
  Pra tentar esclarecer essa definição nós passamos um tempão
  discutindo estes problemas (para a R do grafo E=(A,R)):
    (4) Encontre uma relação R'  transitiva tal que R^sim<=R'<=A×A.
    (5) Encontre uma relação R'' transitiva tal que R^sim<=R''<=A×A e
        R' \subsetneq R''.
  Com isso ficou claro que temos várias relações transitivas entre
  R^sim e A×A - queremos a menor delas. Um "método" (ineficiente, mas
  matematicamente preciso) de calcular o R^trans para uma dada relação
  R é o seguinte: calcule o conjunto \calR de todas as relações
  transitivas entre R e A×A, e depois calcule a interseção de todos as
  relações em \calR.
    ***Pra casa:*** Tentem fazer os exercícios das pags 81 a 83 do
  Scheinerman (sec.11). Não é importante fazer estes exercícios em
  detalhes por enquanto (vários deles dependem de ferramentas que
  ainda não vimos) - mas tentem ler _todos eles_ e pensar um pouco
  sobre cada um.
    [Eu dei dicas importantes nas últimas aulas de GA - preciso
    copiá-las aqui].
  Algumas pessoas me perguntaram que sistema operacional eu uso -
  porque elas viram um Emacs rodando na minha máquina numa janela
  maximizada e sem bordas. Alguns links:
    http://angg.twu.net/eev-current/anim/channels.anim.html
    http://angg.twu.net/eev-current/doc/shot-f3.png
    http://angg.twu.net/eev-current/doc/shot-f9.png

9ª aula (13/abr): Continuamos com o R do grafo direcionado da aula
    anterior: E=(A,R)=({1,...,7}, {(1,2),(3,2),(3,4),(5,6)}).
    Nós tínhamos visto que haviam várias relações transitivas entre
    R^refl^sim e A×A. Peguei uma delas, que eu disse que era a menor
    de todas; chamei ela de R^refl^sim^trans = R^eq. Defini relação de
    equivalência, e enunciei isto:
      Fato: R^sim^refl^trans é sempre relação de equivalência.
    Defini clases de equivalência, e pedi pros alunos calcularem
    [a]_R^eq para cada valor a∈A. Vimos uma representação gráfica - a
    com blobs, como na p.92 do Scheinerman.
      *** termino o resumo depois ***
10ª aula (15/abr): *** depois eu ponho o resumo ***

11ª aula (20/abr): véspera do feriado de Tiradentes.
      *** depois eu ponho o resumo ***
12ª aula (22/abr): não vai ter aula (a UFF costuma enforcar 6ªs
  quando tem feriado na 5ª).

13ª aula (27/abr): 
  consideramos a seqüência (e_0, e_1, ...) que obedece
  e_0=0 ∧ ∀n∈N.((e_n=n  -> e_(n+1)=10e_n+1) ∧
                (e_n!=n -> e_(n+1)=e_n))

  e vimos como calcular e_0, e_1, etc; pedi pros alunos calcularem
  e_12. Defini - informalmente - uma operação de concatenação de
  números, "++"; por exemplo, 12 ++ 345 = 12345, 100 ++ 10 = 10010.
  Todo mundo ficou em dúvida a respeito de qual deveria ser o
  resultado de 123 ++ 0, então tornamos a definição um pouco mais
  precisa criando duas operações diferentes, ++_A e ++_B:
    123 ++_A 0 = 1230,
    123 ++_B 0 = 123.
  (Obs: concatenação é uma operação muito comum em strings; a operação
  ++_A trata o 0 como o string "0", enquanto a operação ++_B trata o 0
  como o string vazio ("").)
  Mostrei que podemos usar a sequência (e_0, e_1, ...) para definir o
  ++ formalmente, generalizando isto aqui:
    123 ++ 45 = 123·100 + 45
              = 123·(e_45 + 1) + 45
  Pedi pros alunos encontrarem uma definição formal para uma operação
  ++_C e usarem ela para calcular 123 ++_C 0, 0 ++_C 123, 20 ++_C 300,
  300 ++_C 20. Apareceram várias idéias:
    Idéia 1:
      ∀a,b,c∈R. a++b=c -> a(e_b + 1)+b=c
      (problema: quanto é 10.2++(-3.140)?)
    Idéia 2:
      ∀a,b,c∈N. a++b=c -> a(e_b + 1)+b=c
    Idéia 3:
      ∀a,b∈N. a++b=a(e_b + 1)+b
  A idéia 1 e a idéia 2 não são totalmente equivalentes. Passei um
  exercício pra casa (aqui está mais detalhado que no quadro), que
  era o seguinte. Digamos que as operações ++_D e ++_E obedecem:
     ∀a,b,c∈N. a ++_D b = c -> a(e_b + 1)+b = c
     ∀a,b  ∈N. a ++_E b =      a(e_b + 1)+b
  Encontre funções (++_D) e (++_E) de N×N em Z, _diferentes_, que
  obedeçam as duas condições acima. Se (++_D) e (++_E) são funções de
  N×N em N então elas são necessariamente iguais; porquê?
  Mostrei um truque que a gente pode usar pra escrever substituições
  complicadas de um modo que todo mundo entenda (até colegas, e
  professores de mau humor):
    Sabemos que
      ∀a,b∈N. a++b = a(e_b + 1)+b
    Para a=123 e b=0, temos:
            123++0 = 123(e_0 + 1)+b
                   = 123(0 + 1)+0
                   = 123
  Aí consideramos a função f:N×N->N, definida (informalmente) por
  este diagrama:
     y=3 |  9
     y=2 |  5    8
     y=1 |  2    4    7
     y=0 |  0    1    3    6
         +-------------------
           x=0  x=1  x=2  x=3
  Pedi pros alunos tentarem encontrar - pra sexta - uma definição
  formal para esta f, e _testá-la_. Dicas: às vezes
  f(y+1,x-1)=f(y,x)+1, às vezes f(a+1,0)=f(0,a)+1.
  Avisei que depois vamos ver um modo de definir esta f que faz com
  que f(x,y) seja fácil de calcular - pelo modo acima calcular
  f(200,100) dá um trabalhão.
14ª aula (29/abr): 
  Problema dos dominós, torres de Hanói, representações.
  Digamos que a gente tem uma sacola com um monte de dominós
  (retângulos 2x1) indistinguíveis, e um retângulo 2x5 na parede que
  queremos preencher com dominós. Quantos modos diferentes temos de
  preenchê-lo? Liste-os. Obs:
     _________       _________    
    |___|___| |     | |___|___|   
    |___|___|_|  e  |_|___|___|     
  devem ser considerados como modos diferentes.
  Definimos a sequencia de conjuntos (D_1, D_2, ...), onde cada D_n é
  o conjunto dos modos de preencher o retângulo 2×n com dominós. Pedi
  pros alunos tentarem calcular D_5 e D_6, e numa certa hora pus um
  aviso no quadro:
    "D_5 = 8" é um ***erro conceitual gravíssimo***
  D_5 é um conjunto, 8 é um número, e um conjuntos nunca é igual a um
  número!!!!!! Mas isto aqui é verdade: |D_5| = 8. Note que neste caso
  o "|·|" não é o módulo, é a cardinalidade.
  Encontramos uma representação que transforma cada "modo" num número
  - e uma das vantagens disto é que nos permite por os modos em ordem,
  e aí fica fácil cada um comparar o seu conjunto com o que o vizinho
  obteve. Exemplos:
       _________            _________    
      |___|___| |          | | | | | |   
      |___|___|_|          |_|_|_|_|_|     
        2   2  1  = 221,    1 1 1 1 1  = 11111.
  Aí:
    D_4 = {22, 112, 121, 211, 1111}
    D_5 = {122, 212, 221,
           1112, 1121, 1211, 2111,
           11111}
    D_6 = {222,
           1122, 1212, 1221, 2112, 2121, 2211,
           11112, 11121, 11211, 12111, 21111,
           111111}.
  Defini a sequência dos C_ns por:
    C_1 = {1}
    C_2 = {2, 11}
    C_(n+2) = {2++a | a∈C_n}
            ∪ {1++b | b∈C_(n+1)}    para n∈{1,2,3,...}
  e pedi pros alunos calcularem alguns C_ns em casa e verificarem que
  C_n = D_n para todo n, e que |C_1|+|C_2|=|C_3|, |C_2|+|C_3|=|C_4|,
  etc. Há vários semestres atrás eu fiz um programa pra gerar os D_ns:
     http://angg.twu.net/2009.1/MD/dominoes.lua.html
             (find-angg "2009.1/MD/dominoes.lua")
  Torres de Hanói
  ---------------
  Problema: como representar cada "posição válida" das Torres de Hanói
  como um número, um conjunto, uma lista, um string, um vetor, ou uma
  matrix? Avisei os alunos que há muitas representações possíveis, e não
  há uma melhor que todas as outras, e abri um espaço no quadro pra pôr
  4 representações diferentes.
    Representação 1:
         |        |          |           / 0 0 0 \
         |        |          |      vira | 0 0 0 | na represtação 1,
       33333      |          1           | 3 0 0 |
      4444444     1         222          \ 4 1 2 /
      ----------------------------
                                     (34, 1, 2) na representação 2,
         {21, 32, 13, 14} na representação 3,
         (onde o 21 quer dizer "o disco 1 está no pino 2",
               o 32 quer dizer "o disco 2 está no pino 3",
               o 13 quer dizer "o disco 3 está no pino 1",
               o 14 quer dizer "o disco 4 está no pino 1")
      34012 na representação 4,
      "34,0,12" na representação 5.
  Vimos que a representação 4 é ambígua - as posições "1,2,34" e
  "1,23,4" (na representação 5) ambas viram 1234 quando usamos a
  representação 4.
  Pra casa: representem o problema das Torres de Hanói com 4 discos como
  uma relação - P_1 R P_2 vai ser verdade se e só se é possível passar
  da posição P_1 para a posição P_2 em um movimento.
  Obs: não confundam os nomes - usem nomes diferentes para discos,
  pinos, posições e movimentos.
  Dica: a parte trabalhosa do problema é descobrir como escrever isso
  de um modo que a minha avó entenda; a parte conceitual é fácil em
  comparação. Treinem usar tanto explicações gerais quanto exemplos, e
  tanto Português quanto matematiquês! Clareza não é fácil de obter.
  Obs: O trabalho que o Fred (ex-monitor de MD) apresentou na semana
  de monitoria de 2010 era sobre as Torres de Hanói:
    http://angg.twu.net/MD/fred_casteloes__hanoi_2010.pdf
    http://angg.twu.net/MD/fred_e_eduardo__hanoi_figuras_2010.pdf

15ª aula (04/mai): *** depois eu completo o resumo desta aula! ***
Lembrem que as operações "+" e "·" estão definidas - de modos
diferentes! - em números, vetores e matrizes.
Vamos definir o "++" (concatenação) em listas:
  (a_1, ..., a_n) ++ (b_1, ..., b_m) =
  (a_1, ..., a_n, b_1, ..., b_m).
Exemplo: (20, 30) ++ (400, 500, 600) = (20, 30, 400, 500, 600).
   i      P_i       d_i  m_i
  --------------------------
   1   "1234,0,0"    1  "1AB"   \
   2   "234,1,0"                | M_2ABC
   3   "34,1,2"
   4   "34,0,12"
   4   "4,3,12"
   5   "
Depois calcule a sequencia (m_1, m_2, m_15) de strings, que diz que
disco é movido de que pino para que pino.
Nós vamos trabalhar com "subsequencias" da sequencia (m_1, ..., m_15).
Def: M_nabc é a sequencia de movimenos necessaria para levar os discos
1, ..., n do pino a para o pino b, usando o pino c como auxiliar.
Def (formal):
  M_nabc = / ("1ac")       quando n=1,
           |
           | M_(n-1)acb ++
           |    ("nab") ++
           \ M_(n-1)cba    quando n>1. 
Pedi pra todo mundo calcular M_3ABC...
Expressões (introdução)
-----------------------
  Em qualquer livro sério sobre uma linguagem de programação vocês vão
  encontrar uma "especificação em BNF" (ou EBNF) da linguagem - em
  geral num apêndice. Obs: "Pascal Estruturado" não é um livro sério!
  Exemplo (p.36 do Ghezzi / Jazayeri):
    <expr> ::= <identifier>
             | <number>
             | (<expr>)
             | <expr><operator><expr>
    <operator> ::= +
                 | *
  Obs: quando escrevemos uma especificação nesta forma não estamos
  (aparentemente!) falando de conjuntos...
    "123" é um <number>        <- obs: "um" é um artigo indefinido!
     "45" é um <number>           A gente evita artigos indefinidos 
      "+" é um <operator>         em matematiquês... "x é um real"
   portanto:                      é formalizado como "x∈R"
    "123" é uma <expr>
      (porque todo <number> é uma <expr>),
    "45" é uma <expr>, e
    "123+45" é uma <expr>
      (porque <expr><operator><expr> é uma <expr>).
  (Fiquei de dar uma definição de certos tipos de expressões via
  conjuntos...)
16ª aula (06/mai): Hoje: o conjunto das expressões válidas!
  Vamos definir um conjunto de strings, E, cujos elementos vão ser
  exatamente os strings que são expressões válidas formadas por números,
  "+", "*", "(" e ")".
  Vamos começar fixando      <- (obs: usamos o termo "fixando" quando
  o conjunto dos strings         existem vários valores razoáveis para
  que representam números.       um objeto, e escolhemos um deles.)
  Vai ser mais conveniente começar
  com N={"n"} do que com N={"0", "1", "2", ..., "10", ...}.
  Como N={"n"} vamos ter:
                  "n+n" ∈ E,
        "(n+n)*(n*n+n)" ∈ E,
        "" não pertence a E, 
      "nn" não pertence a E,
    ")+*n" não pertence a E, etc.
  Idéia pra construção:
    E_0 = N,
    E_1 = E_0 ∪ (o conjunto dos strings da forma "e+e'", e,e'∈E_0)
              ∪ (o conjunto dos strings da forma "e*e'", e,e'∈E_0)
              ∪ (o conjunto dos strings da forma "(e)", e∈E_0)
  Mais precisamente: para n∈N,
    E_(n+1) = E_n
            ∪ {e++"+"++e' | e,e'∈E_n}
            ∪ {e++"*"++e' | e,e'∈E_n}
            ∪ {"("++e++")" | e∈E_n}
  Reparem que agora estamos usando concatenação ("++") em strings!
  Mas, formalmente, strings são listas de números...
  Exercício: calculem E_1.
  Substituindo n por 0 e E_0 por N={"n"} na fórmula anterior, temos:
    E_1 = {"n"}
        ∪ {e++"+"++e' | e,e'∈{"n"}}
        ∪ {e++"*"++e' | e,e'∈{"n"}}
        ∪ {"("++e++")" | e∈{"n"}}
        = {"n"} ∪ {"n+n"} ∪ {"n*n"} ∪ {"(n)"}
        = {"n", "n+n", "n*n", "(n)"}
  Def: E = E_0 ∪ E_1 ∪ E_2 ∪ ...
  Dá um trabalhão escrever o E_10 explicitamente (nós calculamos o E_2
  em sala), mas é fácil provar que
    "(n*n)+(n+(n*n))" ∈ E_10
  e como E = E_0 ∪ E_1 ∪ ... ∪ E_10 ∪ ...
  então "(n*n)+(n+(n*n))" ∈ E.
  Vamos ver isto passo a passo.
  (Obs: isto é uma introdução à segunda parte do curso!)
    1) "n"∈E_0
    2) "n*n"∈E_1        (porque "n*n" = "n"++"*"++"n"
                                      ∈ {e++"+"++e' | e,e'∈E_0},
                                      e E_0 está contido em E_1)
    3) "(n*n)"∈E_2              (porque "n*n"∈E_1)
    4) "n"∈E_1                  (porque E_0 está contido em E_1)
    5) "n"∈E_2                  (idem)
    6) "n+(n*n)"∈E_3            (por (5) e (3))
    7) "(n+(n*n))"∈E_4          (por (6))
    8) "(n*n)"∈E_3              (por (3))
    9) "(n*n)"∈E_4              (por (8))
    10) "(n*n)+(n+(n*n))"∈E_5   (por (9) e (7))
    11) "(n*n)+(n+(n*n))"∈E_6   (por (10))
      etc.

17ª aula (11/mai): (veja abaixo)
18ª aula (13/mai): Vou estar fora a semana toda, num congresso,
  apresentando isto aqui: <http://angg.twu.net/LATEX/2011ebl-abs.pdf>.

19ª aula (18/mai): árvores binárias.
20ª aula (20/mai): pergunta do dia: que passos podemos usar numa
  "prova direta"? O apéndice C do Scheinerman (p.522, "Fundamentos") e
  o capítulo 1 falam de regras básicas, definições, teoremas, lemas...
  A gente começou vendo um pouquinho sobre provas em árvore, depois a
  gente passou pra isso aqui: sabemos que + e · são comutativos,
  associativos, temos 0, "-", distributividade, etc. Como provar,
  _passo a passo_, que (a+b)(a-b) = a^2-b^2? (Vimos uma prova,
  enorme).
  Porque é que ninguém nunca faz essas provas em todos os detalhes?
  O apêndice C do livro dá só as regras básicas...
  No cap 1 do livro há uma discussão sobre definições, teoremas,
  lemas, etc... e cada vez que a gente usa um teorema a gente pode
  expandí-lo, se quiser (tem exercícios sobre isto numa lista do
  semestre passado).
  Pedi pros alunos provarem que se n>4 e 2^n<n! então 2^(n+1)<(n+1)!
  passo a passo; apareceu uma solução, mas ela usava a regra:
    a<b  a'<b'
    ----------(?)
     aa'<bb'
  Uma das próximas técnicas de demonstração que vamos aprender é
  indução...

21ª aula (25/mai): **** Paralisação do Pólo ****
  Tínhamos marcado a P1 para este dia, mas ela vai ter que ser transferida.
22ª aula (27/mai): 

23ª aula (01/jun): exercício de revisão pra P1.
  Considere o seguinte problema: um homem está na margem esquerda de
  um rio com os seus três animais (?!?) de estimação - um lobo, uma
  cabra e um repolho - e ele quer atravessar para a margem direita
  usando um barco no qual só cabe ele e um dos "animais" de cada vez.
  Mas se o lobo for deixado sozinho com a cabra ele come a cabra, e se
  a cabra for deixada sozinha com o repolho ela come o repolho.
  Descreva como representar (todos!!!!!!!!!!!!) os movimentos
  possíveis deste problema num grafo direcionado.
24ª aula (03/jun): P1. Questões e gabarito:
  http://angg.twu.net/MD/MD_P1_2011jun02.pdf
  http://angg.twu.net/MD/MD_P1_2011jun02.djvu

25ª aula (08/jun): aula (meio improvisada) sobre o que é um seqüente e
  o que quer dizer um seqüente ser "verdadeiro". Não chegamos a ver
  com detalhes o que são as "variáveis livres" de um seqüente, mas
  mostrei que podemos testar se um seqüente como
    P->Q,Q->R|-P->R
  é verdadeiro fazendo uma tabela com todos os valores possíveis de
  P,Q,R, marcando como "interessantes" todas as linhas nas quais todas
  as hipóteses são verdadeiras, e testando se em cada linha
  interessante a conclusão é verdadeira:
             hip1  hip2  conc
    P  Q  R  P->Q  Q->R  P->R
    -------------------------
    F  F  F   V     V     V     <= linha interessante
    F  F  V   V     V     V     <= linha interessante
    F  V  F   V     F     V
    F  V  V   V     V     V     <= linha interessante
    V  F  F   F     V     F
    V  F  V   F     V     V
    V  V  F   V     F     F
    V  V  V   V     V     V     <= linha interessante
  Nós vamos usar seqüentes para entender regras de dedução, e muitas
  vezes vamos usar seqüentes cujas tabelas seriam infinitas, como:
    a∈Z|-a^2>0
  Avisei pros alunos que haveria um trabalho extra, em grupos de no
  máximo 3 pessoas, pra aumentar a nota, sobre clareza e modos de
  argumentar. Cada grupo teria que mandar pelo menos um representante
  pra assistir a reunião do CONPURO de 10/junho e fazer anotações...
26ª aula (10/jun): deixei cópias de um trecho do livro da Judith
  Gersting na sala e levei os "representantes" pra reunião do CONPURO.
  O plano original era eles assistirem só o trecho entre 11:00 e
  12:00hs da reunião, mas às 12:00 estava começando uma votação
  confusa e interessante e eles pediram pra ficar um pouco mais.
  Depois a gente voltou pra sala de aula, os não-representantes já
  tinham debandado, e a gente discutiu o que todo mundo tinha visto na
  reunião e como o trabaho seria feito. É pra analisar pelo menos
  isto:
    * _como_ cada lado expõe seus argumentos,
    * que argumentos parecem furados (e porquê),
    * quem vocês acham que está sendo claro, sincero, etc,
    * que "técnicas" certas pessoas usaram pra ser claras (ou
      convincentes, ou interessantes, ou simpáticas, etc; obs: ninguém
      nasce sendo claro - e a gente está tentando aprender a ser claro
      nos nossos argumentos matemáticos e não-matemáticos),
    * _quem_ cada lado defende - que grupos e atitudes eles protegem, e
      que grupos eles atacam, ignoram, excluem, etc.
    * que argumentos eram usados pra atacar os inimigos
  O trabalho é pra ser entregue em duas semanas.

27ª aula (15/jun):
28ª aula (17/jun):
28.5ª aula (17/jun, 14-16): aula extra.

29ª aula (22/jun): P2, sobre demonstrações. A matéria é o início do
  capítulo 2 do livro da Judith Gersting (até indução - detalhes
  depois); como a biblioteca está fechada por causa da greve eu
  scaneeei o cap.2:
    http://angg.twu.net/MD/judith_p59_a_110.pdf
    http://angg.twu.net/MD/judith_p59_a_110.djvu
30ª aula (24/jun): enforcado.

31ª aula (29/jun):
32ª aula (01/jul):

33ª aula (06/jul): P3
34ª aula (08/jul):

35ª aula (13/jul): VR
  Matéria da VR e da VS:
  Relações e funções; construções indutivas: como calcular certas
  funções definidas indutivamente e como definir funções;
  demonstrações: determinar se sentenças com ∀, ∃ e -> são verdadeiras
  ou falsas e mostrar porquê; prova direta, prova por exaustão, prova
  por indução.
36ª aula (15/jul): VS
  ***** Dicas pra VS: *****
  Construções indutivas - como na questão 1 da VR (e na questão 1b da
  P3) - vão ser MUITO importantes! Certifique-se de que você sabe
  calcular conjuntos definidos indutivamente - por exemplo, faça A={1}
  na questão 1 da VR e calcule T_A0, T_A1, T_A2, e garanta que você
  sabe visualizar o resultado de T_A e T_N - e que você sabe definir
  formalmente funções recursivas, como fib (onde, por exemplo, fib(8)
  é o oitavo termo da série de Fibonacci - você vai precisar de
  definições por casos para definir fib) e o Lin_N. Além disso garanta
  que você sabe definir formalmente funções como: "f(n) é n quando n é
  um natural e f(p) é f(a)*f(b) quando p é da forma (a,b)". MESMO QUE
  VOCÊ LEVE MEIA HORA PRA ENTENDER A SINTAXE CERTA PARA ESTAS
  DEFINIÇõES NÃO DESISTA!

  Scans (depois eu ponho eles nos "dias" certos; todos têm gabarito):
http://angg.twu.net/MD/MD_P2_2011jun22.djvu
http://angg.twu.net/MD/MD_P2_2011jun22.pdf
http://angg.twu.net/MD/MD_P3_2011jul06.djvu
http://angg.twu.net/MD/MD_P3_2011jul06.pdf
http://angg.twu.net/MD/MD_VR_2011jul13.djvu
http://angg.twu.net/MD/MD_VR_2011jul13.pdf
http://angg.twu.net/MD/MD_VS_2011jul15.djvu
http://angg.twu.net/MD/MD_VS_2011jul15.pdf    <-- Vejam!