Baixe o app para aproveitar ainda mais
Prévia do material em texto
Tema : Conjuntos Conceitos Diagramas de Venn e operações Número de elementos de um conjunto 1.1 Objetivos: Familiarizar-se com a linguagem de conjuntos. Melhorar o raciocínio lógico. 1.2Conjuntos Importância: Fornece uma linguagem e ferramentas básicas que nos ajudam no raciocínio tanto na vida cotidiana como na manipulação de outros tópicos matemáticos. Aula 1 : Conceitos Conteúdo: Introdução Noção intuitiva Notação Relação de pertinência Definição Descrição Formalização Conjunto vazio Relações entre conjuntos Conjunto de partes 1.3Conjuntos Encontrar a estrutura comum a: uma biblioteca. um rebanho de ovelhas; uma equipe de futebol; Introdução: 1.4Conjuntos: Conceitos uma equipe de futebol é constituída por um grupo de jogadores; Formação de estrutura comum: uma biblioteca está formada por uma coleção de livros. um rebanho de ovelhas é formado por uma reunião de ovelhas; 1.5Conjuntos: Conceitos / Introdução Formação de estrutura comum: um rebanho de ovelhas é formado por uma coleção de ovelhas; uma equipe de futebol é constituída por uma coleção de jogadores; uma biblioteca está formada por uma coleção de livros. 1.6Conjuntos: Conceitos / Introdução equipe de futebol rebanho de ovelhas biblioteca Estrutura comum: 1.7Conjuntos: Conceitos / Introdução está formada(o) por uma coleção de objetos. Um conjunto é uma coleção de objetos, chamados elementos. Noção intuitiva: 1.8Conjuntos: Conceitos é um conjunto de jogadores. os elementos são os jogadores os elementos são as ovelhas é um conjunto de ovelhas. os elementos são os livros é um conjunto de livros. Exemplos: uma equipe de futebol um rebanho de ovelhas uma biblioteca Invente um conjunto com 4 elementos considerando coisas e/ou pessoas do lugar em que você está agora. 1.9Conjuntos: Conceitos / Noção intuitiva Meu conjunto está formado pelo(a): monitor do computador teclado cadeira você mesmo . . . − 1.10Conjuntos: Conceitos / Noção intuitiva Letras maiúsculas são usadas para denotar conjuntos. Exemplo: seu conjunto pode chamar-se A e o meu B. Notação de conjuntos: 1.11Conjuntos: Conceitos Letras minúsculas são usadas para descrever os elementos de um conjunto. Exemplo: os elementos do meu conjunto B podem ser denominados por: m : monitor; t : teclado; c : cadeira; v : você. Descrição de um conjunto: O símbolo } indica o fim da descrição de um conjunto. O símbolo { indica o início da descrição de um conjunto. 1.12Conjuntos: Conceitos / Notação Exemplo: B = {m, t, c, v} Resumindo: Conjunto: letras maiúsculas Elementos de um conjunto: letras minúsculas Início do conjunto: { Fim do conjunto: } 1.13Conjuntos: Conceitos / Notação Noção intuitiva: O elemento t (teclado) está no conjunto B. O elemento r (relógio) não está em B. Relação de pertinência: Seja B = {m, t, c, v} 1.14Conjuntos: Conceitos Notação: x ∈ X Definição de pertinência: 1.15Conjuntos: Conceitos / Relação de pertinência x pertence a um conjunto X se x é um elemento de X. Exemplo: B = { m, t, c, v } t pertence a B , t ∈ B r não pertence a B, r ∉ B Exemplo importante: N = conjunto dos números naturais = { 1, 2, 3, ... } N - 10598 ∈ N - -1 ∉ N - 1/5 ∉ N - 2,5 ∉ N 1.16Conjuntos: Conceitos / Relação de pertinência Outro exemplo: C = conjunto das pessoas que são altas. Conclusão: esta coleção não está bem definida. 1.17Conjuntos: Conceitos / Relação de pertinência - Se você mede 1,50 metros, está claro que você não pertence a C. - Se você mede 1,75 metros, você está em C ou não? - Se você mede 1,95 metros, está claro que você pertence a C. Você pertence a C ? Modificação do exemplo: Você pertence a C ? Conclusão: esta coleção está bem definida. 1.18Conjuntos: Conceitos / Relação de pertinência C = conjunto das pessoas que têm mais de 1,75 metros. Um conjunto é uma coleção de objetos, chamados elementos. Isto é, SEMPRE podemos decidir quando um objeto está ou não no conjunto. BEM DEFINIDA Definição de conjunto: 1.19Conjuntos: Conceitos Um conjunto é uma coleção bem definida de objetos, chamados elementos. 1.20Conjuntos: Conceitos / Definição O conjunto de números naturais que são pares; O conjunto dos meses do ano que têm exatamente 30 dias; O conjunto dos meses do ano que têm pelo menos 30 dias. Exemplos: Representação explícita Descrição de um conjunto: 1.21Conjuntos: Conceitos Enumeração dos elementos do conjunto. Representação implícita Exemplo: C = conjunto das pessoas que têm mais de 1,75 metros de altura Indicação da propriedade que caracteriza os elementos. Exemplo: B = { m, t, c, v } = { 1, 2, 3, ... } N Representação implícita: C = conjunto das pessoas de altura maior que 1,75 metros. C está constituído por elementos (pessoas) x tal que a altura de x é maior que 1,75 metros. ou C = { x | altura de x > 1,75 metros } Levando a idéia da notação matemática: 1.22Conjuntos: Conceitos / Descrição C = { x | altura de x > 1,75 metros } Formalização: 1.23Conjuntos: Conceitos C está constituído por elementos (pessoas) x tal que a altura de x é maior que 1,75 metros. Propriedade que caracteriza os elementos de C: P(x) : a altura de x é maior que 1,75 metros. C = { x | P(x) } C está constituído pelos elementos x tal que verifica P(x) Outro exemplo: D = conjunto de números naturais maiores ou iguais a 5. Representação explícita: D = { 5, 6, 7, ...} Representação implícita: D = { x | x ∈ e x ≥ 5 } P(x) N 1.24Conjuntos: Conceitos / Formalização = conjunto dos números reais R = conjunto dos números racionais Q = conjunto dos números inteiros Z = {... -2, -1, 0, 1, 2, ...} Z = { 1, 2, 3, 4, 5, ...} N = conjunto dos números naturaisN 1.25Conjuntos: Conceitos / Formalização Notação de conjuntos conhecidos = { x | x = p/q , p, q ∈ , q ≠ 0 } Q Z O conjunto vazio, ∅ , é o conjunto que não tem elementos. Conjunto especial: 1.26Conjuntos: Conceitos Exemplos: Pode-se falar da representação de ∅ ? ∅ = { x | x ∈ , x > 5 e x < 0 } N ∅ = { x | x ∈ , 2x - 1 = 0 } Z Definição de igualdade Os conjuntos A e B são iguais quando têm os mesmos elementos. Notação: A = B Relações entre conjuntos: 1.27Conjuntos: Conceitos Sejam A = { 1, 3, a } C = { 1, 3, 1, a } B = { 3, a, 1 } D = { 2, 3, a } Exemplo: Os conjuntos A, B e C são iguais, A = B = C A é diferente de D, A ≠ D Definição de inclusão Notação: A ⊆ B Um conjunto A está contido em um conjunto B se todo elemento de A é elemento de B. 1.28Conjuntos: Conceitos / Relações entre conjuntos N = { 1, 2, 3, 4, ... } P = { 2, 4, 6, 8, ... } S = { 0, 1 } Exemplo 1: N P está contido em , P ⊆ N N S não está contido em , S ⊄ _ N Exemplo 2: A = { 1, 3, a } B = { 3, a, 1 } A ⊆ B e B ⊆ A Conclusão: A = B ⇔ A ⊆ B e B ⊆ A (é equivalente) 1.29Conjuntos: Conceitos / Relações entre conjuntos - A está contido em B A ⊆ B Observação: - A é um subconjunto de B - B contém A ( B ⊇ A ) 1.30Conjuntos:Conceitos / Relações entre conjuntos Definição de inclusão estrita: A ⊆ B e A ≠ B Notação: A ⊂ B ( A está contido estritamente em B) 1.31Conjuntos: Conceitos / Relações entre conjuntos Observação: Para todo conjunto A ≠ ∅ : ∅ ⊂ A Para todo conjunto: ∅ ⊆ A = { 1, 2, 3, 4, ... } P = { 2, 4, 6, 8, ... } Exemplo 1: Conclusão: P ⊂ P ⊆ , mas 1 ∈ e 1 ∉ P N ≠ P N N N N Considere o conjunto A. O conjunto das partes de A, P(A), é o conjunto formado por todos os subconjuntos de A. Conjunto de partes de um conjunto: 1.32Conjuntos: Conceitos Seja A = { 1, 2, 3 } Exemplo: P(A) = {∅, { 1 }, { 2 }, { 3 }, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} } então Observação: Os elementos de P(A) são conjuntos: - { 1 } ∈ P(A) pois { 1 } ⊆ { 1, 2, 3 } - 1 ∉ P(A) - { { 1 }, { 1, 2, 3 } } ⊆ P(A) Exemplo: - { { 1 } } ⊆ P(A) - ∅ ∈ P(A) P(A) = {∅, { 1 }, { 2 }, { 3 }, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} } A = { 1, 2, 3 } 1.33Conjuntos: Conceitos / Conjunto de partes Conceitos - Conjunto - Elemento - Relação de pertinência - Relações entre conjuntos: Igualdade Inclusão Inclusão estrita Conjuntos especiais Propriedade: A = B ⇔ A ⊆ B e B ⊆ A Resumo: 1.34Conjuntos: Conceitos Notação A, B, ... a, b, x, ... x ∈ A, (x ∉ A) A = B, (A ≠ B) A ⊆ B, (A ⊄ B)_ A ⊂ B, (A ⊄ B) ∅, P(A) Conjunto universo Diagramas de Venn Operações e propriedades Identidades básicas Aula 2 : Diagramas de Venn e operações Conteúdo: 2.1Conjuntos 2.2Conjuntos: Diagramas de Venn e operações Introdução N D = { x ∈ | x ≥ 5 } N A = { x ∈ | x2 = 36 } Outra notação: Exemplos: N D = { x | x ∈ e x ≥ 5 } N A = { x | x ∈ e x2 = 36 } = { 5, 6, 7, ... } = { 6 } 2.3Conjuntos: Diagramas de Venn e operações Conjunto universo: Definição O conjunto universo, U, é aquele que contém todos os conjuntos que estão sendo considerados em um dado contexto. Notação: A = { x ∈ U | P(x) } está tal que x verifica P(x) constituído o conjunto A pelos elementos x pertencentes ao conjunto U (universo) 2.4Conjuntos Referência Histórica: matemático inglês John Venn (Século XIX). Característica: representação visual de conjuntos, suas operações e relações. Diagramas de Venn: 2.5Conjuntos: Diagramas de Venn Representação visual O conjunto universo U é representado por um retângulo e os subconjuntos próprios por regiões circulares dentro do retângulo. A ⊂ UA U 2.6Conjuntos: Diagramas de Venn Exemplo: B ⊂ A ⊂ U U A B U = N (x ≥ 10 e x ≤ 100)A = { x ∈ | 10 ≤ x ≤ 100 } N B = { x ∈ | 15 ≤ x ≤ 50 } N 2.7Conjuntos União Interseção Diferença Complemento Vamos definir as operações: Operações e propriedades: 2.8Conjuntos: Diagramas de Venn e operações BA Sejam A e B subconjuntos de U. A união de A e B que denotamos por A ∪ B é o conjunto formado por todos os elementos que pertencem a A ou que pertencem a B. A ∪ B = { x ∈ U | x ∈ A ou x ∈ B } A B Definição de união: VoltarUnião U 2.9Conjuntos: Diagramas de Venn e operações 2 3 4 A 1 8 9 B 7 5 6 A = { 1, 2, 3, 4, 5, 6 } A ∪ B = { x ∈ U | x ∈ A ou x ∈ B } B = { 5, 6, 7, 8, 9 } A ∪ B = Exemplo 1: { 1, 2, 3, 4, 5, 6, 7, 8, 9 } Voltar 5 6 2 3 4 A 1 8 9 B 7 5 6 5 6 União U Propriedade: A ⊆ A ∪ B e B ⊆ A ∪ B 2.10Conjuntos: Diagramas de Venn e operações x yz w v X Y X = { x, y, z } Y = { w, v } X ∪ Y = União { x, y, z, w, v } Exemplo 2: Voltar x yz w v X Y U 2.11Conjuntos: Diagramas de Venn e operações Z = { x ∈ U | altura de x ≥ 1,75 } W = { x ∈ U | altura de x ≥ 1,90 } Z ∪ W = U União ZZ WZ W Exemplo 3: U = conjunto das pessoas (W ⊆ Z) Voltar 2.12Conjuntos: Diagramas de Venn e operações Propriedade: Observação: A ∪ A = A A ∪ ∅ = A Seja A ⊆ U , temos: A ⊆ B ⇔ A ∪ B = B se e somente se (equivalente) A ⊆ B ⇑ A ∪ B = B e A ⊆ B ⇑ A ∪ B = B então 2.13Conjuntos: Diagramas de Venn e operações Definição de interseção: Sejam A e B subconjuntos de U. A ∩ B = { x ∈ U | x ∈ A e x ∈ B } Voltar BA U ∩ A interseção de A e B que denotamos por A ∩ B é o conjunto formado por todos os elementos que pertencem ao conjunto A e ao conjunto B. 2.14Conjuntos: Diagramas de Venn e operações 2 3 4 A 1 8 9 B 7 5 6 A ∩ B = { x ∈ U | x ∈ A e x ∈ B } A = { 1, 2, 3, 4, 5, 6 } B = { 5, 6, 7, 8, 9 } A ∩ B = { 5, 6 } Exemplo 1: Voltar ∩ U 8 9 B 7 2 3 4 A 1 5 6 Propriedade: A ∩ B ⊆ A e A ∩ B ⊆ B 2.15Conjuntos: Diagramas de Venn e operações X = { x, y, z } Y = { w, v } Exemplo 2: X ∩ Y = U ∩ ∅x yz w v X Y Voltar Quando X ∩ Y = ∅ os conjuntos X e Y são ditos disjuntos. 2.16Conjuntos: Diagramas de Venn e operações Exemplo 3: Z = { x ∈ U | altura de x ≥ 1,75 } W = { x ∈ U | altura de x ≥ 1,90 } U = conjunto das pessoas (W ⊆ Z) Z W Z ∩ W = U W ∩ Z W Voltar 2.17Conjuntos: Diagramas de Venn e operações Propriedade: A ⊆ B ⇔ A ∩ B = A Seja A ⊆ U, temos: Observação: A ∩ A = A A ∩ ∅ = ∅ 2.18Conjuntos: Diagramas de Venn e operações BA A − B = U { x ∈ U | x ∈ A e x ∉ B } A B Definição de diferença: Sejam A e B subconjuntos de U. VoltarDiferença A diferença entre A e B que denotamos por A − B é o conjunto formado por todos os elementos que estão em A mas não estão em B. 2.19Conjuntos: Diagramas de Venn e operações 2 3 4 A 1 5 6 5 6 8 9 B 76 5 A − B = { x ∈ U | x ∈ A e x ∉ B } A = { 1, 2, 3, 4, 5, 6 } B = { 5, 6, 7, 8, 9 } U Exemplo 1: B − A = U { 7, 8, 9 } B − A = { x ∈ U | x ∈ B e x ∉ A } A - B Voltar Voltar B - A 2 3 4 A 1 8 9 B 7 5 6 5 66 5 2 3 4 A 1 8 9 7 B 5 6 5 66 5 A − B = { 1, 2, 3, 4 } 2.20Conjuntos: Diagramas de Venn e operações Propriedade: A − B ⊆ A e B − A ⊆ B X = { x, y, z } Y = { w, v } X − Y = X X x z y Y w v x yz Exemplo 2: U Voltar Y − X = X x yz Y w v U w v Y Diferença 2.21Conjuntos: Diagramas de Venn e operações Z W Z − W = U { x ∈ U | 1,75 m ≤ altura de x < 1,90 m } Exemplo 3: Faça W − Z Resposta W − Z = ∅ Z = { x ∈ U | altura de x ≥ 1,75 } W = { x ∈ U | altura de x ≥ 1,90 } U = conjunto das pessoas Voltar Z - W W Z 2.22Conjuntos: Diagramas de Venn e operações Propriedade: A ⊆ B ⇔ A − B = ∅ Observação: A − A = ∅ A − ∅ = A Seja A ⊆ U, temos: 2.23Conjuntos: Diagramas de Venn e operações Sejam o conjunto universo U e o conjunto A ⊆ U. O complemento de A que denotamos por A _ é o conjunto formado por todos os elementos de U que não estão em A. Isto é, A _ = U − A Definição de complemento: A _ A _ = { x ∈ U | x ∉ A } Voltar U A U A Conjuntos: Diagramas de Venn e operações Exemplos: A = { x ∈ | x ≤ 50 } N (conjunto dos números naturais)1. U = N NA _ = − A = { x ∈ | x > 50 } N 2.24 A= { x ∈ | x > 2 } = { 3, 4, 5, ... } Z U = Z2. A _ = { x ∈ | x ≤ 2 } = { 2, 1, 0, -1, -2, ... } Z 3. U = N A = { x ∈ | x > 2 } = { 3, 4, 5, ... } N A _ = { x ∈ | x ≤ 2 } = { 1, 2 } N 2.25Conjuntos: Diagramas de Venn e operações Observações: A − B = A ∩ B _ B − A = B ∩ A _ U _ = ∅ (U _ = U − U ) ∅ _ = U (∅ _ = U − ∅ ) A ∪ A _ = U A ∩ A _ = ∅ 2.26Conjuntos: Diagramas de Venn e operações Identidades básicas: Associatividade (A ∪ B) ∪ C = A ∪ (B ∪ C) = A ∪ B ∪ C3. (A ∩ B) ∩ C = A ∩ (B ∩ C) = A ∩ B ∩ C4. Comutatividade A ∪ B = B ∪ A1. A ∩ B = B ∩ A2. 2.27Conjuntos: Diagramas de Venn / Identidades básicas Distributividade A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)5. ∩ = (A ∪ B) ∩ (A ∪ C) U A B C A ∪ C U A B C A ∪ B U A B C ∪ = A B ∩ C A ∪ (B ∩ C) U A B C U A B C U A B C 2.28Conjuntos: Diagramas de Venn / Identidades básicas Distributividade A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)6. ∩ = A U A B C A ∩ (B ∪ C) U A B C B ∪ C U A B C ∪ = A ∩ B U A B C A ∩ C U A B C (A ∩ B) ∪ (A ∩ C) U A B C 2.29 Leis de Morgan 7. (A ∪ B) = A _ ∩ B _ _____ => U A ∪ B BA U A ∪ B ______ BA (A ∪ B) = U - (A ∪ B) ______ ∩ = U A _ BA A _ = U - A B _ = U - B U B _ A B A _ ∩ B _ U A _ ∩ B _ BA Conjuntos: Diagramas de Venn / Identidades básicas 8. (A ∩ B) = A _ ∪ B ______ Leis de Morgan => U A ∩ B BA U BA A ∩ B ______ (A ∩ B) = U - (A ∩ B) ______ 2.30Conjuntos: Diagramas de Venn / Identidades básicas ∪ = U BA A _ ∪ B _ A _ ∪ B _ U B _ A B B _ = U - B U BA A _ = U - A 2.31Conjuntos: Diagramas de Venn / Identidades básicas A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) ou seja, e (1) A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C) (2) (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C) Prova formal da identidade 5: 2.32Conjuntos: Diagramas de Venn / Identidades básicas (x ∈ A ou x ∈ B) e (x ∈ A ou x ∈ C) x ∈ (A ∪ B) e x ∈ (A ∪ C) x ∈ (A ∪ B) ∩ (A ∪ C) x ∈ A ou x ∈ (B ∩ C) x ∈ A ∪ (B ∩ C) x ∈ A ou (x ∈ B e x ∈ C) => = > = > = > = > 1 2 Voltar Prova de (1) : Dado x ∈ A ∪ (B ∩ C), mostraremos que x ∈ (A ∪ B) ∩ (A ∪ C) : Faça você a prova de 2. Prova de (2): 2.33Conjuntos: Diagramas de Venn e operações Conceitos - Conjunto universo Notação U Resumo: - Operações com conjuntos: União Interseção Diferença Complemento - Conjuntos disjuntos A ∪ B A ∩ B A _ (A ∩ B = ∅) Diagramas de Venn U A U A B U A B U A B U A B U A U A B A − B B − A 2.34Conjuntos: Diagramas de Venn e operações Resumo: Propriedades - A ⊆ A ∪ B , B ⊆ A ∪ B - A ∩ B ⊆ A , A ∩ B ⊆ B - A − B ⊆ A , B − A ⊆ B - A ⊆ B ⇔ A ∪ B = B - A ⊆ B ⇔ A ∩ B = A - A ⊆ B ⇔ A − B = ∅ - A ∩ B = ∅ ⇔ A − B = A - A ∩ B = ∅ ⇔ B − A = B 2.35Conjuntos: Diagramas de Venn e operações Resumo: Identidades Básicas: (A ∩ B) = A _ ∪ B ______ - Leis de Morgan: (A ∪ B) = A _ ∩ B _ _____ - Distributividade: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) - Associatividade: (A ∪ B) ∪ C = A ∪ (B ∪ C) = A ∪ B ∪ C (A ∩ B) ∩ C = A ∩ (B ∩ C) = A ∩ B ∩ C - Comutatividade: A ∪ B = B ∪ A A ∩ B = B ∩ A 2.36Conjuntos: Diagramas de Venn e operações Observações: - A ∪ A = A - A ∩ A = A - A ∪ A _ = U - A ∩ ∅ = ∅ - A ∩ A _ = ∅ - U _ = ∅ - ∅ _ = U - A − ∅ = A - A − B = A ∩ B _ , B - A = B ∩ A _ - A ∪ ∅ = A Resumo: 2.37Conjuntos: Diagramas de Venn e operações Determine os seguintes conjuntos: 1. Sejam U = { 0, 1, 2, 3, 4 } , A = { 0, 4 } , B = { 0, 1, 2, 3 } , C = { 1, 4 }, D = { 0, 1 }. Exercícios a. A ∪ B b. B ∩ C c. A ∩ B _ d. A ∪ (B ∩ C) e. (A ∪ B) ∩ (A ∪ C) j. A ∪ (B ∩ C ∩ D) g. A ∪ B _ h. A − B i. B − A _ f. (A ∩ B) ∪ (A ∩ C) _____ _____ 2.38Conjuntos: Diagramas de Venn e operações 2. Sejam A, B e C subconjuntos de um conjunto universo U. Represente por meio de diagramas de Venn as seguintes situações. (i) A ⊂ B ⊂ C (ii) A ∩ B = ∅ , A ∩ C = ∅ , B ∩ C = ∅ (iii) A ⊆ B ∪ C (iv) A ⊆ B _ (v) A ⊆ B − C 2.39Conjuntos: Diagramas de Venn e operações 3. Verifique, usando os diagramas de Venn as seguintes igualdades: (i) (A − B) ∪ B = A ∪ B (iii) (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B) (ii) (A − B) ∩ B = ∅ (iv) A − B = A ∩ B _ (vi) A ∩ (B − C) = (A ∩ B) − (A ∩ C) (v) ( A _ ) = A _ 2.40Conjuntos: Diagramas de Venn e operações verifique que C ∩ D = E. 6. Dados os conjuntos C = { x ∈ | x é múltiplo de 2 } , N D = { x ∈ | x é múltiplo de 3 } , N E = { x ∈ | x é múltiplo de 6 } , N 4. Mostre que A ⊆ B e A ⊆ C => A ⊆ B ∪ C 5. Mostre que B _ ⊆ A _ ⇔A ⊆ B 2.41Conjuntos: Diagramas de Venn e operações 8. Dado C = { 2, −1, 5 }, considere o conjunto universo sendo o conjunto de partes de C, U = P(C). Calcule: (i) A _ (ii) A ∩ B para A = { {2, −1} , {2} } , B = { {5} , {2, −1, 5} , {−1, 2} }. B = { x ∈ | 1 ≤ 3x − 2 ≤ 30 } . Calcule: N 7. Considere A = { x ∈ | 5 ≤ x2 ≤ 300 } ,N (i) A ∪ B (ii) A ∩ B (iii) A − B (iv) B − A (v) A _ ∩ B _ (vi) A _ ∪ B _ 2.42Conjuntos: Diagramas de Venn e operações 9. Use a propriedade distributiva da interseção em relação a união de conjuntos para provar que (A ∩ D) ∪ D _ = A ∪ D _ . Verifique a igualdade usando o diagrama de Venn. 10. Prove que A − (B − C) = (A − B) ∪ (A ∩ C). Dica: a igualdade A − B = A ∩ B _ (vista no exercício 2 (iv) ), uma propriedade distributiva de conjuntos e uma das leis de Morgan. 2.43Conjuntos: Diagramas de Venn e operações (i) A = B (ii) A _ ≠ B _ 11. Dados os seguintes conjuntos: A = { x ∈ | 0 ≤ x ≤ 7 } , B = { x ∈ | 0 ≤ x ≤ 7 } Verifique que: Z N Aula 3 : Número de elementos de um conjunto 3.1 Conteúdo: Conceitos iniciais Introdução ao princípio aditivo Introdução ao princípio da inclusão e exclusão Faz sentido saber quantos elementos tem um conjunto? É sempre possível contar os elementos de um conjunto? Tem uma fórmula para calcular o número de elementos de A ∪ B ? Conceitos iniciais: 3.2Conjuntos: Número de elementos Questão 1: O vaqueiro João cuida das vacas da fazenda "Três Irmãos". Ele leva as vacas para pastar nos campos fora da fazenda. Ele não pode perder nenhuma vaca. Então o que ele faz ? Conta as vacas que formam o gado antes e depois do pastoreio. Faz sentido saber quantos elementos tem um conjunto ? Exemplo 1: 3.3Conjuntos: Número de elementos / Conceitos iniciais Conjunto de vacas depois do pastoreio. =>Conjunto de vacas antes do pastoreio. => Você deu dez notas de R$ 1,00 para um amigo fazer compras. No retorno, você contou o dinheiro que sobrou (3 notas de R$ 1,00 ). Questão 1: Exemplo 2: 3.4Conjuntos: Número de elementos / Conceitos iniciais Fazsentido saber quantos elementos tem um conjunto ? Resposta: SIM n(A) : é o número de elementos do conjunto A (ou cardinalidade de A). n(A) = 7 Exemplo 1: 3.5Conjuntos: Número de elementos / Conceitos iniciais Notação: = { -3, -2, -1, 0, 1, 2, 3 } A = { x ∈ | |x| ≤ 3 } = Z { x ∈ | -3 ≤ x ≤ 3 } Z Questão 2: É sempre possível contar os elementos de um conjunto ? A = { x ∈ | |x| ≤ 3 } = { -3, -2, -1, 0, 1, 2, 3 } Z - Como contamos os elementos de A ? Exemplo 1: 3.6Conjuntos: Número de elementos / Conceitos iniciais => Enumerando seus elementos: 1 é o número -3 2 é o número -2 7 é o número 3 ...... => Acabamos a enumeração em 7 Questão 2: Exemplo 2: = { 2, 4, 6, ... } Podemos ir enumerando seus elementos mas nunca acabaremos a enumeração. B = { x ∈ | x é par } N 3.7Conjuntos: Número de elementos / Conceitos iniciais É sempre possível contar os elementos de um conjunto ? Resposta: NEM sempre Definição: Um conjunto é finito se é possível contar o número de seus elementos. Um conjunto é infinito se não é possível contar o número de seus elementos. 3.8Conjuntos: Número de elementos / Conceitos iniciais Exemplo 1: , , , , são conjuntos infinitos.N Z Q IR A = { x ∈ ||x| ≤ 3 } é finito Z B = { x ∈ | x é par } é infinito N - n(C) é um número que não conhecemos 3.9Conjuntos: Número de elementos / Conceitos iniciais Conclusão: Embora tenhamos um conjunto finito, pode ser impraticável contá-lo. É sempre possível contar os elementos de um conjunto finito. então: C = { x | x é uma pessoa que nasceu antes de 2000 } - C está bem definido - C é finito Exemplo: Mas, será que sempre conseguimos contar ? Assumimos, nesta aula: A é um conjunto finito; É possível determinar o número de elementos de A, n(A). Questão 3: Tem uma fórmula para calcular o número de elementos de A ∪ B ? 3.10Conjuntos: Número de elementos / Conceitos iniciais Dados os conjuntos A e B, calcular n(A ∪ B) Problema inicial: { Introdução ao princípio aditivo: Encontrar uma fórmula para calcular n(A ∪ B). Objetivo: 3.11Conjuntos: Número de elementos então n(A ∪ B) = n(A) + n(B) Princípio aditivo (para dois conjuntos) Se A e B são disjuntos, A ∩ B = ∅, Α ΒU Dados n(U) = 300, n(A) = 150, n(B)= 40 Determinar o número de alunos do IL que está no 1o ou no 4o ano do curso de inglês. U = { x | x é aluno do Instituto de Línguas IL } A = { x ∈ U | x está no 4o ano do curso de inglês } B = { x ∈ U | x está no 1o ano do curso de inglês } A ∩ B = ∅ => n(A ∪ B) = n(A) + n(B) = 190 Problema: Exemplo 1: 3.12Conjuntos: Número de elementos / Introdução ao princípio aditivo 3.13Conjuntos: Número de elementos / Introdução ao princípio aditivo Problema: Dados os conjuntos A, B e C, calcular n(A ∪ B ∪ C){ Prova: n(A ∪ B ∪ C) = n((A ∪ B) ∪ C) = n(A ∪ B) + n(C) (A ∪ B) ∩ C = ∅ A ∩ B = ∅ = n(A) + n(B) + n(C) então n(A ∪ B ∪ C) = n(A) + n(B) + n(C) Se A, B e C são disjuntos dois a dois: Princípio aditivo (para três conjuntos) A ∩ B = ∅, A ∩ C = ∅, B ∩ C = ∅ U Α Β C Princípio aditivo (para quatro conjuntos) Se A, B, C e D são conjuntos disjuntos dois a dois ( A ∩ B = A ∩ C = A ∩ D = B ∩ C = B ∩ D = C ∩ D = ∅ ) então n(A ∪ B ∪ C ∪ D) = n(A) + n(B) + n(C) + n(D) Tente fazer a prova aplicando o raciocínio anterior. 3.14Conjuntos: Número de elementos / Introdução ao princípio aditivo Prova Prova: n(A ∪ B ∪ C ∪ D) = n((A ∪ B) ∪ C ∪ D) Voltar 3.15Conjuntos: Número de elementos / Introdução ao princípio aditivo isto é, (A ∪ B), C e D são disjuntos dois a dois. Logo, estamos nas condições do problema anterior, portanto temos: n((A ∪ B) ∪ C ∪ D ) = n(A ∪ B) + n(C) + n(D) = n(A) + n(B) + n(C) + n(D) pois, A ∩ B = ∅ Quer dizer, provamos que n(A ∪ B ∪ C ∪ D) = n(A) + n(B) + n(C) + n(D) como A ∩ B = A ∩ C = A ∩ D = B ∩ C = B ∩ D = C ∩ D = ∅ resulta (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) = ∅ (A ∪ B) ∩ D = (A ∩ D) ∪ (B ∩ D) = ∅ C ∩ D = ∅ Encontrar uma fórmula para n(A ∪ B). Objetivo: Problema inicial: A e B podem não ser disjuntos A ∩ B ≠ ∅ Introdução ao princípio da inclusão e exclusão: 3.16Conjuntos: Número de elementos Dados os conjuntos A e B, calcular n(A ∪ B){ Reescrever A ∪ B como conjuntos disjuntos. Estratégia: n(A ∪ B) = ? U Α Β Como reescrever A ∪ B como união de conjuntos disjuntos? U U Α Β Dados A, B, A ∩ B ≠ ∅ Disjuntos Voltar 3.17Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão U União U União ΒΑ U ∩ Β Α Α − Β Β − Α Α − Β Β − Α A ∩ B A - B = A ∩ B _ B - A = B ∩ A _ Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão A = (A - B) ∪ (A ∩ B) B = (B - A) ∪ (A ∩ B) Voltar Voltar Voltar 3.18 n(A ∪ B) = n(A - B) + n(A ∩ B) + n(B - A) Conclusão: A ∪ B = (A - B) ∪ (A ∩ B) ∪ (B - A) n(A ∪ B) = n( (A − B) ∪ (A ∩ B) ∪ (B − A) ) = n(A − B) + n(A ∩ B) + n(B − A) U Α U A ∩ B U => => A = (A − B) ∪ (A ∩ B) B = (A ∩ B) ∪ (B − A) Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão A - B B - A A ∩ B 3.19 n(B) = n(B − A) + n(A ∩ B) n(A) = n(A − B) + n(A ∩ B) U Β Resumindo: Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão 3.20 n(A ∪ B) = n(A − B) + n(A ∩ B) + n(B − A) n(A) = n(A − B) + n(A ∩ B) n(B) = n(B − A) + n(A ∩ B) => => n(A − B) = n(A) − n(A ∩ B) n(B − A) = n(B) − n(A ∩ B) n(A ∪ B) = [ n(A) − n(A ∩ B) ] + n(A ∩ B) + [ n(B) − n(A ∩ B) ] = n(A) + n(B) − n(A ∩ B) Princípio da inclusão e exclusão (para dois conjuntos) n(A ∪ B) = n(A) + n(B) - n(A ∩ B) n(A) + n(B) - n(A ∩ B) Interpretação visual U Α Β Observação: estamos contando 2 vezes os elementos da interseção, então devemos subtrair um deles. Dados A e B, então Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão ∩ Voltar 3.21 U = { x | x é aluno do Instituto de Línguas IL } A = { x ∈ U | x está no 4o ano do curso de inglês } B = { x ∈ U | x está no 2o ano do curso de francês } Exemplo 2: Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão 3.22 então o número de alunos do IL que cursam o 4o ano de inglês ou o 2oano de francês é: = 40 + 20 - 2 = 58 n(A ∪ B) = n(A) + n(B) - n(A ∩ B) n(B) = 20 dados: n(U) = 300 n(A) = 40 n(A ∩ B) = 2 Questão: Como calcular n(A ∪ B ∪ C) usando o Princípio da inclusão e exclusão para dois conjuntos ? Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão n(A ∪ B ∪ C) = n( (A ∪ B) ∪ C ) { 3.23 = [ n(A) + n(B) - n(A ∩ B) ] + n(C) - n((A ∩ C) ∪ (B ∩ C)) = n(A) + n(B) + n(C) - n(A ∩ B) - [ n(A ∩ C) + n(B ∩ C)) - n((A ∩ C) ∩ B ∩ C) ] A ∩ B ∩ C { { = n(A ∪ B) + n(C) - n( (A ∪ B) ∩ C ) {= n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C) Princípio da inclusão e exclusão (para três conjuntos) Interpretação gráfica: Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão 3.24 U n(A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C) Dados A, B e C, então U = { x | x é aluno do Instituto de Línguas IL } A = { x ∈ U | x está no 4o ano do curso de inglês } B = { x ∈ U | x está no 2o ano do curso de francês } C = { x ∈ U | x está no 1o ano do curso de italiano } Exemplo 3: Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão 3.25 Dados: n(U) = 300 , n(A) = 40 , n(B) = 20 , n(C) = 30 n(A ∩ B) = 2 n(A ∩ C) = 5 n(B ∩ C) = 3 n(A ∩ B ∩ C) = 1 então o número de alunos do IL que estão cursando o 4o ano de inglês ou o 2oano de francês ou o 1o ano de italiano é: Exemplo 3 (continuação): Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão 3.26 n(A ∪ B ∪ C) = 40 + 20 + 30 - 2 - 5 - 3 + 1 = 81 n(A ∪ B ∪ C) = = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C) = ∑ 4 i=1 n(Ai) - ∑ 4 i, j=1 i < j n(Ai ∩ Aj) + ∑ 4 i, j, l = 1 i < j j < l i < j < l n(Ai ∩ Aj ∩ Al) - n(A1 ∩ A2 ∩ A3 ∩ A4) Prove o princípio da inclusão e exclusão no seguinte caso: Dados A1 , A2 , A3 e A4 , então n( A1 ∪ A2 ∪ A3 ∪ A4 ) = Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão 3.27 n(A1) + n(A2) + n(A3) + n(A4) − − n(A1 ∩ A2) − n(A1 ∩ A3) − n(A1 ∩ A4) − n(A2 ∩ A3) − n(A2 ∩ A4) − − n(A3 ∩ A4) + n(A1 ∩ A2 ∩ A3) + n(A1 ∩ A2 ∩ A4) + n(A2 ∩ A3 ∩ A4) − − n(A1 ∩ A2 ∩ A3 ∩ A4) = Fórmula Voltar Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão 3.28 Prova: n(A1 ∪ A2 ∪ A3 ∪ A4) = n((A1 ∪ A2) ∪ A3 ∪ A4) Voltar Prova n( A1 ∪ A2 ) = n(A1) + n(A2) − n(A1 ∩ A2) − n((A1 ∪ A2) ∩ A3) − n((A1 ∪ A2 ) ∩ A4) − n(A3 ∪ A4 ) + n((A1 ∪ A2) ∩ A3 ∩ A4) n( A1 ∪ A2 ∪ A3 ∪ A4 ) = n((A1 ∪ A2 ) ∪ A3 ∪ A4 )) = n(A1 ∪ A2 ) + n(A3 ) + n(A4 ) −{ { {n((A1 ∪ A2) ∩ A3) = n((A1 ∩ A3) ∪ (A2 ∩ A3)) = = n((A1 ∩ A3) + (A2 ∩ A3) − n((A1 ∩ A3) ∩ (A2 ∩ A3)) A1 ∩ A2 ∩ A3 A1 ∩ A2 ∩ A3 ∩ A4 n((A1 ∪ A2) ∩ A3 ∩ A4) = n( [(A1 ∪ A2) ∩ Α3 ] ∩ A4) = = n( [(A1 ∩ A3) ∪ (A2 ∩ A3) ] ∩ A4) = n[(A1 ∩ A3 ∩ A4) ∪ (A2 ∩ A3 ∩ A4)] = = n(A1 ∩ A3 ∩ A4) + n(A2 ∩ A3 ∩ A4) − n((A1 ∩ A3 ∩ A4) ∩ (A2 ∩ A3 ∩ A4)) { { A1 ∩ A2 ∩ A4 n((A1 ∪ A2) ∩ A4) = n((A1 ∩ A4) ∪ (A2 ∩ A4)) = = n(A1 ∩ A4) + n(A2 ∩ A4) − n((A1 ∩ A4) ∩ (A2 ∩ A4)) Observação: A partir de n(A ∪ B) podemos obter outras relações. Determine a quantidade de números naturais que existe entre 1 e 100 e não são divisíveis por 2 nem por 5. Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão Exemplo: { x ∈ | x ∈ C, x ∉ A e x ∉ B } N 3.29 C = { x ∈ | 1 ≤ x ≤ 100 } N = {2, 4, 6, ... ,100}A = { x ∈ | x ∈ C, x = 2k, k ∈ } N N = {5, 10, 15, ... ,100}B = { x ∈ | x ∈ C, x = 5k, k ∈ } N N { x ∈ | x ∈ C e x ∉ A e x ∉ B } N Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão = C - (A ∪ B) = { x ∈ | x ∈ C e x ∉ (A ∪ B) } N = { x ∈ | x ∈ C e ( x ∈ A _ ∩ B _ ) } N = { x ∈ | x ∈ C e ( x ∈ A _ e x ∈ B _ ) } N 3.30 N = { x ∈ | x ∈ C e x ∈ (A ∪ B) } _____ Determine a quantidade de números naturais que existe entre 1 e 100 e não são divisíveis por 2 nem por 5. Lembremos o enunciado do exemplo: Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão C A B N Pede-se n( C - (A ∪ B) ) Conclusão: 3.31 Observe que: ( C - (A ∪ B) ) ∪ (A ∪ B) = C e ( C - (A ∪ B) ) ∩ (A ∪ B) = ∅ Conjuntos: Número de elementos / Introdução ao princípio da inclusão e exclusão n(C - (A ∪ B)) = n(C) - n(A ∪ B) => 3.32 =>n((C - (A ∪ B)) ∪ (A ∪ B)) = n(C - (A ∪ B)) + n(A ∪ B) princípio aditivo n(C) Conjuntos: Número de elementos / Introdução ao princípio de inclusão e exclusão Devemos calcular n(C - (A ∪ B)) = n(C) - n(A ∪ B) n(C) = 100 Resumindo: 3.33 C = { x ∈ | 1 ≤ x ≤ 100 } N = 50 + 20 - 10 = 60 n(A ∪ B) = n(A) + n(B) - n(A ∩ B) princípio inclusão e exclusão logo, n(C - (A ∪ B)) = 100 - 60 = 40 Resposta: A quantidade de números naturais que existe entre 1 e 100 e não são divisíveis por 2 nem por 5 é 40. A = { x ∈ | x ∈ C , x = 2k , k ∈ } N N = {2, 4, 6, ... , 100} B = { x ∈ | x ∈ C , x = 5k , k ∈ } N N = {5, 10, 15, ... , 100} 3.34Conjuntos: Número de elementos Resumo: Conceitos: - Número de elementos de um conjunto, n(A) - (cardinalidade) - Conjunto finito - Conjunto infinito - Introdução ao princípio aditivo: (Número de elementos da união de conjuntos disjuntos dois a dois) • A1 e A2 disjuntos => n(A1 ∪ A2) = n(A1) + n(A2) = ∑ 2 i=1 n(Ai) • A1, A2 e A3 disjuntos => n(A1 ∪ A2 ∪ A3) = = n(A1) + n(A2) + n(A3) = ∑ 3 i=1 n(Ai) • Ai disjuntos dois a dois => n(∪ 4 i=1 Ai) = ∑ 4 i=1 n(Ai) Resumo: Conceitos: - Introdução ao princípio da inclusão e exclusão: (Número de elementos da união de conjuntos não necessariamente disjuntos) • n(A1 ∪ A2) = n(A1) + n(A2) - n(A1 ∩ A2) = ∑ 2 i=1 n(Ai) - n(A1 ∩ A2) • n(A1 ∪ A2 ∪ A3) = n(A1) + n(A2) + n(A3) - n(A1 ∩ A2) - n(A1 ∩ A3) - - n(A2 ∩ A3) + n(A1 ∩ A2 ∩ A3) = ∑ 3 i=1 n(Ai) - ∑ 3 i , j=1 i < j n(Ai ∩ A2) + n(∩ 3 i=1 Ai) • n(∪ 4 i=1 Ai) = ∑ 4 i=1 n(Ai) - ∑ 4 i, j=1 i < j n(Ai ∩ Aj) + ∑ 4 i, j, l = 1 i < j j < l i < j < l n(Ai ∩ Aj ∩ Al) - n(∩ 4 i=1 Ai) 3.35Conjuntos: Número de elementos 1. Sejam A e B dois subconjuntos de um conjunto universo U tais que B ⊆ A. Usando o princípio aditivo prove que n(A − B) = n(A) − n(B). Exercícios 2. Quantos números inteiros entre 1 e 100 são divisíveis por 3 ou por 7. 3.36Conjuntos: Número de elementos Dica: Considere A = { x ∈ | 1 ≤ x ≤ 100 e x =3k para algum k ∈ } B = { x ∈ | 1 ≤ x ≤ 100 e x =7k para algum k ∈ } e use o princípio de inclusão e exclusão. Z N Z N 3. Use os princípios aditivo ou de inclusão e exclusão para determinar, em cada caso, a quantidade de números naturais entre 1 e 60 que verificam: (i) são divisíveis por 2 e por 3 (ii) são divisíveis por 2 ou por 3 (iii) não são divisíveis nem por 2 nem por 3 (iv) são ímpares divisíveis por 3 ou são divisíveis por 2 (v) são divisíveis por 2 ou por 3 ou por 5 3.37Conjuntos: Número de elementos 4. Foram consultadas 200 pessoas que estavam pesquisando preços de televisores em lojas de eletrodomésticos. As respostas foram as seguintes: - 40% perguntaram pela marca A; - 35% pela marca B; - 10% pelas marcas A e B; - 25% somente perguntaram por outras marcas. Use o princípio de adição ou o princípio da inclusão e exclusão para determinar: 3.38Conjuntos Número de elementos (i) quantidade de pessoas que perguntaram pelos preços das televisões de marcas A ou B. (ii) númerode pessoas que perguntaram pela marca A e não pela marca B (lembre-se do exercício 1). 4. (continuação) 3.39Conjuntos: Número de elementos Módulo: Indução matemática Indução forte Princípio da indução matemática 4.1 Objetivo: Aprender uma técnica para provar resultados matemáticos. 4.2Indução matemática Por exemplo: Provar que 1 + 2 + 3 + ... + n = n(n + 1) _______ 2 n ∈ 8 N É uma técnica poderosa e muito útil usada para provar resultados que envolvem os números naturais. Importância: Princípio da indução matemática (PIM) Introdução Conteúdo: Aula 4: Princípio da indução matemática Princípio da indução matemática generalizado 4.3 Idéia intuitiva: Exemplo 1: Consideremos uma sequência de dominós alinhados tal que: Se um cair ele vai derrubar o seguinte PIM Voltar Introdução: 4.4Indução matemática Observação: Se o primeiro dominó cair então todos os outros cairão. Exemplo 2: Consideremos lâmpadas elétricas alinhadas e conectadas tal que: ao acender uma delas acende-se a seguinte PIM Voltar 4.5Indução matemática: Introdução Se a primeira lâmpada for acesa então todas as outras estarão acesas. Observação: Formalização: Princípio da indução matemática: 4.6Indução matemática Se : (i) P(1) verdadeira e (ii) P(k) verdadeira => P(k+1) verdadeira, k ∈ 8 N Seja P(n) uma afirmação, para cada n ∈ . N Então P(n) verdadeira para todo n ∈ . N Para aplicarmos o PIM precisamos executar os três passos a seguir: (1) Base da indução: Mostrar que P(n) verdadeira para n = 1 (2) Hipótese de indução: Assumir que P(k) verdadeira para k ≥ 1 (3) Passo indutivo: Mostrar que P(k + 1) verdadeira, assumindo (2). 4.7Indução matemática: Princípio da indução matemática Exemplo 3: verdadeira 4.8Indução matemática: Princípio da indução matemática Mostre que 1 + 2 + 3 + ... + n = n(n + 1)_______ 2 n ∈ . 8 N Prova: Seja P(n) : 1 + 2 + 3 + ... + n = n(n + 1) ________ 2 (1) Base da indução: P(1) : 1 = 1(1 + 1) = 1 _______ 2 (2) Hipótese de indução (HI): Assuma que P(k) é verdadeira, k ≥ 1: 1 + 2 + ... + k = k(k+1)______ 2 4.9Indução matemática: Princípio da indução matemática 1 + 2 + ... + k + (k + 1) = (k + 1) (k + 2)_____________ 2 (3) Passo indutivo: P(k) verdadeira => P(k + 1) verdadeira Desenvolvendo: _______ 2 k(k + 1) + (k + 1) = k2 + k + 2k + 2 =______________ 2 1 + 2 + ... + k + (k + 1) = = (HI) Logo P(k+1) verdadeira = k2 + k + 2k + 2 =______________ 2 (k+1)(k+2) __________ 2 k2 + 3k + 2 =__________ 2 ______ 2 k(k+1) + (k+1) 4.10Indução matemática: Princípio da indução matemática Então pelo PIM verdadeira________ 2 P(n) : 1 + 2 + ... + n = n(n + 1) N n ∈ 8 Exemplo 4: Prova: Seja P(n) : 1 + 3 + 5 + ... + (2n − 1) = n2 verdadeira Mostre que 1 + 3 + 5 + ... + (2n − 1) = n2 N n ∈ . 8 4.11Indução matemática: Princípio da indução matemática (1) Base da indução: P(1) : 1 = 12 (2) Hipótese de indução (HI): P(k) : 1 + 3 + 5 + ... + (2k − 1) = k2 verdadeira (3) Passo indutivo: P(k) verdadeira => P(k + 1) verdadeira 4.12Indução matemática: Princípio da indução matemática 1 + 3 + ... + [ 2(k + 1) − 1] = (k + 1) 2 Logo P(k + 1) verdadeira Então pelo PIM P(n) : 1 + 3 + ... + (2n - 1) = n2 verdadeira 8 n ∈ N 1 + 3 + ... + (2k - 1) + [ 2(k + 1) - 1 ] = Desenvolvendo: k2 + 2k+1 = (k + 1)2 = (HI) = Exemplo 5: Seja P(n) : 8 divide 32n − 1 Prova: 4.13Indução matemática: Princípio da indução matemática Mostre que 8 divide 32n − 1 N 8 n ∈ . 32n - 1 = 8 . p para algum p ∈ N ou (1) Base da indução: verdadeiraP(1) : 32 . 1 − 1 = 9 − 1 = 8 . 1 (p = 1) 4.14Indução matemática: Princípio da indução matemática (2) Hipótese de indução: P(k) verdadeira, 32k - 1 = 8 . p para algum p ∈ N (3) Passo indutivo: P(k) verdadeira => P(k + 1) verdadeira Desenvolvendo: 32(k + 1)- 1 = 32k. 32 - 1 = 32k (8 + 1) - 1 = N 32(k + 1)- 1 = 8 . p para algum p ∈ 4.15Indução matemática: Princípio da indução matemática = 32k. 8 + 32k- 1 = 8 . p (HI) = 32k. 8 = + 32k. 8 32k- 1 Logo P(k+1) verdadeira 32(k + 1)- 1 = 32k. 8 + 8 . p = 8 . (32k+ p) ( p = 32k+ p ) ∈ N Então pelo PIM P(n) : 8 divide 32n - 1 verdadeira n ∈ 8 N 4.16Indução matemática: Princípio da indução matemática Se: (ii,) (i,) P(n0) 8 N N k ≥ n0 ,k ∈ 8 N Princípio da indução matemática generalizado Seja P(n) uma afirmação, para cada inteiro positivo n. verdadeira e P(k) verdadeira => P(k+1) verdadeira, PIM Princípio da indução matemática generalizado: Voltar 4.17Indução matemática 8 Então P(n) verdadeira n ∈ , n ≥ n0 .N Para aplicarmos o PIM generalizado precisamos executar os três passos a seguir: (1) Base da indução: Mostrar que P(n) verdadeira para n = n0 (3) Passo indutivo: Mostrar que P(k + 1) verdadeira, assumindo a hipótese de indução (2) (2) Hipótese de indução: Assumir que P(k) verdadeira para k ≥ n0 4.18Indução matemática: PIM generalizado Exemplo 6: verdadeira (2) Hipótese de indução: P(k) : k2 > 3k , k ≥ 4 verdadeira 4.19Indução matemática: PIM generalizado 8 Mostre que n2 > 3n n ≥ 4 , n ∈ . N (1) Base da indução: P(4) : 16 > 3 . 4 = 12 Prova: Seja P(n) : n2 > 3n , n ≥ 4 (3) Passo indutivo: P(k) verdadeira => P(k + 1) verdadeira k2 + 2k + 1 = 4.20Indução matemática: PIM generalizado Logo P(k + 1) verdadeira Então pelo PIM generalizado P(n) : n2 > 3n verdadeira n ≥ 4 8 (k ≥ 4) ≥ 3k + 8 + 1 = 3k + 9 (k + 1)2 > 3k + 9 = 3(k + 3) > 3(k + 1) Desenvolvendo: P(k) : k2 > 3k verdadeira para k ≥ 4 k2 + (2k + 1) > 3k + (2k + 1) (k + 1) 2 > 3(k + 1) P(n) : n2 > 3n não é verdadeira para n = 1, 2, 3 P(1) : 12 > 3 . 1 P(2) : 22 > 3 . 2 P(3) : 32 > 3 . 3 não são verdadeiras Verifique que: 4.21Indução matemática: PIM generalizado Princípio PIM generalizado Estrutura Resumo: - Base de indução: P(n) verdadeira n = n0 - Passo indutivo: P(k) verdadeira => P(k + 1) verdadeira n0 = 1 : PIM Em particular 4.22Indução matemática - Hipótese de indução: P(k) verdadeira k ≥ n08 Prove usando indução matemática Exercícios: (v) 2 divide n2 + n (i) 1 + 2 + 4 + ... + 2(n - 1) = 2n - 1 8 N n ∈ 4.23Indução matemática (ii) 12 + 22 + 32 + ... + n2 = n(n + 1)(2n + 1)___________________ 6 (iii) 2 + 5 + 8 + ... + (3n - 1) = n(1 + 3n)___________ 2 (iv) (1 + 1) ( 1 + 1 ) ( 1 + 1 ) ... ( 1 + 1 ) = n + 1__ 2 __ 3 __ n Indução forte Série de Fibonacci Conteúdo: Indução forte generalizada Aula 5: Indução forte 5.1Indução matemática É uma sequência de números naturais {F1, F2, F3, ...} , denotada por {Fn} definida da seguinte forma: Sequência de Fibonacci: F1 = 1 F2 = 1 Fn = Fn - 1 + Fn - 2 para n ≥ 3 5.2Indução matemática F1 ... 1 1 ... Ou seja, os termos Fn n ≥ 3 são calculados recursivamente: F2 Voltar2 3 F4 F5 F6 8 F7 F8 13 215 F3 { 1, 1, 2, 3, 5, 8, 13, 21, ... } 5.3Indução matemática: Sequência de Fibonacci Observe a seguinte propriedade: Somando os termos da sequência de Fibonacci elevada ao quadrado: F21 = 1 2 = 1 Voltar F21 + F 2 2 = 1 2 + 12 = 1 + 1 = 2 = 1 . 2 = F2 . F3 F21 + F 2 2 + F 2 3 = 1 2 + 12 + 22 = 6 = 2 . 3 = F3 . F4 F21 + F 2 2 + F 2 3 + F 2 4 = 1 2 + 12 + 22 + 32= 15 = 3 . 5 = F4 . F5 F21 + F 2 2 + F 2 3 + F 2 4 + F 2 5 = 1 2+12+22+32+52= 40 = 5 . 8 = F5 . F6 5.4Indução matemática: Sequência de Fibonacci Conjectura: F21 + F 2 2 + F 2 3 + ... + F 2 n = Fn . Fn + 1 Exemplo 1: (1) Base da indução: P(1) : F21 = 1 = F1 . F2 = 1 . 1 = 1 verdadeira (2) Hipótese de indução (HI): P(k) : F21 + F 2 2 + ... + F 2 k = Fk . Fk - 1 verdadeira Prova: Seja P(n) : F21 + F 2 2 + ... + F 2 n = Fn . Fn + 1 5.5Indução matemática: Sequência de Fibonacci Mostre que F21 + F 2 2 + ... + F 2 n = Fn . Fn + 1 n ∈ N8 (3) Passo indutivo: P(k) verdadeira => P(k + 1) verdadeira 5.6Indução matemática: Sequência de Fibonacci F21 + F 2 2 + ... + F 2 k + F 2 k + 1 = Fk + 1 • Fk + 2 Fk . Fk + 1 + F 2 k + 1 = (HI) = Fk + 1 (Fk + Fk + 1) = Fk +1 . Fk + 2 = Fk + 2 Desenvolvendo: F21 + F 2 2 + ... + F 2 k + F 2 k + 1 = Logo P(k + 1) verdadeira Então pelo PIM P(n) : F21 + F 2 2 + ... + F 2 n = Fn . Fn + 1 verdadeira n ∈ 8 N Indução forte (IF): IF Observação: O PIM e a IF são equivalentes. Voltar Se: (i) P(1) verdadeira e (ii) P(1), P(2), ... ,P(k) verdadeira => P(k+1) verdadeira Então P(n) verdadeira n ∈ N8 5.7Indução matemática 8 N Seja P(n) uma afirmação, para cada n ∈ . N Para aplicarmos a indução forte precisamos executar os três passos a seguir: (1) Base da indução: Mostrar que P(n) verdadeira para n = 1 (2) Hipótese de indução forte: Assumir que P(1), P(2), ... , P(k) são verdadeiras (3) Passo indutivo: Mostrar que P(k + 1) verdadeira, assumindo (2) 5.8Indução matemática: Indução forte Exemplo 2: 5.9Indução matemática: Indução forte 4( ( Considerando a sequência de Fibonacci {Fn} , mostre que Fn < 7__ n n ∈ N 8 Prova: Seja P(n) : Fn < 7__ n 4( ) (1) Base da indução: P1 : F1 = 1 < 7__ 1 verdadeira 4( ) 5.10Indução matemática: Indução forte 4( ) P1, P2, ... , Pk verdadeiras => P(k + 1) verdadeira (3) Passo indutivo: Fk + 1 < 7__ k + 1 4( ) (2) Hipótese da indução forte (HIF): Assuma que P1, P2, ... , Pk são verdadeiras Fi < 7__ i i , 1 ≤ i ≤ k 8 Desenvolvendo: Fk + 1= Fk + Fk - 1 5.11Indução matemática: Indução forte 4( )Fk < 7__ k Fk - 1 < 7__ k-1 4( ) {= {= HF HF Observe que 11__ < 3 < 4 7__ 2 4( ) 49__ = 16 Fk + 1 < < • = 7__ k - 1 4( ) 7__ k - 1 4( ) 7__ 2 4( ) 7__ k + 1 4( ) 11__ 4 Logo P(k + 1) verdadeira Então pelo IF Fn < n ∈ 8 N 7__ n 4( ) 7__ k 11__ 7__ +1 7__ k - 1 7__ k - 1 7__ k - 1 ( 4 )4( )4( ) 4( ) 4( ) 4( )< + = = Se: (i) P(n0) verdadeira (ii) P(n0), P(n0+1), ...,P(k) verdadeira => P(k+1) verdadeira (k = n0 + k , ) 8 Então P(n) é verdadeira n ≥ n0 n ∈ N Indução forte generalizada: VoltarIFG 5.12Indução matemática Seja P(n) uma afirmação, para cada n ∈ . N N8 8 N 8 N N (1) Base da indução: Mostrar que P(n) verdadeira para n = n0 (3) Passo indutivo: Mostrar que P(k + 1) verdadeira, assumindo a hipótese de indução (2) Para aplicarmos a IF generalizada precisamos executar os três passos a seguir: 5.13Indução matemática: Indução forte generalizada (2) Hipótese de indução: Assumir que P(n0), P(n0 + 1), ... , P(k) são 8 verdadeiras ( k ≥ n0 ) Exemplo 3: Mostre que todo inteiro maior do que 1 é primo ou produto de primos. (Obs: primo é um inteiro maior do que 1, que só é divisível por 1 e por ele mesmo. Exemplos: 2, 3, 5, 7 são primos ) (1) Base da indução: P(2) : 2 é primo verdadeira 5.14Indução matemática: Indução forte generalizada Prova: Seja P(n) : n é primo ou produto de primos. (2) Hipótese de indução forte: P(i) é verdadeira para 2 ≤ i ≤ k Assuma que: i é primo ou produto de primos, 2 ≤ i ≤ k k + 1 é primo ou produto de primos = (3) Passo indutivo: P(i) verdadeira 2 ≤ i ≤ k => P(k + 1) verdadeira 5.15Indução matemática: Indução forte generalizada Desenvolvendo: Temos duas possibilidades mutuamente exclusivas (i) k + 1 é primo (ii) k + 1 não é primo Se (i) acontece então P(k + 1) é verdadeira Caso contrário (ii) acontece, então k + 1 não é primo 5.16Indução matemática: Indução forte generalizada k + 1 não é primo Então k + 1 pode ser escrito como: k + 1 = a . b onde 1 < a < k + 1 1 < b < k + 1 5.17Indução matemática: Indução forte generalizada Usando agora a hipótese de indução forte temos que: P(a) e P(b) são verdadeiras 1 < a ≤ k 1 < b ≤ k ou seja, a é primo ou produto de primos e b é primo ou produto de primos 5.18Indução matemática: Indução forte generalizada Então pelo princípio da indução forte generalizada P(n) : n é primo ou produto de primos n ∈ n > 1 8 N Logo k + 1 = a . b é produto de primos Logo P(k + 1) é verdadeira Resumo: Conceitos: - Base de indução: P(n) verdadeira n = n0 - Hipótese de indução: P(n0), (n0+1), ..., P(k) verdadeira => P(k + 1) verdadeira Sequência de Fibonacci Indução forte generalizada Em particular n0 = 1 : Indução forte 5.19Indução matemática Estrutura Exercícios: (1) Seja {an} a sequência definida por: a1 = 1 , a2 = 5 an+1 = an + 2an -1 n ≥ 3 Mostre que usando a indução forte an = 2 n + (-1)n (2) Seja {Fn} a sequência de Fibonacci. Mostre usando a indução forte que 5.20Indução matemática 8 n ≥ 2 8 N n ∈Fn = 1 1 + √5 n 1 1 − √5 n −__ √5 ______ 2 ______ 2 __ √5( )( ) 6.1Módulo: Princípios Aditivo e Multiplicativo Aula 6: Princípios Aditivo e Multiplicativo Princípios básicos de contagem: Conteúdo: Princípio Aditivo Princípio Multiplicativo Desenvolver as idéias e técnicas básicas para problemas de contagem. Reduzir um problema grande a vários problemas pequenos, usando os Princípios Aditivo e Multiplicativo. Objetivos: 6.2Princípios Aditivo e Multiplicativo Os problemas de contagem aparecem naturalmente no nosso dia a dia. Muitas vezes estamos apenas interessados em contar os elementos de um determinado conjunto, sem enumerá-los. Importância: No desenvolvimento de técnicas de contagem que veremos mais adiante, tais como: permutações, combinações, etc, estaremos usando basicamente os Princípios Aditivo e Multiplicativo. 6.3Princípios Aditivo e MultiplicativoExemplo 1: Dados quatro livros distintos de Matemática (M1, M2, M3, M4) e três livros distintos de Português (P1, P2, P3), de quantas maneiras podemos selecionar (escolher): a) Um livro (ou de Matemática ou de Português). b) Dois livros, sendo um de Matemática e outro de Português. Problemas de contagem: 6.4Princípios Aditivo e Multiplicativo Exemplo 1 (continuação): a) Um livro (ou de Matemática ou de Português) O livro de Matemática pode ser escolhido de 4 maneiras: O livro de Português pode ser escolhido de 3 maneiras: Número de maneiras: 4 + 3 = 7 livro M1 ou livro M2 ou livro M3 ou livro M4 livro P1 ou livro P2 ou livro P3 6.5Princípios Aditivo e Multiplicativo A = { , , , } B = { , , }M1 M2 M3 M4 P1 P2 P3 (M1, P1) (M1, P2) (M1, P3) (M2, P1) (M2, P2) (M2, P3) (M4, P2) (M3, P1) (M3, P2) (M3, P3) (M4, P1) Número de maneiras: 3 + 3 + 3 + 3 = 4 × 3 = 12 {C = }(M4, P3) PA Voltar 6.6Princípios Aditivo e Multiplicativo b) Dois livros, sendo um de Matemática e outro de Português. Exemplo 1 (continuação): Temos dois conjuntos: Resumindo a) De quantas maneiras podemos escolher um livro qualquer (ou de Matemática ou de Português)? Resposta: Temos 4 maneiras de escolher um livro de Matemática e 3 maneiras de escolher um livro de Português. Logo temos 4 + 3 = 7 maneiras de escolher um livro qualquer dentre os de Matemática e Português. 6.7Princípios Aditivo e Multiplicativo b) De quantas maneiras podemos escolher dois livros sendo um de Matemática e outro de Português? Resposta: Para cada livro de Matemática, temos 3 maneiras de escolher os livros de Português. Como temos 4 maneiras de escolher os livros de Matemática, teremos 3 × 4 = 12 maneiras de escolher um livro de Matemática e outro de Português. 6.8Princípios Aditivo e Multiplicativo Número de maneiras de escolher um item : 7 + 5 = 12 L = {L1, L2, ..., L7} B = {B1, B2, ..., B5} ou L1, ou L2, ou ... ou L7 → 7 maneiras ou B1, ou B2, ou ... ou B5 → 5 maneiras 6.9Princípios Aditivo e Multiplicativo Maria vai a uma papelaria para comprar lapiseira e borracha. Nessa papelaria há 7 tipos diferentes de lapiseiras e 5 tipos diferentes de borrachas. Exemplo 2: a) Se o dinheiro de Maria só dá para comprar um item, ou uma lapiseira ou uma borracha, de quantas maneiras diferentes ela pode fazer isso? . . . L1 B1 B2 B3 B4 B5 L2 B1 B2 B3 B4 B5 L7 B1 B2 B3 B4 B5 Observe que temos os pares: (L1, B1) (L1, B2) ... (L1, B5) , ... , (L7, B1) (L7, B2) ... (L7, B5) Número de maneiras de escolher 2 itens, sendo um item uma lapiseira e o outro uma borracha: 5 +...+ 5 = 5 × 7 = 35 6.10Princípios Aditivo e Multiplicativo Exemplo 2 (continuação): b) Suponha agora que Maria tem dinheiro para comprar 2 itens, sendo que ela quer uma lapiseira e uma borracha. De quantas maneiras diferentes ela pode fazer isso? 6.11 Resumindo Princípios Aditivo e Multiplicativo a) De quantas maneiras diferentes Maria pode comprar um item (ou uma lapiseira ou uma borracha)? Resposta: Ela tem 7 possibilidades de escolha de lapiseira e 4 possibilidades de escolha de borracha. Logo Maria tem 7 + 5 possibilidades diferentes de comprar ou uma lapiseira ou uma borracha. 6.12Princípios Aditivo e Multiplicativo b) De quantas maneiras diferentes Maria pode comprar 2 itens: uma lapiseira e uma borracha? Resposta: Para cada escolha de lapiseira, ela tem 5 escolhas de borracha. Como ela tem 7 escolhas de lapiseiras diferentes, ela terá 7 × 5 maneiras diferentes de comprar uma lapiseira e uma borracha. então |A ∪ B| = |A| + |B| Princípio Aditivo (para dois conjuntos) Se A e B são dois conjuntos disjuntos (A ∩ B = ∅), Outra notação usual n(A) = |A| Introdução ao Princípio Aditivo (PA): PA Voltar 6.13Princípios Aditivo e Multiplicativo 6.14Princípios Aditivo e Multiplicativo: Introdução ao PA Outra interpretação da formulação: Sejam A e B eventos mutuamente exclusivos. Se um evento A pode ocorrer de m maneiras e outro evento B pode ocorrer de n maneiras, então existem m + n maneiras em que algum desses dois eventos podem ocorrer. A ∩ B = ∅ |A| = n(A) = 4 |B| = n(B) = 3 Podemos identificar os conjuntos: A = { M1, M2, M3, M4 } B = { P1, P2, P3 } |A ∪ B| = |A| + |B| = 7 maneiras de escolher um livro qualquer, ou de Matemática ou de Português. Pelo P. A. temos 6.15Princípios Aditivo e Multiplicativo: Introdução ao PA Voltando ao exemplo 1: Dados quatro livros distintos de Matemática e três livros distintos de Português: a) De quantas maneiras podemos escolher um livro qualquer? 6.16Princípios Aditivo e Multiplicativo: Introdução ao PA Pelo P. A. Maria tem L ∪ B=L + B = 7 + 5 = 12 maneiras de escolher ou uma lapiseira ou uma borracha. L = {L1, L2, ..., L7} Identificando os conjuntos: B = {B1, B2, ..., B5} L ∩ B = ∅ L= 7 B= 5 Voltando ao exemplo 2: Na papelaria há 7 tipos diferentes de lapiseira e 5 tipos diferentes de borracha: a) De quantas maneiras Maria pode comprar um item? Introdução ao Princípio Multiplicativo (PM): Princípio Multiplicativo (para dois conjuntos) Se A é um conjunto com m elementos e B é um conjunto com n elementos então o conjunto A × B |A × B| = |A| . |B| = m × n A × B = { (a, b) | a ∈ A e b ∈ B } tem m × n elementos 6.17Princípios Aditivo e Multiplicativo Outra interpretação da formulação: Se um evento A pode ocorrer de m maneiras e um evento B pode ocorrer de n maneiras então o par de eventos, primeiro um e depois o outro, podem ocorrer de m × n maneiras. 6.18Princípios Aditivo e Multiplicativo: Introdução ao PM Pelo P. M. temos então A × B=A×B= 4 × 3 =12 maneiras de escolher dois livros sendo um de Matemática e outro de Português. O exemplo 2 b) vocês interpretam. 6.19Princípios Aditivo e Multiplicativo: Introdução ao PM Voltando ao exemplo 1: Dados quatro livros distintos de Matemática e três livros distintos de Português: b) De quantas maneiras podemos escolher 2 livros sendo um de Matemática e outro de Português? A = { M1, M2, M3, M4 } B = { P1, P2, P3 }|A| = 4 |B| = 3 Resposta Voltar A = B = { P1, P2, ... , P8 } |A| = 8 |A × B| = |A| × |A| = 8 × 8 = 64 6.20Princípios Aditivo e Multiplicativo: Introdução ao PM 8 × 8 (P1, P1) , (P1, P2) ... (P1, P7) , (P1, P8) (P2, P1) , (P2, P2) ... (P2, P7) , (P2, P8) (P8, P1) , (P8, P2) ... (P8, P7) , (P8, P8) ...... ...... ...... ...... Resposta: Uma pessoa pode entrar e sair do prédio de 64 maneiras. Exemplo 3: a) De quantas maneiras uma pessoa pode entrar e sair? Um prédio tem oito portas: Exemplo 3 (continuação): b) De quantas maneiras uma pessoa pode entrar por uma porta e sair por outra diferente? Observe: Se usarmos a porta P1 para entrar, ela não pode ser usada para sair. Resposta: Uma pessoa pode entrar por uma porta e sair por outra diferente de 56 maneiras. 8 × 7 (P1, P2) , (P1, P3) ... (P1, P7) , (P1, P8) (P2, P1) , (P2, P3) ... (P2, P7) , (P2, P8) (P8, P1) , (P8, P2) ... (P8, P6) , (P8, P7) ...... ...... ...... ...... Princípios Aditivo e Multiplicativo: Introdução ao PM 6.21 Formalização: A = { P1, P2, ... , P8 } , |A| = 8 C = A × A − D Exemplo 3 (continuação): D = { (P1, P1) , ... , (P8, P8) } , |D| = 8 |C| = |A| . |A| − |D| = 8 × 8 − 8 = 8 (8 − 1) = 8 . 7 (Princípio Multiplicativo) |C| = |A × A| − |D| (Princípio Aditivo) 6.22Princípios Aditivo e Multiplicativo:Introdução ao PM Interpretação: Exemplo 3 (continuação): a) De quantas maneiras uma pessoa pode entrar e sair? maneiras de entrar - 8 maneiras de sair - 8 => 8 × 8 = 64 b) De quantas maneiras uma pessoa pode entrar por uma porta e sair por outra diferente? maneiras de entrar - 8 maneiras de sair - 7 => 8 × 7 = 56 6.23Princípios Aditivo e Multiplicativo: Introdução ao PM Numa sala estão reunidos cinco homens, seis mulheres e quatro crianças. De quantas maneiras podemos selecionar: a) uma pessoa? b) um homem, uma mulher e uma criança? Exemplo 4: 6.24Princípios Aditivo e Multiplicativo: Introdução ao PM a) De quantas maneiras podemos selecionar uma pessoa? H = { h1, h2, h3, h4, h5 } M = { m1, m2, m3, m4, m5, m6 } C = { c1, c2, c3, c4 } H ∪ M ∪ C = { h1, h2, ... , h5, m1, m2, ... , m6, c1, ... , c4 } Exemplo 4 (continuação): |H| = 5 |M| = 6 |C| = 4 |H ∪ M ∪ C| = |H| ∪ |M| ∪ |C| = 5 + 6 + 4 = 15 H ∩ M = ∅ H ∩ C = ∅ M ∩ C = ∅ 6.25Princípios Aditivo e Multiplicativo: Introdução ao PM b) De quantas maneiras podemos selecionar um homem, uma mulher e uma criança? H × M × C = { (h, m, c) | h ∈ H, m ∈ M, c ∈ C } Exemplo 4 (continuação): 6.26Princípios Aditivo e Multiplicativo: Introdução ao PM H × M × C = { (h1, m1, c1), (h1, m2, c1), (h1, m3, c1), (h1, m4, c1), (h1, m5, c1), (h1, m6, c1), (h1, mb1, c2), (h1, m1, c3), (h1, m1, c4), ... } |H × M × C| = |H| × |M| × |C| = 5 × 6 × 4 = 120 Observação: |A1 ∪ A2 ∪ ... ∪ An| = |A1| + |A2| + ... + |An| = ∑ n i = 1 mi Se A1, A2, ... , An são conjuntos disjuntos dois a dois Extensão do Princípio Aditivo: ( Ai ∩ Aj = ∅ i ≠ j ) e |A1| = m1 , |A2| = m2 , ... , |An| = mn então o conjunto ∪ n i = 1 Ai = A1 ∪ A2 ∪ ... ∪ An possui m1 + m2 + ... + mn elementos 6.27Princípios Aditivo e Multiplicativo Sejam A1, A2, ... , An eventos mutuamente exclusivos. Se cada evento Ai pode ocorrer de mi maneiras então existem m1 + m2 + ... + mn maneiras em que algum desses n eventos podem ocorrer. Outra interpretação da formulação: 6.28Princípios Aditivo e Multiplicativo: Extensão ao PA Extensão do Princípio Multiplicativo: Sejam A1, A2, ... , An conjuntos tais que |A1| = m1 , |A2| = m2 , ... , |An| = mn |A1 × A2 × ... × An| = |A1| × |A2| × ... × |An| = ∏n i = 1 mi então o conjunto ∏ n i = 1 Ai = A1 × A2 × ... × An possui m1 × m2 × ... × mn 6.29Princípios Aditivo e Multiplicativo Se temos n eventos A1, A2, ... , An , onde cada evento Ai pode ocorrer de mi maneiras então existem m1 × m2 × ... × mn maneiras em que esses n eventos podem ocorrer sucessivamente. Outra interpretação da formulação: 6.30Princípios Aditivo e Multiplicativo: Extensão ao PM Exemplo 5: Uma bandeira é formada por três listras que devem ser coloridas usando-se apenas as cores: amarelo, branco, azul, de tal maneira que listras adjacentes não recebam a mesma cor. De quantos modos podemos colorir esta bandeira? Logo pelo PM temos 3 × 2 × 2 modos de colorir esta bandeira. L1 pode ser colorida de 3 modos L2 pode ser colorida de 2 modos (a cor usada em L1 não pode ser usada em L2) L3 pode ser colorida de 2 modos (a cor usada em L2 não pode ser usada em L3) L1 L2 L3 6.31Princípios Aditivo e Multiplicativo: Extensão ao PM Exemplo 6: Um teste de matemática consta de 20 perguntas para serem classificadas como Verdadeira ou Falsa. Quantos são os possíveis gabaritos para este teste? Logo pelo PM temos 2 × 2 × ... × 2 = 2 20 gabaritos Resposta: Cada pergunta tem duas possibilidades de resposta: Verdadeiro ou Falso ... ... P1 − 2 possibilidades P2 − 2 possibilidades P20 − 2 possibilidades 6.32Princípios Aditivo e Multiplicativo: Extensão ao PM Exemplo 7: Considerando os algarismos 1, 2, 3, 4, 5 e 6, quantos números naturais de três algarismos distintos podem ser formados? P1 - posição das centenas P2 - posição das dezenas P3 - posição das unidades Para formar números naturais de três algarismos, podemos considerar que temos três posições a serem preenchidas: P1 P2 P3___ ___ ___ 6.33Princípios Aditivo e Multiplicativo: Extensão ao PM Exemplo de um número formado Logo pelo PM temos 6 × 5 × 4 = 120 números naturais de três algarismos distintos formados com os algarismos 1, 2, 3, 4, 5 e 6. Exemplo 7 (continuação): 3 6 5___ ___ ___ 6 possibilidades 1 o P1 5 possibilidades 2 o P2 4 possibilidades 3 o P3___ ___ ___ 6.34Princípios Aditivo e Multiplicativo: Extensão ao PM Exemplo 8: Quantos números naturais de três algarismos distintos (na base 10) existem? Observação: Estamos considerando agora os algarismos 0, 1, 2, ... , 9. Logo pelo PM temos 9 × 9 × 8 números naturais de três algarismos distintos. P1 P2 P3 Na posição P1 temos 9 possibilidades (estamos excluindo o zero) Na posição P2 temos 9 possibilidades (diferente do anterior) Na posição P3 temos 8 possibilidades (diferente dos dois anteriores) ___ ___ ___ 6.35Princípios Aditivo e Multiplicativo: Extensão ao PM E se neste exemplo em vez de começarmos analisando a posição P1, começassemos pela P3 ? P1 P2 P3 1 o 2 o 3 o ___ ___ ___ Exemplo 8 (continuação): Na posição P3 temos 10 possibilidades Na posição P2 temos 9 possibilidades (diferente do anterior) Na posição P1 temos 8 (se o algarismo zero já tiver sido usado) ou 7 (caso contrário) 6.36Princípios Aditivo e Multiplicativo: Extensão ao PM Quebramos o problema em dois: 1 o ) Ignoramos o fato do zero não estar na posição P1 e contamos todas as possibilidades (com ele incluído) Logo pelo PM temos 10 × 9 × 8 = 720 números de três algarismos distintos onde o zero pode estar na posição P1 Exemplo 8 (continuação): P1 P2 P3 Na posição P3 temos 10 possibilidades Na posição P2 temos 9 possibilidades Na posição P1 temos 8 possibilidades ___ ___ ___ 6.37Princípios Aditivo e Multiplicativo: Extensão ao PM 2 o ) Contamos os números de três algarismos distintos que têm apenas o zero na posição P1 Temos então 720 - 72 = 648 números naturais de três algarismos distintos. Logo pelo PM temos 1 × 9 × 8 = 72 números de três algarismos distintos que tem apenas o zero na posição P1 Na posição P1 temos 1 possibilidade Na posição P2 temos 9 possibilidades Na posição P3 temos 8 possibilidades P1 P2 P3___ ___ ___ 6.38Princípios Aditivo e Multiplicativo: Extensão ao PM Resumo: Sejam A1, A2, ... , An conjuntos 6.39Princípios Aditivo e Multiplicativo Princípio Aditivo Se Ai ∩ Aj = ∅ , i ≠ j e A = ∪ n i = 1 Ai = A1 ∪ A2 ∪ ... ∪ An então |A| = |A1| + |A2| + ... + |An| Princípio Multiplicativo Se B = ∏ n i = 1 Ai = A1 × A2 × ... × An então |B| = |A1| × |A2| × ... × |An| Módulo: Aplicações dos princípios aditivo e multiplicativo Permutações simples Permutações circulares Arranjos simples Combinações simples Permutações com repetições Arranjos com repetições Combinações com repetições 7.1 Aplicações dos princípios aditivo e multiplicativo Objetivo: Obtenção de uma técnica de contagem para cada problema (de permutação, de arranjo, de combinação) a partir dos princípios aditivo e multiplicativo (isto é, sem a enumeração explícita dos seus elementos). 7.2 As permutações, os arranjos e as combinações aparecem na modelagem de problemas provenientes, principalmente, das seguintes áreas: Importância:probabilidades teoria de grafos análise de algoritmos 7.3Aplicações dos princípios aditivo e multiplicativo Exemplos: • Algoritmos randômicos (probabilísticos) • Armazenamento de informações em banco de dados nos computadores • Análise do comportamento de um algoritmo através da contagem das suas operações. Introdução Conteúdo: Fatorial de um número Permutação simples Número de permutações simples Permutação circular Número de permutações circulares Aula 7: Permutações simples e circulares 7.4Aplicações dos princípios aditivo e multiplicativo Introdução: Exemplo 1: (a) Comprei três canetas de distintas cores, azul, verde e branca, para dar de presente a três amigos, João, Rita e Luiza. (b) Comprei mais uma caneta, de cor preta, pois tinha esquecido do Gabriel. Em cada caso, de quantas maneiras diferentes eu posso distribuí-las? 7.5Permutações simples e circulares Resolução: 7.6Permutações simples e circulares: Introdução João Rita Luiza(a) azul verde branca ______ ___ ___ verde branca ______ ___ ___ azul branca ______ ___ ___ azul verde ______ ______ branca verde ______ ______ branca azul ______ ______ verde azul Número de possibilidades: 3 × 2 × 1 (b) João Rita Luiza Gabriel azul branca preta 7.7Permutações simples e circulares: Introdução verde 4 × 3 × 2 × 1Possibilidades: branca preta branca verde preta verde branca verde branca preta azul verde branca preta branca verde preta verde verde preta verde branca preta azul preta branca verde branca verde preta branca verde azul preta preta verde verde branca verde azul preta branca verde preta verde branca preta branca azul preta verde ______ ___ ___ azul verde branca ______ ___ ___ azul preta branca ______ ___ ___ verde preta branca ______ ___ ___ Resumindo Problema: De quantas maneiras diferentes eu posso distribuir as canetas: (a) azul, verde e branca (b) azul, verde, branca e preta 7.8Permutações simples e circulares: Introdução Resposta: Eu posso reparti-las (a) de 6 maneiras diferentes (b) de 24 maneiras diferentes 24 = 4 × 3 × 2 × 1 Observação: 6 = 3 × 2 × 1 n! := n(n − 1)(n − 2) ... 1 Fatorial de um número: Definição O fatorial de um número natural n, denotado por n! , é o produto dos n primeiros números naturais: 0! := 1 Convenção: 7.9Permutações simples e circulares 3! = 3 × 2 × 1 4! = 4 × 3 × 2 × 1 Ilustração Exemplo 2: Quantos números distintos de 5 algarismos podem se formar com os dígitos 3, 5, 7, 8 e 9 ? 7.10Permutações simples e circulares: Fatorial de um número Podem se formar 5! = 120 números diferentes de 5 algarismos Resposta: = 5!15 4 3 2 Resolução: Possibilidades: p5p1 p2 p3 p4 ________ ____ ____ ____ posições dos dígitos no número 3 5 7 8 9 3 7 8 9 5 3 8 9 7 3 8 9 83 Características dos exemplos: Os elementos considerados são diferentes Cada troca de posição (de ordem) dos elementos corresponde a uma possibilidade Na obtenção do número de possibilidades aplica-se os princípios aditivo e multiplicativo 7.11Permutações simples e circulares: Fatorial de um número Permutação simples: Definição Dados n objetos distintos, a1, a2, ... , an, uma permutação simples é uma ordenação desses elementos. Ilustração Dados os dígitos 3, 5, 7, 8 e 9, 87539 é uma permutação simples de 3, 5, 7, 8, 9. 7.12Permutações simples e circulares Prove esta propriedade usando indução Número de permutações simples: Problema 7.13Permutações simples e circulares Dados n elementos distintos, a1, a2, ... , an, encontrar o número de permutações simples O número de permutações simples de n elementos distintos, denominado Pn, é dado por: Pn = n! = n(n−1) ... 1 Propriedade Prova: Seja P(n): Pn = n! (2) Hipótese de indução: Assume P(k): Pk = k! é verdadeira (1) Base de indução: P(1): P1 = 1! = 1 verdadeira VoltarProva 7.14Permutações simples: Número de permutações simples 7.15 VoltarProva Permutações simples: Número de permutações simples (3) Passo indutivo: Mostrar que Pk+1 = (k + 1)! é verdadeira Provemos que Pk+1 = (k + 1)! é verdadeira: Sejam a1, a2, ... , ak, ak+1 elementos distintos. Na última posição pk+1 tem-se (k + 1) possibilidades ___ ___ .... ___ ___ a1 . . . ak+1 pk+1 pk p1 p2 então, para (k+1) possibilidades em pk+1 tem-se (k+1) Pk permutações das posições pk+1 Fixado um elemento na posição pk+1 restam k elementos para ordenar em k posições (permutação de elementos): para 1 possibilidade em pk+1 tem-se Pk permutações das posições p1, ... , pk Logo, Pk+1 = (k + 1) Pk = (k + 1) k! = (k + 1)! é verdadeira HI Portanto, P(n): Pn = n! é verdadeira para todo n ∈ N Exemplo 3: Vários amigos combinaram passar o dia no clube. Planejaram ir para a piscina, fazer um churrasco e jogar volei. De quantas maneiras diferentes podem programar essas atividades? 7.16Permutações simples: Número de permutações simples número de programas possíveis: P3 = 3! = 6 Resolução: elementos: p (piscina) c (churrasco) v (volei) Resposta: Eles podem programar as atividades planejadas de 6 maneiras diferentes. PS Voltar Lembremos que algarismo é cada um dos símbolos usados na representação de um número no sistema decimal de numeração. 7.17Permutações simples: Número de permutações simples Conclusão: Os números de 5 algarismos não iniciam com 0. 57809 → 5 . 10 4 + 7 . 10 3 + 8 . 10 2 + 0 . 10 1 + 9 . 10 0 05789 é uma ordenação de 5 dígitos que não corresponde à representação no sistema decimal 5789 corresponde à representação no sistema decimal Ilustração: Exemplo 4: Quantos números distintos de 5 algarismos podem se formar com os dígitos 0, 5, 7, 8 e 9 ? Exemplo 4 (resolução): dígitos do problema: 0, 5, 7, 8, 9 Raciocínio 1: ________ ____ ____ ____ 0 posições dos dígitos no número 7.18Permutações simples: Número de permutações simples Resposta: Podem se formar 96 números diferentes de 5 algarismos com 0, 5, 7, 8 e 9. - Na primeira posição temos 4 possibilidades (excluimos o 0) - Nas posições restantes temos 4 posições para 4 dígitos incluindo o 0, ou seja, P4 possibilidades Possibilidades 4 × P4 = 4 . 4! = 96 Exemplo 4 (raciocínio 2): Usamos o conceito de complemento. U: conjunto universo := conjunto das ordenações de 5 dígitos formados com 0, 5, 7, 8 e 9 sem repetição (05798 ∈ U) 5! − 4! = 5.4! − 4! = (5 − 1) 4! = 4.4!Observação: A = U − B número de possibilidades = |A| = |U| − |B| |U| = P5 , |B| = P4 número de possibilidades = P5 − P4 = 5! − 4! = 96 7.19Permutações simples: Número de permutações simples A := conjunto dos números de 5 algarismos formados com 0, 5, 7, 8 e 9 = conjunto dos elementos de U que não iniciam com 0 B := conjunto dos elementos de U que iniciam com 0 Exemplo 5: Nove amigos assistem a um show, com lugares marcados consecutivos. As mulheres (quatro) se sentam todas juntas e os homens também. De quantas
Compartilhar