Baixe o app para aproveitar ainda mais
Prévia do material em texto
Matema´tica Discreta Josimar da Silva Rocha 2 Suma´rio 1 Fundamentos de Lo´gica Matema´tica 7 1.1 Lo´gica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Sentenc¸as ou Proposic¸o˜es Lo´gicas . . . . . . . . . . . . . . . . . . 7 1.2 Conectivos Lo´gicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Conectivo de conjunc¸a˜o (E): ^ . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Conectivo de disjunc¸a˜o (OU): _ . . . . . . . . . . . . . . . . . . . 8 1.2.3 Conectivo de Negac¸a˜o (NA˜O): ¬ . . . . . . . . . . . . . . . . . . 8 1.2.4 Conectivo de Implicac¸a˜o ou conectivo condicional (SE ... ENTA˜O): ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.5 Conectivo de bi-implicac¸a˜o ou conectivo bicondicional (SE, E SO- MENTE SE,): $ . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Tautologia e Contradic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Relac¸o˜es entre sentenc¸as lo´gicas . . . . . . . . . . . . . . . . . . . . . . . 11 1.4.1 Relac¸a˜o de implicac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4.2 Relac¸a˜o de equivaleˆncia . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Sentenc¸a abertas e Sentenc¸as Fechadas . . . . . . . . . . . . . . . . . . . . 13 1.6 Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6.1 Quantificador universal . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6.2 Quantificador existencial . . . . . . . . . . . . . . . . . . . . . . . 14 2 Conjuntos 19 2.1 Relac¸a˜o de pertineˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Relac¸o˜es entre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.1 Relac¸a˜o de igualdade . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.2 Relac¸a˜o de contineˆncia entre conjuntos . . . . . . . . . . . . . . . 19 3 4 SUMA´RIO 2.3 Operac¸o˜es sobre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.1 Operac¸o˜es bina´rias . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3.2 Operac¸a˜o una´ria . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3.3 Operac¸a˜o una´ria restrita . . . . . . . . . . . . . . . . . . . . . . . 21 2.4 Princı´pio da Inclusa˜o-Exclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . 24 3 Te´cnicas de Demonstrac¸a˜o 31 3.1 Te´cnica de demonstrac¸a˜o por exausta˜o . . . . . . . . . . . . . . . . . . . . 31 3.2 Te´cnica de demonstrac¸a˜o direta . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 Te´cnica de demonstrac¸a˜o por contraposic¸a˜o . . . . . . . . . . . . . . . . . 33 3.4 Te´cnica de demonstrac¸a˜o por contradic¸a˜o (ou por absurdo) . . . . . . . . . 33 3.5 Princı´pios de induc¸a˜o matema´tica . . . . . . . . . . . . . . . . . . . . . . 34 4 Relac¸o˜es e Func¸o˜es 43 4.1 Func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5 Ana´lise Combinato´ria 53 5.1 Princı´pio das Casas de Pombo . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2 Princı´pio Fundamental da Contagem . . . . . . . . . . . . . . . . . . . . . 54 5.2.1 Princı´pio da Multiplicac¸a˜o . . . . . . . . . . . . . . . . . . . . . . 54 5.2.2 Princı´pio da Soma . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.3 Outros Me´todos de Contagem . . . . . . . . . . . . . . . . . . . . . . . . 56 5.4 Caso sem te´cnica conhecida . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.5 Fatorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.6 Agrupamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.6.1 Arranjos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.6.2 Permutac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.6.3 Combinac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.6.4 Permutac¸o˜es com repetic¸a˜o . . . . . . . . . . . . . . . . . . . . . . 61 6 Introduc¸a˜o a` Teoria dos Nu´meros 63 6.1 Congrueˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.1.1 Propriedades das Congrueˆncias . . . . . . . . . . . . . . . . . . . 77 7 Conjuntos Enumera´veis 81 SUMA´RIO 5 8 Grafos 91 8.1 Definic¸o˜es iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 8.2 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 8.3 Isomorfismo entre grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 8.4 Matrizes de Adjaceˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.4.1 Matriz de adjaceˆncia para grafo na˜o-direcionado (na˜o-orientado) . . 97 8.4.2 Matriz de adjaceˆncia para grafo ponderado (valorado) . . . . . . . 103 8.5 Matriz de distaˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 8.5.1 Matriz de distaˆncias para Grafos na˜o ponderados . . . . . . . . . . 103 8.5.2 Matriz de distaˆncias para Grafos ponderados . . . . . . . . . . . . 103 8.5.3 Lista de Exercı´cios sobre Grafos . . . . . . . . . . . . . . . . . . . 105 9 A´lgebra de Boole 111 9.1 Minimizac¸a˜o de Func¸o˜es Booleanas . . . . . . . . . . . . . . . . . . . . . 116 9.1.1 Me´todo de Quine-McCluskey . . . . . . . . . . . . . . . . . . . . 116 9.1.2 Me´todo de Karnaugh . . . . . . . . . . . . . . . . . . . . . . . . . 116 9.1.3 Desvantagens na utilizac¸a˜o do me´todo de reduc¸a˜o de Karnaugh . . 120 10 Du´vidas Correlatas em aula 123 6 SUMA´RIO Capı´tulo 1 Fundamentos de Lo´gica Matema´tica 1.1 Lo´gica 1.1.1 Sentenc¸as ou Proposic¸o˜es Lo´gicas Definic¸a˜o 1. Uma afirmac¸a˜o e´ uma sentenc¸a (ou proposic¸a˜o) lo´gica se esta afirmac¸a˜o puder receber uma valorac¸a˜o V (verdadeira) ou F (falsa). 1.2 Conectivos Lo´gicos 1.2.1 Conectivo de conjunc¸a˜o (E): ^ Definic¸a˜o 2. Conectivo de conjunc¸a˜o (^) e´ um conectivo que conecta duas sentenc¸as lo´gicas para formar uma nova sentenc¸a que recebe valorac¸a˜o V (verdadeira) se as sentenc¸as conectadas por este conectivo possuem valorac¸a˜o V (verdadeira). Se p e q sa˜o sentenc¸as lo´gicas enta˜o a sentenc¸a p^q pode ser representada pela seguinte tabela-verdade: p q p ^ q V V V F V F V F F F F F 7 8 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA Exemplo 1. • Se p :O aluno tirou nota maior ou igual a 6 e q :O aluno tem frequeˆncia maior ou igual a 75%; enta˜o p ^ q : O aluno foi aprovado. 1.2.2 Conectivo de disjunc¸a˜o (OU): _ Definic¸a˜o 3. Conectivo de disjunc¸a˜o (_) e´ um conectivo que conecta duas sentenc¸as lo´gicas para formar uma nova sentenc¸a que recebe valorac¸a˜o V (verdadeira) se uma das sentenc¸as conectadas por este conectivo possui valorac¸a˜o V (verdadeira). Se p e q sa˜o sentenc¸as lo´gicas enta˜o a sentenc¸a p_q pode ser representada pela seguinte tabela-verdade: p q p _ q V V V F V V V F V F F F Exemplo 2. Se p : O aluno tirou nota menor ou igual a 6 ou q : O aluno tem frequeˆncia menor do que 75%; enta˜o p _ q : O aluno foi reprovado. Exemplo 3. • (V) p :Windows e´ um sistema operacional ou q pascal e´ uma linguagem de programac¸a˜o; • (V) p : Windows na˜o e´ um sistema operacional ou q pascal e´ uma linguagem de programac¸a˜o; • (V) p : Windows e´ um sistema operacional ou q pascal na˜o e´ uma linguagem de programac¸a˜o; • (F) p : Windows na˜o e´ um sistema operacional ou q pascal na˜o e´ uma linguagem de programac¸a˜o; 1.2.3 Conectivo de Negac¸a˜o (NA˜O): ¬ Definic¸a˜o 4. Este conectivo serve para alterar a valorac¸a˜o de uma sentenc¸a lo´gica. Desta forma, se uma sentenc¸a lo´gica p tiver valorac¸a˜o V enta˜o ¬p possui valorac¸a˜o F e se uma sentenc¸a lo´gica p tiver valorac¸a˜o F, enta˜o ¬p possui valorac¸a˜o V. 1.2. CONECTIVOS LO´GICOS 9 Este conectivopode ser representado pela seguinte tabela-verdade: p ¬p V F F V Exemplo 4. • Se p : o nu´mero e´ primo, enta˜o ¬p : o nu´mero na˜o e´ primo. • Se p : Choveu, enta˜o ¬p : Na˜o choveu. • Se p : Pedro foi aprovado, enta˜o ¬p : Pedro na˜o foi aprovado. 1.2.4 Conectivo de Implicac¸a˜o ou conectivo condicional (SE ... ENTA˜O): ! Definic¸a˜o 5. Conectivo de implicac¸a˜o ou conectivo condicional (!) e´ um conectivo que conecta duas sentenc¸as lo´gicas p e q para formar uma nova sentenc¸a p ! q que recebe valorac¸a˜o F (falsa) se, e somente se, p tem valorac¸a˜o verdadeira e q tem valorac¸a˜o falsa. Neste caso, p e´ chamada de hipo´tese e q e´ chamada de tese. Se p e q sa˜o sentenc¸as lo´gicas enta˜o a sentenc¸a p ! q pode ser representada pela seguinte tabela-verdade: p q p! q V V V F V V V F F F F V Observac¸a˜o 1. Para o sı´mbolo p! q leˆ-se se p enta˜o q ou p implica em q. Exemplo 5. Seja p : o nu´mero m e´ maior do que 10 e q : o nu´mero m e´ maior do que 3. Assim, p! q quer dizer que se o nu´merom e´ maior do que 10, enta˜o o nu´merom e´ maior do que 3. 10 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA 1.2.5 Conectivo de bi-implicac¸a˜o ou conectivo bicondicional (SE, E SOMENTE SE,): $ Definic¸a˜o 6. Conectivo de bi-implicac¸a˜o ou conectivo bicondicional ($) e´ um conectivo que conecta duas sentenc¸as lo´gicas p e q para formar uma nova sentenc¸a p$ q que recebe valorac¸a˜o V (verdadeira) se, e somente se, p e q possuem a mesma valorac¸a˜o. Se p e q sa˜o sentenc¸as lo´gicas enta˜o a sentenc¸a p $ q pode ser representada pela seguinte tabela-verdade: p q p$ q V V V F V F V F F F F V Observac¸a˜o 2. Para o sı´mbolo p$ q leˆ-se p se, e somente se, q. Exemplo 6. Sejam p : n e´ um nu´mero natural primo; q : n e´ um nu´mero natural e seus u´nicos divisores de n sa˜o 1 e n. Enta˜o p $ q significa que um nu´mero n natural e´ primo se, e somente se, seus u´nicos divisores sa˜o 1 e n. Exemplo 7. Sejam p : As retas r e s teˆm o mesmo coeficiente angular; q : As retas r e s sa˜o paralelas. Enta˜o p $ q significa que duas retas sa˜o paralelas se, e somente se, teˆm o mesmo coeficiente angular. 1.3 Tautologia e Contradic¸a˜o Definic¸a˜o 7. Se uma sentenc¸a recebe valorac¸a˜o V para quaisquer que sejam as valorac¸o˜es das sentenc¸as componentes, enta˜o dizemos que esta sentenc¸a e´ uma tautologia. Exemplo 8. Mostre que (p! q) ^ (q ! r)! (p! r) e´ uma tautologia. Definic¸a˜o 8. Se uma sentenc¸a recebe valorac¸a˜o F para quaisquer que sejam as valorac¸o˜es das sentenc¸as componentes, enta˜o dizemos que esta sentenc¸a e´ uma contradic¸a˜o. Exemplo 9. Prove que (p! q) ^ (p _ ¬q) e´ uma contradic¸a˜o. 1.4. RELAC¸O˜ES ENTRE SENTENC¸AS LO´GICAS 11 1.4 Relac¸o˜es entre sentenc¸as lo´gicas 1.4.1 Relac¸a˜o de implicac¸a˜o Definic¸a˜o 9. Relac¸a˜o de implicac¸a˜o: ()) Diz-se que uma sentenc¸a lo´gica (proposic¸a˜o) p implica em uma sentenc¸a lo´gica (ou proposic¸a˜o) q, (p) q), se a sentenc¸a lo´gica q tem valorac¸a˜o verdadeira V sempre que a sentenc¸a lo´gica q possuir valorac¸a˜o verdadeira V, ou seja, se p! q e´ uma tautologia. Exemplo 10. Mostre que: (a) p ^ q ) p (b) p) p _ q. 1.4.2 Relac¸a˜o de equivaleˆncia Definic¸a˜o 10. Relac¸a˜o de equivaleˆncia: (,) Diz-se que duas sentenc¸as lo´gicas (ou proposic¸o˜es) p e q sa˜o equivalentes, p, q, quando suas tabelas-verdade forem iguais, ou seja, se p$ q e´ uma tautologia. Equivaleˆncias Nota´veis 1. Dupla negac¸a˜o ¬(¬p), p (1.1) 2. Idempoteˆncia p _ p, p (1.2) p ^ p, p (1.3) 3. Comutatividade p _ q , q _ p (1.4) p ^ q , q ^ p (1.5) 12 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA 4. Associatividade p _ (q _ r), (p _ q) _ r (1.6) p ^ (q ^ r), (p ^ q) ^ r (1.7) 5. Bicondicionalidade p$ q , (p! q) ^ (q ! p) (1.8) 6. Contraposic¸a˜o p! q , ¬q ! ¬p (1.9) 7. Leis de De Morgan ¬(p _ q), ¬p ^ ¬q (1.10) ¬(p ^ q), ¬p _ ¬q (1.11) Exercı´cio 1. Prove que p! q , (¬p _ q) Usando o computador Na linguagem de programac¸a˜o e´ comum utilizarmos conectivos lo´gicos. Estes conectivos lo´gicos muitas vezes sa˜o apresentados de uma forma (ou com um sı´mbolo) diferente do que vimos aqui. A tabela abaixo apresenta alguns conectivos lo´gicos utilizados com sua representac¸a˜o nas linguagens de programac¸a˜o C e pascal. Sı´mbolo padra˜o Linguagem C Linguagem Pascal ^ && and _ || or ¬ ! not Para demonstrar que uma sentenc¸a lo´gica q formada a partir das sentenc¸as constituintes a, · · · , c e´ uma tautologia basta utilizarmos o seguinte algoritmo em C para demonstrar esta condic¸a˜o: #include<stdlib.h> #include<stdio.h> 1.5. SENTENC¸A ABERTAS E SENTENC¸AS FECHADAS 13 int main() { int a, ... , c, x; x=1; for (a=0; a<2; a+ +) { ... { for(c=0; c<2; c++) if (!q) {x=0; break;} if (!q) {break;} } ... if (!q) {break;}} return x; } 1.5 Sentenc¸a abertas e Sentenc¸as Fechadas Definic¸a˜o 11. Uma sentenc¸a fechada e´ uma sentenc¸a lo´gica cuja valorac¸a˜o na˜o depende de atribuic¸a˜o de valores para varia´veis. Exemplo 11. A sentenc¸a p : 5 > 7 e´ uma sentenc¸a fechada cujo valor lo´gico e´ falso. Definic¸a˜o 12. Uma sentenc¸a aberta e´ uma sentenc¸a lo´gica cuja valorac¸a˜o depende de atribuic¸a˜o de valores para varia´veis. Exemplo 12. A sentenc¸a q : x2 < 5 e´ uma sentenc¸a aberta. Definic¸a˜o 13. O conjunto universo de uma sentenc¸a aberta e´ o conjunto de todos os va- lores atribuı´dos as varia´veis de modo a torna´-la uma sentenc¸a lo´gica. O conjunto universo e´ representado pela letra U (maiu´scula). Definic¸a˜o 14. O conjunto verdade de uma sentenc¸a aberta p(x) e´ o subconjunto de U de todos os valores atribuı´dos a varia´vel x de modo que p(x) seja verdadeira. O conjunto verdade de uma sentenc¸a aberta p(x) e´ representado por V = {x 2 U | v(p(x)) = V }. 14 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA 1.6 Quantificadores Definic¸a˜o 15. Expresso˜es como “existe”, “para algum”, “para todos”, “para qualquer”que expressa˜o quantidades sa˜o chamadas de quantificadores. 1.6.1 Quantificador universal Definic¸a˜o 16. Expresso˜es como “para todo”, “para qualquer”que expressam que para qualquer elemento x do conjunto universo a sentenc¸a aberta p(x) e´ verdadeira sa˜o repre- sentadas pelo que chamamos de quantificador universal 8, de modo que a expressa˜o “para todo x, p(x)”pode ser substituı´da simbolicamente por (8x) (p(x)) . Exemplo 13. (a) (8x) (x2 + 1 > 0) (b) (8x) (x > 5) Observac¸a˜o 3. Observe que se o conjunto-verdade de uma sentenc¸a aberta p(x) for igual ao conjunto universo U, enta˜o a sentenc¸a lo´gica (8x) (p(x)) e´ verdadeira, ou seja, v ((8x) (p(x))) = V , V = U. 1.6.2 Quantificador existencial Definic¸a˜o 17. Expresso˜es como “existe”ou “para algum”que expressam a existeˆncia de que para algum elemento x do conjunto universo a sentenc¸a aberta p(x) e´ verdadeira sa˜o representadas pelo que chamamos de quantificador existencial 9, de modo que a expressa˜o “para algum x, p(x)”pode ser substituı´da simbolicamente por (9x) (p(x)) . Exemplo 14. (a) (9x) (x2 = 1) (b) (9x) (x2 + 1 < 0) Observac¸a˜o 4. Observe que se o conjunto-verdade de uma sentenc¸a aberta p(x) for na˜o vazio, enta˜o a sentenc¸a (9x) (p(x)) e´ sempre verdadeira, ou seja, v(p(x)) = V , V 6= ?. Definic¸a˜o 18. Uma sentenc¸a quantificada e´ uma sentenc¸a formada a partir de quantifi- cadores. 1.6. QUANTIFICADORES 15 Lista de Exercı´cios sobre Lo´gica Matema´tica 1. Mostre que as seguintes sentenc¸as lo´gicas sa˜o tautologias: (a) (p$ q)$ (p! q) ^ (q ! p) (b) ¬(¬p _ ¬q)$ (p ^ q) 2. Mostre que as seguinte sentenc¸a lo´gica (p! q) ^ (p ^ ¬q) e´ uma contradic¸a˜o. 3. Sejam as proposic¸o˜es p : Joa˜o joga futebol e q : Joa˜o joga teˆnis. Escreva na lingua- gem usual asseguintes proposic¸o˜es: (a) p _ q (b) p ^ q (c) p ^ ¬q (d) ¬p ^ ¬q (e) ¬(¬p) (f) ¬(¬p ^ ¬q) 4. Dadas as proposic¸o˜es p :Maria e´ bonita e q :Maria e´ elegante, escreva na linguagem simbo´lica as seguintes proposic¸o˜es: (a) Maria e´ bonita e elegante. (b) Maria e´ bonita, mas na˜o e´ elegante. (c) Na˜o e´ verdade que Maria na˜o e´ bonita ou elegante. (d) Maria na˜o e´ bonita nem elegante. (e) Maria e´ bonita ou na˜o e´ bonita e elegante. (f) E´ falso que Maria na˜o e´ bonita ou que na˜o e´ elegante. 5. Se V (p) = V (q) = V e V (r) = V (s) = F, determinar os valores lo´gicos das seguintes proposic¸o˜es: (a) ¬p _ r (b) [r _ (p! s)] (c) [¬p _ ¬(r ^ s)] 16 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA (d) ¬[q $ (¬p)] (e) (p$ q) _ (q ! ¬p) (f) (p$ q) ^ (¬r ! s) (g) ¬{¬[¬q ^ ¬(p ^ ¬s)]} (h) ¬p _ [q ^ (r ! ¬s)] (i) (¬p _ r)! (q ! s) (j) ¬[¬p _ (q ^ s)] _ (r ! ¬s) (k) ¬q ^ [(¬s _ s)$ (p! ¬q)] (l) ¬[p! (q ! r)]! s 6. Verifique que: (a) (p! q) ^ (q ! p), (p$ q) (b) (p ^ q)) (p _ q) (c) ¬(p _ q), ¬p ^ ¬q (d) p _ (q ^ r), (p _ q) ^ (p _ r) (e) ¬b ^ q ) q 7. Negue as seguintes sentenc¸as lo´gicas: (a) (p! q)! r (b) (p! q) ^ (q ! r) (c) (¬r ! q) ^ p (d) ¬(p ^ r) _ p (e) p$ r 8. Negue as seguintes sentenc¸as lo´gicas com quantificadores: (a) (8") (9�) (0 < |x� c| < � ! |f(x)� L| < ") (b) (9x) (x2 + 2x > 10) (c) (8x) (x2 + 1 6= 0) 1.6. QUANTIFICADORES 17 (d) (8x) (8y) �(px > py)! (x > y)� (e) (8x) (8y) (x 6= y ! ((x > y) _ (y > x))) 9. Negue as seguintes sentenc¸as lo´gicas e escreva estas sentenc¸as na forma simbo´lica. (a) Todo retaˆngulo e´ um quadrila´tero. (b) Nem todo polı´gono e´ regular. (c) Toda a´rvore que possui n ve´rtices possui n� 1 arestas. (d) Nenhuma a´rvore conte´m ciclos. (e) Um grafo conexo e acı´clico e´ uma a´rvore. (f) Todo homem e´ bom. (g) Existem homens valentes e homens covardes. 18 CAPI´TULO 1. FUNDAMENTOS DE LO´GICA MATEMA´TICA Capı´tulo 2 Conjuntos Os termos elemento e conjunto sa˜o primitivos, ou seja, na˜o precisam ser definidos. Con- junto da´ ideia de colec¸a˜o de objetos, que sa˜o os elementos do conjunto. Daı´, conjunto poder ser visto como sinoˆnimo de colec¸a˜o. 2.1 Relac¸a˜o de pertineˆncia Quando um elemento a pertence a um conjunto A utilizamos o sı´mbolo 2 para representar esta relac¸a˜o, de modo que a 2 A. Caso contra´rio, quando um elemento a na˜o pertence a um conjunto A utilizamos o sı´mbolo 62 para representar esta relac¸a˜o, de modo que a 62 A. 2.2 Relac¸o˜es entre conjuntos 2.2.1 Relac¸a˜o de igualdade Definic¸a˜o 19. Dois conjuntos sa˜o iguais se possuem os mesmos elementos. Exemplo 15. Se A = {1; 1; 2; 4; 6; 7} e B = {1; 2; 4; 4; 6; 7; 7; 7}, enta˜o A = B, pois A e B possuem os mesmos elementos. 2.2.2 Relac¸a˜o de contineˆncia entre conjuntos Definic¸a˜o 20. Sejam A e B conjuntos. Dizemos que um conjunto A e´ um subconjunto de um conjunto B (ou A esta´ contido em B ou que B conte´m A) se todo elemento do conjunto A e´ elemento do conjunto B. Utilizamos os sı´mbolos A ⇢ B (A esta´ contido 19 20 CAPI´TULO 2. CONJUNTOS em B) e B � A (B conte´m A) para representar que o conjunto A e´ um subconjunto do conjunto B. No caso em que um conjuntoA na˜o e´ um subconjunto de um conjuntoB (ouA na˜o esta´ contido em B ou que B na˜o conte´m A, enta˜o existem elementos do conjunto A que na˜o esta˜o no conjunto B. Neste caso utilizamos os sı´mbolos A 6⇢ B (A na˜o esta´ contido em B) e B � A (B na˜o conte´m A) para representar que o conjunto A na˜o e´ um subconjunto do conjunto B. Em sı´mbolos, A ⇢ B , (8x) ((x 2 A) ^ (x 2 B)) , ou seja, (A ⇢ B)$ (8x) ((x 2 A) ^ (x 2 B)) e´ uma tautologia. Algumas propriedades dos subconjuntos sa˜o (1) A ⇢ A. (2) Se A ⇢ B e B ⇢ C, enta˜o A ⇢ C. (3) Se A ⇢ B e B ⇢ A, enta˜o A = B. (4) A ⇢ U. Definic¸a˜o 21. O Conjunto Universo U e´ o conjunto de todos os elementos do sistema. Definic¸a˜o 22. O Conjunto Vazio ? (ou {}) e´ o conjunto que na˜o possui elementos. Definic¸a˜o 23. Conjunto Unita´rio e´ um conjunto que possui apenas um elemento. Exemplo 16. Os conjuntos {?}, {{}} e {1} sa˜o conjuntos unita´rios. 2.3 Operac¸o˜es sobre conjuntos As operac¸o˜es sobre conjuntos dividem-se em operac¸o˜es bina´rias, operac¸ oes una´rias e operac¸o˜es restritas. 2.3. OPERAC¸O˜ES SOBRE CONJUNTOS 21 2.3.1 Operac¸o˜es bina´rias Definic¸a˜o 24. O conjunto intersec¸a˜o A\B e´ o conjunto formado pelos elementos comuns entre os conjuntos A e B. Em sı´mbolos, (8x) (x 2 A \ B $ (x 2 A) ^ (x 2 B)) e´ uma tautologia. Definic¸a˜o 25. O conjunto unia˜o A [ B e´ o conjunto formado por todos os elementos de A e por todos os elementos de B. Em sı´mbolos, (8x) (x 2 A [ B $ (x 2 A) _ (x 2 B)) e´ uma tautologia. Definic¸a˜o 26. O conjunto diferenc¸a A � B e´ o conjunto formado pelos elementos que esta˜o em A e na˜o esta˜o em B. Em sı´mbolos, (8x) ((x 2 A� B)$ (x 2 A) ^ (x 62 B)) e´ uma tautologia. 2.3.2 Operac¸a˜o una´ria Definic¸a˜o 27. O complementar de um conjunto A, AC (ou C(A) ou A) e´ o conjunto dos elementos que esta˜o no conjunto universo U mas que na˜o esta˜o em A. Em sı´mbolos, (8x) �x 2 AC $ x 62 A� e´ uma tautologia. 2.3.3 Operac¸a˜o una´ria restrita Definic¸a˜o 28. Sejam A e B conjuntos tais que A ⇢ B. O complementar de A em B, CAB ou CB(A), e´ o conjunto dos elementos que esta˜o em B e que na˜o esta˜o em A. Em sı´mbolos, (8x) (x 2 CB(A)$ ((A ⇢ B) ^ (x 2 B � A))) Exemplo 17. Se A = {1; 2; 3; 7; 8; 9}, B = {2; 4; 6; 8} e C = {1; 3; 7; 9}, enta˜o (1) A \ B = {2; 8}; (2) A [ B = {1; 2; 3; 4; 6; 7; 8; 9}; (3) A� B = {1; 3; 7; 9}; (4) B � A = {4; 6}; (5) CA(C) = {2; 8}. Definic¸a˜o 29. O conjunto das partes de um conjunto A, P (A) ou P(A), e´ o conjunto dos subconjuntos de A. 22 CAPI´TULO 2. CONJUNTOS Exemplo 18. Se A = {0; 1}, enta˜o o conjunto das partes de A e´ o conjunto P (A) = {?; {0}; {1}; {0; 1}} Exemplo 19. Se A = {1; 2; 3}, enta˜o o conjunto das partes de A e´ o conjunto P (A) = {?; {1}; {2}; {3}; {1; 2}; {1; 3}; {2; 3}; {1; 2; 3}} Observac¸a˜o 5. n(P (A)) = ✓ n(A) 0 ◆ + ✓ n(A) 1 ◆ + · · ·+ ✓ n(A) n(A) ◆ = 2n(A) Definic¸a˜o 30. O conjunto diferenc¸a sime´trica entre os conjuntos A e B e´ o conjunto A4B = (A� B) [ (B � A). Outras propriedades dos conjuntos (1) A \ A = A (Idempotente); (2) A [ A = A (Idempotente); (3) A \? = A (identidade); (4) A [? = ? (identidade); (5) A [B = B [ A (comutativa); (6) A \B = B \ A (comutativa); (7) (A \ B) \ C = A \ (B \ C) (associativa); (8) (A [ B) [ C = A [ (B [ C) (associativa); (9) A \ (B [ C) = (A \B) [ (A \ C) (distributiva); (10) A [ (B \ C) = (A [B) \ (A [ C) (distributiva); (11) A \ B = A [B (De Morgan); (12) A [ B = A \B (De Morgan); (13) (A� B) [ (A \ B) = A. 2.3. OPERAC¸O˜ES SOBRE CONJUNTOS 23 Demonstrac¸a˜o. x 2 A , (x 2 A e x 62 B) ou (x 2 A e x 2 B) , (x 2 A� B) ou (x 2 A \ B) , x 2 (A� B) [ (A \B) Existe uma equivalencia entre sentenc¸as lo´gicas e teoria dos conjuntos que pode ser traduzida pela seguinte tabela, onde p : x 2 A e q : x 2 B. Sentenc¸a equivalente Em conjuntos p! q A ⇢ B p ^ q A \ B p _ q A [ B Tautologia U Contradic¸a˜o ? ¬p A p ^ ¬q A� B (p! q) ^ (p ^ ¬q) CB(A) (p ^ ¬q) _ (q ^ ¬p) A4B De Morgan De Morgan Exemplo 20. Verifique a validade da relac¸a˜o (A�B)[ (A\B) = A utilizando sentenc¸as lo´gicas. E´ suficiente mostrarmos que a sentenc¸a (p ^ ¬q) _ (p ^ q)$ p e´ sempre verdadeira Construindo a tabela verdade para a sentenc¸a acima, obtemos p q ¬q p ^ ¬q p ^ q (p ^ ¬q) _ (p ^ q) (p ^ ¬q) _ (p ^ q)$ p V V F F V V V V F V V F V V F V F F F F V F F V F F F V 24 CAPI´TULO 2. CONJUNTOS Como a coluna que corresponde a sentenc¸a (p ^ ¬q) _ (p ^ q)$ passume apenas valorac¸a˜o V, enta˜o a relac¸a˜o (A� B) [ (A \ B) = A esta´ correta. 2.4 Princı´pio da Inclusa˜o-Exclusa˜o O nu´mero de elementos da unia˜o de dois conjuntos e´ igual a soma do nu´mero de elementos de cada um dos conjuntos subtraı´do do nu´mero de elementos da intersec¸a˜o entre estes conjuntos. Em sı´mbolos, n(A [ B) = n(A) + n(B)� n(A [ B) Exemplo 21. Durante a Segunda Guerra Mundial, os aliados tomaram um campo de concentrac¸a˜o nazista e de la´ resgataram 1500 prisioneiros. Desses, 650 estavam com sarampo, 350 com tuberculose e 700 na˜o tinham nenhuma dessas duas doenc¸as. Qual o nu´mero de prisioneiros com as duas doenc¸as? Resoluc¸a˜o gra´fica S T x650-x 350-x 700 xy~z}{|xy~z}{| 650 + 350� x+ 700 = 1500 ) 1700� x = 1500 ) x = 1700� 1500 = 200 Resposta: 200 prisioneiros. Resoluc¸a˜o alge´brica n(U) = 1500 n(S) = 650 2.4. PRINCI´PIO DA INCLUSA˜O-EXCLUSA˜O 25 n(T ) = 350 n(S [ T ) = 700 n(U) = n((S [ T ) [ (S [ T )) ) n(U) = n(S [ T ) + n(S [ T )� n((S [ T ) \ (S [ T )) ) n(U) = n(S) + n(T )� n(S \ T ) + n(S [ T )� n(?) ) 1500 = 650 + 350� n(S \ T ) + 700� 0 ) 1500 = 1700� n(S \ T ) ) n(S \ T ) = 1700� 1500 ) n(S \ T ) = 200 Exemplo 22. Objetivando conhecer a prefereˆncia musical dos seus ouvintes, certa emis- sora de ra´dio realizou uma pesquisa, dando como opc¸a˜o treˆs compositores: M, B e S. Os resultados sa˜o: Votos Opc¸o˜es 27 Gostam de B 34 Gostam de M 40 Gostam de S 16 Gostam de B e M 12 Gostam de B e S 14 Gostam de M e S 6 Gostam de B, M e S 4 Na˜o gostam de B, M e S Qual e´ o nu´mero de pessoas consultadas? Resoluc¸a˜o alge´brica: n(B) = 27 n(M) = 34 n(S) = 40 n(B \M) = 16 n(B \ S) = 12 26 CAPI´TULO 2. CONJUNTOS n(M \ S) = 14 n(B \M \ S) = 6 n(B [M [ S) = 4 n(U) = n((B [M [ S) [ (B [M [ S)) ) n(U) = n(B [M [ S) + n(B [M [ S) ) n(U) = n(B [M) [ S) + n(B [M [ S) ) n(U) = n(B [M) + n(S)� n((B [M) \ S) + n(B [M [ S) ) n(U) = n(B) + n(M)� n(B \M) + n(S) �n((B \ S) [ (M \ S)) + n(B [M [ S) ) n(U) = n(B) + n(M)� n(B \M) + n(S) �n(B \ S)� n(M \ S) + n((B \ S) \ (M \ S)) + n(B [M [ S) ) n(U) = n(B) + n(M)� n(B \M) + n(S) �n(B \ S)� n(M \ S) + n(B \M \ S) + n(B [M [ S) ) n(U) = 27 + 34� 16 + 40� 12� 14 + 6 + 4 ) n(U) = 111� 42 = 69 Resposta: 69 pessoas consultadas. Resoluc¸a˜o gra´fica B M S 4 6 105 10 86 20 xy~z}{|xy~z}{|xy~z}{| Resposta: 27 + 10 + 8 + 20 + 4 = 69 pessoas consultadas. Observac¸a˜o 6. O nu´mero de informac¸o˜es necessa´rias e suficientes para resolver qual- quer problema utilizando o Princı´pio da Inclusa˜o-Exclusa˜o e´ 2m, onde m e´ o nu´mero de conjuntos envolvidos diferentes do conjunto universo. Listas de Exercı´cios sobre Conjuntos 1) Encontre P (A), se 2.4. PRINCI´PIO DA INCLUSA˜O-EXCLUSA˜O 27 (a) A = {1; 2}. (b) A = {2; 3; 4}. 2) O que se pode dizer sobre o conjunto A se P (A) = {?, {x}, {y}, {x, y}}? 3) Prove que P (A) \ P (B) = P (A \B), onde A e B sa˜o conjuntos arbitra´rios. 4) Mostre que se (A� B) [ (B � A) = A [B, enta˜o A \ B = ?. Dica: Demonstre por contradic¸a˜o. 5) Prove que se P (A) = P (B), enta˜o A = B. 6) Verifique se as seguintes propriedades de conjuntos sa˜o satisfeitas atrave´s de sentenc¸as lo´gicas equivalentes: (a) A� (B [ C) = (A� B) \ (A� C) (b) A = (A [ B)� B (c) (A \ B) ⇢ A. 7) SeU = {1, 3, 9, 27, 2, 4, 6, 8, 10, 12, 16, 24} e´ o conjunto universo,A = {1, 2, 3, 6, 12, 24}, B = {1, 3, 6} e D = {1, 2, 4, 8, 16}, calcule (a) A�D (b) D � A (c) CBA (d) AC (e) DC (f) A [D 28 CAPI´TULO 2. CONJUNTOS (g) AC \DC 8) Numa escola de 630 alunos, 350 deles estudam Portugueˆs, 210 estudam Espanhol e 90 estudam as duas mate´rias (Portugueˆs e Espanhol). Pergunta-se: (a) Quantos alunos estudam apenas Portugueˆs? (b) Quantos alunos estudam apenas Espanhol? (c) Quantos alunos estudam Portugueˆs ou Espanhol? (d) Quantos alunos na˜o estudam nenhuma das duas mate´rias? 9) De 200 pessoas que foram pesquisadas sobre suas prefereˆncias em assistir aos cam- peonatos de corrida pela televisa˜o, foram colhidos os seguintes dados: 55 dos entre- vistados na˜o assitem; 101 assistem a`s corridas de Fo´rmula 1 e 27 assitem a`s corridas de Fo´rmula 1 e de Motovelocidade. Quantas das pessoas entrevistadas assistem, ex- clusivamente, a`s corridas de Motovelocidade? 10) Numa prova constituı´da de dois problemas, 300 alunos acertaram somente um dos problemas, 260 acertaram o segundo, 100 alunos acertaram os dois e 210 erraram o primeiro. Quantos alunos fizeram a prova? 11) Um grupo de alunos de uma escola deveria visitar o Museu de Cieˆncia e o Museu de Histo´ria da cidade. Quarenta e oito alunos foram visitar pelo menos um desses museus. 20% dos que foram ao de Cieˆncia visitaram o de Histo´ria e 25% dos que foram ao de Histo´ria visitaram tambe´m o de Cieˆncia. Calcule o nu´mero de alunos que visitaram os dois museus. 12) Num grupo de 99 esportistas, 40 jogam voˆlei, 20 jogam voˆlei e xadrez, 22 jogam xadrez e teˆnis, 18 jogam voˆlei e teˆnis, 11 jogam as treˆs modalidades. O nu´mero de pessoas que jogam xadrez e´ igual ao nu´mero de pessoas que jogam teˆnis. Quantas jogam: (a) teˆnis e na˜o jogam voˆlei? (b) xadrez ou teˆnis e na˜o jogam voˆlei? 2.4. PRINCI´PIO DA INCLUSA˜O-EXCLUSA˜O 29 (c) voˆlei e na˜o jogam xadrez? 13) Analisando-se as carteiras de vacinac¸a˜o das 84 crianc¸as de uma creche, verificou-se que 68 receberam vacina Sabin, 50 receberam vacina contra sarampo e 12 na˜o foram vacinadas. Quantas dessas crianc¸as receberam as duas vacinas? 14) 10 000 aparelhos de TV foram examinados depois de um ano de uso, e constatou-se que 4 000 deles apresentavam problemas de imagem, 2 800 tinham problemas de som e 3 500 na˜o apresentavam nenhum dos tipos de problemas citados. Qual e´ o nu´mero de aparelhos que apresentaram somente problemas de imagem? 15) Dos 80 alunos de uma turma, 15 foram reprovados em Matema´tica, 11 em Fı´sica e 10 em Quı´mica. Oito alunos foram reprovados simultaneamente em Matema´tica e Fı´sica, seis em Matema´tica e Quı´mica e quatro em Fı´sica e Quı´mica. Sabendo que 3 alunos foram reprovados nas treˆs disciplinas, determine quantos alunos na˜o foram reprovados em nenhuma dessas disciplinas. 16) Numa pesquisa verificou-se que, das pessoas consultadas, 100 liam o jornal A, 150 liam o jornal B, 20 liam os dois jornais (A e B) e 110 na˜o liam nenhum dos jornais. Quantas pessoas foram consultadas? 17) Seja U = {0, 1, 2, 3, 4, 5, 6, 7, 8} o conjunto universo. (a) Encontre o conjunto A sabendo que AC = {1, 5, 7, 8}. (b) Encontre o maior conjunto D satisfazendo D [ C = {1, 4, 5, 6}. (c) Encontre o conjunto E sabendo que F = {4, 5, 6, 7, 8} e CEF = {4, 8}. (d) Encontre o conjunto G sabendo que G [ B = {1, 5, 6, 7, 8}, G \ B = {1, 6} e B = {1, 6, 8}. 18) Demonstre as seguintes propriedades de conjuntos: (a) (A [ B)C = AC \ BC . (b) A [B = A, B ⇢ A. (c) A [ (B \ C) = (A [ B) \ (A [ C). (d) A = (A� B) [ (A \ B). 30 CAPI´TULO 2. CONJUNTOS Capı´tulo 3 Te´cnicas de Demonstrac¸a˜o Uma proposic¸a˜o (ou teorema) do tipo P ! Q e´ formado por um conjunto P de hipo´teses que sa˜o condic¸o˜es necessa´rias e que, conjuntamente, sa˜o suficientes para se chegar a uma conclusa˜o (tese) Q. Dentre as diversas te´cnicas de demonstrac¸a˜o utilizadas, abordaremos as seguintes te´cnicas: • Te´cnica de demonstrac¸a˜o por exausta˜o; • Te´cnica de demonstrac¸a˜o direta; • Te´cnica de demonstrac¸a˜o por contraposic¸a˜o; • Te´cnica de demonstrac¸a˜o por contradic¸a˜o. Como ferramenta em algumas demonstrac¸o˜es, abordaremos o Princı´pio de induc¸a˜o matema´tica. 3.1 Te´cnica de demonstrac¸a˜o por exausta˜o Esta te´cnica consiste na verificac¸a˜o da validade da proposic¸a˜o P ! Q a partir da verificac¸a˜ode uma quantidade finita de casos particulares. Exemplo 23. Demonstre que se um nu´mero natural n satisfaz n 2, enta˜o n! n+ 1. Demonstrac¸a˜o. Neste caso P : n 2 31 32 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O e Q : n! n+ 1. Para n = 0, temos que n! = 0! = 1 1 = 0 + 1 = n+ 1. Para n = 1, temos que n! = 1! = 1 = 1 2 = 1 + 1 = n+ 1. Para n = 2, temos que n! = 2! = 2 3 = 2 + 1 = n+ 1. Logo, por exausta˜o, se n 2 N e n 2, enta˜o n! n+ 1. 3.2 Te´cnica de demonstrac¸a˜o direta Esta te´cnica consiste na verificac¸a˜o da validade da proposic¸a˜o P ! Q a partir do cami- nho natural que se inicia a partir da suposic¸a˜o da validade da hipo´tese P para chegar na verificac¸a˜o da validade da tese Q. Utilizaremos as seguintes definic¸o˜es nos pro´ximos exemplos: Definic¸a˜o 31. Um nu´mero inteiro n e´ um nu´mero par se existir um nu´mero inteiro k tal que n = 2k. Definic¸a˜o 32. Um nu´mero inteiro n e´ um nu´mero ı´mpar se existir um nu´mero inteiro k tal que n = 2k + 1. Exemplo 24. Demonstre que soma de dois nu´meros pares e´ um nu´mero par. Demonstrac¸a˜o. Sejam a e b nu´meros pares. Pela definic¸a˜o de nu´mero par, existem k, s 2 Z tais que a = 2k e b = 2s. Assim, a+ b = 2k + 2s = 2(k + s), com k + s 2 Z. Logo a+ b e´ um nu´mero par. Exemplo 25. Demonstre que o quadrado de um nu´mero par e´ tambe´m e´ um nu´mero par. Demonstrac¸a˜o. Seja n um nu´mero par, enta˜o, pela definic¸a˜o, existe k 2 Z tal que n = 2k. Assim, n2 = (2k)2 = 4k2 = 2 · (2k2), com 2k2 2 Z. Logo n2 e´ um nu´mero par. Exemplo 26. Demonstre que o quadrado de um nu´mero ı´mpar tambe´m e´ um nu´mero ı´mpar. 3.3. TE´CNICA DE DEMONSTRAC¸A˜O POR CONTRAPOSIC¸A˜O 33 3.3 Te´cnica de demonstrac¸a˜o por contraposic¸a˜o Esta te´cnica consiste em demonstrarmos a validade da proposic¸a˜o P ! Q a partir da demonstrac¸a˜o da validade da proposic¸a˜o ¬Q ! ¬P, uma vez que a proposic¸a˜o P ! Q e´ logicamente equivalente a sua contrapositiva ¬Q! ¬P. Exemplo 27. Se n 2 N satisfaz n! > n+ 1, mostre que n > 2. Demonstrac¸a˜o. Pelo exemplo 23 mostramos que a seguinte proposic¸a˜o e´ va´lida: Se n 2 N satisfaz n 2, enta˜o n! n+ 1. Logo, sua contrapositiva Se n 2 N satisfaz n! > n+ 1, enta˜o n > 2. tambe´m e´ va´lida. Exemplo 28. Prove que se n2 e´ ı´mpar, enta˜o n e´ ı´mpar. Demonstrac¸a˜o. Esta proposic¸a˜o e´ logicamente equivalente a sua contrapositiva: Se n e´ um nu´mero par, enta˜o n2 e´ um nu´mero par. Portanto, como a proposic¸a˜o acima e´ verdadeira, pelo Exemplo 25, enta˜o a demonstrac¸a˜o segue por contraposic¸a˜o. Exemplo 29. Demonstre que se n2 e´ um nu´mero par, enta˜o n e´ um nu´mero par. 3.4 Te´cnica de demonstrac¸a˜o por contradic¸a˜o (ou por ab- surdo) Esta te´cnica consiste em demonstrarmos a validade da proposic¸a˜o P ! Q a partir da suposic¸a˜o de que P e ¬Q sa˜o verdadeiras para chegar em uma afirmac¸a˜o falsa, uma vez que P ! Q e´ logicamente equivalente a ¬(P ^ ¬Q). P Q ¬Q P ^ ¬Q P ! Q ¬(P ^ ¬Q) V V F F V V V F V V F F F V F F V V F F V F V V 34 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O Exemplo 30. Prove que se x2 = 2, enta˜o x na˜o e´ um nu´mero racional. Demonstrac¸a˜o. Suponhamos que x 2 Q e x2 = 2. Como x 2 Q, enta˜o x = ab onde a e b na˜o possuem divisores primos comuns. Assim, � a b �2 = 2 ) a2 = 2b2 ) (a e´ par e a2 = 2b2) ) (9k 2 Z) (a = 2k e a2 = 2b2) ) (9k 2 Z) (a = 2k e (2k)2 = 2b2) ) (9k 2 Z) (a = 2k e 2k2 = b2) ) (9k 2 Z) (a = 2k e b e´ par e 2k2 = b2) ) (9s 2 Z) (9k 2 Z) (a = 2k e b = 2s e 2k2 = b2) , o que e´ um absurdo, ja´ que 2 seria um nu´mero primo divisor comum de a e b e a e b na˜o possuem divisores primos comuns. 3.5 Princı´pios de induc¸a˜o matema´tica Primeiro Princı´pio de Induc¸a˜o Matema´tica Seja a 2 Z e suponhamos que para cada inteiro n � a esteja associada uma proposic¸a˜o P (n). Enta˜o P (n) sera´ verdadeira para todo n � a desde que seja possı´vel provar que: (a) P (a) e´ verdadeira; (b) Se P (k) e´ verdadeira para k � a, enta˜o P (k + 1) tambe´m e´ verdadeira. Neste caso, utilizamos a seguinte denominac¸a˜o: • base de induc¸a˜o: demonstrar que P (a) e´ verdadeira; • hipo´tese de induc¸a˜o: supor que P (k) e´ verdadeira para algum k � a; • passo de induc¸a˜o: provar que se P (k) e´ verdadeira enta˜o P (k + 1) tambe´m e´ verdadeira para k � a. Exemplo 31. Prove por induc¸a˜o que para qualquer n 2 N, vale n < 2n. 3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 35 Exemplo 32. Prove por induc¸a˜o que para qualquer n 2 N, se n > 3, enta˜o 2n < n!. Exemplo 33. Prove por induc¸a˜o que para qualquer n 2 N, tem-se que 1 + 2 + · · ·+ n = n(n+ 1) 2 Demonstrac¸a˜o. Seja P (n) : 1 + 2 + 3 + · · ·+ n = n(n+1)2 . Base de Induc¸a˜o: Como 1 = 1·(1+1)2 , enta˜o P (1) e´ verdadeira. Hipo´tese de Induc¸a˜o: Suponhamos que P (k) seja verdadeira. Passo de Induc¸a˜o: Como P (k) e´ verdadeira, enta˜o 1 + 2 + 3 + · · ·+ k = k(k + 1) 2 . Assim, 1 + 2 + 3 + · · ·+ k + (k + 1) = k(k+1)2 + (k + 1) = (k + 1) ⇥ k 2 + 1 ⇤ = (k + 1) ⇥ k+2 2 ⇤ = (k+1)((k+1)+1)2 . Portanto, P (k + 1) e´ verdadeira. Logo, por induc¸a˜o P (n) : 1 + 2+ 3+ · · ·+ n = n(n+1)2 e´ verdadeira para todo n 2 N⇤. Outra demonstrac¸a˜o sem utilizar os indicativos Como 1 = 1·(1+1)2 e supondo 1 + 2 + 3 + · · ·+ k = k(k+1)2 temos que 1 + 2 + 3 + · · ·+ k + (k + 1) = k(k+1)2 + (k + 1) ) 1 + 2 + 3 + · · ·+ k + (k + 1) = (k + 1) ⇥k2 + 1⇤ ) 1 + 2 + 3 + · · ·+ k + (k + 1) = (k+1)(k+2)2 ) 1 + 2 + 3 + · · ·+ k + (k + 1) = (k+1)((k+1)+1)2 Logo, por induc¸a˜o, 1 + 2 + 3 + · · ·+ n = n(n+1)2 para todo n 2 N. Exemplo 34. Mostre que n2 > 2n+ 1 para todo n 2 N, n � 3. Demonstrac¸a˜o. Seja p(n) : n2 > 2n+ 1. Como 32 = 9 > 7 = 2 · 3 + 1, enta˜o p(3) e´ verdadeira. 36 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O Suponhamos que p(m) seja verdadeira para algumm � 3. Assim, m2 > 2m+1) m2+2m+1 > 4m+2 = 2(m+1)+2m > 2(m+1)+1) (m+1)2 > 2(m+1)+1. Portanto, p(m+ 1) e´ verdadeira. Logo, por induc¸a˜o, n2 > 2n+ 1 para todo n 2 N, n � 3. Exemplo 35. Mostre que 1 + 3 + 32 + · · ·+ 3n = 3n+1�12 para todo n 2 N. Demonstrac¸a˜o. Seja p(n) : 1 + 3 + 32 + · · ·+ 3n = 3n+1�12 . Como 1 = 3�12 = 30+1�1 2 , enta˜o p(0) e´ verdadeira. Suponhamos que p(m) seja verdadeira para algumm 2 N. Assim, 1 + 3 + 32 + · · ·+ 3n = 3n+1�12 ) 1 + 3 + 32 + · · ·+ 3n + 3n+1 = 3n+1�12 + 3n+1 ) 1 + 3 + 32 + · · ·+ 3n+1 = 3n+1 �12 + 1�� 12 ) 1 + 3 + 32 + · · ·+ 3n+1 = 3n+2�12 . Portanto, p(m+ 1) e´ verdadeira. Logo, por induc¸a˜o, 1 + 3 + · · ·+ 3n = 3n+1�12 para todo n 2 N. Segundo Princı´pio de Induc¸a˜o Matema´tica Seja a 2 Z e suponhamos que para cada inteiro n � a esteja associada uma proposic¸a˜o P (n). Enta˜o P (n) sera´ verdadeira para todo n � a desde que seja possı´vel provar que: (a) P (a) e´ verdadeira; (b) Dado k > a, se P (m) e´ verdadeira para todo m tal que a m < k, enta˜o P (k) e´ verdadeira. Exemplo 36. Mostre que qualquer postagem de valor igual ou maior que 12 reais pode ser formado usando exclusivamente selos de 4 e 5 reais. Demonstrac¸a˜o. Seja p(n) : n = a · 4 + b · 5, para a, b 2 N. Assim, • P (12) e´ verdadeira, pois 12 = 4 + 4 + 4 = 3 · 4 + 0 · 5. • P (13) e´ verdadeira, pois 13 = 4 + 4 + 5 = 2 · 4 + 1 · 4. 3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 37 • P (14) e´ verdadeira, pois 14 = 4 + 5 + 5 = 1 · 4 + 2 · 5. • P (15) e´ verdadeira, pois 15 = 5 + 5 + 5 = 0 · 4 + 3 · 5. Suponhamos que P (m) seja verdadeira para todo m satisfazendo 15 m < k. Assim, P (k� 4) e´ verdadeira. Portanto, como k� 4 pode ser escrito como somas com parcelas iguais a 4 e/ou 5, enta˜o k = (k�4)+4 tambe´m pode ser escrito como somas com parcelas iguais a 4 e/ou 5. Logo P (k) tambe´m e´ verdadeira. Logo, por induc¸a˜o, P (n) e´ verdadeira para todo nu´mero natural n � 12, ou seja, qual- quer postagem de valor igualou maior que 12 pode ser formado usando exclusivamente selos de 4 e 5 reais. Exemplo 37. Mostre que todo nu´mero natural maior ou igual a 2 ou e´ primo ou pode ser escrito como produto de nu´meros primos. Demonstrac¸a˜o. Seja p(n) : n e´ um nu´mero primo ou n pode ser escrito como produto de nu´meros primos. Sejam um nu´mero natural maior ou igual a 2. Sem = 2, enta˜o p(2) e´ verdadeira, pois 2 e´ um nu´mero primo. Sem > 2 em e´ primo, enta˜o, p(m) e´ verdadeira. Se m > 2 e m e´ composto, enta˜o existem nu´meros naturais a, b maiores ou iguais a 2 tais quem = a · b. Como a e b sa˜o nu´meros naturais maiores ou iguais a 2, podemos supor que p(a) e p(b) sejam verdadeiras. Portanto a ou e´ primo ou pode ser escrito como produto de nu´meros primos e b ou e´ primo ou pode ser escrito como produto de nu´meros primos. De qualquer forma, concluimos que m e´ o produto de nu´meros primos. Portanto, p(m) e´ verdadeira. Logo, pelo segundo princı´pio de induc¸a˜o, todo nu´mero natural maior ou igual a 2 ou e´ primo ou pode ser escrito como produto de nu´meros primos. 38 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O Lista de Exercı´cios sobre Te´cnicas de Demonstrac¸a˜o Ale´m das definic¸o˜es de nu´mero par e de nu´mero ı´mpar, citadas no texto, para a seguinte lista de exercı´cios, utilizamos as seguintes definic¸o˜es: (1) Dizemos que a divide b ou que a e´ um divisor de b ou que b e´ um mu´ltiplo de a se existir k 2 Z tal que b = ka. Neste caso utilizamos o sı´mbolo a | b. (2) Dizemos que a e´ congruente a bmo´dulo n ou que a e´ equivalente a bmo´dulo n se n | (b� a). Neste caso utilizamos o sı´mbolo a ⌘ b mod n. (3) Dizemos que d = mmc(a, b) se (a) a | d e b | d. (b) Para qualquer d0 2 Z, a | d0 e b | d0 ) d | d0. (4) Dizemos que d = mdc(a, b) se (a) d | a e d | b. (b) Para qualquer d0 2 Z, d0 | a e d0 | b) d0 | d. (5) Se d = mdc(a, b), enta˜o d e´ o menor inteiro positivo satisfazendo d = x · a+ y · b, para x, y 2 Z. (6) Dizemos que um nu´mero inteiro p > 1 e´ um nu´mero primo se os u´nicos divisores inteiros positivos de p sa˜o 1 e p. Te´cnica de Demonstrac¸a˜o Direta 1) Sejam a, b e c inteiros. Se a | b e b | c, enta˜o a | c. 2) Se x e´ um inteiro par, enta˜o x2 � 6x+ 5 e´ ı´mpar. 3) Se a, b, c 2 N, enta˜o mmc(ca, cb) = c ·mmc(a, b). 4) Sejam x e y nu´meros positivos. Se x y, enta˜o px py. 5) Se x e y sa˜o nu´meros reais positivos, enta˜o 2pxy x+ y. 3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 39 6) Se n 2 N, enta˜o 1 + (�1)n(2n� 1) e´ um mu´ltiplo de 4. 7) Todo mu´ltiplo de 4 tem a forma 1 + (�1)n(2n� 1) para algum n 2 N. 8) Suponha que x, y 2 Z. Se x e y sa˜o pares, enta˜o xy e´ par. 9) Suponha que x, y 2 Z. Se x e y sa˜o ı´mpares, enta˜o xy e´ ı´mpar. 10) Suponha que a, b, c 2 Z. Se a | b e a | c, enta˜o a | (b+ c). 11) Suponha que a, b 2 Z. Se a | b, enta˜o a2 | b2. 12) Seja a um inteiro. Se 5 | 2a, enta˜o 5 | a. 13) Seja a um inteiro. Se 7 | 4a, enta˜o 7 | a. 14) Sejam a, b 2 Z. Se a | b, enta˜o a | (3b3 � b2 + 5b). 15) Sejam a, b, c, d 2 Z. Se a | b e c | d, enta˜o ac | bc. 16) Se x 2 R e 0 < x < 4, enta˜o 4 x(4� x) � 1. 17) Se n 2 Z, enta˜o 5n2 + 3n+ 7 e´ ı´mpar. 18) Se n 2 Z, enta˜o n2 + 3n+ 4 e´ par. 19) Sejam a, b e c inteiros. Se a2 | b e b3 | c, enta˜o a6 | c. 20) Se n 2 N e n � 2, enta˜o os nu´meros n! + 2, n! + 3, n! + 4, · · · , n! + n sa˜o todos compostos. Consequentemente, para qualquer n � 2, podemos encontrar n consecu- tivos nu´meros compostos. Isto significa que existe um arbitrariamente largo deserto de nu´meros primos. 21) Todo nu´mero inteiro ı´mpar e´ diferenc¸a de dois quadrados. Te´cnica de demonstrac¸a˜o por contraposic¸a˜o 22) Seja x 2 Z. Se 7x+ 9 e´ par, enta˜o x e´ ı´mpar. 23) Se x2 � 6x+ 5 e´ par, enta˜o x e´ ı´mpar. 24) Sejam x, y 2 R. Se y3 + yx2 x3 + xy2, enta˜o y x. 25) Sejam x, y 2 Z Se 5 - xy, enta˜o 5 - x e 5 - y. 40 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O 26) Sejam a, b 2 Z e n 2 N. Se a ⌘ b( mod n), enta˜o a2 ⌘ b2(modn). 27) Sejam a, b 2 Z e n 2 N. Se 12a 6⌘ 12b(modn), enta˜o n - 12. 28) Seja x 2 R. Se x2 + 5x < 0, enta˜o x < 0. 29) Seja x 2 R. Se x3 � x > 0, enta˜o x > �1. 30) Sejam x, y, z 2 Z e x 6= 0. Se x - yz, enta˜o x - y e x - z. 31) Se n 2 N e 2n � 1 e´ primo, enta˜o n e´ primo. 32) Se n 2 Z, enta˜o 4 - (n2 � 3). Te´cnica de demonstrac¸a˜o por contradic¸a˜o 33) Se a, b 2 Z, enta˜o a2 � 4b 6= 2. 34) Existem infinitos nu´meros primos. 35) Para todo nu´mero real x 2 [0, ⇡/2], temos sen x+ cosx � 1. 36) Prove que 3 p 2 e´ irracional. 37) Se a, b 2 Z, enta˜o a2 � 4b� 2 6= 0. 38) Para todo n 2 Z, 4 - (n2 + 2). 39) Na˜o existem nu´meros inteiros a e b tal que 18a+ 6b = 1. Princı´pio de Induc¸a˜o Matema´tica 40) Se n 2 N, enta˜o 1 + 3 + 5 + 7 + · · ·+ (2n� 1) = n2. 41) Se n e´ um inteiro na˜o-negativo, enta˜o 5 | (n5 � n). 42) Se n 2 Z e n � 0, enta˜oPni=0 i · i! = (n+ 1)!� 1. 43) Se n 2 N, enta˜o (1 + x)n � 1 + nx para todo x 2 R com x > �1. 44) Se n 2 N e n � 1, enta˜o 1 + 2 + 3 + 4 + · · ·+ n = n 2 + n 2 . 3.5. PRINCI´PIOS DE INDUC¸A˜O MATEMA´TICA 41 45) Para todo inteiro n � 1, 12 + 22 + 32 + · · ·+ n2 = n(n+ 1)(2n+ 1) 6 . 46) Para todo inteiro n 2 N, nX i=1 (8i� 5) = 4n2 � n. 47) Se n 2 N, enta˜o 1 · 3 + 2 · 4 + 3 · 5 + · · ·+ 4 · 6 + · · ·+ n(n+ 2) = n(n+ 1)(2n+ 7) 6 . 48) Se n 2 N, enta˜o 1 2! + 2 3! + · · ·+ n (n+ 1)! = 1� 1 (n+ 1)! 49) Para qualquer inteiro n � 0, prove que 9 | (43n + 8). 50) Prove que para todo nu´mero natural n, 2n + 1 3n. Observac¸a˜o: Nas demonstrac¸o˜es destes exercı´cios e´ va´lido citar qualquer resultado conhecido, desde que a demonstrac¸a˜o deste resultado na˜o seja equivalente a demonstrac¸a˜o do exercı´cio. Resposta dos Exercı´cios sobre Te´cnicas de Demonstrac¸a˜o 1) Como a | b e b | c, enta˜o existem r, s 2 Z tais que b = ra e c = sb. Assim, c = sb = s(ra) = (sr)a com sr 2 Z. Logo a | c. 2) Como x e´ par, enta˜o existe k 2 Z tal que x = 2k. Assim, x2 � 6x+ 5 = (2k)2 � 6 · (2k) + 5 = 4k2 � 12k + 5 = 2(2k2 � 6k + 2) + 1, com 2k2 � 6k + 2 2 Z. Logo x2 � 6x+ 5 e´ ı´mpar. 42 CAPI´TULO 3. TE´CNICAS DE DEMONSTRAC¸A˜O 3) Sejam d1 = mmc(a, b) e d2 = mmc(ac, bc). Se d1 = mmc(a, b), enta˜o a | d1 e b | d1 ) ac | cd1 e bc | cd1 ) d2 | cd1 Se d2 = mmc(ac, bc), enta˜o ac | d2 e bc | d2 ) d2 = kc, ac | kc e bc | kc ) d2 = kc, a | k e b | k ) d2 = kc e d1 | k ) cd1 | kc ) cd1 | d2 Logo, como d2 | cd1 e cd1 | d2, enta˜o d2 = cd1, ou seja, mmc(ac, bc) = cmmc(a, b). 4) Como p x+ p y > 0, enta˜o 1py+px > 0. Ale´m disso, como x y, enta˜o y � x � 0. Logo, py � px = ( p y�px)(py+px) ( p y+ p x) = 1p y+ p x · (y � x) � 0, o que implica emp x < p y. 10) Como a | b e a | c, enta˜o existem k1, k2 2 Z tais que b = k1a e c = k2a, o que implica em b+ c = (k1 + k2)a com k1 + k2 2 Z. Logo a | (b+ c). Capı´tulo 4 Relac¸o˜es e Func¸o˜es Definic¸a˜o 33. Sejam A e B conjuntos. Uma relac¸a˜o R de A em B e´ um subconjunto do produto cartesiano de A por B, A⇥ B = {(a, b) | a 2 A, b 2 B}. Exemplo 38. Se A = {1; 2} e B = {1; 3; 5}, enta˜o A⇥ B = {(1; 1); (1; 3); (1; 5); (2; 1); (2; 3); (2; 5)} e teremos 2n(A⇥B) = 26 = 64 relac¸o˜es deA emB.Uma destas relac¸o˜es e´R = {(1; 3); (2; 5); (2; 3)}. Relac¸o˜es sobre um conjunto Definic¸a˜o 34. Uma relac¸a˜o R sobre A e´ uma relac¸a˜o de um conjunto A em A. Definic¸a˜o 35. Seja R uma relac¸a˜o sobre A. (1) Se (8a 2 A) ((a, a) 2 R) , enta˜o R e´ chamada de relac¸a˜o reflexiva. (2) Se (a, b) 2 R implicar em (b, a) 2 R para todos a, b 2 A, enta˜o R e´ chamada de relac¸a˜o sime´trica. (3) Se (a, b) 2 R e (b, c) 2 R implicarem em (a, c) 2 R para todo a, b, c 2 A, enta˜o R e´ chamada de relac¸a˜o transitiva. (4) Se (a, b) 2 R e (b, a) 2R implicarem em a = b, enta˜o R e´ chamada de relac¸a˜o anti-sime´trica. (5) Uma relac¸a˜o R e´ uma relac¸a˜o de equivaleˆncia, se R satisfaz as propriedades (1), (2) e (3), ou seja, se R e´ reflexiva, sime´trica e transitiva. 43 44 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES 5 7 3 1 77ooooooooooooooooooooooooooooo 2 SS'''''''''''''''''''''''''' ??���������������� Figura 4.1: R(A) (6) Uma relac¸a˜o R e´ uma relac¸a˜o de ordem parcial, se R satisfaz as propriedades (1), (3) e (4), ou seja, se R e´ reflexiva, anti-sime´trica e transitiva. Se A e B sa˜o conjuntos finitos, enta˜o toda relac¸a˜o R de A em B pode ser representada por um grafo direcionado cujos ve´rtices sa˜o os pontos de A e de B e cujas arestas sa˜o representadas por pares (a, b) 2 R que representa uma aresta orientada de a para b. Exemplo 39. Se A = {1; 2} e B = {3; 5; 7}, enta˜o a relac¸a˜o R de A em B definida por R = {(1; 3); (2; 5); (2; 3)} pode ser representada graficamente pelo grafo da figura 3.1. Definic¸a˜o 36. Um ciclo e´ uma aresta que conecta um ve´rtice nele mesmo. Observac¸a˜o 7. Graficamente: • Uma relac¸a˜o R sobre A e´ reflexiva se existem ciclos em cada elemento de A; • Uma relac¸a˜o R sobre A e´ sime´trica se na˜o existem setas simples ligando elementos de A; • Uma relac¸a˜o R sobre A e´ transitiva se para todo caminho ligando dois pontos a e b de A, existe uma seta ligando a e b; • Uma relac¸a˜oR sobreA e´ anti-sime´trica se na˜o existem setas duplas ligando elemen- tos de A. Exemplo 40. Se R = {(a, b) 2 N ⇥ N | a | b}, enta˜o R e´ uma relac¸a˜o de ordem parcial sobre N. De fato, 45 (i) Se a 2 A, enta˜o a = 1 · a, i.e., a e´ mu´ltiplo de a. Logo (a, a) 2 R. Portanto R e´ reflexiva. (ii) Sejam a, b, c 2 A tais que (a, b), (b, c) 2 R. Assim b e´ mu´ltiplo de a e c e´ mu´ltiplo de b. Logo existem r, s 2 Z tais que b = ra e c = sb. Portanto c = rb = s(ra) = (sr)a, onde sr 2 Z, ou seja, c e´ mu´ltiplo de a. Consequentemente, (a, c) 2 R. Logo (8a, b, c 2 A) (((a, b), (b, c) 2 R)) ((a, c) 2 R)) . Portanto, R e´ transitiva. Simbolicamente, se a, b, c 2 N, ((a, b) 2 R e (b, c) 2 R) ) (b e´ mu´ltiplo de a e c e´ mu´ltiplo de b) ) (9r, s 2 Z) (b = ra e c = sb) ) (9r, s 2 Z) (c = sb = s(ra) = (sr)a) t=sr) (9t 2 Z) (c = ta) ) (c e´ mu´ltiplo de a) ) ((a, c) 2 R) Logo R e´ transitiva. (iii) Sejam a, b 2 N tais que (a, b) 2 R e (b, a) 2 R, enta˜o existem r, s 2 Z tais que b = ra e a = rb. Assim, b = ra = r(sb) ) b(1 � rs) = 0 ) 1 � rs = 0 ) rs = 1 ) r = s = ±1 a,b>0) r = s = 1. Logo b = a. Portanto, R e´ anti-sime´trica. Logo, por (i), (ii) e (iii), R e´ uma relac¸a˜o de ordem parcial sobre A. Exemplo 41. Seja A um conjunto. Se R = {(B,C) 2 P (A) ⇥ P (A) | B ⇢ C}, enta˜o R e´ uma relac¸a˜o de ordem parcial sobre P (A). De fato, (i) Como B ⇢ B para todo B ⇢ A, enta˜o (B,B) 2 R para todo B 2 P (A). Logo R e´ reflexiva. (ii) Sejam B,C 2 P (A), tais que (B,C) 2 R e (C,B) 2 R. Assim, B ⇢ C e C ⇢ B, o que implica em B = C. Logo R e´ anti-sime´trica. (iii) Sejam B,C,D 2 P (A) tais que (B,C) 2 R e (C,D) 2 R, enta˜o B ⇢ C e C ⇢ D, o que implica em B ⇢ D. Assim, (B,D) 2 R. Logo R e´ transitiva. 46 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES ComoR e´ reflexiva, anti-sime´trica e transitiva, enta˜oR e´ uma relac¸a˜o de ordem parcial sobre P (A). Exemplo 42. Sejam A e B conjuntos disjuntos e R uma relac¸a˜o de ordem sobre A [ B definida por R = {(a, b) 2 (A [ B)⇥ (A [B) | {a, b} ⇢ A ou {a, b} ⇢ B}, enta˜o R e´ uma relac¸a˜o de equivaleˆncia sobre A [B. De fato, como (1) Se a 2 A [ B, enta˜o {a, a} ⇢ A ou {a, a} ⇢ B. Logo (a, a) 2 R. Portanto R e´ reflexiva. (2) Se (a, b) 2 R, enta˜o {a, b} ⇢ A ou {a, b} ⇢ B. Logo {b, a} ⇢ A ou {b, a} ⇢ B, o que implica em (b, a) 2 R. Portanto R e´ sime´trica. (3) Se (a, b) 2 R e (b, c) 2 R, enta˜o {a, b} ⇢ A ou {a, b} ⇢ B e {b, c} ⇢ A ou {b, c} ⇢ B. Como A \ B = ?, enta˜o {a, b} ⇢ A e {b, c} ⇢ A ou {a, b} ⇢ B e {b, c} ⇢ B. Logo {a, c} ⇢ A ou {a, c} ⇢ B, o que implica em (a, c) 2 R. Portanto, R e´ transitiva Logo, por (1), (2) e (3), R e´ uma relac¸a˜o de equivaleˆncia. Definic¸a˜o 37. Dizemos que R⇤ e´ o fecho de uma relac¸a˜o R por uma propriedade P se R⇤ e´ a menor relac¸a˜o que conte´m R e que satisfaz a propriedade P, ou seja, se (i) R⇤ satisfaz a propriedade P ; (ii) R ⇢ R⇤; (iii) Se S satisfaz a propriedade P e R ⇢ S, enta˜o R⇤ ⇢ S. Exemplo 43. Encontre os fechos reflexivo, sime´trico e transitivo deR = {(1; 2); (2; 1); (1; 3)} sobre S = {1; 2; 3}. O fecho reflexivo de R sobre S e´ R⇤ = {(1; 2); (2; 1); (1; 3); (1; 1); (2; 2); (3; 3)} 47 O fecho sime´trico de R sobre S e´ R⇤ = {(1; 2); (2; 1); (1; 3); (3; 1)} O fecho transitivo de R sobre S e´ R⇤ = {(1; 2); (2; 1); (1; 3); (1; 1); (2; 3); (2; 2)} Definic¸a˜o 38. Se R e´ uma relac¸a˜o de equivaleˆncia sobre um conjunto A, enta˜o, para cada x 2 A podemos definir uma classe de equivaleˆncia para esta relac¸a˜o R como sendo o conjunto [x] = {a 2 A | (a, x) 2 R} Notac¸a˜o 1. O conjunto das classes de equivaleˆncia de uma relac¸a˜o R sobre um conjunto A e´ representado pelo sı´mbolo A/R. Lista de Exercı´cios sobre Relac¸o˜es (1) Mostre que a relac¸a˜o R definida por R = {(a, b) 2 Z⇥ Z | a ⌘ b mod 5} e´ uma relac¸a˜o de equivaleˆncia e encontre Z/R. (2) Seja Y = {0, 1} eM o conjunto de todas as palavras de comprimento finito formada a partir de 0 e 1.Mostre que a relac¸a˜o R definida por R = {(a, b) 2M ⇥M | a e´ prefixo de b} e´ uma relac¸a˜o de ordem parcial. Obs: Dizemos que a e´ prefixo de b se existe c 2M tal que b = ac. (3) Seja X = {0; 1; 2; 3; 4}. Mostre que a relac¸a˜o R sobre P (X) definida por R = {(A,B) 2 P (X)⇥ P (X) | n(A) = n(B)} e´ uma relac¸a˜o de equivaleˆncia e encontre P (X)/R. (4) Encontre todas as relac¸o˜es de equivaleˆncia sobre A = {1; 2; 3}. (5) Encontre todas as relac¸o˜es de ordem sobre A = {1; 2; 3}. 48 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES (6) Construir sobre o conjunto E = {a, b, c, d} relac¸o˜es R1, R2, R3 e R4 tais que R1 so´ tem a propriedade reflexiva, R2 so´ a sime´trica, R3 so´ a transitiva e R4 so´ a anti- sime´trica. (7) Seja A = {x 2 Z | |x| 5} a relac¸a˜o definida por (x, y) 2 R, x2+2x = y2+2y. Mostre que R e´ uma relac¸a˜o de equivaleˆncia. (8) Sejam E = {�3,�2,�1, 0, 1, 2, 3} e R = {(x, y) 2 E ⇥ E | x + |x| = y + |y|}. Mostre que R e´ uma relac¸a˜o de equivaleˆncia e encontre E/R. (9) SejaR a relac¸a˜o sobreQ definida da forma seguinte (x, y) 2 R, x�y 2 Z. Provar que R e´ uma relac¸a˜o de equivaleˆncia. (10) Seja R = {(x, y) 2 R2 | x� y 2 Q}. Provar que R e´ uma relac¸a˜o de equivaleˆncia. 4.1 Func¸o˜es Definic¸a˜o 39. Uma func¸a˜o f de A em B e´ uma relac¸a˜o que associa a cada elemento x do conjunto A um u´nico elemento y do conjunto B. Como este elemento y 2 B e´ u´nico para cada x 2 A, enta˜o e´ comum representarmos este elemento por f(x), ou seja, y = f(x). Notac¸a˜o 2. Usamos o sı´mbolo f : A! B para representarmos que f e´ uma func¸a˜o de A em B. Definic¸a˜o 40. Seja f : A! B, enta˜o • O domı´nio de f e´ o conjunto Dom(f) = A • O contradomı´nio de f e´ o conjunto CDom(f) = B • A imagem de f e´ o conjunto Im(f) = {y 2 B | y = f(x) para algum x 2 A} Definic¸a˜o 41. Func¸o˜es reais sa˜o func¸o˜es f : A! B, onde A ⇢ R e B = R. 4.1. FUNC¸O˜ES 49 Quando precisamos encontrar o domı´nio de uma func¸a˜o real f dada por uma fo´rmula matema´tica significa que precisamos encontrar o maior subconjunto A de R de tal forma que fac¸a sentido definirmos f como sendo uma func¸a˜o de A em R. Exemplo 44. Encontre o domı´nio e a imagem da func¸a˜o real f(x) = x2. Neste caso, Dom(f) = R e Im(f) = R+. Exemplo 45. Encontre o domı´nio e a imagem de f(x) = p x� 1. Como na˜o existem raı´zes reais de nu´meros negativos, enta˜o x� 1 � 0) x � 1. Assim, Dom(f) = [1;+1[= {x 2R | x � 1} e Im(f) =]0;+1[= {y 2 R | y � 0}. Exemplo 46. Encontre o domı´nio e a imagem de f(x) = q 1+x 1�x . A condic¸a˜o de existeˆncia para que f seja uma func¸a˜o real e´ que 1+x 1�x � 0 1� x 6= 0 Como 1 + x � 0 e 1� x > 0) �1 x < 1 e 1 + x 0 e 1� x < 0 e´ possı´vel. Logo, Dom(f) = {x 2 R | �1 x < 1} e Im(f) = R+. Definic¸a˜o 42. Uma func¸a˜o f : A! B e´ sobrejetora ou sobrejetiva se Im(f) = B. Exemplo 47. Uma func¸a˜o f : R ! R⇤+ definida por f(x) = x2 e´ sobrejetora, pois Im(f) = R+ = CDom(f). Definic¸a˜o 43. Uma func¸a˜o f : A! B e´ injetora ou injetiva se (8x, y 2 A) (f(x) = f(y)) x = y) ou, equivalentemente, se (8x, y 2 A) (x 6= y ) f(x) 6= f(y)) 50 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES Exemplo 48. Uma func¸a˜o f : R! R definida por f(x) = 2x e´ injetora, pois (8a, b 2 R) �2a = 2b ) a = b� . Definic¸a˜o 44. Uma func¸a˜o f : A ! B e´ bijetora ou bijetiva se f for injetora e sobreje- tora. Exemplo 49. A func¸a˜o real f(x) = 2x+ 3 e´ bijetora, pois • f e´ injetora: (8a, b 2 R) (f(a) = f(b)) 2a+ 3 = 2b+ 3) 2a = 2b) a = b) e • f e´ sobrejetora: (8c 2 R) �f � c�32 � = 2 c�32 + 3 = c� 3 + 3 = c� . Logo f e´ bijetora. Definic¸a˜o 45. Sejam f : A ! B e g : C ! D func¸o˜es tais que B ⇢ C. A func¸a˜o composta de g e f e´ uma func¸a˜o g � f : A! D tal que (g � f)(x) = g(f(x)). Exemplo 50. Se f(x) = 1x e g(x) = p x, enta˜o (f � g)(x) = 1px . Definic¸a˜o 46. Seja f : A ! B uma func¸a˜o injetiva. A func¸a˜o inversa de f e´ uma func¸a˜o f�1 : Im(f)! A tal que f�1(y) = x) f(x) = y. Exemplo 51. Calcule f�1, onde f(x) = 2x� 5. Definic¸a˜o 47. Sejam f : A ! B e g : C ! B com C ✓ A. Dizemos que g e´ a restric¸a˜o de f ao conjunto C se g(x) = f(x), 8x 2 C. Notac¸a˜o 3. Utilizamos g = f |C quando g e´ a restric¸a˜o de f ao subconjunto C do domı´nio de f. Exemplo 52. Seja f : N! N definida por f(n) = (�1)n. Se S e´ o conjunto dos nu´meros pares, enta˜o g : S ! N definida por g(n) = 1 e´ uma restric¸a˜o de f ao subconjunto S de N. Definic¸a˜o 48. Sejam f : A! B e g : C ! D com A ✓ C e B ✓ D. Dizemos que g e´ um prolongamento (ou extensa˜o ) de f se f(x) = g(x), 8x 2 A. Exemplo 53. Se f : R � {1} ! R e g : R ! R sa˜o definidas por f(x) = x2�1x�1 e g(x) = x+ 1, enta˜o g e´ um prolongamento (ou extensa˜o) de f. 4.1. FUNC¸O˜ES 51 Lista de Exercı´cios sobre Func¸o˜es 1) Prove que se f : A! B e´ sobrejetora, enta˜o existe C ✓ A com f |C bijetora. 2) Prove que se f : A! B e´ bijetora, enta˜o a aplicac¸a˜o inversa f�1 : B ! A tambe´m e´ bijetora. 3) Prove que se f : A! B e´ injetora e B for finito, enta˜o A tambe´m e´ finito. 4) Prove que se f : A! B e´ sobrejetora e A for finito, enta˜o B tambe´m e´ finito. 5) Prove que se f : A! B e g : B ! C sa˜o aplicac¸o˜es injetoras, enta˜o g � f : A! C tambe´m e´ uma aplicac¸a˜o injetora. 6) Prove que se f : A! B e g : B ! C sa˜o aplicac¸o˜es sobrejetoras, enta˜o g �f : A! C tambe´m e´ uma aplicac¸a˜o injetora. 7) Prove que se f : A! B e g : B ! C sa˜o aplicac¸o˜es bijetoras, enta˜o g � f : A! C tambe´m e´ uma aplicac¸a˜o bijetora. 52 CAPI´TULO 4. RELAC¸O˜ES E FUNC¸O˜ES Capı´tulo 5 Ana´lise Combinato´ria 5.1 Princı´pio das Casas de Pombo Definic¸a˜o 49 (Princı´pio das Casas de Pombo). Se mais de k itens sa˜o colocados em k caixas, enta˜o pelo menos uma caixa conte´m mais de um item. Exemplo 54. Quantas pessoas precisam estar presentes em uma sala para garantir que duas delas tenham o u´ltimo nome comec¸ando com a mesma letra? Exemplo 55. Prove que, se quatro nu´meros forem escolhidos do conjunto {1, 2, 3, 4, 5, 6}, pelo menos um par tem que somar 7. Exemplo 56. Quantas pessoas devera˜o estudar numa escola para garantir que pelo menos 2 destas pessoas tenham nascido: • no mesmo meˆs? • no mesmo dia da semana? • no mesmo meˆs e no mesmo dia da semana? • no mesmo meˆs e no mesmo dia? • no mesmo dia e no mesmo dia da semana? • no mesmo meˆs, no mesmo dia da semana e no mesmo dia? 53 54 CAPI´TULO 5. ANA´LISE COMBINATO´RIA 5.2 Princı´pio Fundamental da Contagem 5.2.1 Princı´pio da Multiplicac¸a˜o Se uma decisa˜o d1 pode ser tomada de x maneiras e se, uma vez tomada a decisa˜o d1, a decisa˜o d2 puder ser tomada em y maneiras enta˜o o nu´mero de maneiras de se tomarem as deciso˜es d1 e d2 e´ xy. 5.2.2 Princı´pio da Soma Se uma decisa˜o d1 pode ser tomada de x maneiras e uma decisa˜o d2 pode ser tomada de y maneiras e estas deciso˜es sa˜o tomadas de forma independente (disjuntas), enta˜o o nu´mero de maneiras distintas de se tomarem as deciso˜es d1 ou d2 e´ x+ y. Exemplo 57. Numa sala ha´ 3 homens e 4 mulheres. De quantos modos e´ possı´vel selecio- nar um casal homem-mulher? Resposta: 3|{z} homens · 4|{z} mulheres = 12. Exemplo 58. Para fazer uma viagem Rio-Sa˜o Paulo-Rio, posso usar como transporte o trem, o oˆnibus ou o avia˜o. De quantos modos posso escolher os transportes se na˜o desejo usar na volta o mesmo meio de transporte usado na ida? Resposta: 3|{z} ida · 2|{z} volta = 6. Exemplo 59. As placas dos automo´veis sa˜o formadas por duas letras (num alfabeto de 26 letras) seguidas por quatro algarismos. Quantas placas podem ser formadas? Resposta: 26| {z } 1a letra · 26| {z } 2a letra · 10| {z } 1oalgarismo · 10| {z } 2oalgarismo · 10| {z } 3oalgarismo · 10| {z } 4oalgarismo = 6 760 000. Exemplo 60. De quantos modos 3 pessoas podem sentar-se em 5 cadeiras em fila? Resposta: 5| {z } 1a pessoa · 4| {z } 2a pessoa · 3| {z } 3apessoa = 60. Exemplo 61. Quantos nu´meros diferentes podem ser formados multiplicando alguns (ou todos) dos nu´meros 1, 5, 6, 7, 7, 9, 9, 9? 5.2. PRINCI´PIO FUNDAMENTAL DA CONTAGEM 55 Resposta: Os nu´meros formados multiplicando alguns (ou todos) dos nu´meros 1, 5, 6, 7, 7, 9, 9, 9 teˆm a forma n = 5m1 · 6m2 · 7m3 · 9m4 , ondem1 2 {0, 1},m2 2 {0, 1},m3 2 {0, 1, 2} em4 2 {0, 1, 2, 3}. Logo, 2| {z } m1 · 2| {z } m2 · 3| {z } m4 · 4| {z } m5 = 48. Exemplo 62. A selec¸a˜o brasileira de futebol ira´ disputar um torneio internacional com outras cinco selec¸o˜es, no sistema “todos jogam contra todos uma u´nica vez”. Quais as possı´veis sequeˆncias de resultados – vito´ria (V), empate (E) e derrota (D) – da equipe brasileira nesse torneio? Exemplo 63. No primeiro semestre de 2012 sera˜o oferecidas quatro turmas de Ca´lculo I, treˆs turmas de Geometria Analı´tica, duas turmas de Fundamentos de Matema´tica Elemen- tar e apenas uma turma de Introduc¸a˜o a` Lo´gica Matema´tica. Sabendo-se que um calouro aprovado para o curso de Matema´tica devera´ cursar todas as disciplinas acima mencio- nadas, de quantas maneiras distintas ele podera´ se matricular nas mesmas, levando-se em considerac¸a˜o que as turmas de uma mesma disciplina sa˜o oferecidas num mesmo hora´rio e na˜o existe coincideˆncia de hora´rios entre as disciplinas? Exemplo 64. (a) Quantos nu´meros de cinco algarismos existem? (b) Quantos nu´meros ı´mpares de cinco algarismos existem? (c) Quantos nu´meros pares de cinco algarismos distintos existem? Exemplo 65. Um dado foi lanc¸ado n vezes sucessivamente. Sabendo-se que o nu´mero de sequeˆncias de faces possı´veis de se obter e´ 368, qual e´ o valor de n? Exemplo 66. Para os ho´spedes que desejam tomar cafe´ da manha˜ no quarto, um hotel oferece as seguintes opc¸o˜es: • bebidas quentes: chocolate, cafe´ puro, cha´ e cafe´ com leite. • sucos: laranja e abacaxi. • pa˜es: croissant, pa˜o franceˆs, pa˜o de foˆrma e pa˜o integral. 56 CAPI´TULO 5. ANA´LISE COMBINATO´RIA • queijo: branco, mussarela e queijo prato. O ho´spede X fez a seguinte solicitac¸a˜o: um suco, um pa˜o e um tipo de queijo. O ho´spede Y pediu: uma bebida quente ou um suco, um pa˜o e um tipo de queijo. De quantas formas distintas cada ho´spedepodera´ ser servido? Exemplo 67. Num hospital existem 3 portas de entrada que da˜o para um amplo sagua˜o no qual existem 5 elevadores. Um visitante deve se dirigir ao 6o ¯ andar, utilizando-se de um dos elevadores. De quantas maneiras diferentes podera´ fazeˆ-lo? Exemplo 68. Numa eleic¸a˜o de uma escola ha´ treˆs candidatos a presidente, cinco a vice- presidente, seis a secreta´rio e sete a tesoureiro. Quantos podem ser os resultados da eleic¸a˜o? 5.3 Outros Me´todos de Contagem Exemplo 69. Dois preˆmios sa˜o sorteados entre 10 pessoas. Quantos sera˜o os possı´veis resultados, sabendo que uma pessoa na˜o pode ser sorteada mais de uma vez? 5.4 Caso sem te´cnica conhecida Caso sem te´cnica conhecida Quero retirar 100 reais de um caixa eletroˆnico que dispo˜e de notas de 5 e 10 reais. Quantas sera˜o as possibilidades para este saque? 5.5 Fatorial Fatorial de um nu´mero natural O Fatorial de um nu´mero natural n e´ definido matema´ticamente por n! = 8<: 1 se n = 0n(n� 1)! se n 2 N⇤ Exercı´cio 2. Calcule o valor de: 5.6. AGRUPAMENTOS 57 a) 7! 5! · 2! d) 15! · 4! 13! · 3! b) 8! · 6! 7! · 7! e) 21!� 3 · 20! 19! c) 17!� 17 · 16! Exercı´cio 3. Resolva as seguintes equac¸o˜es: (a) n! (n� 1)! = 4 (b) (n� 1)!(n+ 1)! (n!)2 = 5 4 (c) (n!)2 � 100n! = 2400 5.6 Agrupamentos Tipos de Agrupamentos Existem treˆs tipos de Agrupamentos de k elementos distintos escolhidos entre n disponı´veis que podem ser obtidos a partir do Princı´pio Fundamental da Contagem: (a) Arranjos (a ordem importa); (b) Permutac¸o˜es (arranjos, onde k=n); (c) Combinac¸o˜es (a ordem na˜o importa). 5.6.1 Arranjos Arranjos Definic¸a˜o 50. Dado um conjunto com n elementos distintos, chama-se arranjo dos n ele- mentos, tomados k a k, a qualquer sequeˆncia ordenada de k elementos distintos escolhidos entre os n existentes. Obtenc¸a˜o da Fo´rmula: Pelo PFC: | {z } n modos | {z } (n�1) modos | {z } (n�2) modos · · · | {z } (n�k+1) modos 58 CAPI´TULO 5. ANA´LISE COMBINATO´RIA Logo, An,k = n! (n� k)! Exemplos Exemplo 70. Para ocupar os cargos de presidente e vice-presidente do greˆmio de um cole´gio, candidataram-se dez alunos. De quantos modos distintos pode ser feita essa es- colha? Exemplo 71. A senha de acesso a uma rede de computadores e´ formada por uma sequeˆncia de quatro letras distintas (alfabeto com 26 letras) seguida por dois algarismos distintos. (a) Quantas sa˜o as possı´veis senhas de acesso? (b) Quantas senhas apresentam simultaneamente apenas consoantes e algarismos mai- ores que 5? Exemplo 72. Sabe-se que as cinco pessoas de uma famı´lia (pai, ma˜e e treˆs filhos) nasceram emmeses diferentes do ano. Quantas sa˜o as sequeˆncias que representam os possı´veis meses de nascimento dos membros dessa famı´lia? Exemplo 73. Seis amigos participam de uma brincadeira de futebol, que consiste em cobranc¸a de peˆnaltis. Cada um escolhe, de todas as formas possı´veis, um colega para bater o peˆnalti e um outro para tentar defendeˆ-lo. (a) Quantas cobranc¸as de peˆnalti sa˜o feitas nessa brincadeira? (b) Quantas cobranc¸as haveria se o grupo resolvesse convidar um se´timo amigo para que ele escolhesse, de todas as formas possı´veis, o cobrador e o defensor do peˆnalti? 5.6.2 Permutac¸o˜es Permutac¸o˜es Definic¸a˜o 51. Quando uma sequeˆncia ordenada (arranjo) e´ formada por todos os elemen- tos disponı´veis, dizemos que se trata de uma permutac¸a˜o. Assim, o nu´mero de permutac¸o˜es Pn de n elementos distintos e´ Pn = n! 5.6. AGRUPAMENTOS 59 Exemplo 74. Quais sa˜o os anagramas formados a partir da palavra SAPO? AOPS AOSP APOS APSO ASOP ASPO OAPS OASP OPAS OPSA OSAP OSPA PAOS PASO POAS POSA PSAO PSOA SAOP SAPO SOAP SOPA SPAO SPOA Sa˜o p4 = 4! = 4 · 3 · 2 · 1 = 24 anagramas. Exemplo 75. Jose´ e Maria teˆm treˆs filhos: Thiago, Pedro e Andre´. A famı´lia quer tirar uma foto de recordac¸a˜o de uma viagem na qual todos aparec¸am lado a lado. (a) De quantas formas distintas os membros da famı´lia podem se distribuir? (b) Em quantas possibilidades o casal aparece junto? Exemplo 76. Considere os anagramas formados a partir de CONQUISTA. (a) Quantos sa˜o? (b) Quantos comec¸am por vogal? (c) Quantos comec¸am e terminam por consoante? (d) Quantos teˆm as letras CON juntas e nessa ordem? (e) Quantos apresentam a letra C antes da letra A? Exemplo 77. Dona Lola tem treˆs filhos: Pedro, Paulo e Andre´. Os treˆs casaram-se e teˆm, respectivamente, 1, 3 e 2 filhos. Em um domingo, dona Lola recebeu, para o almoc¸o, seus treˆs filhos, acompanhados das respectivas esposas, ale´m de todos os netos. Como recordac¸a˜o, ela fotografou todos os familiares, lado a lado, mas pediu que cada filho aparecesse junto de sua famı´lia. De quantas formas distintas a foto poderia ter sido feita? Exemplo 78. Se colocarmos em ordem crescente todos os nu´meros de 5 algarismos distin- tos, obtidos com 1, 3, 4, 6 e 7, qual sera´ a posic¸a˜o do nu´mero 61473 ? 60 CAPI´TULO 5. ANA´LISE COMBINATO´RIA 5.6.3 Combinac¸o˜es Definic¸a˜o 52. Dado um conjunto A com n elementos distintos, chama-se combinac¸a˜o dos n elementos de A, tomados k a k, qualquer subconjunto de A formado por k elementos. Fo´rmula para o Ca´lculo do nu´mero de Combinac¸o˜es Cn,k = An,k k! = n! (n� k)!k! = ✓ n k ◆ Exemplo 79. Quantas saladas contendo exatamente 4 frutas podemos formar se dispomos de 10 frutas diferentes? Exemplo 80. Marcam-se 5 pontos sobre uma reta r e 8 pontos sobre uma reta r0 paralela a r. Quantos triaˆngulos existem com ve´rtices em 3 desses 13 pontos. Exemplo 81. De quantos modos podemos escolher 6 pessoas, incluindo pelo menos duas mulheres, em um grupo de 7 homens e 4 mulheres? Exemplo 82. De um grupo de 5 pessoas, de quantas maneiras distintas posso convidar uma ou mais para jantar? Exemplo 83. Quantos subconjuntos de 2 elementos tem um conjunto de 6 elementos? Exemplo 84. Quantas diagonais possui um polı´gono de n lados? Exemplo 85. Sobre uma circunfereˆncia marcam-se dez pontos. (a) Qual e´ o nu´mero de segmentos de reta que podemos trac¸ar com extremidades em dois desses pontos? (b) Quantos triaˆngulos podemos construir com ve´rtices em treˆs desses pontos? (c) Quantos polı´gonos com 4, 5, 6 ou 7 lados podem ser trac¸ados com ve´rtices nesses pontos? Exemplo 86. Em um curso de espanhol estudam vinte alunos, sendo dozes rapazes e oito moc¸as. O professor quer formar uma equipe de quatro alunos para intercaˆmbio em outro paı´s. Quantas equipes de dois rapazes e duas moc¸as podem ser formadas? Exemplo 87. Para montar uma cesta de cafe´ da manha˜ esta˜o disponı´veis os seguintes itens: quatro tipos de pa˜es, treˆs tipos de queijo, treˆs tipos de frutas, cinco sabores de gele´ia e quatro sabores de tortas doces. De quantos modos distintos a ceta podera´ ser montada se um cliente pedir dois tipos de pa˜es, um tipo de queijo, duas frutas, dois sabores de gele´ia e um torta doce? 5.6. AGRUPAMENTOS 61 5.6.4 Permutac¸o˜es com repetic¸a˜o Permutac¸o˜es com repetic¸a˜o Definic¸a˜o 53. Nos casos em que cada resultado possı´vel e´ uma sequeˆncia ordenada, nos quais ocorre repetic¸a˜o de elementos, dizemos que se trata de permutac¸a˜o com repetic¸a˜o. Fo´rmula Geral Se temos n elementos, dos quais • n1 sa˜o iguais a a1, • n2 sa˜o iguais a a2, • n3 sa˜o iguais a a3, ... • nk sa˜o iguais a ak, enta˜o o nu´mero de permutac¸o˜es possı´veis e´ dado por p(n1,n2,··· ,nk)n = n! n1!n2! · · ·nk! Exemplo 88. Qual e´ o nu´mero de anagramas formados a partir da palavra VENEZUELA? Exemplo 89. Qual e´ o nu´mero de anagramas da palavra MARROCOS? Exemplo 90. Permutando os algarismos 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, quantos nu´merosde 10 algarismos podemos formar? Exemplo 91. Uma prova e´ constituı´da de dez testes do tipo V ou F. (a) Quantas sequeˆncias de respostas sa˜o possı´veis? (b) Quantas sequeˆncias apresentam treˆs respostas V e sete respostas F? Exemplo 92. Quantos nu´meros de 7 dı´gitos, maiores que 6 000 000, podem ser formados usando apenas os algarismos 1, 3, 6, 6, 6, 8, 8 ? 62 CAPI´TULO 5. ANA´LISE COMBINATO´RIA Capı´tulo 6 Introduc¸a˜o a` Teoria dos Nu´meros Princı´pio da Boa Ordem: Todo subconjunto na˜o vazio do conjunto dos nu´meros inteiros constituı´do de elementos na˜o negativos possui um mı´nimo. Proposic¸a˜o 1 (Algorı´tmo de Euclides). Sejam a, b 2 Z, b 6= 0, enta˜o existe um u´nico par (q, r) 2 Z⇥ Z tal que a = bq + r, 0 r < |b|. Demonstrac¸a˜o. (Existeˆncia) Seja A = {a � bq 2 Z | a � bq 0, q 2 Z}, enta˜o A 6= ?, pois a� b · 0 = a > 0, ou seja, a 2 A. Portanto, pelo Princı´pio da Boa Ordem, como A 6= ? e A e´ constituı´do de nu´meros inteiros na˜o negativos, enta˜o existe r0 = minA. Assim, existe q0 2 Z tal que r0 = a� bq0. Afirmac¸a˜o: 0 r0 < |b|. De fato, se r0 � |b|, enta˜o existiria m � 0 tal que r0 = |b| +m e, como 0 m < r0 e r0 = |b|+m = a� bq0, terı´amos que m = a� bq � |b| = 8<: a� b(q + 1), se b > 0a� b(q � 1), se b < 0 ou seja, 0 m < r0 em 2 A, o que e´ um absurdo, pois r0 = minA. Logo 0 r0 < b. Portanto, tomando q = q0 e r = r0, temos que (q, r) satisfaz a = bq + r e 0 r < b. (Unicidade) Sejam (q1, r1), (q2, r2) 2 Z⇥ Z tais que a = bq1 + r, 0 r1 < b e a = bq2 + r2, 0 r2 < b. 63 64 CAPI´TULO 6. INTRODUC¸A˜O A` TEORIA DOS NU´MEROS Assim, bq1 + r1 = bq2 + r2 ) b(q1 � q2) = r2 � r1 ) |b||q1 � q2| = |r2 � r1| < |b| ) |q1 � q2| < 1 ) |q1 � q2| = 0 ) q1 = q2 ) 8<: q1 = q2r2 � r1 = b(q1 � q2) = 0 ) 8<: q1 = q2r1 = r2 ) (q1, r1) = (q2, r2) Exemplo 93. Para encontrarmos (q, r) 2 Z⇥ Z satisfazendo a = bq + r, com 0 r < b, onde a = 45 e b = 56, basta escolhermos q = 0 e r = a = 45. Desta forma, obtemos que a = 45 = 56 · 0 + 45 = bq + r, com 0 r = 45 < 56 = b. Definic¸a˜o 54. Dizemos que um nu´mero inteiro a e´ um divisor de um nu´mero inteiro b se existe z 2 Z tal que b = za. Neste caso, dizemos que b e´ divisı´vel por a ou que b e´ mu´ltiplo de a. Notac¸a˜o 4. a | b significara´ que a e´ um divisor de b ou b e´ mu´ltiplo de a. Proposic¸a˜o 2 (Propriedades). Seja A = Z⇤+, enta˜o a relac¸a˜o R = {(a, b) 2 A⇥ A | a | b} e´ uma relac¸a˜o de ordem parcial sobre Z⇤+, ou seja, (i) (8a 2 A) (a | a) (Reflexiva) (ii) (8a, b, c 2 Z) (a | b e b | c) a | c) (Transitiva) (iii) (8a, b 2 A) (a | b e b | a) a = b) (Anti-sime´trica) Demonstrac¸a˜o. (i) Como a = 1 · a, 8a 2 A, enta˜o a | a, 8a 2 A. (ii) Se a | b e b | c, enta˜o existem z1, z2 2 Z tais que b = z1a e c = z2b, o que implica em c = z2(z1a) = (z2z1)a. Logo a | c. 65 (iii) Para a, b 2 R⇤+, temos que (a | b e b | a) ) (9z1, z2 2 Z) (b = z1a e a = z2b) ) (9z1, z2 2 Z) (b = z1a e a = z2(z1a)) ) (9z1, z2 2 Z) (b = z1a e a = (z2z1)a) ) (9z1, z2 2 Z) (b = z1a e 1 = z2z1) a,b2Z⇤+) (9z1, z2 2 Z) (b = z1a e z1 = z2 = 1) ) (a = b) Observac¸a˜o 8. As propriedades (i) e (ii) valem tambe´m para A = Z. Definic¸a˜o 55. Sejam a, b 2 Z. Dizemos que um nu´mero inteiro positivo d e´ o ma´ximo divisor comum de a e b se (i) d | a e d | b; (ii) Se d0 2 Z satisfaz d0 | a e d0 | b, enta˜o d0 | d. Notac¸a˜o 5. Utilizaremos o sı´mbolo mdc(a, b) ou (a, b) para representarmos o ma´ximo divisor comum de a e b (ou entre a e b). Exemplo 94. Vamos calcular agora o ma´ximo divisor comum entre 45 e 12. Para fazermos isto, observe primeiramente que • o conjunto dos divisores positivos de 45 e´ d(45) = {1, 3, 5, 9, 15, 45}; • o conjunto dos divisores positivos de 12 e´ d(12) = {1, 2, 3, 4, 6, 12}; • o conjunto dos divisores positivos de 12 e de 45 sa˜o d(45) \ d(12) = {1, 3}. Portanto, o ma´ximo divisor comum entre 45 e 12 sera´ o ma´ximo do conjunto d(45)\d(12), que e´ 3, ou seja, mdc(45, 12) = max d(45) \ d(12) = 3. Proposic¸a˜o 3. Se a, b 2 Z d um divisor de a e de b. Enta˜o d | (↵a+ �b), 8↵, � 2 Z. Demonstrac¸a˜o. Se d | a e d | b, enta˜o existem z1, z2 2 Z tais que a = z1d e b = z2d. Assim, ↵a+ �b = ↵(z1d) + �(z2d) = (↵z1 + �z2)d, com ↵z1 + �z2 2 Z. Logo d | (↵a+ �b). 66 CAPI´TULO 6. INTRODUC¸A˜O A` TEORIA DOS NU´MEROS Proposic¸a˜o 4. Sejam a, b 2 Z e A = {↵a + �b | ↵a + �b > 0,↵, � 2 Z}, enta˜o mdc(a, b) = minA. Demonstrac¸a˜o. Pelo Princı´pio da Boa Ordem, existem0 = minA. Como d = mdc(a, b) e´ tal que d0 | a e d0 | b, enta˜o, pela proposic¸a˜o anterior, d | (↵a+ �b), 8↵, � 2 Z. Comom0 2 A, existem ↵0, �0 2 Z tais quem0 = ↵0a+ �0b. Logo d | (↵0a+ �0b), o que implica em d | m0. Provaremos agora que m0 | a e m0 | b. De fato, pelo Algorı´tmo de Euclides, existem q, r 2 Z tais que (a = m0q + r, 0 r < m0) ) (a = (↵0a+ �0b)q + r, 0 r < m0) ) ((1� ↵0q)a+ (��0q)b = r, 0 r < m0) Logo r = 0, pois 0 r < m0 e m0 e´ o menor nu´mero inteiro positivo escrito na forma ↵a+ �b, com ↵, � 2 Z. Assim, a = m0q + r = m0q ) m0 | a. Da mesma forma podemos concluir quem0 | b. Comom0 | a em0 | b, enta˜om0 | d. Portanto, comom0 > 0 e d0 | m0 em0 | d0, enta˜o d = m0. Logo minA = mdc(a, b). Corola´rio 1. mdc(n, n+ 1) = 1, 8n 2 Z. Demonstrac¸a˜o. Como 1 = n+1�n = 1 · (n+1)+(�1) ·n e 1 e´ o menor nu´mero inteiro positivo, enta˜o, pela Proposic¸a˜o anterior, mdc(n, n+ 1) = 1. Corola´rio 2. Para todo inteiro n, mdc ✓ 2n+ 1, n(n+ 1) 2 ◆ = 1. Demonstrac¸a˜o. Basta observar que se ↵ = 2n+ 1 e � = �8, enta˜o ↵(2n+ 1) + � n(n+ 1) 2 = (2n+ 1)(2n+ 1) + (�8)n(n+ 1) 2 = 1. Definic¸a˜o 56. Um nu´mero inteiro p 6= ±1 e´ primo se os u´nicos divisores de p sa˜o ±1 e ±p. 67 Proposic¸a˜o 5. Seja p um nu´mero primo e sejam a, b 2 Z, tais que p | (ab), enta˜o p | a ou p | b. Demonstrac¸a˜o. Se p | a, enta˜o ja´ temos o que querı´amos. Se p - a, enta˜o mdc(a, p) = 1, pois os u´nicos divisores de p sa˜o ±p e ±1. Como mdc(p, a) = 1, enta˜o existem ↵, � 2 Z tais que ↵p+ �a = 1) b · 1 = b(↵p+ �a)) b = (↵b)p+ �(ab) Como p | (ab) e mdc(p, a) = 1, enta˜o existem z,↵, � 2 Z tais que ab = zp (6.1) e ↵p+ �a = 1 (6.2) Portanto, 1 = ↵p+ �a ) b · 1 = b(↵p+ �a) ) b = (b↵)p+ �(ab) (6.1)) b = (b↵)p+ �(zp) ) b = (b↵ + �z)p ) p | b Logo p | a ou p | b. Exercı´cio 4. Se c | (ab) e mdc(c, a) = 1, enta˜o c | b. Definic¸a˜o 57. Um nu´mero inteirom 62 {±1, 0} e´ um nu´mero composto sem na˜o e´ primo, ou seja, sem 6= 0 em possui mais de 4 divisores. Proposic¸a˜o 6. Seja m um nu´mero inteiro positivo maior ou igual a 2, enta˜o o menor elemento do conjunto (o mı´nimo) S = {x 2 Z | x > 1 e x | m} e´ um nu´mero primo. Demonstrac¸a˜o. Comom 2 S e S e´ constituı´do por nu´meros inteiros positivos, enta˜o, pelo Princı´pio da Boa Ordem, existe p = minS. Para provar que p e´ primo, suponhamos que p seja composto. Se p for composto, enta˜o existem inteiros z1, z2 > 1 tais que p = z1z2. Assim, como p | a e z2 | p, enta˜o z2 | a. Portanto, z2 2 S e z2 < p, o que contradiz a minimalidade de p. Logo p e´ primo. 68 CAPI´TULO 6. INTRODUC¸A˜O A` TEORIA DOS NU´MEROS Proposic¸a˜o 7 (Primeiro Princı´pio de Induc¸a˜o). Seja P (n) uma afirmac¸a˜o que depende de n 2 N = {0, 1, 2, · · · } que pode ser julgada como verdadeira ou falsa para cada n. Se (i) P (n0) e´ verdadeira para algum n0 2 N e (ii) (8n 2 N) (P (n) verdadeira ) P (n+ 1) verdadeira) , enta˜o P (n) e´ verdadeira para todo n 2 N tal que n � n0. Demonstrac¸a˜o. Seja S = {n 2 N | n > n0 e P (n) e´ falsa, }. Suponhamos que P (n) seja falsa para algum m > n0. Assim, S 6= ? e pelo Princı´pio da Boa Ordem, existe m0 = minS. Logo, m0 � 1 62 S e P (m0 � 1) e´ verdadeira. Se P (m0 � 1) e´ verdadeira, por (ii), P (m0) e´ verdadeira, o que e´ um absurdo. Portanto, na˜o existe P (m) falsa para
Compartilhar