Matemática Finita, Notas de estudo de Matemática

Baixe Matemática Finita e outras Notas de estudo em PDF para Matemática, somente na Docsity! Tópicos de Matemática Finita Matemática Discreta Luı́s Sequeira 10 de Março de 2004 TMF/MD – p.1 Exemplo Mostrar que (2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n)n 2n , para n ≥ 1 TMF/MD – p.2 Exemplo Mostrar que (2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n)n 2n , para n ≥ 1 Base de Indução (n = 1): 1 = 2 1 21 TMF/MD – p.2 Exemplo Mostrar que (2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n)n 2n , para n ≥ 1 Base de Indução (n = 1): 1 = 2 1 21 X TMF/MD – p.2 Exemplo Passo de Indução TME/MD - p.2 Exemplo Passo de Indução Hipótese de Indução: (2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n) n 2n Tese de Indução: (2n + 1)(2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n+2) n+1 2n+1 (2n + 2)n+1 2n+1 = (2n + 2)(2n + 1) 2 (2n)n−1 2n TMF/MD – p.2 Exemplo Passo de Indução Hipótese de Indução: (2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n) n 2n Tese de Indução: (2n + 1)(2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n+2) n+1 2n+1 (2n + 2)n+1 2n+1 = (2n + 2)(2n + 1) 2 (2n)n−1 2n = (n + 1)(2n + 1) (2n)n−1 2n TMF/MD – p.2 Exemplo Passo de Indução Hipótese de Indução: (2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n) n 2n Tese de Indução: (2n + 1)(2n − 1)(2n − 3)(2n − 5) · · · 1 = (2n+2) n+1 2n+1 (2n + 2)n+1 2n+1 = (2n + 2)(2n + 1) 2 (2n)n−1 2n = (n + 1)(2n + 1) (2n)n−1 2n = (2n + 1) (2n)n−1(n + 1) 2n TMF/MD – p.2 Exemplo Quantas maneiras há de re-arranjar as letras da palavra CASPA ? TMF/MD – p.3 Exemplo Quantas maneiras há de re-arranjar as letras da palavra CASPA ? TMF/MD – p.3 Exemplo Quantas maneiras há de re-arranjar as letras da palavra CASPA ? 5! 2! TMF/MD – p.3 Exemplo Quantas maneiras há de re-arranjar as letras da palavra CASPA ? 5! 2! E da palavra DRACONIANO ? 10! 2!2!2! TMF/MD – p.3 Exemplo Quantas maneiras há de re-arranjar as letras da palavra CASPA ? 5! 2! E da palavra DRACONIANO ? 10! 2!2!2! ou ( 10 2 )( 8 2 )( 6 2 ) × 4! TMF/MD – p.3 Que Hotel! Infinitopolis Beach and Golf Resort TMF/MD – p.4 Enumerabilidade Exemplo. • Z é enumerável: 0, 1, −1, 2, −2, 3, −3, . . . TMF/MD – p.6 Enumerabilidade Exemplo. • Z é enumerável: 0, 1, −1, 2, −2, 3, −3, . . . • Todo o conjunto finito { a1, . . . , an } é enumerável: a1, a2, . . . , an, an, an, . . . TMF/MD – p.6 Enumerabilidade Exemplo. • Z é enumerável: 0, 1, −1, 2, −2, 3, −3, . . . • Todo o conjunto finito { a1, . . . , an } é enumerável: a1, a2, . . . , an, an, an, . . . • A união de dois conjuntos enumeráveis ainda é enumerável. Dadas enumerações x0, x1, x2, . . . e y0, y1, y2, . . ., podemos construir a enumeração x0, y0, x1, y1, x2, y2, . . . TMF/MD – p.6 União enumerável “A união enumerável de conjuntos enumeráveis é ainda enumerável.” TMF/MD – p.8 União enumerável Seja X = {X0, X1, . . . } um conjunto enumerável, cujos elementos são eles próprios conjuntos enumeráveis. Então a sua união, ⋃ X = X0 ∪ X1 ∪ . . ., é ainda um conjunto enumerável. TMF/MD – p.8 União enumerável Seja X = {X0, X1, . . . } um conjunto enumerável, cujos elementos são eles próprios conjuntos enumeráveis. Então a sua união, ⋃ X = X0 ∪ X1 ∪ . . ., é ainda um conjunto enumerável. x00 x10 x20 x30 x40 x01 x11 x21 x31 x41 x02 x12 x22 x32 x42 x03 x13 x23 x33 x43 x04 x14 x24 x34 x44 x05 x15 x25 x35 x45 x06 x16 x26 x36 x46 · · · · · · · · · · · · · · · ... ... ... ... ... ... ... . . . TMF/MD – p.8 Produto cartesiano de enu- meráveis Se X e Y são conjuntos enumeráveis, então X × Y é enumerável. Seja x0, x1, x2, . . . uma enumeração de X. TMF/MD – p.9 Produto cartesiano de enu- meráveis Se X e Y são conjuntos enumeráveis, então X × Y é enumerável. Seja x0, x1, x2, . . . uma enumeração de X. É claro que cada um dos conjuntos {x0 } × Y , {x1 } × Y , . . . é enumerável, TMF/MD – p.9 Produto cartesiano de enu- meráveis Se X e Y são conjuntos enumeráveis, então X × Y é enumerável. Seja x0, x1, x2, . . . uma enumeração de X. É claro que cada um dos conjuntos {x0 } × Y , {x1 } × Y , . . . é enumerável, portanto X × Y = {x0 } × Y ∪ {x1 } × Y ∪ . . . é enumerável. TMF/MD – p.9 Conjuntos Numeráveis Lema. Todo o subconjunto infinito de N tem cardinalidade ℵ0. TMF/MD – p.11 Conjuntos Numeráveis Lema. Todo o subconjunto infinito de N tem cardinalidade ℵ0. Proposição. Um conjunto infinito é numerável se e só se é enumerável. TMF/MD – p.11 Conjuntos não Numeráveis Será que todo o conjunto infinito é numerável? TMF/MD – p.12 Conjuntos não Numeráveis Lema (Lema da Diagonalização). Dada uma “matriz” infinita de zeros e uns α00 α01 α02 α03 α04 α10 α11 α12 α13 α14 α20 α21 α22 α23 α24 α30 α31 α32 α33 α34 α40 α41 α42 α43 α44 α50 α51 α52 α53 α54 α60 α61 α62 α63 α64 · · · · · · · · · · · · · · · ... ... ... ... ... ... ... . . . existe necessariamente uma sequência binária infinita d0, d1, d2, . . . que difere de todas as linhas da matriz. TMF/MD – p.12 Conjuntos não Numeráveis Lema (Lema da Diagonalização). Dada uma “matriz” infinita de zeros e uns α00 α01 α02 α03 α04 α10 α11 α12 α13 α14 α20 α21 α22 α23 α24 α30 α31 α32 α33 α34 α40 α41 α42 α43 α44 α50 α51 α52 α53 α54 α60 α61 α62 α63 α64 · · · · · · · · · · · · · · · ... ... ... ... ... ... ... . . . existe necessariamente uma sequência binária infinita d0, d1, d2, . . . que difere de todas as linhas da matriz. TMF/MD – p.12 Conjuntos não Numeráveis Lema (Lema da Diagonalização). Dada uma “matriz” infinita de zeros e uns α00 α01 α02 α03 α04 α10 α11 α12 α13 α14 α20 α21 α22 α23 α24 α30 α31 α32 α33 α34 α40 α41 α42 α43 α44 α50 α51 α52 α53 α54 α60 α61 α62 α63 α64 · · · · · · · · · · · · · · · ... ... ... ... ... ... ... . . . existe necessariamente uma sequência binária infinita d0, d1, d2, . . . que difere de todas as linhas da matriz. α00, α11, α22, . . . TMF/MD – p.12