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")
|