1ª aula (09/ago): Ninguém veio (1ª semana)
2ª aula (11/ago): Introdução ao curso...
3ª aula (16/ago): (...)
4ª aula (18/ago): Depois eu vou digitar o resumo da aula -
por enquanto vai só o exercício mais urgente.
Estamos usando (temporariamente!) as seguintes definições:
Se b∈{2,3,...} então
_b é primo_ se e só se ¬∃a∈{2,...,b-1}.a|b;
Se n∈N então
_n é par_ se e só se ∃k∈{0,1,...,n}.2k=n;
Se n∈N então
_n é ímpar_ se e só se ∃k∈{0,1,...,n}.2k+1=n.
Exercício (***MUITO*** importante):
calcule (passo a passo, como sempre), o valor de:
6 é primo,
2 é par,
3 é par,
3 é ímpar.
Obs: a versão 0.00 (muito preliminar) das notas sobre a relação
de redução está aqui:
http://angg.twu.net/LATEX/2010reducao.pdf
5ª aula (23/ago): Trabalhamos com a folha de "Exercícios sobre
expressões equivalentes" que eu preparei no semestre passado:
http://angg.twu.net/MD/MD_exercicios_2010mar29.pdf
Acho que deixei bem claro que o objetivo mais básico (e mais
urgente!) desta aula era todo mundo sair sendo capaz de completar
por si mesmo esta tabela: se A={1,2} e B={2,3} então
P(x) = (x=3) P(x) = (x=1->x=3) P(x) = V
-------------+-------------------+---------
(E0) ∀x∈A∪B.P(x) F | F | V
(E1) ∀x∈A∩B.P(x) F | V | V
(E2) ∃x∈A∪B.P(x) V | V | V
(E3) ∃x∈A∩B.P(x) F | V | V
(E4) ∀x∈A.(x∈B->P(x)) F | V | V
(E5) ∀x∈A.(x∈B∧P(x)) F | F | F
(E6) ∃x∈A.(x∈B->P(x)) V | V | V
(E7) ∃x∈A.(x∈B∧P(x)) F | V | V
6ª aula (25/ago): Tentamos classificar as expressões E_0,...,E_7
em vários grupos de expressões equivalentes, e chegamos a uma
classificação preliminar:
P(x) = (x=3) P(x) = (x=1->x=3) P(x) = V
-------------+-------------------+---------
(E5) ∀x∈A.(x∈B∧P(x)) F | F | F
(E0) ∀x∈A∪B.P(x) F | F | V
(E1) ∀x∈A∩B.P(x) F | V | V
(E3) ∃x∈A∩B.P(x) F | V | V
(E4) ∀x∈A.(x∈B->P(x)) F | V | V
(E7) ∃x∈A.(x∈B∧P(x)) F | V | V
(E2) ∃x∈A∪B.P(x) V | V | V
(E6) ∃x∈A.(x∈B->P(x)) V | V | V
mas ainda não vimos como distinguir E1,E3,E4,E7 (ou provar que
são equivalentes); idem para E2 e E6.
Falei que uma outra relação mais fraca que equivalência vai ser mais
importante pra nós que equivalência: "->". Vimos como ela se
comporta para os predicados P(n)=2|n, P(n)=3|n, P(n)=6|n.
7ª aula (30/ago): Semana de Paralisação e Pesquisa:
http://angg.twu.net/spp-2010.html
Vou passar exercícios - uns em sala, outros pra casa - e a aula em
si vai durar menos que o normal. Vamos ter atividades extras
(opcionais - só pra quem quiser participar), mas elas só serão
definidas no próprio dia.
8ª aula (01/set): idem.
9ª aula (06/set): Enforcado - véspera de 7/setembro.
10ª aula (08/set): Modos de definir funções; se o domínio de f:A->B é
finito basta definir o valor de f para cada elemento do domínio;
muitas vezes funções e seqüências são definidas "indutivamente",
como as que aparecem no Scheinerman a partir da p.154, por exemplo:
k_n = 1 quando n = 0, k_n = 2 * k_(n-1) quando n > 0
Pedi pros alunos calcularem em casa B_0, ..., B_16 quando (B_0, B_1,
...) é esta seqüência definida indutivamente "de um modo estranho":
B_0 = 0
B_(2n) = 10 * B_n para n∈{1, 2, 3, 4, ...}
B_(2n+1) = 10 * B_n + 1 para n∈{0, 1, 2, 3, ...}
Começamos a ver que uma definição por casos, como
F(n) = / 1 quando n=0
| 1 quando n=1
\ F(n-2)+F(n-1) quando n>=2
é equivalente a uma certa expressão lógica - essa F é a única função
F:N->N que obedece:
∀n∈N.((n=0 -> F(n)=1)
∧(n=1 -> F(n)=1)
∧(n>=2 -> F(n)=F(n-2)+F(n-1)))
Esta idéia de procurar a única função que obedece uma certa
propriedade é parecida com procurar o único número que obedece
certas equações... por exemplo, temos dois valores de x que
obedecem:
(x-1)(x+2)=0,
um só valor de x que obedece:
(x-1)(x+2)=0 ∧ x>0,
e nenhum valor de x que obedece:
(x-1)(x+2)=0 ∧ x>3.
Começamos a ver como escrever demonstrações e contas grandes usando
"proposições", "lemas", etc. Veja:
http://angg.twu.net/MD/MD_props_e_lemas_2010sep08.pdf
11ª aula (13/set): relações reflexivas, simétricas e transitivas,
formalmente e graficamente. Vimos como provar que certas relações
não são R/S/T encontrando contra-exemplos, e usando idéias da folha
sobre proposições e lemas. Vimos fecho reflexivo, fecho simétrico e
fecho transitivo. Um comentário, pros alunos pensarem em casa: a
relação de "redução", que ainda não definimos precisamente, é
transitiva.
12ª aula (15/set): funções, formalmente: o gráfico de uma função
f:A->B é uma relação R de A em B obedecendo ∀a∈A.∃!b∈B.aRb.
É possível definir o "∃!" em termos de outras operações que já
conhecemos:
∃!b∈B.P(b) <-> (∃b∈B.P(b))∧(∀b,b'∈B.(P(b)∧P(b')->b=b')).
Pegamos um exemplo: A={1,2,3}, B={1,2,3,4},
S={(1,4),(2,1),(3,2),(3,3)}. Sabemos que S não é (o gráfico de)
uma função de A em B, mas como mostrar isto formalmente, sem
contas enormes, traduzindo a nossa intuição para algo formal?
Uma solução possível é esta. Se P(b) = aSb então:
Lema: se a=3, b=2, b'=3, então P(b)∧P(b')->b=b' é falso.
Lema: se a=3 então ∀b,b'∈B.(P(b)∧P(b')->b=b' é falso.
Lema: se a=3 então (∃b∈B.P(b))∧(∀b,b'∈B.(P(b)∧P(b')->b=b')) é falso.
Lema: se a=3 então ∃!b∈B.P(b) é falso.
Lema: ∀a∈A.∃!b∈B.aSb é falso.
Teorema: S não é o gráfico de uma função de A em B.
13ª aula (20/set): notação {_|_} para gerar conjuntos - e o que mais?
14ª aula (22/set): notação {_|_}, de novo; composição de funções;
{(a,f(a))|a∈A} sempre gera o gráfico de uma função; algumas funções
interessantes com domínios infinitos: |·|, conjunto das partes,
o "inf" de subconjuntos de N não-vazios.
Passamos um tempão vendo versões adaptadas das questões 2 e 4 da P1
do semestre passado:
http://angg.twu.net/LATEX/2010-1-MD-prova-1.pdf
mais precisamente, vimos como a sentença
d_0=0 ∧
∀n∈N.((d_n=n -> d_(n+1)=10·d_n+9) ∧
(d_n!=n -> d_(n+1)=d_n))
define uma sequência (d_0, d_1, ...) tal que, por exemplo:
d_0 = 0 (porque 0 não tem nenhum dígito significativo)
d_6 = 9 (porque 6 tem 1 dígito significativo)
d_22 = 99 (porque 22 tem 2 dígitos significativos)
d_407 = 999 (porque 407 tem 3 dígitos significativos)
e aí podemos definir a++b ("concatenação") como a·(d_b+1)+b.
Pedi pros alunos tentarem fazer os problemas da P1 do semestre
passado.
15ª aula (27/set): vimos a seqüência D_0={0}, D_1={1}, D_2={2, 11},
D_3={12, 21, 111}, que diz todos os modos de cobrir um retângulo 2×n
com dominós; ela pode ser definida "mais-ou-menos formalmente" por:
D_n = {k∈{0,...,10^k} | todos os dígitos de k são "1" ou "2",
a soma dos dígitos de k é n}
e esta definição nos permite checar rapidamente que, por exemplo,
99∈D_4 é falso, e
121∈D_4 é verdadeiro.
O modo como estamos encarando a notação {_|_} - como sendo feita de
"geradores" e "filtros" - não é exatamente o padrão; o mais usual é
interpretarmos a construção {_|_} como uma relação de pertencimento
disfarçada, e:
34 ∈ {10a+4b | a∈N, b∈N, b<=2} -~-> ∃a∈N.∃b∈N.(b<=2 ∧ 10a+4b=34)
Lembre que tínhamos um modo de comparar conjuntos finitos, e um modo
de comparar funções comparando os seus gráficos (como conjuntos)...
Por incrível que pareça, a operação de comparar dois conjuntos
quaisquer é considerada admissível matematicamente, apesar de que
intuitivamente ela é péssima - para comparar duas funções de R em R
temos que testar se elas dão o mesmo resultado para todo x∈R, o que
já é ruim, porque R é infinito; mas pra testar se A=B quando A e B
são conjuntos temos que testar se x∈A e x∈B dão os mesmos resultados
para _todos os valores possíveis de x_ - para "x"zes que são
números, para "x"zes que são conjuntos, para "x"zes que são listas,
etc...
Definimos a seqüência (E_0, E_1, E_2, ...) de conjuntos por:
E_0 = {0},
E_1 = {1},
E_n = {10a+1 | a∈E_(n-1)} ∪ {10b+2 | b∈E_(n-2)} (para n>=2),
e pedi pros alunos calcularem E_2 e E_3.
É bem mais fácil calcular formalmente (|E_0|, |E_1|, |E_2|, ...) -
que dá (1, 1, 2, 3, 5, 8, ...) - do que calcular as cardinalidades
dos "D_n"s. Aos poucos vamos ver como provar sentenças como
∀n∈N.D_n=E_n.
16ª aula (29/set): mais definição indutivas (obs: preciso olhar no
caderno de alguém pra descobrir o que eu dei). Terminei a aula com
uma definição indutiva equivalente a isto:
M_(n,d) = {(x_1,...,x_n) | x_1,...,x_n∈{0,...,9}, x_1=d,
x_1 >= x_2 >= ... >= x_n}.
17ª aula (04/out): revisão, toda em cima de uma lista de exercícios
(falta scaneá-la).
18ª aula (06/out): P1:
http://angg.twu.net/MD/MD_P1_2010oct06.pdf
19ª aula (11/out): Enforcado - véspera de 12/outubro (N.Srª aparecida).
20ª aula (13/out): Começamos a ver demonstrações. Todos os problemas
deste módulo do curso vão ser da forma "convença alguém que...", e a
distinção que vai ser mais útil pra gente não vai mais ser a entre
"expressões verdadeiras" e "expressões falsas", e sim a entre "o que
já sabemos" e "o que ainda não sabemos" - e vamos ver como aumentar
o conjunto das coisas que sabemos. Comecei com um exemplo:
2^4-2^3=2^3 é verdade, mas não é nada óbvio que 2^100-2^99=2^99 seja
verdade; no entanto, isto
2^100 - 2^99 = 2*2^99 - 1*2^99
= (2-1)*2^99
= 2^99
convence qualquer pessoa de que 2^100-2^99 = 2^99 é verdade, sem que
precisemos calcular numericamente nenhuma das expressões.
Tentei fazer um paralelo com uma tabela que construímos para
calcular os valores da seqüência (b(0), b(1), ...) (definida
abaixo); a gente começava com uma tabela quase toda vazia (cheia de
"não sei"s), e ia preenchendo ela aos poucos - e a ordem na qual a
gente ia preenchendo ela era importante. Não sei se fui muito
convincente nessa comparação. 8-)
Consideramos cinco seqüências:
(b(0), b(1), ...), com axiomas:
(B0) b(0)=0
(B1) ∀k∈N.b(2k)=10*b(k)
(B2) ∀k∈N.b(2k+1)=10*b(k)+1
(c(0), c(1), ...), com axiomas:
(C0) c(0)=0
(C1) ∀k∈N.c(2k)=10*c(k)
(C2) ∀k∈N.c(2k+1)=10*c(k)+1
(C3) ∀k∈N.c(k+1)=c(k)+1
(a(0), a(1), ...), com axiomas:
(A1) ∀k∈N.a(2k)=10*a(k)
(A2) ∀k∈N.a(2k+1)=10*a(k)+1
(A3) ∀k∈N.a(k)∈R
(e(0), e(1), ...), com axiomas:
(E0) e(0)=0,
(E1) ∀k∈N.e(k+1)=10*e(k)+1
(f(0), f(1), ...), com axioma:
(F1) ∀k∈N.f(k)=(10^k-1)/9
(g(0), g(1), ...), com axiomas:
(G199) g(199)=(10^199-1)/9
(G200) g(200)=10*g(199)+1
Os exercícios foram provar que b(5)=101, c(4)=100, c(4)=4, a(0)=0,
a(4)=100; depois calcular e(0), e(1), e(2), e(3), f(0), f(1), f(2),
f(3), e provar que g(200)=(10^200-1)/9 (este último ficou pra casa).
Um exemplo de um modo de arrumar demonstrações:
1) b(0)=0 (por B0)
2) b(2*0+1)=10*b(0)+1 (por B2, com k=0)
3) b(1)=10*b(0)+1 (por (2))
4) b(1)=0+1 (por (3) e (1))
5) b(1)=1 (por (4))
6) b(2*1)=10*b(1) (por B1, com k=1)
7) b(2)=10*1=10 (por (6) e (5))
8) b(5)=b(2*2+1)=10*b(2)+1=10*10+1=101 (por B2 com k=2 e (7))
21ª aula (18/out): Examinamos vários fatos que iremos provar por
indução, e examinamos a "prova direta" que está escondida dentro de
cada um deles (e que o livro finge que é trivial).
Pra casa: livro, p.155, problemas 2,3,4; p.165, problemas 2,3,4.
Avisei que estes problemas são trabalhosos, e mostrei que pra
formalizá-los temos que dar nomes a certas seqüências e definí-las
indutivamente - p.ex., a_n = 1 + 2 + ... + n.
22ª aula (20/out): Semana de Ciência e Tecnologia.
23ª aula (25/out): Começamos a ver como arrumar as tais "provas
diretas" em árvores - mas a aula não foi muito clara.
24ª aula (27/out): Motivação: o problema da pirâmide de cervejas.
Sabemos que:
A \subseteq {1,2,3,4,5,6} (alfa)
1∈A -> 2∈A ∧ 3∈A (beta)
2∈A -> 4∈A ∧ 5∈A (gama)
3∈A -> 5∈A ∧ 6∈A (delta)
1∈A (epsilon)
Como provar formalmente que se alfa, beta, gama, delta e epsilon são
verdade então 6∈A? Vimos a prova em árvore disto (usando as regras
∧E1, ∧E2, ∧I, ->E) e traduzimos ela para uma prova "linha a linha",
que depois foi modificada para ter uma linha de tipo "suponha que".
A versão modificada era:
1) Sabemos que 1∈A->2∈A∧3∈A, (pela hipótese beta)
2) e sabemos que 3∈A->5∈A∧6∈A. (pela hipótese delta)
3) Vamos supor (temporariamente) que 1∈A.
4) Então 2∈A∧3∈A, (por (3), (1) e ->E)
5) e 3∈A, (por (4) e ∧E2)
6) e 5∈A∧6∈A; (por (5), (2) e ->E)
7) daí, 6∈A. (por (6) e ∧E2)
8) Portanto 1∈A->6∈A. (por (3)-(7) e ->I)
A regra que empurra a hipótese do "suponha" pra dentro da conclusão
é difícil de entender (marquei ela com três caveirinhas), e todo
mundo vai ter que praticar ela bastante.
beta, delta, 1∈A |- 6∈A
-----------------------(->I)
beta, delta |- 1∈A->6∈A
25ª aula (01/nov): Feriado: dia do funcionário público
26ª aula (03/nov): discussão sobre como provar que ∀n∈N.2^n<=n!.
Os alunos tinham uma noção intuitiva de que isso devia ser verdade,
mas eu disse que 2^777 > 777! e que portanto a situação era bem mais
complicada do que parecia, e que teríamos que analisar tudo com
cuidado. No final da aula eles chegaram a este argumento:
2^4 < 4!
------------
2·2^4 < 5·4!
----------------
2·2·2^4 < 6·5·4!
----------------
................
----------------
2^777 < 777!
27ª aula (08/nov): Semana Acadêmica.
**** Aviso 1: vai ter aula (as atividades da semana acadêmica só
começam de tarde). Aviso 2: todos os assuntos pendentes da P1
serão resolvidos (mas talvez de um modo um pouco surpreendente).
Aviso 3: as próximas aulas serão em cima de textos extras e
listas exercícios. Vou por os primeiros no site de noite. ***
(Mas ninguém veio na aula e o PURO estava praticamente vazio, aí
eu esperei meia hora e fui fazer outras coisas.)
28ª aula (10/nov): Semana Acadêmica.
29ª aula (15/nov): Feriado: proclamação da república
30ª aula (17/nov):
http://angg.twu.net/MD/MD_sists_dedutivos_2010nov17.pdf
http://angg.twu.net/MD/MD_sists_dedutivos_2010nov17.djvu
31ª aula (22/nov):
http://angg.twu.net/MD/MD_sists_dedutivos_2010nov21.pdf
http://angg.twu.net/MD/MD_sists_dedutivos_2010nov21.djvu
32ª aula (24/nov): Vou ter que estar no fórum do Rio neste dia, pra
uma audiência de um processo trabalhista no qual eu estou envolvido.
33ª aula (29/nov): P2. Matéria: demonstrações.
Scan da prova e do gabarito:
http://angg.twu.net/MD/MD_P2_2010nov29.pdf
http://angg.twu.net/MD/MD_P2_2010nov29.djvu
33.5ª aula (30/nov): aula extra (18:00, sala E10).
Mini-introdução a estruturas algébricas: anéis, grupos, monóides.
Permutações.
34ª aula (01/dez): Idem, com um ponto de vista um pouco diferente.
Expliquei que uma coisa que vai pesar muito na P3 é o esquema de
prova 23, da p.333 do Scheinerman, que é sobre provar que uma
estrutura é um grupo, e que pelo menos 4 pontos da prova vão ser
em questões relacionadas com provas de implicações. Os exercícios
que eu recomendo pra treinar esse tipo de prova são os exercícios
3 e 4 da p.165, numa forma um pouco simplificada - por exemplo:
3a: se as seqüências (a_0, a_1, ...) e (b_0, b_1, ...)
são definidas por:
(∀n∈N. a_n = a_(n-1) + (3n-2)) ∧ (a_0 = -2) e
(∀n∈N. b_n = n(3n-1)/2),
prove que:
∀n∈N. a_n=b_n -> a_(n+1)=b_(n+1)
*** Obs: tentem encontrar a "forma simplificada" do 3b, 3c, 3d,
4a, 4b, 4c por si mesmos - tenho que cuidar de outras coisas por
enquanto (incluindo a correção da P2) e não sei se vou poder pôr
todas as formas simplificadas aqui na página a tempo!
35ª aula (06/dez): P3:
http://angg.twu.net/MD/MD_P3_2010dec06.pdf
http://angg.twu.net/MD/MD_P3_2010dec06.djvu
35.5ª aula (07/dez): aula extra (18:00)
36ª aula (08/dez): Feriado municipal (dia de São Jesus das Ostras).
36ª aula (10/dez): VR (14:00)
http://angg.twu.net/MD/MD_VR_2010dec10.pdf
http://angg.twu.net/MD/MD_VR_2010dec10.djvu
37ª aula (13/dez): VS
http://angg.twu.net/MD/MD_VS_2010dec13.pdf
http://angg.twu.net/MD/MD_VS_2010dec13.djvu
38ª aula (15/dez):
|