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 - 2010.1

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.

Resumos das aulas que já foram dadas
(e planos para algumas aulas futuras):

Primeira aula (08/março):
  só um aluno veio
Segunda aula (10/março):
  redução versus igualdade
  operações cujos resultados são valores de verdade: <, <=, =, >=, >
  operações definidas por tabelas: e, ou, implica, não
  operações cujo resultado nem sempre está definido: /, sqrt
  operações cujo domínio não está definido: + (serve para vetores e matrizes)
  tradução entre português e linguagem matemática
  análise sintática em português: sujeito, predicado, objeto, etc; árvores
  termos suprimidos em português: "o gato comeu o rato e cuspiu os ossos"
    versus: "o gato comeu o rato e depois o gato cuspiu os ossos do rato"
  em matematiquês tudo é explícito
  expansão de definições, substituição de valores; contextos
  que expressões são válidas? "12+3*+/-" não é válida
  vamos precisar de construções indutivas pra definir "expressões válidas"
  o que é uma demonstração? Exemplo do 2^100-2^99=2^99
  quando é que uma demonstração está correta?
  quando é que uma demonstração está completa?
  a definição precisa de "demonstração" é indutiva

Terceira aula (15/março):
  definição alternativa de "divide":
    (que pode não ser equivalente à definição "real"!)
    a|b se a∈N ∧ b∈N ∧ ∃k∈{0,1,2,...b}.b=ka
  vimos várias definições para {0,1,2,...,-3} que pareciam razoáveis
  problemão: quando é que uma definição está "errada"?
  [vou completar o resumo da 3ª aula depois]
Quarta aula (17/março):
  na aula anterior vimos que no ∧ e F "domina", e no ∨ o V "domina"
  usamos isto para reduzir 50|1000 a V rapidamente
  idéia parecida: Seção 4, Contra-exemplo (pp.24-26)
  comparação com 10*9*8*...*(-2)*(-3)*(-4) = 0
  vimos como definir "proposições sobre números": P(x) = (x>4), P(x)=V
  a redução ∀x∈A.P(x) -v^v-> F por contra-exemplo envolve encontrar um a∈A
    tal que  P(a) seja falso, e envolve uma "justificativa" - uma anotação
    do lado da seta -v^v->, explicando o porquê.
  Seção 6: Listas
  listas são diferentes de números, de valores de verdade e de conjuntos
  duas listas são iguais se têm o mesmo comprimento e mesmas componentes
  já vimos pares ordenados: (3,4)∈R^2, (3,4) \neq (4,3)
  em conjuntos a ordem não importa: {3,4}={4,3}
  redução para "∈": a∈{b,c,d} -v^v-> a=b∨a=c∨a=d
  a definição formal de produto cartesiano só aparece na p.72:
    A×B = {(a,b)|a∈A, b∈B}
  podemos pensar que "a∈A" e "b∈B" são "geradores", e geram todos os
    valores possíveis de a e b
  em C = {n∈{10,...,20} | n é primo} o gerador é o n∈{10,...,20};
    o "n é primo" é um "filtro" que descarta certos valores de n
  filtros e geradores podem ser combinados:
    {(a,b) | a∈{0,1,2}, b∈{1,2,3}, a<=b}
    {a^2 | a∈{-1,0,1,2}}  -v^v->  {1,0,1,4}  =  {0,1,4}

Quinta aula (22/março):
  Seção 5: Álgebra de Boole
  Esquema de prova 4: tabelas de verdade
  Apêndice C: Fundamentos
Sexta aula (24/março):
  Exercício.
  Considere as expressões abaixo:
    ∀x∈A∪B.P(x)
    ∀x∈A∩B.P(x)
    ∃x∈A∪B.P(x)
    ∃x∈A∩B.P(x)
    ∀x∈A.(x∈B->P(x))
    ∀x∈A.(x∈B∧P(x))
    ∃x∈A.(x∈B->P(x))
    ∃x∈A.(x∈B∧P(x))
  Algumas são equivalentes entre si. Quais?
  Encontre modos de mostrar que algumas sentenças não são equivalentes.
  Dicas: podemos começar com A={1,2} e B={2,3}.
  P pode ser qualquer proposição definida sobre {1,2,3}.
  Exemplos de proposições:
    P(x) = (x=3)
    P(x) = (x=1->x=3)
    P(x) = V
  Pense em Álgebra e Cálculo 1...
    x e x^2 são funções diferentes mas que coincidem em x=0 e x=1;
    x^2 e (x+1)(x-1)+1 são duas funções de x "equivalentes", mas
    tivemos que aprender bastante Álgebra pra entender isto...
    estamos aprendendo métodos álgebricos para outras operações.

Sétima aula (29/março):
  Distribuí uma folha que tinha o exercício da aula
  anterior e várias outros problemas relacionados:
  http://angg.twu.net/MD/MD_exercicios_2010mar29.pdf
  [Falta transcrever o resumo da aula].

Oitava aula (31/março):
  Funções como relações, i.e., como conjuntos de pares; consertamos a
  idéia de ver as oito expressões lógicas acima funções de três
  argumentos. [Transcrever o resumo da aula]

Nona aula (5/abril):
  Relações reflexivas, simétricas, transitivas;
  fechos reflexivos, simétricos, transitivos;
  relações de equivalência; partições.
Décima aula (7/abril):
  Revisão para a prova.
  O gabarito dos exercícios da sétima aula está em:
  http://angg.twu.net/MD/MD_exercicios_2010mar29_gabarito.djvu
  http://angg.twu.net/MD/MD_exercicios_2010mar29_gabarito.pdf

Décima-primeira aula (12/abril):
  Primeira prova ("P1"). A matéria são as definições e construções das
  seguintes seções do livro:
    Seção 1. Definição
    Seção 2. Teorema
    Seção 3. Prova
      (só a discussão da p.22: "Omitindo passos")
    Seção 4. Contra-exemplo
    Seção 5. Álgebra de Boole
    Seção 6. Listas
    Seção 8. Conjuntos I: Introdução, Subconjuntos
    Seção 9. Quantificadores
    Seção 10. Conjuntos II: Operações
    Seção 11. Relações
    Seção 12. Relações de Equivalência
    Seção 13. Partições
    Seção 20. Funções
  Lembre que vimos algumas coisas em sala - como a relação de redução
  - que não estão no livro e que podem cair na prova, e lembre também
  que estamos deixando para ver as demonstrações direito na segunda
  unidade do curso.
12ª aula (14/abril):
  Discussão do gabarito da prova.
  Introdução à segunda unidade do curso: "demonstrações".

13ª aula (19/abril):
  Vou estar fora, num congresso.
  Depois vamos decidir como repor esta aula.
14ª aula (21/abril):
  Idem.

15ª aula (26/abril):
  Aula virtual - nesse dia eu já deveria ter voltado, mas só consegui
  um vôo de volta que chega no Rio na segunda de tarde... vou passar
  atividades pro monitor e deixar um scan dos exercícios na internet.
16ª aula (28/abril)
  "Prova direta de teoremas da forma se-então"...
  Examinamos com bastante cuidado a prova da p.18 do livro:
    1) Vamos mostrar que se (x é par) e (y é par)
       então (x+y é par), ou seja:
       (x é par)∧(y é par)->(x+y é par)
     2)  Seja x∈Z par.
     2') Seja y∈Z par.
     3)  2|x                     (por (2) e pela def 1.1)
     4)  2|y                     (por (2') e pela def 1.1)
     5)  ∃a∈Z.x=2a               (por (3) e pela def 1.2)
     5') Seja a∈Z tal que x=2a   (possível por (5))
     6)  ∃b∈Z.y=2b               (por (4) e pela def 1.2)
     6') Seja b∈Z tal que y=2b   (possível por (6))
     7)  x+y=2a+2b=2(a+b)        (por (5') e (6'))
     8)  Seja c∈Z tal que c=a+b
     8') x+y=2c                  (por (7) e (8))
     8'') ∃c∈Z.(x+y)=2c          (por (8) e (8'))
     9)  2|(x+y)                 (por (8'') e pela def 1.2)
     10) x+y é par               (por (9) e pela def 1.1)

17ª aula (03/maio):
  Continuação da aula anterior.
  Exemplo: queremos provar que (P->Q)∧(Q->R)∧(R->S)->(P->S).
  Se seguimos o modelo da aula passada, temos:
   1) queremos provar que (P->Q)∧(Q->R)∧(R->S)->(P->S).
    2) Suponha (P->Q).
    3) Suponha (Q->R).
    4) Suponha (R->S).
    5) Queremos provar que (P->S) é verdade.
     6) Olhe todas as linhas da tabela-verdade que obedecem
        (2), (3) e (4); elas obedecem (P->S).
  Repare que no passo (6) nós olhamos para todos os "mundos" que
  obedecem as hipóteses (2), (3) e (4) e vimos que em cada um
  deles (P->S) é verdade.
  Podemos modificar isto um pouco:
   1) queremos provar que (P->Q)∧(Q->R)∧(R->S)->(P->S).
    2) Suponha (P->Q).
    3) Suponha (Q->R).
    4) Suponha (R->S).
    5) Queremos provar que (P->S) é verdade.
     6') Suponha que P é verdade.
     7) Q é verdade (por (6) e (2)).
     8) R é verdade (por (7) e (3)).
     9) S é verdade (por (8) e (4)).
  Agora olhamos para todos os "mundos" que obedecem (2), (3), (4)
  e (6') e descobrimos que S é verdade em todos eles.
  No exemplo da aula anterior temos infinitos "mundos" que
  obedecem as hipóteses.
18ª aula (05/maio):
  Como muitas pessoas tinham a sensação de que o livro não tinha
  exemplos e exercícios suficientes de provas da forma "se-então" nós
  demos uma olhada em provas por indução.

19ª aula (10/maio):
  Provas por indução.
  Obs: antes da aula de 10/maio vou fazer mais uma apresentação
  informal sobre programação em Lua, das 14:00 às 16:00hs, na sala 2,
  pra quem estiver interessado. Os temas principais vao ser como usar
  linguagens dinâmicas (em contraposição a compiladas) e como
  programar e resolver problemas sem (quase) nunca pensar em I/O e
  usuários.
20ª aula (12/maio):
  Provas por contradição.

21ª aula (17/maio):
  Passei uma folha de exercícios pra ajudar a entender hipóteses
  contraditórias e provas por contradição. A versão LaTeXada dessa
  folha virou a 4ª página da versão online da P1:
    http://angg.twu.net/LATEX/2010-1-MD-prova-1.pdf
22ª aula (19/maio):
  Discussão dos exercícios da folha e da representação gráfica dos
  "mundos". Passei alguns problemas pras pessoas pensarem em casa:
    1) o que acontece quando P,Q∈{F,V}, n∈N (N=conj dos naturais)?
    2) Eu mostrei em sala uma representação boa desses mundos como
       números, e mostrei uma outra que eu disse que era ruim;
       encontrar dois mundos diferentes que a representação ruim
       encodifica como o mesmo número.
    3) Como representar como números os mundos se as variáveis são
       P,Q∈{F,V}, m,n∈N?
    4) Entender provas por contradição usando conjuntos de mundos.

23ª aula (24/maio):
  Não vou poder dar aula neste dia, vou repor depois.
24ª aula (26/maio):
  Não vou poder dar aula neste dia, vou repor depois.

25ª aula (31/maio):
  Torres de Hanói (detalhes depois).
26ª aula (2/junho):

27ª aula (7/junho):
28ª aula (9/junho):

29ª aula (14/junho): P2. Matéria: "demonstrações". Ainda vamos
  definir precisamente que "esquemas de provas" (ver p.525 do
  livro) podem cair... até a aula de 19/maio vimos estes aqui:
    1 (p.20; "=>")
    2 (p.22; "<=>")
    3 (p.25; como refutar um "=>" por contra-exemplo)
    4 (p.30; equivalência lógica via tabela verdade)
    7 (p.57; "∃")
    8 (p.58; "∀")
    11 (p.136; contrapositiva)
    12 (p.138; contradição)
    17 (p.158; indução)
    http://angg.twu.net/LATEX/2010-1-MD-prova-2.pdf
            (find-angg "LATEX/2010-1-MD-prova-2.tex")
30ª aula (16/junho):

31ª   aula (21/junho): Estruturas algébricas - introdução
31.5ª aula (22/junho - reposição): aritmética modular
32ª   aula (21/junho): Grupos e permutações.
  Exercícios recomendados: p.210, 1,2,3,5.

33ª   aula (28/junho): Aula cancelada por causa do jogo do Brasil.
33.5ª aula (29/junho): Cardinalidade, conjuntos infinitos enumeráveis
  e não-enumeráveis, teorema da diagonal de Cantor, paradoxo de
  Russell.
34ª   aula (30/junho): Mais sobre grupos.

35ª   aula (5/julho): mini-revisão.
35.5ª aula (6/julho): reposição??
36ª   aula (7/junho): P3, sobre estruturas algébricas (grupos).
  Exercícios recomendados: p.210: 1-12
  Exercícios recomendados: p.334: 1-7,9-15
  Exercícios recomendados: p.350: 1,2,4,7,9,10

37ª aula (12/julho): VR (ninguém fez)
38ª aula (14/julho): VS:
    http://angg.twu.net/LATEX/2010-1-MD-prova-VS.pdf
            (find-angg "LATEX/2010-1-MD-prova-VS.tex")

4ª feira, 28/julho: VS extra, no PURO, das 14:00 às 16:00hs,
  sobre provas formais e regras de dedução.
  Os exercícios de preparação pra VS extra estão aqui:
    http://angg.twu.net/LATEX/2010-1-MD-exercs-P4.pdf
            (find-angg "LATEX/2010-1-MD-exercs-P4.tex")
  E a prova em si (ainda não terminei de digitar o gabarito):
    http://angg.twu.net/LATEX/2010-1-MD-prova-VS2.pdf
            (find-angg "LATEX/2010-1-MD-prova-VS2.tex")
Notas da P1, P2, P3, VR, VS, VS2:
P1  P2   P3   VS VS2
                     10960036 ALVARO CESAR DE ANDRADE NETTO
4.1 2.2  0.0         11060036 ANA CAROLINA CLIVATTI FERRONATO
2.7 3.7  0.5         11060002 ANDREW DE CASTRO SANT ANNA
8.4 6.3 10.0         11060003 ARTHUR RORIS PEDROZO
2.2                  11060010 BRISA JARDIM LOSQUE
                     10860017 CESAR AUGUSTO SALGADO CREMONEZI
4.0 2.6              20960059 CICERO MARQUES DE ALMEIDA
4.2 4.4  7.5 4.6 6.0 11060011 DANILO LUIZ EBIHARA BARBOSA
2.7 2.2  0.0         20960043 DAYANA GONCALVES BARBOSA
3.5 3.2  0.0         11060012 DIEGO GOMES DA SILVA
2.2 3.8  0.0         11060013 ELI JAMES DE SOUZA AGUIAR
0.2 4.4  0.5         11060014 ERICK OLIVEIRA DE MENDONCA
6.6 7.7  6.0         11060015 FABIO MARQUES RODRIGUES
                     11060029 FELIPE PINHEIRO ORNELLAS
2.6 4.4  4.5 3.1     10960026 FERNANDO ELIAS LIMA PICHONE
1.5                  20960061 FERNANDO TEIXEIRA MAGALHAES
1.9 5.1  0.0 2.2 7.3 10960009 GABRIEL ALEIXO MORENO
5.7 6.0  4.5 3.6     11060030 GABRIELA QUEIROZ DE AVILA
7.0 6.8 11.0         11060004 HENRIQUE CARVALHAL SILVEIRA
1.6 2.2  0.0         20960045 HUGO CESAR BAUR SALGADO
6.2 5.1 10.0         11060005 HUGO RODRIGUES SILVA
1.0 1.2              10960012 IGOR DA CUNHA SOUZA
---                  10860002 IURY DE OLIVEIRA GOMES FIGUEIREDO
4.1 3.2  0.5         11060016 JOSE SANTOS LOPES
1.4 3.1  1.2         20960047 JULIANA SALES MARTINS      (P3 -> 1.2)
1.6 4.9  3.5 2.7 0.0 20960048 JULIO CESAR DE OLIVEIRA FREITAS
2.3 4.6  8.0 4.8     11060031 KILDARE ALVES DA SILVEIRA
0.9      2.5         11060038 LEANDRO GOMES BARRETO
3.2 5.2  1.6         11060017 LEONATHAN DE MESQUITA BRAGA
3.2 2.2  0.0         11060018 LUANA PESSANHA BAPTISTA DE ASSIS
0.9 5.7  0.0 2.7     20960051 LUCAS ALVES ALONSO
4.6 7.2  3.5 2.2     11060019 LUCAS GONCALVES WESTPHAL LIMA
0.0                  11060006 LUCAS PERES MARQUES DA SILVA
3.0 2.2              11060020 LUCIANA ALMEIDA EPPINGHAUS
5.0 3.5  1.0         11060037 LUIS FELIPE SEABRA         (P1 -> 5.5?)
                     11060021 LUIZ FELIPE ORPHAO DE MATTOS
1.8                  20960063 MARCELLO DUARTE CRESCENCIO
                     11060032 MARCELO VAITSMAN NERCESSIAN M CANARIO
2.1                  11060033 MARCO PAULO BRITO DE ALMEIDA MAINART
0.4 2.2              20960064 MARCO VINCIUS DA COSTA ALVES
0.5 2.2              20960065 MARCOS AURELIO JOSE RAMOS JUNIOR
0.4 4.6  0.5 3.8 0.0 11060022 MARIA CAROLINA SORIANO FREIRE
3.3 5.0  1.6         11060023 MAURICIO CARDOSO BARBOZA
4.1 5.4  4.0 4.6 1.0 11060024 MURILO DE MELO JATOBA
                     10960001 NATHAN ARAUJO FREITAS
1.0                  20960067 PEDRO CAVALCANTI TRINDADE MARINS
1.9 6.0  0.0         11060008 PETER CLAYDER LOPES DA SILVA
                     20960069 RAFAEL LOURENCO GOMES
3.5 4.5  3.6 2.0     20960053 RAPHAEL BARBOSA DA SILVA MORATO
2.9 3.3  0.5         11060009 RENAN DA SILVA RODRIGUES
0.0 0.0              20960055 RENAN DO CARMO DE SOUZA
                     11060026 RODOLFO HAMMES BASTOS
6.0 6.5 11.8         11060034 ROMULO CARLOS ALMEIDA DA SILVA
                     11060027 THAIS QUESADA FERNANDES
4.7 5.5  6.5         11060028 ULYSSES ALESSANDRO COUTO ROCHA
1.0                  20960057 WALLACE CABRAL DA SILVA
4.2 2.5  1.5 1.7     20960071 WILDER NICO BARCELOS
3.1 3.8              ???????? ALICE CIRUFO
3.0      0.5 1.1     ???????? JONOTHAS

Ajustes de notas:
Danilo e Gabriel Aleixo Moreno -> aprovados
Luis Felipe Seabra: nota pré-VS aumenta alguns décimos
(- 18 3.5)

Ainda não terminei o plano de curso! 8-(

Página da versão de 2009.2 do curso: 2009.2-MD.html.