Quick
index
main
eev
eepitch
maths
angg
blogme
dednat6
littlelangs
PURO
(C2,C3,C4,
 λ,ES,
 GA,MD,
 Caepro,
 textos,
 Chapa 1)

emacs
lua
(la)tex
maxima
git
agda
forth
squeak
icon
tcl
tikz
fvwm
debian
irc
contact

Matemática Discreta - 2011.2

Horários do curso em 2011.2:
  4ªs 14-16, sala 5A ou 6A,
  5ªs  9-11, sala 5A ou 6A.
  Veja: http://angg.twu.net/2011.2.html
                  (find-TH "2011.2")
Página do curso de 2011.1:
  http://angg.twu.net/2011.1-MD.html
            (find-TH "2011.1-MD")
Arquivo com todas as folhas manuscritas do curso de 2011.1:
  http://angg.twu.net/MD/MD-2011.1-tudo.pdf
  http://angg.twu.net/MD/MD-2011.1-tudo.djvu
Vamos usar o livro do Scheinerman,
alguns capítulos do livro da Judith Gersting,
e o primeiro capítulo do Hopcroft/Ullman/Motwani.
Versão para impressão:
  http://angg.twu.net/MD/MD-2011.2.pdf
(Pode estar desatualizada!)

A monitora é a Gabriela Ávila <gabrielaa@id.uff.br>. Os horários de atendimento dela são nas 2ªs das 9:00 às 13:00, nas 4ªs das 14:00 às 16:00, e nas 5ªe a 6ªs das 14:00 às 17:00.

A Ana Isabel está dando o curso dela de modo bem diferente, mas vale muito a pena olhar o material do curso dela (no Moodle):

http://softwarelivre.uff.br/esl/
http://softwarelivre.uff.br/esl/course/view.php?id=51  MD Bel 2011.2
http://softwarelivre.uff.br/esl/mod/forum/discuss.php?d=209 Gabriela

Plano de aulas / resumo do que já aconteceu:

1ª aula (10/ago): aula cancelada por ainda não ter sala alocada.
2ª aula (11/ago): dei uma aula para a minha turma e uma para a turma
  da Ana Isabel (que fraturou o tornozelo e está sem poder andar), e
  as duas foram só um pouco diferentes. Discutimos tipos de objetos -
  números, strings, conjuntos, valores de verdade... - e avisei que
  confundir tipos é "erro conceitual gravíssimo" - veja estas regras
  sobre como escrever questões em provas:
    http://angg.twu.net/LATEX/2011-1-GA-regras.pdf
  (depois vou fazer uma versão delas específica para MD).
  Consideramos o exemplo de um programa de computador que é uma
  calculadora na qual o "display" dela funciona também como uma barra
  de texto na qual podemos digitar expressões, e quando apertamos o
  botão "CALC" ela calcula o valor da expressão. Por exemplo,
    "2+3"        -->  "5"
    "2*3+4*5"    -->  "26"
    "26"         -->  "26"
    "2<3"        -->  "V"
    "4>=5"       -->  "F"
    "1/0"        -->  "ERRO"
    "Alexandre"  -->  "ERRO"
    "ERRO"       -->  "ERRO"
  Às vezes vamos considerar que essa calculadora suporta váriaveis,
  como em linguagens de programação... então quando a=2 temos
    "a"          --> "2"
    "a+3"        --> "5"
  e quando a=10 temos:
    "a"          --> "10"
    "a+3"        --> "13"
  Aí nós deixamos de lado temporariamente a idéia dessa calculadora
  que mostra direto o resultado final e começamos a ver como calcular
  expressões passo a passo. Vimos como funcionam o "∧", o "∨" e o "->"
  (definimos eles por tabelas por enquanto), e, supondo que a=2, b=3,
  P=F, Q=V, tentamos calcular "a*b+a" e "(Q->P)∨Q". Mostrei que tipo
  de diagramas estávamos procurando, avisei que os diagramas pra estas
  expressões teriam 11 nós e 16 setas, e os alunos chegaram a isto
  aqui:
                a*b+a                       (Q->P)vQ
              /   |   \                   /     |    \
             /    |    \                 /      |     \
            v     v     v               v       v      v
        2*b+a   a*3+a   a*b+2     (V->P)vQ   (Q->F)vQ   (Q->P)vV
          |  \ /     \ /  |           |   \ /        \ /  |
          |   X       X   |           |    X          X   |
          v  v v     v v  v           v   v v        v v  v
        2*3+a   2*b+2   a*3+2     (V->F)vQ   (V->P)vV   (Q->F)vV
        /   \     |     /           /   \       |      /
       /     \    |    /           /     \      |     /
      v       v   v   v           v       v     v    v
   6*a          2*3+2          FvQ          (V->F)vV
      \       /                   \       /
       \     /                     \     /
        v   v                       v   v
         6+2 ---> 8                  FvV ---> V
  Discutimos também vários tipos de setas erradas - por exemplo:
    2*3+4 --> 2*7
  Não queremos incluir setas erradas nos nossos diagramas.
  Pra minha turma falei do grafo direcionado do "é divisível por" em
  {1,...,6}:
      /\    /\   
      \v    v/   
       6 -> 3    
       | \  |
       v  v |
       2 -> 1 <--- 5
      /^    ^\     ^\
      \/    \/     \/
  e lembrei a todos que ele é representado "em matematiquês" como o
  par ordenado
    ( {1,2,3,4,5},
      {                                    (6,6)
                                    (5,5),
                             (4,4),
                      (3,3),               (6,3),
               (2,2),        (4,2),        (6,2),
        (1,1), (2,1), (3,1), (4,1), (5,1), (6,1) } )
  e que o grafo direcionado do cálculo passo a passo do "a*b+a" é algo
  parecido, mas com strings:
    ( {"a*b+a", "2*b+a", ..., "8"},
      { ("a*b+a", "2*b+a"), ..., ("6+2", "8") } )
  Pra turma da Bel fizemos a tabela do x>3->x^2>3 para alguns valores
  de x,
    x    x>3   x^2  x^2>3  x>3->x^2>3
    --+------------------------------
    0 |   F     0     F       V
    1 |   F     1     F       V
    2 |   F     4     V       V
    3 |   F     9     V       V
    4 |   V    16     V       V
    5 |   V    25     V       V
  e perguntei: será que x>3->x^2>3 é sempre verdade? E disse que na
  aula seguinte nós veríamos expressões que formalizam a idéia de
  "x>3->x^2>3 é sempre verdade" (e que os detalhes seriam complicados
  e que num primeiro momento as pessoas arrancariam os cabelos).

3ª aula (17/ago): cancelada.
4ª aula (18/ago): Voltando à idéia da calculadora, se ela usa a
  sintaxe do C, em que o "=" quer dizer atribuição e comparação é
  "==", então:
    "b = (a = 22) + 3"    -->   25
         \------/
            22
         \----------/
              25
     \--------------/
           25
   e depois disto as variáveis "a" e "b" passam a ter os valores 22 e
   33 respectivamente, e:
     "a"      -->  "22"
     "b"      -->  "25"
     "a+b"    -->  "47"
   em MD nós vamos SEMPRE usar ":=" para atribuição, mas essas
   atribuições vão ser TEMPORÁRIAS (!!!!!!!!!!!!!!!)... Em Matemática,
   ao contrário de em programação as variáveis nunca mudam de valor -
   vamos entender isto aos poucos.
   Se a calculadora suporta atribuição com ":=", então:
     "x := 2"    -->  "2"
     "x^2 < 10"  -->  "V"
     "x := 3"    -->  "3"
     "x^2 < 10"  -->  "V"
     "x := 4"    -->  "4"
     "x^2 < 10"  -->  "F"
   A calculadora que a Gabriela (monitora) está implementando vai
   saber calcular coisas como:
     "∀x∈{2,3,4}.x^2<10"   -->  "F"
   Mas precisamos entender como ela (a calculadora) faz isto...
   Como podemos calcular expressões com "∀" e "∃" passo a passo?
   A sintaxe das expressões com "∀" é SEMPRE assim:
     ∀ (variável) ∈ (conjunto) . (expressão)
   então, por exemplo,
     "∀x∈{2,3,4} x^2<10"   -->  "ERRO"
   porque falta o "." (!!!!!!!!!!) e
     "∀2∈{2,3,4}.x^2<10"   -->  "ERRO"
   porque 2 não é uma variável!!!!!!!!!! Em Matemática Discreta, como
   em calculadoras e em linguagens de programação, QUALQUER erro de
   sintaxe TEM que ser tratado como erro - se a gente começa a ser
   tolerante com erros de sintaxe mais tarde a gente vai ser obrigado
   a decidir o significado de expressões ambíguas, e a gente vai se
   ferrar; o único modo da gente se proteger contra ambiguidades é a
   gente se restringir a expressões com a sintaxe correta.
     A regra pra gente fazer o "passo" que nos livra de um "∀" é a
   seguinte: "∀ (variável) ∈ (conjunto) . (expressão)" vira várias
   "cópias" da "expressão", uma para cada elemento do "conjunto", mas
   em cada "cópia" substituimos cada ocorrência da "variável" pelo
   elemento correspondente do conjunto, e depois conectamos as
   "cópias" com "∧"s...
   Passei estes exercícios, e passamos muito tempo discutindo eles:
     (1) ∀a∈{-1,0,1}.a^2<a
     (2) ∀P∈{V,F}.(P->P)
     (3) ∀P∈{V,F}.∀Q∈{V,F}.P∨Q
     (4) ∀a∈{0,1}.a<2∨(∀a∈{1,2}.a>1)
   Por exemplo:
        ∀a∈{-1,0,1}.a^2<a
                  |
                  v
     ((-1)^2<(-1))∧(0^2<0)∧(1^2<1)
                  :
                  v
                F∧V∧V
   e:
       ∀P∈{V,F}.∀Q.{V,F}.P∨Q -----> ∀P∈{V,F}.((P∨V)∧(F∨F))
                  |                         :
                  v                         :
    (∀Q∈{V,F}.V∨Q)∧(∀Q∈{V,F}.F∨Q)           :
                  :                         :
                  v                         :
     ((V∨V)∧(V∨F))∧((F∨V)∧(F∨F)) <- - - - - /
  A diferença entre "∀" e "∃" é que no "∀" a gente usa "∧" e no "∃" a
  gente usa "∨". Comentei que "∀" e "∃" são parecidos com somatórios -
  por exemplo,
    _5_
    \     2	     2	        2	   2	
    /__ (k  + 1) = (3  + 1) + (4  + 1) + (5  + 1)
    k=3
  repare que em somatórios a gente liga as "cópias" com sinais de "+".
  Fiquei de pôr aqui na página do curso mais um monte de exercícios de
  fixação sobre quantificadores. Os primeiros exercícios são:
    (5) ∀P∈{F,V}.P∨¬P
    (6) ∀P∈{F,V}.∀Q∈{F,V}.P->(P∧Q)
    (7) ∀P∈{F,V}.∀Q∈{F,V}.(P∧Q)->P
    (8) ∀P∈{F,V}.∀Q∈{F,V}.(P∨Q)->P
    (9) ∀P∈{F,V}.∀Q∈{F,V}.P->(P∨Q)
    (10) ∃a∈{0,1,2,3}.2*a=3
    (11) ∃a∈{0,1,2,3,4}.2*a=4
    (12) ∃a∈{0,1,2,...,100}.2*a=100
  nos próximos exercícios onde estiver escrito "a|b" (pronúncia: "a
  divide b") você vai ter que substituir o "a|b" por
  "∃k∈{0,...,b}.a*k=b" - ou seja, a _definição_ de "a|b" vai ser 
  "∃k∈{0,...,b}.a*k=b" (vamos ver mais sobre definições em breve).
    (13) ∃a∈{2,3,4}.a|5
    (14) ∃a∈{2,...,5}.a|6

5ª aula (24/ago): pus os problemas (5) a (14) da aula passada no
  quadro, e mais estes:
    (15) -2|4
    (16) 2|-4
  Está na hora de todo mundo aprender a fazer as próprias definições
  (pus no quadro avisos de que os alunos vão passar o curso todo de
  Ciência da Computação fazendo definições, que eles vão ter que
  começar a treinar logo, caveira × 10, etc), e a passei estes
  exercícios:
    (A) Dê uma definição para "a é par" e teste-a.
    (B) Dê uma definição para "a é ímpar" e teste-a.
    (C) Isto vale? ∀a∈Z.(a é par)∨(a é ímpar)
    (D) Isto vale? 2/3 é ímpar
    (E) Dê uma definição de ímpar na qual 2/3 seja ímpar (e teste-a).
  Acabamos ficando só no (A). Apareceram várias definições erradas,
  além da certa, e vi que o mais interessante seria testarmos cada uma
  delas.
    (A1) Def: a é par_1 se e só se ∀b∈Z.∀a∈R.a/2=b
    (A2) Def: a é par_2 se e só se ∃k∈Z.(ak=b∧(a/2∈Z))
    (A3) Def: a é par_3 se e só se ∃b∈Z.∀a∈R.a/2=b
    (A4) Def: a é par_4 se e só se ∃x∈Z.x/2∈Z
    (A5) Def: a é par_5 se e só se ∃a∈Z.a/2∈Z
  Vimos que os quantificadores criam "variáveis locais", como em
  linguagens de programação....
6ª aula (25/ago):
  Vimos duas sintaxes para definições:
    Def: f(P,Q) = (P->(P∧Q))
    Def: f(P,Q) se e só se P->(P∧Q)
  E discutimos como usar definições pra calcular mais rapidamente
  os itens (5) a (16) da 4ª aula.

7ª aula (31/ago): na aula anterior só 5 pessoas vieram...
  Voltamos aos problemas (15) e (16). Ninguém sabia o que deveria ser
  {-4,...,0}, então trabalhamos em cima deste problema (que chamamos
  de "4", por motivos que não importam aqui):
    (4) Encontre uma definição para {a,...,b} e teste-a. Sua definição
        deve dar o resultado "óbvio" pelo menos nos itens 4a e 4b
        abaixo:
      (4a) Calcule {0, ..., 2}.
      (4b) Calcule {1, ..., 4}.
      (4c) Calcule {1.1, ..., 4.1}.
      (4d) Calcule {1.1, ..., 4}.
      (4e) Calcule {1.1, ..., 1.1}.
      (4f) Calcule {0, ..., -4}.
  Apareceram as seguintes definições, e começamos a testá-las:
    {a,...,b} se e só se ∃k∈{a,...,b}.ak=b∧b=a+n∧n∈R   (Gustavo)
    {a,...,b} = ∀a<b.∃k∈Z.{{a,...,b} | a<k<b}          (Thiago)
    {a,...,b} = (∃k∈{a,...,b}.4+k>b)                   (Rodrigo)
    {a,...,b} = (∃!n∈R.a+n_1+n_2+...+n_x=b)            (Natan)
    {a,...,b} = ∀k∈{0,...,2}.k+1<=2∧n∈N                (Luis Fernando)
    {a,...,b} se e só se ∃k∈R.a<k<b                    (Luis Felipe)
    {a,...,b} se e só se ∃k∈{0,...,2}.a<=2k            (Dângelo)
8ª aula (01/set): "Workshop de definições".
  Vimos alguns critérios rápidos pra testar se definições - em
  particular as definições para {a,...,b} da aula passada - estão
  erradas:
    1) Sintaxe
    2) Tipos
    3) Variáveis indefinidas
    4) Recursão
  e vimos que cada uma das definições propostas na aula passada tinha
  pelo menos um desses erros.
  Pra casa: encontre duas definições diferentes para {a,...,b}, que
  dêem os resultados "esperados" quando a,b∈Z e a<=b, mas:
    {4.1, ..., 6.1}_I = {5, 6}
    {4.1, ..., 6.1}_R = {4.1, 5.1, 6.1}

9ª aula (07/set): feriado.
10ª aula (08/set):
  Mostrei duas regras pra lidar com "_∈{_|_}": a "regra nova" e a
  "regra horrível". A "regra nova" nos permite lidar com expressões da
  forma "_ ∈ {gerador | filtro}". Exemplo:
    2.5 ∈ {k∈R | a+k<=b}
             |
             v
      2.5∈R ∧ a+2.5<=b
  A "regra horrível" nos permite traduzir expressões da forma
  "{expressão | gerador}" para "{gerador | filtro}". Exemplo (com dois
  geradores):
    {a+b | a∈{10,20}, b∈{3,4}}
                |
                v
    {x∈R | ∃a∈{10,20}.∃b∈{3,4}.a+b=x}
  Repare que "x∈R" é um gerador difícil de usar (porque gera valores
  demais) e "∃a∈{10,20}.∃b∈{3,4}.a+b=x" também pode ser um filtro
  difícil de usar... mas num caso como este, que eu passei como
  exercício na aula,
    14 ∈ {a+b | a∈{10,20}, b∈{3,4}}
  podemos usar a "regra horrível", depois a "regra nova", depois
  expandir os dois "∃"s, e chegar ao resultado.
  Os alunos passaram a aula quase toda propondo definições para
  {a,...,b}_R e testando-as (eu avisei que é muito melhor a gente
  escrever definições possivelmente erradas e tentar testá-las e
  consertá-las do que não escrever nada). As definições que foram
  postas no quadro foram estas:
    {a,...,b}_RNatan1    = {k∈Z | a<=k<=b | k∈[a,b]}
    {a,...,b}_RNatan2    = {k∈Z | a<=k<=b ∧ k∈[a,b]}
    {a,...,b}_RNatan3    = {k∈R | a<=k<=b ∧ k∈[a,b]}
    {a,...,b}_RThaynara  = {k∈R | a+k<=b}
    {a,...,b}_RThaynara2 = {k∈R | a<=k<=b}
    {a,...,b}_RThiago    = {k∈N | a<=a+k<=b}
    {a,...,b}_RRodrigo   = {∃k∈N | 0<=k<=b ∧ k+a<=b}
    {a,...,b}_RNatan4    = {k∈N | a+k∈(a,b)}
    {a,...,b}_RNatan5    = {k∈N | a+k∈[a,b]}
    {a,...,b}_RRodrigo2  = {a+k | k∈{0,1,2}}
    {a,...,b}_RNatan'    = {k∈R | x<b ∧ a+x=k}
  Vimos que este programa em C,
    int main(void) {
      float a=2.1, b=4.1, k;
      for (k=0; a+k<=b; k++)
        printf("%f\n", a+k);
    }
  meio que corresponde a esta expressão em matematiquês:
    {a+k | k∈Z, a+k<=b}

11ª aula (14/set): Definições indutivas e notação para definições por
  casos. Exerçícios:
  (F_0, F_1, F_2, ...) = (0, 1, 1, 2, 3, 5, ...)   (Fibonacci)
  (a_0, a_1, a_2, ...) = (0, 1, 1+2, 1+2+3, ...)
                             1  1+2  1+2+3     )
  (b_0, b_1, b_2, ...) = (0, -, ---, -----, ...)
                             1   2     3
  a%d = resto da divisão de a por d
12ª aula (15/set): Introdução a gramáticas e BNF.
  Discutimos uma gramática parecida com esta ("G1"),
    digit  : '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'   /* 1 */
    digits : digit                       /* 2 */
           | digit digits                /* 3 */
    number | digits                      /* 4 */
    exp    : number                      /* 5 */
           | exp '+' exp                 /* 6 */
           | exp '-' exp                 /* 7 */
           | exp '*' exp                 /* 8 */
           | exp '/' exp                 /* 9 */
           | '-' exp                     /* 10 */
           | exp '^' exp                 /* 11 */
           | '(' exp ')'                 /* 12 */
  e como o conjunto dos strings que são "exp"s pode ser expresso como
  uma construção indutiva; vimos como provar que "2*3+(-45*6)" é uma
  "exp". Obs: esta gramática é adaptada da que aparece aqui:
    (find-node "(bison)Infix Calc")

13ª aula (21/set): A gramática G1, acima, tem "ambiguidades". Vimos
  que há vários modos de parsear a expressão "2*3+(-45*6)", e que
  podemos usar uma relação Val_G1 pra definir precisamente o que quer
  dizer "s é uma expressão válida que pode ter o valor v". Por
  exemplo:
      Val_G1("2*3",6)  Val_G1("(-45*6)",-270)
      ---------------------------------------
             Val_G1("2*3+(-45*6)",-264)
  e:
      Val_G1("2",2)  Val_G1("3+(-45*6)",-267)
      ---------------------------------------
             Val_G1("2*3+(-45*6)",-534)
  um modo de consertá-la é este. A gramática G2 é:
    digit  : '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'  /* 13 */
    digits : digit                        /* 14 */
           | digit digits                 /* 15 */
    number | digits                       /* 16 */
    pexp   : number                       /* 17 */
           | '(' aexp ')'                 /* 18 */
    mexp   : pexp                         /* 19 */
           | mexp '*' pexp                /* 20 */
           | mexp '/' pexp                /* 21 */
    aexp   : mexp                         /* 22 */
           | '-' mexp                     /* 23 */
           | aexp '+' mexp                /* 24 */
           | aexp '-' mexp                /* 25 */
  Esta gramática nos dá a noção certa de "subexpressão" - quando
  parseamos "2*3+(-45*6)" as subexpressões são os substrings que
  aparecem como "pexp"s, "mexp"s ou "aexps".
  [[Falta uma parte]]
14ª aula (22/set): variáveis ligadas, substituição, regras de dedução.
        /------------y------------\
        |               /---x---\ |
        |               |       | |
    P(x,y) := ∀x∈{2,3}.∀x∈{3,4}.x<y
  é equivalente a:
        /------------y------------\
        |               /---z---\ |
        |               |       | |
    P(x,y) := ∀x∈{2,3}.∀z∈{3,4}.z<y
  e daí
    P(5,6) = ∀x∈{2,3}.∀z∈{3,4}.z<6
  [[ Acabei não transcrevendo muita coisa! Usei alguns exemplos
  bastante bons, preciso pegá-los do caderno de algum aluno... ]]

15ª aula (28/set): Introdução a provas formais "em Fitch".
  [[ Preciso pôr aqui os exemplos e exercícios da aula... ]]
16ª aula (29/set): Que regras são válidas numa prova formal (em
  Fitch)? Nós já vimos várias regras válidas ("*" = caveirinha),
    | P      
    | Q      | P∧Q     | P∧Q        
    +----    +----     +----        
    | P∧Q    | P       | P    
    (conj)   (simp1)   (simp2)            
                                          | | P         
    | P      | P->Q                       | +---        
    | P->Q   | ¬Q      | P      | ¬¬P     | | :         
    +-----   +-----    +----    +----     | | :         
    | Q      | P       | ¬¬P    | P       | | Q         
    (MP)     (MT)      (neg)    (neg)     | P->Q        
                                          (-> Intro (*))
    | P      | Q
    +----    +----
    | P∨Q    | P∨Q
    (∨I1)    (∨I2)
      Links:
      (find-books "__logic/__logic.el" "barwise-etchemendy")
      (find-barwiseetchemendypage (+ 10 148) "6.2 Disjunction rules")
      (find-barwiseetchemendypage (+ 10 206) "8.2" "-> Intro")
  Mas estas não são todas, e nenhuma pessoa normal decora todas.
    A qualquer momento numa prova em Fitch podemos colocar uma
  "conclusão" que seja algo que já sabíamos - por exemplo os axiomas
  do apêndice C do Scheinerman - ou uma tautologia, ou algo que
  provamos "por contas"... Lembre que cada novo passo tem que ter uma
  "justificativa", e ela tem que ser válida.
    Como é que tautologias viram regras de dedução?
    Exemplo: ∀P,Q,R∈{F,V}.((P->R)∧(Q->R)->(P∨Q->R)). Calcular por
  redução ("-~->") que isto é verdade dá um trabalhão (tente em casa -
  procure modos de reduzir as contas, depois tente explicá-los em
  português de forma que todo mundo entenda); verificamos isto com uma
  tabela improvisada:
      P  Q  R   (P-->R)∧(Q-->R)-->(P∨Q-->R)
      --------+----------------------------
      F  F  F |                 V  FFF V
      F  F  V |                 V      V V
      F  V  F |        F V F F  V
      F  V  V |                 V      V V
      V  F  F |  V F F F        V
      V  F  V |                 V      V V
      V  V  F |        F V F F  V
      V  V  V |                 V      V V
   [[ completar ]]
   (find-QUADROfile "" "2011-09-29-MD")
   (find-QUADRO        "2011-09-29-MD-1.jpg")
   (find-QUADRO        "2011-09-29-MD-2.jpg")
   (find-QUADRO        "2011-09-29-MD-3.jpg")
   Em exercício (grande & difícil; pedi pra tentarem improvisar antes
   de ver as regras de verdade). Digamos que sabemos que:
     Def:   a é par <-> ∃x∈Z.2x=a
     Def: a é ímpar <-> ∃x∈Z.2x+1=a
     e que ∀x∈Z.(x é par)∨(x é ímpar).
   Prove que ∀x∈Z.x^2+x é par.
   Um exemplo de uma dedução em Fitch com regras ∃-intro e ∃-elim - a
   regra ∃-elim é uma das regras difíceis (com caveira!) que envolvem
   hipóteses temporárias que são descartadas.
      1 | a é par
        +--------
      2 | ∃x∈Z.2x=a               (por 1 e pela def de par)
      3 | | x∈Z                   (HIPÓTESE TEMPORÁRIA!)
      4 | | 2x=a                  (HIPÓTESE TEMPORÁRIA!)
        | +-----
      5 | | a^2+a = (2x)^2+(2x)   (por 4 e álgebra)
      6 | | a^2+a = 2(2x^2+x)     (por 5 e álgebra)
      7 | | 2x^2+x∈Z              (por 3 e álgebra)
      8 | | ∃y∈Z.a^2+a=2y         (por 6,7, ∃-intro)
      9 | | a^2+a é par           (por 8 e pela def de par)
     10 | a^2+a é par             (por 2-9, ∃-elim)

17ª aula (05/out): Hoje: conjuntos!
  (Dica: pra seguir esta parte do curso é melhor usar o livro da
  Judith, principalmente o cap.3).
  Conjuntos são definidos pelos seus elementos: se A e B são
  conjuntos, então
    A=B <-> ∀x.(x∈A<->x∈B)
  Note que aqui apareceu um "∀_._" - estávamos usando só "∀_∈_._"!
  Além disso:
    y∈{x∈A|P(x)} <-> y∈A∧P(y)
  Note que os "<->"s acima podem ser utilizados como _definições_ para
  igualdade de conjuntos e para "_∈{_|_}".
    Def: [a,b] = {x∈R|a<=x<=b}
    Def: a<=b<=c <-> a<=b∧b<=c
  Vamos ver como provar formalmente coisas como
    ∀x∈[3,4].2<x     e
    A∩(B∩C)=(A∩B)∩C,
  e no caminho vamos entender mais coisas sobre as regras do "∀".
  [*CAV*] O livro da Judith - e o do Scheinerman - usam principalmente
  "∀_._" e "∃_._" ao invés de "∀_∈_._" e "∃_∈_._" - isso é horrível
  para _calcular_ coisas, mas facilita _demonstrações_.
  Duas definições possíveis (equivalentes) para "∩":
    Def:   A∩B  = {a∈A|a∈B}    (*)
    Def: x∈A∩B <-> x∈A∩x∈B     (**)
  Não estamos acostumados a usar definições como a (**)...
  Obs: def: P<->Q <-> (P->Q)∧(Q->P)
  Exercícios: prove que
    | x∈A∩B    | x∈(A∩B)∩C   |			    
    +------    +----------   |			    
    |  :       |  :          | :		    
    | x∈B∩A    | x∈A∩(B∩C)   | x∈(A∩B)∩C<->x∈A∩(B∩C)
  Alguns modos de resolvê-los:
    1 | x∈A∩B    
      +------    
    2 | x∈A∧x∈B  (por (**))
    3 | x∈A
    4 | x∈B      
    5 | x∈B∧x∈A
    6 | x∈B∩A    (por (**))
  e
     1 | x∈(A∩B)∩C
       +----------
     2 | x∈(A∩B)∧x∈C  (por 1, (**))
     3 | x∈A∩B
     4 | x∈A∧x∈B      (por 3, (**))
     5 | x∈A
     6 | x∈B
     7 | x∈C
     8 | x∈B∧x∈C
     9 | x∈B∩C        (por 8, (**))
    10 | x∈A∧x∈B∩C    
    11 | x∈A∩(B∩C)   (por 10, (**))
  e
    100 | | x∈A∩(B∩C)
        | +----------			    
    101 | | x∈A∧x∈B∩C
        | | :
    148 | | x∈(A∩B)∩C  
    149 | x∈A∩(B∩C)->x∈(A∩B)∩C    (por 101-148, ->Intro)
    150 | | x∈(A∩B)∩C			    
        | +----------			    
        | | :		    
    197 | | x∈A∩(B∩C)
    198 | x∈(A∩B)∩C->x∈A∩(B∩C)    (por 150-197, ->Intro)
    199 | x∈(A∩B)∩C<-x∈A∩(B∩C)    (por 149, reescrevendo P->Q como Q<-P)
    200 | x∈(A∩B)∩C<->x∈A∩(B∩C)   (por 198, 199, def do "<->" (conj))
  Note que a passagem 197,198->200 poderia ser feita "mais
  honestamente" assim:
    198   | P->Q
    199   | P<-Q
    199.5 | (P->Q)∧(P<-Q)
    200   | P<->Q             (por 199.5, def do "<->")
  Regras novas ([*CAV*] - são difíceis de formalizar):
    | P(x)
    +-----
    |  :
    | Q(x,y)
    | ∀y.Q(x,y)   (∀-Intro)
  a regra "∀-Intro", que generaliza a conclusão de Q(x,y) para
  ∀y.Q(x,y), _só pode ser utilizada quando não há nenhuma hipótese
  adicional sobre y_ - ou seja, quando o y que estávamos utilizando
  "podia ser qualquer y" (a hipótese P(x) acima está lá só pra sugerir
  que "nenhuma das hipóteses envolve condições sobre o y).
  Variação:
    | P(x)
    +-----
    | | y∈A
    | +----
    | | :
    | | Q(x,y)
    | ∀y∈A.Q(x,y)   (∀-Intro)
  Com estas regras podemos fazer:
    200 | x∈(A∩B)∩C<->x∈A∩(B∩C)
    201 | ∀x.(x∈(A∩B)∩C<->x∈A∩(B∩C))
    202 | (A∩B)∩C=A∩(B∩C)
18ª aula (06/out):
    (find-QUADROfile "" "2011-10-05-MD")
    (find-QUADRO        "2011-10-05-MD-1.jpg")
    (find-QUADRO        "2011-10-05-MD-2.jpg")
    (find-QUADRO        "2011-10-05-MD-3.jpg")

19ª aula (12/out): feriado (dia das crianças e dia nacional da luta
  contra a corrupção).
20ª aula (13/out):
    (find-QUADROfile "" "2011-10-13-MD")
    (find-QUADRO        "2011-10-05-MD-1.jpg")
    (find-QUADRO        "2011-10-05-MD-2.jpg")
    (find-QUADRO        "2011-10-05-MD-3.jpg")
    (find-QUADRO        "2011-10-05-MD-4.jpg")

21ª aula (19/out): semana acadêmica
22ª aula (20/out): semana acadêmica

23ª aula (26/out): revisão pra prova
    (find-QUADROfile "" "2011-10-26-MD")
24ª aula (27/out): Pegamos uma demonstração em Português que apareceu
  na P2 do semestre passado, que era:
    (A) Suponha que a é um inteiro que é par e ímpar ao mesmo tempo.
        Então existem inteiros x e y tais que a=2x e a=2y+1, e temos
        2x=2y+1 e 1=2x-2y=2(x-y); portanto x-y = 1/2, que não pertence
        a Z, mas como x,y∈Z temos x-y∈Z, uma contradição.
  E tentei ver que dificuldades os alunos teriam para traduzí-la para
  Fitch. Dei as seguintes dicas:
    (1) nomeie as sub-sentenças (P, Q, P_1, ...)
        e subprovas (P->¬Q, ...);
    (2) divida o problema maior em vários subproblemas;
    (3) anote quais são as variáveis livres em cada sentença e as
        hipóteses que foram usadas pra chegar a cada conclusão;
    (4) **teste os subproblemas**;
    (5) liste as definições;
    (6) anote que regra de dedução você usou para chegar a cada
        conclusão;
    (7) ponha "?"s nos passos dos quais você não tem certeza ou que
        você acha que merecem mais detalhes;
    (8) traduza entre português e matematiquês, usando vários passos
        se necessário.
  Exercícios (pequenos):
    (I) Quais são as hipóteses da prova A e qual a conclusão?
    (II) Expresse A como "H_1∧H_2∧...∧H_n->C" ou como "∀_∈_._".
    (III) Liste as definições usadas em A e expresse-as em
          matematiquês formal.
  Não fomos muito longe 8-(.
  Algumas dificuldades que surgiram: às vezes as pessoas confundem
  definir "___ é par" e definir o conjunto dos números pares; e
    Def: par = {a | ∀x∈R | a=2x}
  tem _montes_ de problemas!...

25ª aula (02/nov): feriado - finados
  *** vou pôr aqui as idéias que surgiram em e-mails ***
  Um exemplo simples de como usar o ∃-elim:
        | .
        | :
    100 | ∃a∈A.a<20
    101 | | a∈A        (hipótese temporária)
    102 | | a<20       (hipótese temporária)
        | +-----
    103 | | a<30       (por 102 e álgebra)
    104 | | ∃a∈A.a<30  (por 101 e 103)
    105 | | ∃b∈A.b<30  (por 104, renomeando uma variável local)
    106 | ∃b∈A.b<30    (por ∃-elim - repare que tínhamos concluído
        | .             ∃b∈A.b<30 usando ∃a∈A.a<20, a∈A e a<20, mas
        | :             a regra ∃-elim nos permite descartar as hipóteses
                        a∈A e a<20 e manter só a hipótese ∃a∈A.a<20)
  Uma dica importante:
  ====================
  Se uma dedução estiver certa então cada linha dela pode ser
  reescrita "com todas as suas hipóteses explícitas", como no exemplo
  abaixo:
    100 | ∃a∈A.a<20         (∃a∈A.a<20)             ->(∃a∈A.a<20)
    101 | | a∈A             (∃a∈A.a<20)∧(a∈A)       ->(a∈A)
    102 | | a<20            (∃a∈A.a<20)∧(a∈A)∧(a<20)->(a<20)
        | +-----
    103 | | a<30            (∃a∈A.a<20)∧(a∈A)∧(a<20)->(a<30)
    104 | | ∃a∈A.a<30       (∃a∈A.a<20)∧(a∈A)∧(a<20)->(∃a∈A.a<30)
    105 | | ∃b∈A.b<30       (∃a∈A.a<20)∧(a∈A)∧(a<20)->(∃b∈A.b<30)
    106 | ∃b∈A.b<30         (∃a∈A.a<20)             ->(∃b∈A.b<30)
  e todas estas "proposições com hipóteses explícitas" têm que ser
  verdadeiras - e sem hipóteses adicionais!
    Repare que neste exemplo o valor de cada proposição que apareceu
  na coluna da direita "depende" do valor de algumas variáveis. Mas
  precisamente: só sabemos CALCULAR - pelas regras de redução - o
  valor da expressão da linha 100,
    100                                  (∃a∈A.a<20)->(∃a∈A.a<20)
  se A for conhecido, e só sabemos CALCULAR o valor de
    105                     (∃a∈A.a<20)∧(a∈A)∧(a<20)->(∃b∈A.b<30)
  se conhecemos A e a...

  O problema dos "inteiros pares e ímpares ao mesmo tempo"
  ========================================================
  A tradução para Fitch dele é:
     1 | a∈Z
     2 | a é par e ímpar
       +--------------------------
     3 | (∃x∈Z.2x=a)∧(∃y∈Z.2y+1=a)
     4 | ∃x∈Z.2x=a
     5 | ∃y∈Z.2y+1=a
     6 | | x in Z
     7 | | 2x=a
       | +---------
     8 | | | y in Z
     9 | | | 2y+1=a
       | | +--------
    10 | | | 2x=2y+1
    11 | | | 2x-2y=1
    12 | | | 2(x-y)=1
    13 | | | x-y=1/2
    14 | | | ¬(x-y∈Z)
    15 | | | x-y∈Z
    16 | | | F
    17 | | F
    18 | F
  Exercícios:
    1) Explique porque - e em que sentido - P∧Q->F é equivalente
       a P->¬Q.
    2) Escreva à direita de cada proposição da prova acima a sua
       "versão com hipóteses explícitas", e as variáveis das quais ela
       depende.
    3) Explique esta dedução:
         1 | ¬(x-y∈Z)
         2 | x-y∈Z
           +------
         3 | F
    4) Complete a dedução acima (a de 18 linhas) dizendo o nome da
       regra utilizada em cada passo. Obs: este exercício é uma
       desculpa pra fazer você se familiarizar com as regras do Fitch.
    5) Explique (pode ser em Português) como é que a demonstração
       acima prova que não existe inteiros que são pares e ímpares ao
       mesmo tempo.
    6) (Difícil.) Releia a seção 1.4 - "Lógica de Predicados" - do
       livro da Judith Gersting, e compare o "axioma 6" dela com a
       regra "∃-elim" do Fitch. Obs: as "várias livres" nas deduções
       funcionam de modos completamente diferentes no Fitch e no
       sistema da Judith...
    7) Verifique que "∃a∈A.P(a)" é equivalente a "∃a.(a∈A∧P(a))" (se
       você não achar isto óbvio), e explique porque é que a nossa
       regra pro "∃" introduz _duas_ hipóteses temporárias ao invés de
       uma só; compare com a do Barwise/Etchemendy, que introduz uma
       hipótese temporária só.
    8) Traduza para Fitch a demonstração que aparece na questão 6 da
       P2 do semestra passado:
         http://angg.twu.net/MD/MD_P2_2011jun22.pdf
    9) Traduza para Fitch mais demonstrações que aparecem no capítulo
       2 do livro da Judith.
    Obs: há um scan de uma parte do livro da Judith em:
      http://angg.twu.net/MD/judith_p59_a_110.pdf
    e um scan inteiro dele (e do Barwise/Etchemendy também) no
    bcclivros.
26ª aula (03/nov): P1 - matéria: construções indutivas e um pouco de
  demonstrações - basicamente tudo o que vimos até agora!
    *** As questões e o gabrito estão aqui: ***
    http://angg.twu.net/MD/MD_P1_2011nov03.pdf
    http://angg.twu.net/MD/MD_P1_2011nov03.djvu

27ª aula (09/nov): não teve aula (a prova de GA esticou demais)
28ª aula (10/nov):
   Falta transcrever...
   (find-QUADRO "2011-11-10-MD-1.jpg")
   (find-QUADRO "2011-11-10-MD-2.jpg")
   (find-QUADRO "2011-11-10-MD-3.jpg")
   (find-QUADRO "2011-11-10-MD-4.jpg")
   (find-QUADRO "2011-11-10-MD-5.jpg")

29ª aula (16/nov):
  [Falta transcrever...]
30ª aula (17/nov):
  Ontem vimos quantas comparações certos algoritmos de ordenação
  precisam. Por exemplo, tanto o "bubble sort" quanto o "selection
  sort" usam:
    compr(a) | comparações
    ---------+------------
        5    | 4+3+2+1       =   5(5-1)/2     =  5^2/2 - 5/2
       20    | 20+19+...+2+1 = 20(20-1)/2     = 20^2/2 - 20/2
     1000    | 999+...+1     = 1000(1000-1)/2 = 1000^2/2 - 1000/2
  Vamos ver que 
    [Falta completar]

31ª aula (23/nov): Ordem de crescimento de funções.
32ª aula (24/nov): Ordem de crescimento de funções.
  Seja f(n) o número máximo de comparações para o mergesort ordenar
  uma lista de comprimento 2^n; seja g(n) o número de comparações que
  o selection sort precisa para uma lista de comprimento 2^n, e seja
  h(n) o número de comparações que o selection sort precisa para uma
  lista de comprimento n. Podemos usar uma abreviação:
    nmaxcomp(algoritmo, comprimento)
  Então:
    f(n) = nmaxcomp(mergesort,      2^n)
    g(n) = nmaxcomp(selection sort, 2^n)
    h(n) = nmaxcomp(selection sort,   n) = g(2^n)
  Tabelas:
    n   h(n)               n   2^n   f(n)   g(n)   
    --+-----		   --+-----+------+------  
    1 |   0		   0 |   1 |  0   |   0    
    2 |   1  =       1	   1 |   2 |  1   |   1    
    3 |   3  =     2+1	   2 |   4 |  5   |   6    
    4 |   6  =   3+2+1	   3 |   8 | 17   |  28    
    5 |  10  = 4+3+2+1	   4 |  16 | 49   | 120    
  Exercício 1: dê uma definição formal, em matematiquês puro, das
    funções f, g e h.
  Aí eu convenci os alunos de que uma definição indutiva iria nos
  ajudar mais com os problemas seguintes que uma definição em forma
  fechada, e a gente chegou a:
    Def: h: N^+ -> N
             n |-> / 0              quando n=1
                   |
                   \ h(n-1)+(n-1)   quando n>1
  Essa definição é fácil de justificar, e a forma fechada aparece como
  um teorema (a prova é por indução)...
    Teorema: ∀n∈N^+.(h(n) = n(n-1)/2).
  Daí: g(n) = h(2^n) = ((2^n-1)*2^n)/2 = ... = 2^(2n-1)-2^(n-1).
  Aí usamos um argumento gráfico pra ver como fazer uma definição
  indutiva pra função f. Representando os dados por caixinhas,
            _
    f(0) = |_| = 0 comparações
            ___ 
    f(1) = |_|_| = 1 comparação
	   |___|
            _______     ___     ___ 
           |_|_|_|_|   |_|_| + |_|_|
    f(2) = |___|___| = |___|   |___|     = 2*f(1)+3
    	   |_______|    + 3 comparações
            _______________     _______     _______ 
    	   |_|_|_|_|_|_|_|_|   |_|_|_|_|   |_|_|_|_|
    f(3) = |___|___|___|___| = |___|___| + |___|___|
    	   |_______|_______|   |_______|   |_______|
    	   |_______________|    + 7 comparações
   E chegamos a:
     f(0) = 0
     f(1) = 2f(0) + 2^1 - 1
     f(2) = 2f(1) + 2^2 - 1
     f(3) = 2f(2) + 2^3 - 1
     f(4) = 2f(3) + 2^4 - 1
     ...
     f(n) = 2f(n-1) + 2^n - 1   
  Na próxima aula vamos ver como entender com que velocidade a função
  f cresce - sem fazer contas horríveis. Falei um pouquinho de funções
  O(n), O(n^2), etc, e os alunos ficaram com xeroxes das páginas
  248-251 do livro da Judith (a seção "Ordem de grandeza de funções",
  que só tem na edição de capa branca).

33ª aula (30/nov): Def: sejam f,g: R^+ -> R^+ (obs: R^+ = (0,∞)).
  Então os gráficos de f e g estão no 1º quadrante.
  Def: f<=g se e só se ∀x∈R^+.(f(x)<=g(x)).
  (Idem para <, >, >=, =).
  Def: f<=g a partir de 4 se e só se ∀x∈(4,∞).(f(x)<=g(x)).
  (Idem para <, >, >=, =, para 5, 6, etc).
  Vamos começar com f(x)=x e g(x)=1+x/2.
    1) Faça os gráficos de f e g.
    2) Mostre que f>=g a partir de algum ponto.
    3) Mostre que f>=g é falso.
  Def: se a∈R, f:R->R, então
    af: R  -> R
        x |-> af(x)
  Ex: se g(x)=1+x/2, então 4g = ?
  Def (*cav*): se f,g:R^+ -> R^+, então
    f=O(g) se e só se ∃c∈R^+.(f<=cg a partir de algum ponto).
  Exercícios:
  Mostre que:
    a) 3 = O(2),
    b) 2 = O(x),
    c) x = O(10x),
    d) x = O(1) é falso
  e descubra se cada uma das afirmações abaixo é verdade:
    e) 2+sen(x) = O(1)
    f) x = (Ox^2)
    g) x^2 = O(x)
    h) x <= x^2 a partir de algum ponto
    i) x^2 <= 10x a partir de algum ponto
    j) 2x = O(x+1)
    k) x+1 = O(2x)
34ª aula (01/dez): Como as coisas que a gente viu se encaixam?
  A maior parte das funções que descrevem o número de operações
  necessário pra executar certa tarefa são definidas indutivamente.
  Exemplos:
    Se f(n) = maxcomp(selection sort, n) = (n-1)+(n-2)+...+1
    então f(n) = f(n-1) + n-1
    (^ isto é fácil de entender; f(n) = n(n-1)/2 é difícil)
    Se g(n) = maxcomp(mergesort, 2^n)
    então g(n) = 2g(n-1) + 2^n - 1
  Precisamos treinar definições indutivas...
  Problema: digamos que queremos descobrir quantos números de 3
    dígitos existem que são menores que 500 e têm "dígitos
    não-crescentes" (por exemplo, 430 é "não crescente" porque
    4>=3>=0; 440 também; 042 não, porque 0<4).
  Método da força bruta ("when in doubt, use brute force" - Ken
    Thompson). Podemos definir
      A = {n∈N | n<=500, n "tem 3 dígitos não crescentes"}
  A parte entre aspas pode ser formalizada, mas essa definição
  informal basta por enquanto. Aí:
    A = {000, 100, 110, 111, 200, ..., 443, 444, 500}
  e |A| = 36.
  Caso geral:
    D_(k,N) = {n∈\N | n tem k dígitos "não-crescentes", n<=N}
  Exercício 1: calcule
       D_(1,0),    D_(1,1),    D_(1,2),    D_(1,3),    D_(1,4),
      D_(2,00),   D_(2,11),   D_(2,22),   D_(2,33),   D_(2,44),
     D_(3,000),  D_(3,111),  D_(3,222),  D_(3,333),  D_(3,444),
    D_(4,0000), D_(4,1111), D_(4,2222), D_(4,3333), D_(4,4444),
  Consideramos o grafo direcionado G = {V,R},
  onde V={400,300,200,100,000,40,30,20,10,00,4,3,2,1,0}
  e R={(400,40), (400,30), (400,20), (400,10), (400,00),
                 (300,30), (300,20), (300,10), (300,00),
                           (200,20), (200,10), (200,00), ...,
       (20, 2), (20, 1), (20, 0), (10, 1), (10, 0), (00, 0)}
  e vimos que os elementos de D_(3,444) correspondem a caminhos neste
  grafo passando por 3 vértices - p.ex., 422 corresponde a (400, 20,
  2); uma notação melhor para isto é 400->20->2.
  Exercícios, pra todo mundo tentar fazer em grupo nos próximos dias -
  é difícil mas é uma super boa preparação pra prova:
    2) Descubra como definir D_(5,888) a partir de conjuntos menores,
    3) Descubra como calcular |D_(5,888)|.

         (06/dez): vou estar no PURO de tarde. Me procurem para dúvidas
                   e vista de prova!
35ª aula (07/dez): P2. Scan das questões e do gabarito:
  http://angg.twu.net/MD/MD_P2_2011dez07.pdf
  http://angg.twu.net/MD/MD_P2_2011dez07.djvu
36ª aula (08/dez): Feriado

37ª aula (14/dez): VR
38ª aula (15/dez): VS
.                   P1    P2   VR   VS    NF
                   ---   ---  ---  ---   ---
Allan              3.1   2.3  2.6  1.0   2.9
Dângelo            1.1   0.5  0.0   -    0.8
Gustavo            2.1    -    -    -    1.1
Leandro            7.2   3.4   -   3.4   5.3/3.4   -> 4.0/6.0 (*)
Luis Felipe        9.0   5.0   -    -    7.0
Luis Fernando      2.6   0.7   -    -    1.7
Natan Henrique     4.8   3.7  1.0  5.0   4.3/5.0
Natan Tavares      3.4   0.0  0.0   -    1.7
Rodrigo            3.7    -    -    -    1.9
Thaynara           7.2   9.3   -    -    8.3
Thiago             9.2   7.2   -    -    8.2