Baixe o app para aproveitar ainda mais
Prévia do material em texto
Instituto Federal de Educação, Ciência e Tecnologia de Pernambuco Edição 2008 Recife-PE Licenciatura em Matemática Elementos de Lógica e Teoria dos Conjuntos José Arimatéia Rocha livro_matematica_M01.indd 34livro_matematica_M01.indd 34 3/12/2007 16:52:453/12/2007 16:52:45 Presidência da República Federativa do Brasil Ministério da Educação Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES Este Caderno foi elaborado em parceria entre o Instituto Federal de Educação, Ciência e Tecnologiade Pernambuco - IFPE e a Universidade Aberta do Brasil - UAB Equipe de Elaboração Coordenação do Curso Maria de Fátima Neves Cabral Supervisão de Tutoria Sônia Quintela Carneiro Logística de Conteúdo Giselle Tereza Cunha de Araújo Maridiane Viana Coordenação Institucional Reitoria Pró-Reitoria de Ensino Diretoria de Educação a Distância Pró-Reitoria de Extensão Pró-Reitoria de Pesquisa e Inovação Pró-Reitoria de Administração e Planejamento Diagramação Luciano Aguiar Leila Nunes Projeto Gráfi co Eliana Virgínia Vieira de Melo Projeto Gráfi co - Capa Verônica Emília Campos Freire Giselle Tereza Cunha de Araújo Revisão Linguística Leona Maria de Sá livro_matematica_M01.indd 34livro_matematica_M01.indd 34 3/12/2007 16:52:453/12/2007 16:52:45 Módulo 1 Disciplina: Elementos de Lógica e Teoria dos Conjuntos livro_matematica_M01.indd 33livro_matematica_M01.indd 33 3/12/2007 16:52:453/12/2007 16:52:45 livro_matematica_M01.indd 34livro_matematica_M01.indd 34 3/12/2007 16:52:453/12/2007 16:52:45 35 A Linguagem da Matemática Meta: Apresentar as bases de como se organiza o discurso na matemática Objetivos: Descrever sentenças atômicas1) Definir o valor lógico de uma sentença e relacioná-lo com o Princípio do 2) Terceiro Excluído Compreender e fazer uso de alguns símbolos de uso freqüente em 3) Matemática. Entender a noção de Conjunto em Matemática como conceito unificador 4) de sua linguagem. 1. Introdução Neste módulo consideramos de modo elementar a organização da linguagem matemática. Nele você estudará as sentenças ou proposições do ponto de vista de como um Matemático às considera e de como um professor de mate- mática deve fazer uso de modo a organizar o pensamento de seu aluno. 2. Sentenças Atômicas Consideramos as afirmações traduzidas abaixo: (a) 3 é um número ímpar. (b) 5 é maior que 8. (c) Hoje é sábado. (d) Plutão é um Planeta. (e) Recife é a capital do estado de Pernambuco. (f) Todo homem tem alma. Observe que algumas das afirmações acima exprimem fatos que você sabe serem verdadeiros como, por exemplo, (a) e (e). A afirmativa (b) é evidentemente falsa. As demais afirmativas têm sua veracidade dependente Aristóteles (384 a.C- 322 a.C) foi um dos primeiros pensadores a escrever sobre a lógica. Em seu “Organon”, obra clássica de Filosofia Grega, ele projeta construir um instrumento para construção segura da ciência. livro_matematica_M01.indd 35livro_matematica_M01.indd 35 3/12/2007 16:52:453/12/2007 16:52:45 36 de certas considerações ou convenções humanas. Por exemplo, até bem pouco tempo atrás (d) era verdadeira mais agora não é mais (Veja quadro ao lado), a afirmativa (c) depende do dia que você tiver fazendo a leitura desse texto enquanto que (f) depende de suas considerações pessoais. De um modo geral, uma proposição ou sentença transmite pensamentos as quais exprimem juízos a respeito de certos objetos ou entes. Tais juízos podem ser verdadeiros, falsos ou indecidíveis quanto a sua vera- cidade ou falsidade. Em Matemática, iremos considerar sentenças sobre as quais possamos decidir se são verdadeiras ou falsas. Logo, estão excluídas de nosso estudo: 1) As sentenças interrogativas tipo “Que dia é hoje?” 2) As sentenças exclamativas tipo “Que dia calorento!” 3) As sentenças imperativas tipo “Dane-se você e sua corja”. Assim, a estrutura básica de uma sentença matemática é: SUJEITO + PREDICADO em que o predicado descreve algum fato sobre o sujeito para o qual é possí- vel decidir se o fato é verdadeiro ou falso, como mostram os exemplos: (g) 5 é um número primo. (h) é um número racional (i) 2 é maior que 1. Tal tipo de sentença chamaremos de Sentença Atômica ou Simples. Atividade 1: Pesquise o significado dos termos Sujeito e Predicado e para cada uma das sentenças (a,b,c,d,e,f,g,h,i) acima, diga qual o sujeito e qual o predicado. 3. Valor Lógico De Uma Proposição Não é só a estrutura “sujeito + predicado” que determina uma sentença matemática. O fato mais relevante é a possibilidade de podermos decidir o chamado valor lógico da sentença, isto é, se ela é verdadeira ou falsa. Tal fato é chamado Princípio do Terceiro Excluído (PTE) pelos matemáticos e assume um papel fundamental na chamada lógica matemática. Nas ciências, em geral, determi- nados conceitos podem mudar. Em matemática este é um fato difícil de ocorrer, acontecendo em geral, quando uma estrutura nova é observada permeando o conceito. Plutão perde o status de Planeta Fonte: Folha Online 15/08/2006 livro_matematica_M01.indd 36livro_matematica_M01.indd 36 3/12/2007 16:52:453/12/2007 16:52:45 37 No que segue iremos representar as sentenças por letras latinas minúsculas, com p, q, r, ... e seus valores lógicos por V(p), V(q), V(r), .... Veja os exemplos abaixo: p: 3 é maior que 2. q: 5 é a metade de 8. No caso V(p)= v e V(q)=f, ou seja, os valores lógicos das sentenças p e q são respectivamente v (verdadeiro) e f (falso). Atividade 2: Complete com os valores lógicos das sentenças dadas abaixo. a: 15 é um número primo V(a) = f b: 2 =1,41 V(b) = ___ c: V(c) = ___ d: V(d) = ___ e: V(e) = ___ f: V(f) = ___ g: Todo quadrado é retângulo V(g) = ___ h: V(h) = ___ i: Dois triângulos semelhantes têm a mesma área V(i) = ___ j: Se x é um número então V(j) = ___ 4. Os Símbolos da Matemática A linguagem matemática escrita contém muitos símbolos tais como: = significa “é igual a” < significa “é menor que” significa “é menor ou igual que” > significa “é maior que” significa “é maior ou igual que” TRISTEZA NO CÉU No céu também há uma hora melancólica. Hora difícil, em que a dúvida penetra as almas. Por que fiz o mundo? Deus se pergunta e se responde: não sei. Os anjos olham-no com reprovação, e plumas caem. Todas as hipóteses: a graça, a eter- nidade, o amor caem, são plumas. Outra pluma, o céu se desfaz. Tão manso, nenhum fragor denun- cia o momento entre tudo e nada, ou seja, a tristeza de Deus. In: Drummond. Antologia Poética.Rio de Janeiro: José Olympio, 1978. Na poesia, a linguagem tem outros objetivos. Ela visa, por exemplo, provocar emoções. Veja: Não há preocupação sobre a Verdade ou falsidade dos Versos acima de Carlos Drummond de Andrade. (1902-1987) A escrita V(d) = f significa que o valor lógica da afirmativa (d) é falso. Quanta economia de palavras conseguimos com tal notação! ATENÇÃO livro_matematica_M01.indd 37livro_matematica_M01.indd 37 3/12/2007 16:52:453/12/2007 16:52:45 38 O DIA O DIA EM QUE UM MATEMÁTICO PROVOU A EXISTÊNCIA DE DEUS. Em uma disputa famosa entre o filosófo Diderot (1713-1784) e o matemático Euler (1707-1783) sobre a existência de Deus, este último coloca a seguinte sentença para o filosófo redargüir: , logo Deus existe! Segundo Hogben (1950) “Como acontece a muitos de nós, Diderot ficou cheio de dedos quando defrontado com uma frase na linguagem das grandezas. Por isso, retirou-se abruptamentedo salão, debaixo do escárneo dos presentes, fechou-se em seus aposentos, pediu seu passaporte e tratou de partir para França.”(p.19) O exemplo acima mostra que os símbolos matemáticos podem nos afastar da compreensão de um fato, logo devemos ter cuidado com seu uso em sala de aula. Tais símbolos, assim como outros, têm significado universal. Você pode en-contrá-los em livros matemáticos americanos, italianos, alemães, etc. Boa parte da tarefa de compreender matemática está associada a apro- priação de uso de símbolos e você deve dedicar atenção especial a isso. Na tabela abaixo indicamos alguns símbolos de uso freqüente em matemá- tica e seu significado. Você deve consultá-la sempre que achar necessário. 5. A Noção de Conjunto De um ponto de vista de sua estrutura interna, a Matemática costuma organi- zar seus objetos de estudo em conjuntos. Assim, por exemplo, os pontos do plano são vistos como um conjunto, o conjunto dos pontos do plano. Neste caso, para indicar que um ponto está em um conjunto, usa-se o símbolo . Desta forma se designarmos o conjunto dos pontos do plano por E, a sen- tença P E (lê-se P pertence a E) significa que P é um ponto do plano E. Do mesmo modo, Q ∉ E (lê-se Q não pertence a E) significa que Q não é um ponto de E. livro_matematica_M01.indd 38livro_matematica_M01.indd 38 3/12/2007 16:52:453/12/2007 16:52:45 39 É usual, representar-se um conjunto por uma letra maiúscula. Os objetos do conjunto, também chamados de elementos, são colocados entre chaves e separados por vírgulas, sem repetição e numa ordem qualquer. Por exemplo, A={a,e,i,o,u} é uma maneira de indicar que A é o conjunto cujos elementos são as vogais. Muito freqüentemente, um conjunto matemático é formado por uma infinidade de elementos. Por isso, também podemos indicar o conjunto no formato. X= {x | x satisfaz a propriedade P} Tal tipo de representação é chamada Representação por Compreensão. No caso, P é uma propriedade que caracteriza os elementos de X enquanto x designa um elemento genérico do conjunto X. Veja, isto não quer dizer que x X, mas simplesmente que x representa um elemento qualquer de X. Ademais é freqüente o uso de símbolos especiais para designar certos con- juntos de objetos matemáticos. Por exemplo: N → Conjunto dos Números Naturais, isto é N = {0, 1, 2, 3, ...} Z → Conjunto dos Números Inteiros, isto é Z = {..., -3, -2, -1, 0, 1, 2, 3, ...} Q → Conjunto dos Números Racionais, portanto Q = Treine tais considerações nas atividades abaixo. Atividade 3: Assinale V (verdadeiro) ou F(falso) de acordo com as afirmati- vas abaixo: ( ) 2 {1,2,3} ( ) 5 {13,14,15} ( ) 0 ∉ {10} ( ) – 3 {1,2,3} ( ) a {vogal} Didaticamente, alguns autores falam em representação por extensão de um conjunto, aquela que indicamos seus elementos separados por virgula. Também podemos representar conjuntos por diagramas como o descrito abaixo Fig 3. A representação do conjunto das vogais por diagrama. livro_matematica_M01.indd 39livro_matematica_M01.indd 39 3/12/2007 16:52:453/12/2007 16:52:45 40 DICAS DE ESTUDO Você está com o objetivo bem relevante para sua vida: Fazer um curso de Licenciatura em Matemática a distância. É fundamental que você organize seu tempo! Aconselhamos que: * Estabeleça horários de estudo individual diariamente * Reúna-se com um grupo de colegas igualmente matriculados no curso uma ou duas vezes por semana * Consulte seus tutores a distância sempre que dúvidas surgirem * Use os momentos de tutoria presencial para dirimir suas duvidas * Faça um diagrama dos objetivos propostos para cada disciplina e reflita sobre seu desempenho nas atividades propostas. ( ) 2 {1,{2},3} ( ) Recife { x | x é cidade de Pernambuco} Observação: Uma vez admitida a representação {x | x satisfaz a proprie- dade P} podemos escrever {x | x x}. Como não existe x tal que x x, um tal conjunto é dito Conjunto Vazio sendo representado pelo símbolo . Da mesma forma podemos indicar conjuntos com um único elemento como, por exemplo, {x | x é um número inteiro e 2 < x < 4}. Conjuntos como estes – que têm um único elemento – são chamados conjuntos unitários. Portanto, a idéia matemática de conjunto, amplia aquela que se tem na linguagem comum, sinônima de coleção. Atividade 4: Para cada sentença indicada à esquerda do quadro abaixo indi- que uma possibilidade de leitura no lado direito do quadro. Atividade 5: Para cada sentença indicada no quadro acima, informe qual o valor lógico que você acha que ela tem (Discuta essa questão com seus colegas e em caso de dúvida, consulte seu tutor). livro_matematica_M01.indd 40livro_matematica_M01.indd 40 3/12/2007 16:52:453/12/2007 16:52:45 41 Resumo 1. As sentenças simples (atômicas) em Matemática têm a forma básica “sujeito+predicado” e admitem um único valor lógico (verdadeiro ou falso); 2. Se p é uma sentença então V(p) é o modo como se indica seu valor lógico. 3. Compreender o uso dos símbolos especiais em matemática é parte impor- tante da tarefa de compreender matemática. 4. A idéia de conjunto é básica em Matemática e amplia a idéia que temos de coleção.São considerados conjuntos com um único elemento, chamados conjuntos unitários e até mesmo um conjunto que não tem elemento, cha- mado vazio. Auto-avaliação Muna-se de lápis e papel e em um lugar tranqüilo tente resolver as seguin- tes questões. As respostas para elas podem ser encontradas ao final deste caderno. Só as consulte após ter escrito todas as respostas. 1. Traduza para a linguagem corrente as seguintes sentenças matemáticas: a. b. c. d. 2. Indique qual o valor lógico das sentenças acima. 3. Traduza para forma simbólica matemática as seguintes sentenças: a. Todo o número natural é um número racional. livro_matematica_M01.indd 41livro_matematica_M01.indd 41 3/12/2007 16:52:453/12/2007 16:52:45 42 b. Existe um número racional que não é inteiro. c. Se x é um inteiro par então x2 é um inteiro par. d. x é um inteiro impar se, e somente se x2 também é um inteiro impar. 4. Indique o valor lógico de cada uma das sentenças da questão 3. 5. Escreva explicitamente os elementos dos seguintes conjuntos: A = B = C = livro_matematica_M01.indd 42livro_matematica_M01.indd 42 3/12/2007 16:52:453/12/2007 16:52:45 43 Bibliografi a ALENCAR FILHO, Edgar. Iniciação a Lógica Matemática. São Paulo: Nobel, 1981. ANDRADE, Carlos Drummond de. Antologia Poética. 12 ed. Rio de Janeiro: J. Olimpio, 1978. BOYER, Carl B. História da Matemática. São Paulo: Edgar Blücher, 1974. CASTRUCI, Benedito. Elementos da Teoria dos Conjuntos. São Paulo: Nobel, 1972. HALMOS, P. R. Teoria Ingênua dos conjuntos.São Paulo: Polígono, 1977. HOGBEN, Lancelot. Maravilhas da Matemática: influência e função da mate- mática nos conhecimentos humanos. Tradução: Paulo Moreira da Silva. 2ºed. São Paulo: Globo,1950. LIPSCHUTZ, Seymour. Teoria dos conjuntos. São Paulo: Ao Livro Técnico S.A, 1980. MONTEIRO, L. H. Jacy. Iniciação as estruturas algébricas. São Paulo: Nobel, 1973. Referência Bibliográfi ca FOLHA ONLINE. Conferência decide se Plutão é planeta. Figura publi- cada em 15/08/2006 – 12h03 <http://www1.folha.uol.com.br/folha/ciencia/ ult306u15023.shtml> acessada em 14/02/2007 as 10h30 RUIZA, M.(dir.) Figura publicada na pagina Biografías y Vidas, São Francisco, Barcelona 2004. <http://www.biografiasyvidas.com/biografia/a/ aristoteles.htm> acessada em 14/02/2007 as 10h35 livro_matematica_M01.indd 43livro_matematica_M01.indd 43 3/12/2007 16:52:453/12/2007 16:52:45 livro_matematica_M01.indd 44livro_matematica_M01.indd 44 3/12/2007 16:52:453/12/200716:52:45 Módulo 2 Disciplina: Elementos de Lógica e Teoria dos Conjuntos livro_mat_mod2.indd 31livro_mat_mod2.indd 31 4/12/2007 15:03:154/12/2007 15:03:15 livro_mat_mod2.indd 32livro_mat_mod2.indd 32 4/12/2007 15:03:154/12/2007 15:03:15 33 Sentenças Compostas Objetivos 1. Definir a conjunção e a disjunção de sentenças lógicas; 2. Definir a união de conjuntos e a intersecção de conjunto; 3. Relacionar tais operações de conjuntos com as operações lógicas correspondentes; 4. Inferir as propriedades de tais operações. 1. Introdução Continuaremos desse modo a apresentação de como a linguagem matemá- tica se organiza. Desta feita, consideraremos a composição de sentenças através dos conectivos: “ou” (representado pelo símbolo ∨) e “e” (represen- tado por ∧). Relacionaremos também tais conectivos com as operações de união e de intersecção de conjuntos. 2. A Disjunção e a Conjunção Lógicas Consideremos as sentenças: p: Recife é a capital do frevo. q: Recife é a cidade mais populosa de Pernambuco. Com elas, podemos compor as seguintes sentenças: p ∨ q: Recife é a capital do frevo ou é a cidade mais populosa de Pernambuco. p ∧ q: Recife é a capital do frevo e é a cidade mais populosa de Pernambuco. A sentença p ∨ q é chamada disjunção da sentença p com a sentença q. Analogamente, a sentença p ∧ q é chamada conjunção da sentença p com a sentença q. Os conectivos “ou” (∨) e “e” (∧) são usados na matemática como modo de compor sentenças. De fato, eles são considerados como uma espécie de Dicas de Estudo Uma regra básica, para quem quer aprender matemática, é não acumular dúvidas. Palavras, cujo significado você desconhece, devem ser consultadas nos dicionários ou, ainda, ser solucionadas com os seus tutores ou professores. Por exemplo: Você sabe o que é conectivo? Meta Indicar modos básicos de composição de sentenças matemáticas. George Boole (1815-1864) O matemático G. Boole publicou, em 1847, The Mathematical Analysis of Logic, onde fundamentou as bases da lógica moderna. livro_mat_mod2.indd 33livro_mat_mod2.indd 33 4/12/2007 15:03:154/12/2007 15:03:15 34 produtores de sentenças. Mais tarde, em nosso curso, definiremos a noção de operação caracterizando-os como operadores lógicos. No momento, devemos nos preocupar como associar os valores lógicos (verdadeiro ou falso) a tais sentenças compostas, a partir dos valores lógicos das senten- ças dadas. Isto é feito com a construção das chamadas tabelas lógicas, as quais analisam todas as possibilidades de valores lógicos para as sentenças. Postulamos que: 1) p ∨ q é falso se somente se tanto p quanto q são sentenças falsas. 2) p ∧ q é verdadeiro se somente se ambas as sentenças p e q são verda- deiras. Com tais postulados, podemos compor as seguintes tabelas lógicas para a disjunção e para conjunção. p q p ∨ q V V V V F V F V V F F F p q p ∧ q V V V V F F F V F F F F Atividade 1: Considere dado que a sentença p: João é médico é verdadeira, enquanto que a sentença q: João é professor é falsa. Qual o valor lógico para as sentenças p ∨ q: João é médico ou professor? p ∧ q: João é médico e professor? Respostas: V (p ∨ q) = V (p ∧ q) = A partir de tabelas lógicas, é fácil inferir se os operadores lógicos possuem determinadas propriedades. Por exemplo, mostraremos, a seguir, que a conjunção é comutativa, isto é, que p ∨ q é equivalente a q ∨ p. Siga as orientações dadas abaixo: Passo 1: Construindo a tabela lógica para p ∨ q. ATENÇÃO! LEMBRE: Cada sentença tem um único valor lógico V ou F. Assim, para duas sentenças, temos 2 x 2 = 4 possibilidades de análise. ATENÇÃO! LEMBRE: O “ou” só é falso se ambas as sentenças forem falsas. livro_mat_mod2.indd 34livro_mat_mod2.indd 34 4/12/2007 15:03:154/12/2007 15:03:15 35 p q p ∨ q V V V V F V F V V F F F Passo 2: Construindo a tabela lógica para q ∨ p. q p q ∨ p V V V V F V F V V F F F Passo 3: Comparamos os resultados obtidos para “p∨q” e para “q∨p”. A seqüência de valores lógicos encontrados na terceira coluna de ambas as tabelas, quando lidos de cima para baixo é a mesma, o que significa que as sentenças “p∨q” e “q∨p” são logicamente equivalentes. Escrevemos: p ∨ q ⇔ q ∨ p (lê-se: p∨q equivale a q∨p) Atividade 2: Verifique que p ∧ q ⇔ q ∧ p. Passo 1: Construindo a tabela lógica para p ∧ q. p q p ∧ q V V V F F V F F Passo 2: Construindo a tabela lógica para q ∧ p. q p q ∧ p V V V F F V F F livro_mat_mod2.indd 35livro_mat_mod2.indd 35 4/12/2007 15:03:164/12/2007 15:03:16 36 Passo 3: Comparando os valores lógicos obtidos para p∧q e q ∧ p, indique as seqüências encontradas para: p ∧ q: q ∧ p: Uma questão interessante é a de determinarmos o número de linhas na tabela lógica, a partir do número de sentenças dadas para análise. Como sabemos, para cada sentença, temos duas possibilidades: V ou F. Assim, o total de análise possível para duas sentenças é 422 =× possibilidades, como mostram as tabelas acima. Para três sentenças, haverá 8222 =×× possibilidades de análises. Utilizemos este fato para mostrar que a conjunção é associativa, isto é, que: (p ∧ q) ∧ r = p ∧ (q ∧ r) Quaisquer que sejam as sentenças p, q e r. Passo 1: Construção da tabela lógica para (p ∧ q) ∧ r. p q p ∧ q r (p ∧ q) ∧ r V V V V V V V V F V V F F V F V F F F F F V F V F F V F F F F F F V F F F F F F Passo 2: Construção da tabela lógica para p ∧ (q ∧ r). p q r q ∧ r p ∧ (q ∧ r) V V V V V V V F F F V F V F F V F F F F F V V V F F V F F F F F V F F F F F F F Passo 3: Comparação dos valores lógicos. Observamos que a última coluna de ambas as tabelas contém a mesma seqüência: V, F, F, F, F, F, F, F, F. Portanto, (p ∧ q) ∧ r = p ∧ (q ∧ r) IMPORTANTE! SINAIS DE AGRUPAMENTOS Em matemática, quando se têm várias operações a executar, é usual indicar-se com o uso de parênteses, colchetes ou chaves a prioridade **com que se deve realizá-las. O convencionado é de que, primeiro, se resolvem as operações entre parênteses, depois aquelas entre colchetes e, por fim, as entre chaves. Por exemplo, na investigação do valor lógico de uma sentença do tipo {p ∧ [q ∧ (r ∨ s)]} ∨ t, primeiro, analisaríamos r ∨ s, depois, q ∧ (r ∨ s), em seguida, p ∧ [q∧(r∨s)] , para por fim, concluir a análise. livro_mat_mod2.indd 36livro_mat_mod2.indd 36 4/12/2007 15:03:164/12/2007 15:03:16 37 ATENÇÃO! Segundo a história, o grande filósofo Sócrates dizia: “Se queres discutir comigo, defi na-se teus termos”. Para a sociedade, as leis morais que definem o que se deve e o que não se deve fazer. O operário age a partir de suas ferramentas de trabalho. Correspondentemente, para um matemático, a idéia de Conjunto Universo indica de que objetos ele pode lançar mão para obter os resultados desejados. Por exemplo, uma pergunta do tipo “Pode a metade de um número ser maior do que ele?” Tem a resposta negativa no Universo dos Números Naturais; e afirmativa no Universo dos inteiros. Portanto, sempre que estiver resolvendo um problema veja em que Universo ele está sendo proposto! Atividade 3: Verifique a associatividade para a disjunção, ou seja, que (p ∨ q) ∨ r = p ∨ (q ∨ r) Passo 1: Construção da tabela lógica para (p ∨ q) ∨ r. p q p ∨ q r (p ∨ q) ∨ r Passo 2: Construção da tabela lógica para p ∨ (q ∨ r). p q r q ∨ r p ∨ (q ∨ r) Passo 3: Comparando as últimas colunas das tabelas. (p ∨ q) ∨ r: p ∨ (q ∨ r): 3. A União e a Intersecção de Conjuntos Uma idéia muito importante em matemática é a de Conjunto Universo. Para o matemático, o Conjunto Universo é aquele que contém todos os elementos a serem considerados em um dado problema ou situação matemática. Assimse dissermos que o conjunto Universo é o conjunto das letras do alfabeto, só poderemos usar conjuntos cujos elementos são tais letras (ou o conjunto vazio). Representaremos conjunto universo pela letra grega ‘Ω’. Desta forma, se dissermos que ‘A’ é um conjunto, estamos pressupondo a existência de um Universo Ω em que ele está inserido, isto é, cada elemento livro_mat_mod2.indd 37livro_mat_mod2.indd 37 4/12/2007 15:03:164/12/2007 15:03:16 38 de ‘A’ deve ser um elemento de ‘Ω’ (Escreve-se A ⊂ Ω e lê-se: “A está contido em Ω”). Dados ‘A’ e ‘B’ conjuntos em um certo Universo ‘Ω’, estamos interessados em obter outros conjuntos em ‘Ω’ a partir de ‘A’ e ‘B’. Um dos modos de realizar isto é através das operações de disjunção e conjunção lógicas. Das sentenças p: x ∈ A q: x ∈ B podemos criar as sentenças p ∨ q: x ∈ A ou x ∈ B p ∧ q: x ∈ A e x ∈ B Assim sendo, podemos obter os conjuntos: A ∪ B = BxouAxx ∈∈Ω∈ A ∩ B = BxeAxx ∈∈Ω∈ O conjunto A ∪ B é chamado “união de A com B” e contem tanto os elementos de ‘A’ como os elementos de ‘B’, sem repetição e numa ordem qualquer. Por sua vez ,o conjunto A ∩ B é chamado “intersecção de A com B” contendo apenas os elementos comuns a ‘A’ e a ‘B’. Por exemplo, sendo Ω = ℵ e dados os conjuntos: 51 ≤≤ℵ∈= xxA e 73 ≤<ℵ∈= xxB então 5,4,3,2,1=A e 7,6,5,4=B logo A ∪ B = 7,6,5,4,3,2,1 e A ∩ B = 5,4 Atividade 4: No Universo dos Números Naturais, considere os conjun- tos 92 ≤ℵ∈= xxA e 102 <<ℵ∈= xxB . Escreva A e B por livro_mat_mod2.indd 38livro_mat_mod2.indd 38 4/12/2007 15:03:164/12/2007 15:03:16 39 extenso e em seguida obtenha A ∪ B e A ∩ B. Uma vez que, para quaisquer sentenças p e q, ‘p∨q’ equivale a ‘q∨p’, assim como ‘p∧q’ equivale a ‘q∧p’ ,então A ∪ B é igual a B ∪ A e A ∩ B é igual a B∩A, quaisquer que sejam os conjuntos do Universo Ω. Outras propriedades destas operações de conjuntos são: A ∪ A = A (Idempotência) A ∩ A = A (Idempotência) A ∪ ∅ = A (∅ é elemento neutro) A ∩ ∅ = ∅ (Absorção) A ∪ Ω = Ω (Absorção) Representação da União de Conjuntos em Diagramas CASO I: Os conjuntos A e B têm elementos em comum. A B Ω CASO II: Os conjuntos A e B não têm elementos em comum. A B Ω VEJA: No Caso I, um elemento pertence a ‘A∪B’ pode significar: Ele pertence a ‘A’, mas não pertence a ‘B’; » Ele pertence a ‘B’, mas não pertence a ‘A’; » Ele pertence a ambos os conjuntos. » livro_mat_mod2.indd 39livro_mat_mod2.indd 39 4/12/2007 15:03:164/12/2007 15:03:16 40 Este fato corresponde, na lógica matemática , à idéia de que o ‘ou’ é em geral, ‘inclusivo’ e pode agregar as duas sentenças. Na linguagem usual, o ‘ou’ é exclusivo (indicado pela situação do caso II). Quando digo vou à praia ou ao cinema, em geral, não se imagina que eu execute as duas ações simultaneamente. A ∩ Ω = A (Ω é elemento neutro) (A ∪ B) ∪ C = A ∪ (B ∪ C) (Associatividade) (A ∩ B) ∩ C = A ∩ (B ∩ C) (Associatividade) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) (Distributividade) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C) (Distributividade) Algumas dessas propriedades são imediatas, outras serão comentadas em nosso módulo de exercícios resolvidos (Módulo 5). Exercite-se na atividade abaixo! Atividade 5: No Universo 150 ≤≤ℵ∈=Ω xx considere os conjuntos: 4,3,2,1=A ; 8,6,3=B ; 12,10,8,6,4,2=C Determine cada uma dos conjuntos abaixo: a) A ∪ B b) A ∩ B c) A ∩ C d) B ∩ C e) (A ∪ B) ∩ C f) A ∪ (B ∩ C) g) (A ∪ B) ∩ (A ∪ C) h) (A ∩ C) ∪ (B ∩ C) i) (A ∪ B) ∪ C j) A ∪ (B ∪ C) REPRESENTAÇÃO DA INTERSECÇÃO DE CONJUNTOS EM DIAGRAMAS CASO I: Os conjuntos A e B têm elementos em comum. A B Ω livro_mat_mod2.indd 40livro_mat_mod2.indd 40 4/12/2007 15:03:164/12/2007 15:03:16 41 CASO II: Os conjuntos A e B não têm elementos em comum. A B Ω Neste último caso, os conjuntos se dizem disjuntos (não têm elementos comuns), isto é, A∩B=∅ Resumo A partir de duas sentenças p e q ,podemos obter as sentenças p 1) ∨ q chamadas disjunção lógica e p ∧ q chamadas conjunção lógica. A sentença p 2) ∨ q é falsa, se somente se as sentenças p e q forem fal- sas. A sentença p3) ∧q é verdadeira, se somente se p e q forem verdadeiras. Dados os conjuntos A e B, podemos construir os conjuntos A 4) ∪ B e A ∩ B. O conjunto A 5) ∪ B está associado à disjunção lógica do mesmo modo que A ∩ B está associado à conjunção lógica. Podemos usar esse fato na verificação de propriedades sobre tais operações de conjuntos. Auto-Avaliação Uma boa técnica para estudo é a que chamamos “técnica do espelho”. Ela consiste em você e um colega tentarem resolver separadamente os mes- mos exercícios. Em seguida, cada um corrige a solução dada pelo outro. É feita a discussão das questões em que não há concordância e, em seguida, busca-se ajuda de um tutor ou professor para dirimir as dúvidas. Aplique a técnica do espelho para as questões abaixo. Mostre, através de Tabela Lógica, que (p 1) ∨ q) ∧ r é equivalente a (p ∧ r) ∨ (q ∧ r). Qual a conseqüência desse fato para as operações de união e intersecção de conjuntos? Suponha que p seja uma sentença verdadeira; q uma sentença falsa,e 2) livro_mat_mod2.indd 41livro_mat_mod2.indd 41 4/12/2007 15:03:164/12/2007 15:03:16 42 r seja outra sentença verdadeira. Qual o valor lógico da sentença (p ∧ q) ∨ r? E da sentença p ∧ (q ∨ r)? No diagrama abaixo, 3) Ω representa o conjunto dos pernambucanos, A o conjunto dos pernambucanos que estuda matemática, B é o conjunto dos pernambucanos que fala inglês e C o conjunto dos alunos pernam- bucanos da UAB. Ω A C B Pinte de amarelo o conjunto dos pernambucanos que estuda na UAB e a) fala inglês. Pinte de azul o conjunto dos alunos que estuda matemática pela UAB.b) Você sabe que a composição do azul com o amarelo reproduz o verde. c) De acordo com essa informação, descreva que pernambucanos fica- riam demarcados de verde. Se um conjunto A tem 15 elementos e um conjunto B tem 8 elemen-4) tos, qual o número máximo de elementos que têm A ∪ B? E o número mínimo de elementos? Bibliografi a BOYER, Carl B. História da Matemática. São Paulo: Edgar Blücher, 1974. CASTRUCI, Benedito. Elementos da Teoria dos Conjuntos. São Paulo: Nobel, 1972. HALMOS, P. R. Teoria Ingênua dos conjuntos.São Paulo: Polígono, 1977. LIPSCHUTZ, Seymour. Teoria dos conjuntos. São Paulo: Ao Livro Técnico S.A, 1980. livro_mat_mod2.indd 42livro_mat_mod2.indd 42 4/12/2007 15:03:164/12/2007 15:03:16 Módulo 3 Disciplina: Elementos de Lógica e Teoria dos Conjuntos Livro_Matematica_M03.indd 27Livro_Matematica_M03.indd 27 4/12/2007 15:21:354/12/2007 15:21:35 Livro_Matematica_M03.indd 28Livro_Matematica_M03.indd 28 4/12/2007 15:21:354/12/2007 15:21:35 29 Subconjuntos e Implicações Meta Indicar modos básicos de composição de sentenças matemáticas Objetivos: Definir subconjunto de um conjunto1) ; Apresentar a implicação como operação lógica sobre sentenças relacio-2) nando-a com a inclusão de conjuntos; Inferir propriedades dos subconjuntos.3) 1. Introdução Neste módulo, estudaremos uma maneira fundamental de construção de sentenças matemática: a implicação lógica. A partir da idéia natural de sub- conjunto de um conjunto dado, apresentaremos tal operação lógica e, em seguida, faremos aplicações desta importante forma de organização do dis- curso matemático. 2. A Idéia de Subconjunto Dados A e B conjuntos quaisquer em um Universo Ω, diz-se que A é subcon- junto de B se cada elemento de A é elemento de B. Escrevemos, então,A ⊂ B (lê-se: “A está contido em B” ou “A é subconjunto de B”). Assim, simbolica- mente podemos afirmar: A ⊂ B se, e somente se, ∀ x ∈A, x ∈ B Ou seja, temos outro modo de produção de conjuntos a partir de um conjunto dado: a determinação dos subconjuntos dele. Porexemplo, a partir do con- junto { }dcbaA ,,,= ,podemos gerar os subconjuntos { }cb, , { }dba ,, , { }a etc. ATENÇÃO!! Não confundir o uso dos símbolos ∈ (pertence) e ⊂ (está contido). O primeiro (∈) deve ser usado para indicar que um elemento está em um conjunto, enquanto o segundo (⊂) para exprimir que um conjunto é um subconjunto de outro conjunto. O símbolo ⊂ também é chamado da inclusão de conjuntos. Livro_Matematica_M03.indd 29Livro_Matematica_M03.indd 29 4/12/2007 15:21:354/12/2007 15:21:35 30 É importante observar que, para escrevermos A ⊂ B, é necessário que: A e B sejam conjuntos; » Cada elemento de A seja elemento de B. » Portanto, mesmo que A e B sejam conjuntos, em caso de A, é preciso que cada elemento de A seja elemento de B para escrevermos A ⊂ B. Treine o uso de símbolos ∈ e ⊂ na atividade seguinte! Atividade 1: Complete com ∈ ou ⊂ as sentenças abaixo: a) 3 ∈ {1,2,3,4} b) {}3 _____ { }4,3,2,1 c) { }2,1 _____ { }4,3,2,1 d) {}3 _____ {}{ }4,3,2,1 Observe que, na letra (d) da atividade acima, o preenchimento correto deve ser: {}3 ∈ {}{ }4,3,2,1 , pois mesmo que {}3 seja um conjunto unitário, ele é elemento do conjunto {}{ }4,3,2,1 . Se A é um conjunto, é claro que cada elemento de A é um elemento de A, daí dizer que A ⊂ A, sempre. Por outro lado, para que A não seja subconjunto de B (A ⊄ B, simbolicamente), basta que algum elemento de A não seja ele- mento de B. Por exemplo: {1,2,3,4,5} ⊄ {1,2,3,4,6,7} Pois o elemento 5 do primeiro conjunto, não é elemento do segundo con- junto. Como cada sentença matemática deve ter um único valor lógico, devemos considerar ∅ como subconjunto de qualquer conjunto. O argumento lógico ATENÇÃO!! Veja: a idéia de elemento é um conceito primitivo enquanto que a de subconjunto é dada por definição. Muitas vezes, um conjunto figura como elemento para outro conjunto. Por exemplo, o conjunto dos triângulos do plano tem como elementos os triângulos, os quais são conjuntos de pontos. Livro_Matematica_M03.indd 30Livro_Matematica_M03.indd 30 4/12/2007 15:21:354/12/2007 15:21:35 31 é que, se ∅ ⊄ A deveria existir x ∈ ∅ com x ∉ A, mais é claro que isto não ocorre. Daí, é sempre verdade que ∅ ⊂ A. Atividade 2 Complete o quadro abaixo em que, na coluna da direita, estão os subconjun- tos do conjunto apontado na coluna da esquerda: Conjunto Subconjuntos ∅ ∅ {a} ∅ e {a} {a,b} ∅, {a}, {b}, {a,b} {a,b,c} Indutivamente, observamos que, a partir de um conjunto de n elementos, podem-se construir exatamente n2 subconjuntos. (nesta conta, incluem-se ∅ e o próprio conjunto). Uma outra propriedade da inclusão de conjuntos é que se A, B e C são con- juntos tais que A ⊂ B e B ⊂ C, então A ⊂ C. Tal propriedade é chamada de transitividade para a inclusão de conjuntos. Descubra mais fatos sobre con- juntos resolvendo as atividades abaixo: Atividade 3: Um conjunto A tem 350 elementos. Diga quantos são os subconjuntos de A com 349 elementos cada um. (Sugestão: pense em quantos subconjuntos com um elemento ele tem). Atividade 4: Assinale V (verdadeiro) ou F (Falso) conforme o caso. a) ( ) Se x ∉ A e A ⊂ B então x ∉ B. b) ( ) Se x ∈ A e A ⊄ B então x ∉ B. c) ( ) Se x ∉ A e A ⊄ B então x ∉ B. d) ( ) Se x ∈ A e A ⊂ B então x ∈ B. I M P O R T A N T E A Produção dos Conjuntos A partir de um conjunto X, podemos produzir o conjunto formado por todos os subconjuntos de X. Tal conjunto é chamado Conjuntos das Partes de X sendo denotado P(X). Nele estão presentes o conjunto vazio e o próprio conjunto X, chamados subconjuntos triviais de X. A Transitividade da Relação de Inclusão. Se todo número natural é um número inteiro e todo número inteiro é um número racional, então todo número natural é um número racional. Em geral, se A ⊂ B e B ⊂ C, então A ⊂ C. Q Z Livro_Matematica_M03.indd 31Livro_Matematica_M03.indd 31 4/12/2007 15:21:354/12/2007 15:21:35 32 3. A Implicação Lógica A sentença, se x ∈ A então x ∈ B pode ser dita que, a condição x ∈ A implica a condição x ∈ B. Simbolicamente escrevemos: x ∈ A ⇒ x ∈ B De um modo geral, se “p” e “q” são sentenças, podemos obter a sentença “p ⇒ q” a qual pode ser lida: “p é condição sufi ciente para q” ou “q é condição necessária para p”. Por exemplo, seja Ω, o conjunto dos cidadãos brasileiros e nele considere: A= {x ∈ Ω/ x é pernambucano} B = {x ∈ Ω/ x é nordestino} Como podemos observar A ⊂ B, ou seja, ser pernambucano implica ser nor- destino. Dito de outra maneira, a condição ser pernambucano é suficiente para se ser nordestino. Alternativamente, a condição ser nordestino é neces- sária para se ser pernambucano. Abaixo indicamos a tabela-lógica para a implicação. p q p ⇒ q V V V V F F F V V F F V Na implicação p ⇒ q, p é dita antecedente enquanto q é dita conseqüente. Não é necessário haver relação de causa e efeito entre p e q. Boa parte dos teoremas matemáticos tem essa forma lógica. Neste caso, p é dita hipótese, e q é chamada tese do Teorema. No caso, demonstrar o teorema significa mostrar que tal implicação é verdadeira. Atividade 5 Considere as sentenças abaixo: p: todo triângulo é retângulo q: os lados de um quadrilátero são congruentes Implicação x Inclusaõ É suficiente pertencer a A para pertencer a B. É necessário pertencer a B para está em A. A B Livro_Matematica_M03.indd 32Livro_Matematica_M03.indd 32 4/12/2007 15:21:354/12/2007 15:21:35 33 r: 5 + 8 é um número primo Determine os valores lógicos seguintes: a) V (p ⇒ q) = V pois V(p) = F e V(q) = F. b) V (q ⇒ p) = c) V (r ⇒ p) = d) V ((p ∨ r) r ⇒ q) = e) V ((p ∧ r) r ⇒ q) = 4. A Equivalência Lógica Se p ⇒ q e q ⇒ p então dizemos que p e q são logicamente equivalentes escrevendo p ⇔ q. Neste caso, também se diz que p (ou q) é condição necessária e suficiente para q (ou p) ou que “p se e somente se q”. A tabela lógica para p ⇔ q é dada por: p q p ⇒ q V V V V F F F V F F F V Sendo A e B conjuntos dados por sentenças p e q, respectivamente, então dizer que A = B significa que p ⇔ q. Por exemplo, sendo A = {x∈ℵ⎟ x2 – 3x + 2 = 0} e B = {1,2} observam que A = B, ou seja: x2 – 3x + 2 = 0 ⇔ x ∈{1,2} Atividade 6 Sabendo que p e q são sentenças verdadeiras e que r e s são sentenças falsas, qual o valor lógico das seguintes sentenças: a) (p ⇔ q) ⇔ (r ⇔ s) Resposta: V b) (p ⇒ r) ⇒ (q ⇒ s) Resposta: _______________ c) (p ⇔ r) ⇒ (q ⇒ s) Resposta: _______________ d) (r ⇒ q) ⇔ (p ⇒ s) Resposta: _______________ Dicas de Estudo Uma etapa importante de sua formação matemática é a de demonstrar certas afirmativas. Por exemplo: para provar que dois conjuntos são iguais, você deve lembrar que: A = B ⇔ A ⊂ B e B ⊂ A Assim, você deve cumprir as seguintes etapas: 1) Tomar x ∈ A e comprovar que x ∈ B; 2) Tomar x ∈ B e comprovar que x ∈ A. Livro_Matematica_M03.indd 33Livro_Matematica_M03.indd 33 4/12/2007 15:21:354/12/2007 15:21:35 34 e) (r ⇒ q) ⇔ (s ⇒ p) Resposta: _______________ 5. Exercícios de Fixação A partir desse módulo, você encontrará uma lista de exercícios para que você treine os conceitos e resultados trabalhados até agora. Nela introduziremos alguns fatos complementares, portanto é fundamental que você tente fazer todos os exercícios. 1. Represente por compreensão os conjuntos: a) A = {0,2,4,6,8,...} b) B = {0,1,2,...,9} c) C = Conjunto dos múltiplos de 3 d) D = Conjunto das frações com numerador e denominador compreendidos entre 1 e 3 (inclusive) e) E = {1,4,9,16,25,36,...} 2. Diga se é Verdadeira ou Falsa cada uma das sentenças: a) ( ) 0 ∈ {0,1,2,3} e) ( ) {a} ∈ {a, {a}} b) ( ) {1} ∈ {1,2,3} f) ( ) ∅ ∈ {∅, 1} c) ( ) 0 ∈ ∅ g) ( ) ∅ ∈ {0, {∅}} d) ( ) ∅ ∈ {0}h) ( ) ∅ ⊂ {0,{ ∅}} 3. Dados os conjuntos A = {1,2,3}, B = {3,4} e C = {1,2,4}, determine X = conjunto tal que X ∪ B = A ∪ C e X ∩ B = ∅. 4. Quantos são os subconjuntos do conjunto das vogais? 5. Assinale ,no diagrama dado, os seguintes conjuntos: a) A ∩ B ∩ C b) A ∩ (B ∪ C) c) A ∪ (B ∩ C) 6. Determine o valor lógico das seguintes sentenças: Use esse espaço abaixo para suas observações e dúvidas! Livro_Matematica_M03.indd 34Livro_Matematica_M03.indd 34 4/12/2007 15:21:354/12/2007 15:21:35 35 a) 1 + 3 = 4 e 2 > 5 b) 1 + 3 = 4 ou 2 > 5 c) 1 + 3 = 4 ⇒ 2 > 5 d) 2 > 5 ⇒ 1 + 3 = 4 e) 5 ≥ 2 e 0 + 1 = 1 f) 5 ≥ 2 ou 0 + 1 = 1 g) 5 ≥ 2 ⇒ 0 + 1 = 1 h) 5 ≥ 2 ⇔ 0 + 1 = 1 7. Determine V(p) nos seguintes casos: a) V(q) = F e V(p∧q) = F b) V(q) = F e V(p∨q) = F c) V(q) = F e V(p ⇒ q) = V d) V(q) = F e V(p ⇔ q) = V Resumo 1. Sendo A e B conjuntos, A ⊂ B signifi ca que: x ∈ A ⇒ x ∈ B. 2. Para quaisquer conjuntos A, B e C sempre vale que: A ⊂ A; A ⊂ B e B ⊂ A ⇔ A = B A ⊂ B e B ⊂ C ⇒ A ⊂ C ∅ ⊂ A 3. A implicação p ⇒ q só é falsa se V(p) = V e V(q) = F. 4. A equivalência p ⇔ q é verdadeira se, e somente se, p e q tiverem o mesmo valor lógico. Use esse espaço abaixo para suas observações e dúvidas! Livro_Matematica_M03.indd 35Livro_Matematica_M03.indd 35 4/12/2007 15:21:354/12/2007 15:21:35 36 Auto-avaliação 1. Assinale V ou F conforme verdadeira ou falsa seja cada uma das afirmati- vas; Justifique as que são falsas. a) ( ) p ∧ p ≡ p ∨ p b) ( ) p ∧(q ∨ r) ≡ (p ∨ r) ∧ (p ∨ q) c) ( ) p ∨ (q ∧ r) ≡ (p ∨ r) ∧ (p ∨ q) d) V(p) = V e V (q) = F ⇒ V(p ∧ q) = F e) V(q) = F e V (p ∧ q) =F ⇒ V(p) = V. 2. Sendo ℜ o conjunto dos números reais, determine o valor lógico de cada uma das seguintes proposições: a) (∀ x ∈ ℜ; ⎟ x ⎟ = x) b) (∃ x ∈ ℜ; ⎟ x ⎟ = 0) c) (∀ x ∈ ℜ; x + 1 > x) d) (∃ x ∈ ℜ; x2 = x) e) (∃ x ∈ ℜ; x + 2 = x) f) (∀x ∈ ℜ; x2 = x) 3. Se p, q e r são sentenças construa a tabela lógica para p ⇒ (q ∨ r): 4. Um conjunto tem precisamente 1024 subconjuntos. Indique quantos ele- mentos ele tem? 5. Determine o conjunto P(P(∅)) Use esse espaço abaixo para suas observações e dúvidas! Livro_Matematica_M03.indd 36Livro_Matematica_M03.indd 36 4/12/2007 15:21:364/12/2007 15:21:36 37 BIBLIOGRAFIA BOYER, Carl B. História da Matemática. São Paulo: Edgar Blücher, 1974. CASTRUCI, Benedito. Elementos da Teoria dos Conjuntos. São Paulo: Nobel, 1972. LIPSCHUTZ, Seymour. Teoria dos conjuntos. São Paulo: Ao Livro Técnico S.A, 1980. MONTEIRO. JACY L.H. Iniciação às Estruturas Algébricas. São Paulo: GEEM, 1973. Livro_Matematica_M03.indd 37Livro_Matematica_M03.indd 37 4/12/2007 15:21:364/12/2007 15:21:36 Livro_Matematica_M03.indd 38Livro_Matematica_M03.indd 38 4/12/2007 15:21:364/12/2007 15:21:36 Módulo 4 Disciplina: Elementos de Lógica e Teoria dos Conjuntos Livro_M04.indd 15Livro_M04.indd 15 5/12/2007 13:13:245/12/2007 13:13:24 Livro_M04.indd 16Livro_M04.indd 16 5/12/2007 13:13:245/12/2007 13:13:24 17 A Diferença de Conjuntos e a Negação de Pro- posições Meta Apresentar modos de negação de uma sentença matemática. Objetivos Definir diferença entre dois conjuntos inserindo o conceito de comple- » mentar de um conjunto como caso particular; Relacionar a complementação de conjuntos com a negação lógica; » Deduzir propriedades da complementação de conjuntos e da negação. » 1.introdução Uma maneira simples de produzir uma sentença é negando-se outra sen- tença dada. Por exemplo, se p: 3 + x = 7 é uma sentença, então sua negação, denotada por ∼p, é a sentença: ∼p: 3 + x ≠ 7 Portanto, ∼p será verdadeira se p for falsa, e será falsa se p for verdadeira. Então, a tabela lógica para a negação é: Na negação, encontramos algumas “armadilhas” da escrita e do pensamento matemáticos; pretendemos, então, ajudar você a evitá-las. Neste módulo, estudaremos ,ainda, a noção de complementar de um conjunto, naturalmente relacionada à negação lógica. Livro_M04.indd 17Livro_M04.indd 17 5/12/2007 13:13:245/12/2007 13:13:24 18 2. Os Quantifi cadores Lógicos Na matemática, é comum o uso de sentenças que se utilizam dos símbo- los ∀ (para todo, qualquer que seja) e ∃(existe, existe pelo menos um). Por Exemplo: p: ∀ x ∈ IN x² ≥ x (Qualquer que seja o número natural, seu quadrado é maior ou igual a ele próprio) q: ∃ x ∈ IN /2x + 1 = 7 (Existe um número natural cujo dobro mais um é igual a 7). Estes dois símbolos são chamados Quantificadores. O símbolo ∀ é chamado Quantificador Universal, enquanto que o símbolo ∃ é chamado Quantificador Existencial. É importante que você fixe a idéia seguinte: Cada um destes símbolos é usado na negação de sentenças que contenham o outro. Por exemplo, a negação das sentenças acima é dada por: ∼p: ∃ x ∈ IN / x² < x (Existe um número natural cujo quadrado é maior que ele próprio). ∼q: ∀ x ∈ IN, 2x + 1 ≠ 7 (Qualquer que seja o número natural, seu dobro mais um é diferente de sete). Use a informação acima para resolver a atividade abaixo: Atividade 1: Negue as sentenças abaixo: a: Todo dia da semana é dia de feira. ∼a: Existe um dia da semana que não é dia de feira . b: Em algum dia da semana, eu não vou à missa. ∼b: c: ∃ x ∈ Z / x ≠.x ∼c: d: ∀ x ∈ Q , - x ≤ x Desafi o Um náufrago chega a uma ilha onde convivem duas tribos A e B. Todos os nativos da tribo B sempre falam a verdade. Ao se deparar com um nativo, o náufrago fez a seguinte pergunta: “Existe ouro nesta ilha?” O nativo respondeu: “Existe ouro na ilha se e somente se eu falo a verdade”. Usando a lógica matemática para analisar a resposta do nativo, descubra se existe ou não ouro na ilha. Livro_M04.indd 18Livro_M04.indd 18 5/12/2007 13:13:245/12/2007 13:13:24 19 ~ d: e: Todo triângulo eqüilátero é isósceles ~ e: Um uso importante das idéias acima está na noção de subconjunto. Como vimos, dizer que um conjunto A é subconjunto de um B (A ⊂ B) significa que todo elemento de A é também elemento de B. simbolicamente, escrevemos: A ⊂ B ⇔ ∀ x ∈ A, x ∈ B Portanto, para que A não seja subconjunto de B (A ⊄ B), basta que ao menos um elemento de A não seja elemento de B. Ou seja: A ⊄ B ⇔ ∃ x ∈ A / x ∉ B Neste último fato, encontra-se o dado relevante para considerarmos o conjunto vazio como subconjunto de qualquer conjunto. De fato, se A é um conjunto, pelo princípio do terceiro excluído, apenas uma das afirmativas abaixo deve ser verdadeira: ( i ) ∅ ⊂ A ou (ii) ∅ ⊄ A Se (ii) fosse verdadeira, então deveria existir um elemento no x conjunto ∅ tal que x ∉ A. Mas é impossível x ∈⋅∅, logo tal afirmativa é falsa. Resta, então, (i) ser verdadeira. Este tipo de raciocínio é chamado Raciocínio por Vacuidade, tendo importante função na filosofia e na Ciência em Geral. 3. Conjunto Complementar Sendo A e B conjuntos em um universo Ω, define-se o conjunto diferença A – B por: A – B ={X ∈ Ω / x ∈ A e x ∉ B} Por exemplo, se A = {1,2,3,4,5} e B = {0,1,3,7} então A – B = {2, 4, 5 }. Note que (A – B) ⊂ A. Em particular, é claro que, em geral, A – B ≠ B – A. Um caso particular desta noção encontra-se quando B ⊂ A. Neste caso, A – B é chamado complementar de B com relação a A sendo denotado por C A B. Por exemplo, se A = {1, 2, 3, 4, 5} e B = {1, 3, 5}, então A – B ={2, 4}. Dicas de Estudo Em matemática, o raciocínio por Vacuidade é muito importante. Muitas vezes, para provarmos que uma afirmativa p é falsa, mostramos queo conjunto dos elementos que satisfazem p é vazio. Livro_M04.indd 19Livro_M04.indd 19 5/12/2007 13:13:245/12/2007 13:13:24 20 Neste caso, como B ⊂ A tal diferença pode ser representada por C A B. Exercite tais considerações na atividade abaixo. Atividade 2 Sejam Ω = {x ∈ IN / x ≤ 10}. Considere A = {1,2,3,4,5,6}; B = {3,4,5,6} e C = {5,6,7,8}. Determine: A – B =a) B – A =b) A – C =c) C – A =d) B – C =e) C – B =f) Cg) A B = Ch) ΩB = Ci) ΩA = Cj) ΩC = As representações CΩA, CΩB, CΩC significam Ω – A, Ω – B, Ω – C sendo, pois, os complementares dos conjuntos A, B e C, respectivamente. Neste caso, por uma simplificação de linguagem e do simbolismo usados, iremos representar-lhe a notação , , chamando tais conjuntos de comple- mentares de A, de B e de C respectivamente. Ou seja, se x é um conjunto qualquer em um universo Ω denotamos por ao complementar de X (em relação ao Universo Ω) Isto é, =CΩX = Ω –X No caso da atividade 2, como você pode confirmar: Atenção! Na notação CAB ,o conjunto A é chamado conjunto base ou referência. No caso em que A = Ω, é melhor usarmos a notação (Complementar de B). Livro_M04.indd 20Livro_M04.indd 20 5/12/2007 13:13:245/12/2007 13:13:24 21 = {0,7,8,9,10}, = {0,1,2,7,8,9,10} e = {0,1,2,3,4,9,10}. (Confira com os itens h, i, e j da atividade). Atividade 3 Seja Ω = {a, b, c, d, e, f, g, h }. Considere A = { a, b, c, d } e B = {c, d, e, f, g}. Determine: a) b) A c) ∪ B d) A e) ∩ B f) g) ∪ (União dos complementos) h) ∩ (Interseção dos complementos) i) (Complementar de ) j) (Complementar de ) 4. As Leis de Morgan Você deve ter notado no exercício acima que, = ∪ , isto é, o complementar da união de dois conjuntos é igual à interseção dos comple- mentares dos mesmos. Analogicamente, você deve observar que = ∪ isto é: O Complementar da Interseção de dois conjuntos é igual à união dos complementares dos conjuntos. Estes dois resultados são devidos ao matemático inglês (hindu de nasci- mento) Augustus de Morgan (1806 -1871). A seguir, faremos a justificativa destes resultados com base no uso de tabelas lógicas. Note Que: A – B A B B A B – A A B CAB A Ω A Atenção! Se você diz que não é verdade que é mentira que o Brasil é pentacampeão. O que,de fato, você disse... Livro_M04.indd 21Livro_M04.indd 21 5/12/2007 13:13:245/12/2007 13:13:24 22 Devemos antes notar que, dizer que x ∈ é equivalente a dizer que x ∉ A. Como a negação da negação de uma sentença equivale à própria sentença (Ver tabela ao lado), o complementar do complementar de um conjunto é igual ao próprio conjunto ( = ). Mostraremos agora que, se p e q são sen- tenças então: ~(p ∧ q) ⇔ ~p ∧ ~q (Em termos da linguagem dos conjuntos isto quer dizer que = ∩ ). Passo 1: Construída a tabela para ∼(p ∨ q) p q p ∪ q ∼( p ∨ q ) V V V F V F V F F V V F F F F V Passo 2: Construindo a tabela para (∼ ∧ p) ∧ (~ q) p q ∼p ∼q (∼p) ∧ (∼q) V V F V F F F V V F F V Passo 3: Comparando a seqüência de resultados nas últimas colunas das duas tabelas. ∼(p ∨ q): (∼p) ∧ (∼q): Agora, mostre você mesmo que ∼(p ∧ q) ⇔ (∼ p) ∨ (∼ q) Atividade 4 Mostre que ∼(p ∧ q) ⇔ (∼ p) ∨ (∼ q) Passo 1: Tabela para ∼ (p ∧ q) Curiosidade! Em uma cidade,existe um barbeiro que barbeia todo mundo que não se barbeia. Esse barbeiro barbeia-se a si próprio... Livro_M04.indd 22Livro_M04.indd 22 5/12/2007 13:13:245/12/2007 13:13:24 23 p q p ∧ q ∼(p ∧ q) Passo 2: Tabela para (∼ p ) ∨ (∼ q ) p q ∼p ∼q (∼p) ∧ (∼q) Passo 3: Comparação dos valores lógicos obtidos na última coluna. ~(p ∧ q): (~ p) ∧ (~ q): Observe que, se p e q são propriedades características dos conjuntos A e B,então, equivalentemente, você acabou demonstrar que: = ∪ De fato, se x ∈ ,então x ∉ ∩ , isto é, ou x não satisfaz a proprie- dade p ou o x não satisfaz a propriedade q. Logo, x ∈ ∪ , reciprocamente se x ∈ ∪ então ou x ∈ ou x ∈ , portanto ou x não satisfaz a pro- priedade p ou o x não satisfaz a propriedade q. 5. Negação e Implicação Dada a implicação p implica q (p ⇒ q) a partir das negações de p (∼p) e de q (∼q) podemos formar as implicações: (1. ∼p) ⇒ (∼q). Essa implicação é a chamada contrária de (p ⇒ q); q 2. ⇒ p. Essa implicação é a chamada de recíproca de (p ⇒ q); (3. ∼q) ⇒ (∼p). Essa é a chamada de contra-recíproca de (p ⇒ q); Organizando as tabelas de p ⇒ q e de sua contra-recíproca, podemos obser- var que elas são logicamente equivalentes. Assim ,por exemplo, no teorema: “Se um número inteiro é par, então seu quadrado é par”. O teorema contrário seria: “Se um número inteiro não é par, Atenção! p q ∼q ∼p (∼q) ⇒ (∼p) V V F F V V F V F F F V F V V F F V V V Como você pode observar a contra-recíproca de p ⇒ q é equivalente a p ⇒ q. Este fato vai ser importante nas demonstrações por redução ao absurdo Livro_M04.indd 23Livro_M04.indd 23 5/12/2007 13:13:245/12/2007 13:13:24 24 então seu quadrado também não é par”. O teorema recíproco seria: “Se o quadrado de um número inteiro é par, então ele é par”; e o contra-recíproco seria: “Se o quadrado de um número inteiro não é par, então ele não é par”. No caso, todos os teoremas acima são válidos, mas não é verdade que o recíproco e o contrário de um teorema válido sejam válidos. O contra-recí- proco de um teorema válido também é válido visto que ele é equivalente. Atividade 5: Dada a proposição: “Se João é paraibano, então é nordestino”, escreva as proposições contrária, recíproca e contra-recíproca. Acrescente mais duas palavras ao seu vocabulário matemático: Tautologia e Contradição. Uma Tautologia é uma sentença sempre verdadeira enquanto que uma contradição é uma sentença sempre falsa. Portanto, a negação de uma tautologia é uma contradição é vice-versa. Por exemplo, a sentença p ∨ (∼p) é uma tautologia, enquanto que, p ∧ (∼p) é uma contradição, qualquer que seja a sentença p dada. Resumo Os quantificadores 1. ∀ e ∃ são usados um na negação do outro. Se A é um conjunto em um certo universo 2. Ω, então o complementar de A é o conjunto dos elementos de Ω que não estão em A. Esta operação de conjunto está associada à negação de sentenças, visto que dizer que x ∈ significa que x ∉ . Vale que 3. = , = ∪ e = ∩ . Do ponto de vista das sentenças matemáticas, isto quer dizer que negar uma negação é afirmar; nega-se um “e” com um “ou” e nega-se um “ou” com um “e”. Cada implicação “p4. ⇒q” é equivalente ao seu contra-recíproco “∼q ⇒ ∼p”. Auto-Avaliação Mostre que as proposições são tautologias:1. (pa) →q) → ((p∧r)→q) (pb) →q) → (p→(q ∨ r)) (pc) →q) → ((p ∧ r) → (q ∧ r)) (pd) →q) → ((p ∨ r) → (q ∨ r)) Livro_M04.indd 24Livro_M04.indd 24 5/12/2007 13:13:245/12/2007 13:13:24 25 2. Mostre que as proposições são contradições: a) ∼p ∧ (p ∧ (∼q)) ((p b) ∧ q) ∧ ∼(p ∨ q)) p c) ↔ ∼p p d) ∧ ∼p 3. Escreva o teorema relativo às proposições p e q, ou seja, p ⇒ q, como também seu recíproco, seu contrário e seu contra-recíproco. 4. Sendo ℜ o conjunto dos números reais, determine o valor lógico de cada uma das seguintes proposições: (a) ∀x∈ℜ, |x|=x) (b) ∃x∈ℜ, x2=x) (c) ∃x∈ℜ, |x|=0) (d) ∃x∈ℜ, x+2=x) (e) ∀x∈ℜ, x+1>x) (f) ∀x∈ℜ, x2=x) 5. Dar a negação das proposições do item 4. Bibliografi a BOYER, Carl B. História da Matemática. São Paulo: Edgar Blücher, 1974. CASTRUCI, Benedito. Elementos da Teoria dos Conjuntos. São Paulo: Nobel, 1972. LIPSCHUTZ, Seymour. Teoria dos conjuntos. São Paulo: Ao Livro Técnico S.A, 1980. MONTEIRO. JACY L.H. Iniciação às Estruturas Algébricas. São Paulo: GEEM, 1973 Livro_M04.indd 25Livro_M04.indd 25 5/12/2007 13:13:245/12/2007 13:13:24Livro_M04.indd 26Livro_M04.indd 26 5/12/2007 13:13:245/12/2007 13:13:24 Módulo 5 Disciplina: Elementos de Lógica e Teoria dos Conjuntos Livro_M05.indd 19Livro_M05.indd 19 4/12/2007 16:20:234/12/2007 16:20:23 Livro_M05.indd 20Livro_M05.indd 20 4/12/2007 16:20:234/12/2007 16:20:23 21 Métodos de Demonstração Meta Exemplifi car alguns métodos de demonstração de proposições matemáticas Objetivos Descrever métodos de demonstração usuais em Matemática. » Compreender a indução como modo de obtenção do conhecimento » matemático. 1. Introdução Grande parte do discurso matemático é construída com implicações. A vali- dade de uma implicação, quando não aceita “a priori”, é verificada por sua demonstração, sendo esta palavra, responsável pelo recheio relevante nas teorias matemáticas. Neste módulo, você entrará em contato com algumas demonstrações de Teoremas matemáticos acessíveis a este nível de conhe- cimento. A organização dada ao texto presente tem caráter didático e não se propõe definir o conceito de demonstração ou esgotar o assunto. Leia criticamente cada demonstração dada e comece a pensar em “Teoremas” matemáticos já assimilados por você, tentando organizar demonstrações para eles. 2. Demonstração Direta Em um teorema do tipo p ⇒ q ( se p então q ) você já sabe que p é a hipótese e q é a tese do teorema. A demonstração direta consiste em a partir da afirmativa p, usando argumentos válidos, obter a afirmativa q. ATENÇÃO!! Consultando o Dicionário A priori: segundo um princípio anterior admitido como evidente; sem os fundamentos dos fatos; por hipótese. In: Dicionário Contemporâneo de Língua Portuguesa: Caldas Aulete, Rio de Janeiro: Delta S. A., 1964. Livro_M05.indd 21Livro_M05.indd 21 4/12/2007 16:20:234/12/2007 16:20:23 22 IMPORTANTE A demonstração de um teorema é a sua essência. Para o lógico matemático austríaco Ludwig Wittgenstein (1989 – 1951) “se você quer ver o que um teorema diz, observe o que sua demonstração prova”. Observe a demonstração abaixo: Teorema 1 O quadrado de um número natural par é um número natural par. Hipótese: INx ∈ é um número par. Tese: 2x é um número par. Demonstração Dizer que INx ∈ é um número par significa que x pode ser escrito como nx 2= em que INn ∈ (Um número natural par é o duplo de algum número natural). Assim, ( ) ( )2222 2.242 nnnx === . Como 22n é um número natural, segue-se que 2x é o duplo de um número natural, portanto também é par. C.Q.D. Atividade 1 Use que INx ∈ é um número ímpar significa que x pode ser escrito como 12 += nx com INn ∈ para mostrar que o quadrado de um número natural ímpar é um número natural ímpar. Teorema 2 O produto de dois números naturais ímpares é um número natural ímpar. Hipótese: INx ∈ e INy ∈ são números ímpares. Tese: O produto INyx ∈. . Demonstração Dizer que x e y são números ímpares em IN é dizer que x = 2n + 1 com INn ∈ y = 2m + 1 com INm ∈ Daí, x . y = (2n + 1) . (2m + 1) = 4nm + 2n + 2m + 1 Livro_M05.indd 22Livro_M05.indd 22 4/12/2007 16:20:234/12/2007 16:20:23 23 I M P O R T A N T E A demonstração por redução ao absurdo também é chamada demonstração por contradição. Chamamos contradição a uma sentença sempre falsa. Exemplo: p ^ (~ p) .: xy = 2 (2nm + n + m) + 1 Como 2nm + n + m = k IN∈ tem-se que xy = 2k + 1 com INk ∈ Logo, x.y é ímpar. Veja: uma vez demonstrado o Teorema 2 acima você pode deduzir o resultado obtido na atividade 1 acima. Diz-se que este resultado é um corolário do Teorema em apreço. 3. Demonstrações por Redução ao Absurdo. A demonstração por redução ao absurdo consiste em partir da negação da tese e, usando argumentos válidos, concluir a negação da hipótese. Ela se baseia na equivalência entre as sentenças p ⇒ q e ~q ⇒ ~p. Estude o exemplo abaixo: Teorema 3 Se a soma de dois números inteiros é par e um deles for ímpar então o outro também é impar. Hipótese: ∈ba, Z; ba + par; a ímpar. Tese: b é ímpar. Se b é par então – b é par. Daí (a + b) + (-b) é par pois a soma de inteiros pares é um número par. Mas (a + b) + (-b) = a, logo seria par o que contradiz a hipótese. Atividade 2 Demonstre a afirmativa seguinte: Se a soma de dois inteiros é ímpar e um deles é par então o outro é ímpar. Livro_M05.indd 23Livro_M05.indd 23 4/12/2007 16:20:234/12/2007 16:20:23 24 Curiosidade Para os gregos antigos, todo número era um número racional. Coube aos seguidores de Pitágoras, grande matemático grego do século IV a.C. a descoberta de que havia números irracionais: se o quadrado tem lado 1 então sua diagonal tem lado . Na época, expressava-se este fato dizendo-se que a diagonal do quadrado não é comensurável com o seu lado. A demonstração por redução assume outros modos de organização. Por exemplo, pode-se negar a tese, usar que a hipótese é verdadeira e obter- se uma contradição qualquer. Este esquema de demonstração baseia-se na equivalência das sentenças “p ⇒ q” ⇔ ( ~ q ) Λ p ⇒ r Λ ( ~ r). Muitos resultados importantes em matemática não conhecem uma prova direta. Abaixo ilustramos algumas clássicas demonstrações por redução ao absurdo. Teorema 4 2 é um número irracional. Demonstração Se 2 fosse um número racional então existiriam p e q inteiros tais que q p =2 Sem perda de generalidade podemos supor que p e q são primos entre si, ou seja, que a fração q p é irredutível. Daí ( ) 2222 qp= donde p² = 2q² logo p² é par, portanto p é par, isto é, p = 2k com Zk ∈ . Substituindo na igualdade acima obtém-se: (2k)² = 2 q² ∴ 4k² = 2q² ∴ 2k² = q² Portanto q² é par e assim q é par. Obtemos que tanto p como q é um número par, o que é um absurdo contra o fato da fração q p ser irredutível. Teorema 5 Existem infinitos inteiros primos. Demonstração Seja P(n) uma afirmativa sobre um número natural n ≥ 1 genérico tal que Curiosidade O teorema 5 ao lado é conhecido como Teorema de Euclides, mais importante matemático grego da antiguidade. Sem “Elementos” são considerados o texto matemático mais consultado no mundo. Livro_M05.indd 24Livro_M05.indd 24 4/12/2007 16:20:234/12/2007 16:20:23 25 Suponhamos que o conjunto de todos os números primos fosse finito. Então existiria um inteiro positivo k tal que seria possível indicar todos os primos da seguinte maneira: P1, P2, ..., Pk. Consideremos o número inteiro N = P1 . P2 . ... Pk + 1 Ora cada número inteiro que não seja 1 ou –1 tem um divisor primo p. Seja p o divisor primo de N. Como p divide P1 . P2 ... Pk. Isto é p divide 1, logo não pode ser primo, contradizendo a hipótese adicional assumida. 4. Demonstrações por Indução Finita. Uma das bases construtivas dos números naturais é conhecida como Princípio da Indução Finita (P. I. F.). Ele admite várias formulações, uma das quais indicaremos abaixo. Seja P(n) uma afirmativa sobre um número natural n ≥ 1 genérico tal que (i) P(1) é verdadeira, isto é, a afirmativa é verdadeira para n = 1. (ii) Se P(k) é verdadeira para um natural k ≥ 1, então P (k + 1) é verda- deira. Então: P(n) é verdadeira para todo *INn ∈ . Por exemplo, considere a afirmativa: ( ) ( ) *, 2 1...321: INnnnnnP ∈+=++++ Tem-se que: (i) P(1) é verdadeira pois ( ) 2 11.11 += (fizemos n = 1 na afirmativa) (ii) Suponhamos P(k) verdadeira: ( ) 2 1....321 +=++++ kkk Provemos que P(k+1) é verdadeira, isto é que I M P O R T A N T E O teorema 5 ao lado é conhecido como Teorema de Euclides, mais importante matemático grego daantiguidade. Sem “Elementos” são considerados o texto matemático mais consultado no mundo. Livro_M05.indd 25Livro_M05.indd 25 4/12/2007 16:20:234/12/2007 16:20:23 26 ( ) ( ) ( ) 2 2.11...321 ++=+++++ kkk De fato: 1 + 2 + ... + (k + 1) = 1 + 2 + ... + k + (k+1) = ( ) ( ) ( ) ( ) ( ) ( ) 2 2.1 2 1.21.1 2 1. ++ = +++ =++ + = kkkkkkkk Portanto P(n) é verdadeira *INn ∈∀ . Atividade 3 Use o P. I. F. para mostrar que ( ) .*,12...531 2 INnnn ∈∀=−++++ Muitas vezes a proposição P(n) tem significado para n = 0. Neste caso, a condição (i) do P.I.F. é substituída por (i) P(0) é verdadeira A conclusão é que P(n) é verdadeira INn ∈∀ . Por exemplo, considere a tarefa de demonstrar a proposição: P(n): o número de subconjuntos de um conjunto com n elementos é 2n. Neste caso, a afirmativa tem significado para n = 0. Portanto, o primeiro passo é provar que P(0) é verdadeira. Consideremos A um conjunto de n elementos. (i) Se n = 0 então A = {}. Logo, A tem apenas 1 = 2º subconjunto, a saber, ele próprio. (ii) Supondo que afirmativa é verdadeira para n = k. Isto é, todo conjunto com k elementos tem 2k subconjuntos. Vamos provar que ela vale para k + 1. Seja: { } { } { }121121 ,...,,,,...,, ++ ∪== kkkk aaaaaaaaA Dicas de Estudo Se você quiser provar que “a soma dos ângulos internos de um polígono convexo é 180º.(n- 2) “então é claro que o menor valor de n a ser tomado é n = 3. Este é o valor inicial para se realizar a indução. Livro_M05.indd 26Livro_M05.indd 26 4/12/2007 16:20:234/12/2007 16:20:23 27 Obter subconjuntos de A envolve dois passos: 1º) Obter todos os subconjuntos de { }kaaa ,...,, 21 . 2º) Juntar a estes, o elemento 1+ka para obter os demais subconjuntos de A. Ora, pela hipótese de indução, o 1º passo garante 2k subconjuntos para A. Com o 2º passo, dobramos esta quantidade, obtendo 2 . 2 subconjuntos. Isto é 2k + 1 subconjuntos. C. Q. D. Atividade 4 Prove que INn n n ∈∀−=++++ + , 2 133...333 1 210 . Uma forma muito usada do P. I. F. substitui a condição (ii) por: (ii) Se P(k) é verdadeira para todo k < n então P(n) é verdadeira. Usaremos esta forma para demonstrar um importante resultado da Teoria dos Números. Algoritmo da Divisão: Dados a e b ≠ 0 números naturais, existem q e r em IN tais que: (i) a = b.q + r (ii) 0 ≤ r < b Demonstração Faremos indução sobre a (supondo b fixado). Tem-se. (i) A afirmativa vale se a = 0. De fato, basta tomar q = r = 0. Podemos supor, sem perder generalidade, que a ≥ b uma vez que se a < b tomamos q = 0 e r = a para provar a afirmativa. (ii) Suponhamos que a afirmativa vale para todo natural menor que a. Então ela vale para a – b. Isto é, existem q e r naturais tais que: Curiosidade Ache o erro no raciocínio abaixo: n = n + 1 ,∀ n ∈ IN. Provemos a afi rmativa: De fato, suponha que a afi rmativa vale para n = k, isto é k = k + 1. Vamos provar que ela vale para k + 1, ou seja, k + 1 = (k + 1) + 1 = k + 2. Ora, se k = k + 1 então adicionando-se 1 a ambos os membros obtém-se: k + 1 = (k + 1) + 1 = k + 2 C.Q.D. Livro_M05.indd 27Livro_M05.indd 27 4/12/2007 16:20:234/12/2007 16:20:23 28 (I) a – b = b.q + r e (II) 0 ≤ r < b De (I) segue-se que a = b.q + r + b ∴a = b (q + 1) + r Ou seja, existem naturais q + 1 e r tais que (I) a = b (q+1) + r (II) 0 ≤ r < b Portanto a afirmativa vale para a. 5. Exercícios de Fixação 1) Prove que a soma de dois números inteiros pares também é par. 2) Mostre que m + n + m² + n² é para INnm ∈∀ , . 3) Prove que INn ∈∀ é verdadeiro afirmar que ( ) INnn ∈+ 2 1. . 4) Na divisão dos números naturais a e b o quociente é 1060 e o resto 304. Qual o maior número de que se pode aumentar o dividendo e o divisor sem que o quociente se altere. 5) Prove por indução finita que: a) ( ) *,1.2...642 INnnnn ∈∀+=++++ b) ( )( ) INnnnnn ∈∀++=++++ , 6 2.1....321 2222 Resumo 1. A forma básica de um teorema matemático é: H ⇒ T (Hipótese Implica Tese) 2. Na prova direta, supõe-se H, usa-se argumentos válidos e conclui-se T. Livro_M05.indd 28Livro_M05.indd 28 4/12/2007 16:20:234/12/2007 16:20:23 29 3. A redução ao absurdo consiste em negar T e obter-se uma negação de H, alternativamente, pode-se negar T, usar-se H e chegar-se a uma contradição qualquer. 4. O Princípio da Indução Finita é um modo básico para demonstrar afirmati- vas sobre números naturais. Auto-Avaliação Interpretação de texto matemático Considere o seguinte teorema: Teorema Todo número inteiro n diferente de 0, 1 e – 1 ou é primo ou é um produto de primos. Demonstração Basta demonstrar o resultado quando n > 0. Seja S o conjunto de todos os inteiros n > r que sejam primos ou que sejam produto de primos, claro, 2 e 5. Suponhamos que o Teorema é verdadeiro para todo inteiro k tal que 2 ≤ k < n. Se n é primo então n ∈ S, trivialmente, logo não há o que provar. Se n não é primo então existem inteiros p e q tais que n = p.q, com 2 ≤ q < n e 2 ≤ p < n. Logo p ∈ S e q ∈ S. Portanto, n ∈ S, conforme queríamos demonstrar. Agora, responda as questões abaixo: 1º) Qual o formato da demonstração (direta, redução ao absurdo, indução)? 2º) Porque a suposição n > 0 não invalida a demonstração? 3º) Em que se baseia a afirmativa de que n = p.q para p e q inteiros? 4º) Porque afirmar-se que n ∈ S e como isto prova o teorema? Livro_M05.indd 29Livro_M05.indd 29 4/12/2007 16:20:234/12/2007 16:20:23 30 Bibliografi a DOMINGUES, H. H. Fundamentos de Aritmética. São Paulo: Atual, 1991. EVES, H. Introdução à História da Matemática. Campinas, SP: Editora da Unicamp. MONTEIRO, L. H. J. Elementos de álgebra. 2ª Ed. Rio de Janeiro: Livros Técnicos e Científicos, 1978. Livro_M05.indd 30Livro_M05.indd 30 4/12/2007 16:20:234/12/2007 16:20:23 Módulo 6 Disciplina: Elementos de Lógica e Teoria dos Conjuntos Livro_M06_grafica.indd 17Livro_M06_grafica.indd 17 4/12/2007 16:32:254/12/2007 16:32:25 Livro_M06_grafica.indd 18Livro_M06_grafica.indd 18 4/12/2007 16:32:254/12/2007 16:32:25 19 Métodos de Demonstração Meta Apresentar o universo das relações binárias como modo de conceituar a idéia de relação entre dois objetos matemáticos. Objetivos: 1. Definir o produto cartesiano de dois Conjuntos; 2. Compreender o produto cartesiano como Universo apropriado para defini- ção das relações binárias. 1. Introdução Uma tarefa constante no trabalho do matemático é a de estabelecer relações entre os objetos matemáticos. A igualdade entre números ou conjuntos, a pertinência entre elementos e conjuntos, a inclusão de conjuntos, são exem- plos de relações entre objetos matemáticos (elementos, números, conjuntos) até agora estabelecidas. Neste módulo, pretendemos apresentar a própria relação como um objeto matemático a ser estudado e, daí, inferir proprieda- des básicas de seu estudo. Você deve focar bem sua atenção nas definições e notações dadas, pois elas serão um ingrediente muito importante na sua compreensão da matemática. 2. O Produto Cartesiano de Dois Conjuntos Se A e B são Conjuntos não vazios, iremos produzir um tipo de Universo Matemático muito importante: o produto cartesiano de A por B. Ele é o con- junto formado por todos os pares ordenados (x,y) tais que x ∈A e y ∈ B, sendo representado por A x B (lê-se: “A cartesiano B”). Assim, simbolica- Livro_M06_grafica.indd 19Livro_M06_grafica.indd 19 4/12/2007 16:32:254/12/2007 16:32:25 20 IMPORTANTE O tipo de diagrama ao lado é chamado cartesiano. O nome cartesiano é derivado de Cartesius, modo como o matemático francês René Descartes erachamado. Descartes foi responsável pela criação da Geometria Analítica cuja idéia básica é a de identificar um ponto no plano como um par ordenado (x,y) de números reais, como indicado abaixo: Plano Cartesiano mente: A x B = ( ){ Axyx ∈/; e }By ∈ . Por exemplo: se A = { }3,2,1 e =B { },ba ,então A x B é o conjunto. A x B = ( ) ( ) ( ) ( ){ ( ) ( )}bababa ;3,;3,;2,;2,;1,;1 Podemos representar A x B em diagramas de setas como: Outra maneira de representar A x B é através de diagrama cartesiano: Como, em geral, o par ordenado (x, y) é diferente do par ordenado (y, x), o conjunto A x B é diferente do conjunto B x A. De fato, A x B é igual a B x A, se e somente se, A = B. Neste caso, A x B = A x A é denotado de A2. Atividade 1 Sendo { }52/ ≤<∈= xINxA e }{ 2,1=B , encontre A explicitamente e em seguida determine: a) A x B b) B x A Livro_M06_grafica.indd 20Livro_M06_grafica.indd 20 4/12/2007 16:32:254/12/2007 16:32:25 21 Diagrama de Setas da Relação R Diagrama Cartesiano da Relação R c) A2 d) B2 Para cada um destes conjuntos, dê também o diagrama de setas e o dia- grama cartesiano. 3. As Relações Binárias O princípio multiplicativo mostra que, se A for um conjunto finito com m ele- mentos e B for um conjunto finito com n elementos, então A x B terá m x n elementos. Por exemplo: se }{ dcbaA ,,,= e B = {∆, } então: Como notamos, A x B tem 4 x 2 = 8 pares ordenados. Portanto, se o número de subconjuntos de A x B é 28 = 256 subconjuntos (incluindo-se aí os subconjuntos triviais ∅ e A x B). Cada um de tais subconjuntos é chamado relação binária de A em B. No caso, R={(a ; ), (a ; ∆)} é uma relação do conjunto A no conjunto B. Podemos representar R tanto em diagrama de setas como em diagrama cartesiano (veja ao lado). Se R é uma Relação de A em B ,então o subconjunto de A, {x ∈ A/ (x;y) ∈ R para algum y ∈ B} é chamado Domínio de R sendo representado por D(R) ou DR. No caso da relação acima, DR = {a}. Como vemos D(R) contém apenas os primeiros elementos dos pares orde- nados de R. Analogamente, o subconjunto de B formado pelo segundo elemento dos pares ordenados de R é chamado Imagem de R, sendo denotado por Im(R) ou IMR. No caso acima, Im(R) = {∆ , } = B. Simbolicamente, se R ⊂ (A x B), então Im(R) = {y ∈ B / (x ; y) ∈ R para algum x ∈ A} A x B={(a;∆),(a; ),(b;∆),(b; ),(c;∆),(c; ),(d;∆),(d; )} Livro_M06_grafica.indd 21Livro_M06_grafica.indd 21 4/12/2007 16:32:254/12/2007 16:32:25 22 Dicas de Estudo Veja: você não diz na linguagem comum que: “João está na relação de namoro com Joana”. Você diz: “João namora Joana”. Do mesmo modo se o par (x,y) pertence a uma relação R, então se escreve xRy e lê-se: “x está na relação R com y”. A negação deste fato é escrita Observe o exemplo abaixo: Considere R = {(x , y) ∈ N 2 / x + y = 5}. Assim um par ordenado (x ,y) está na relação R ,se e somente se, 1º) x ∈ N e y ∈ N 2º) x + y = 5 Atribuindo valores naturais para x e obtendo – se os valores correspondentes para y ,podemos calcular todos os pares ordenados de R. x y = 5 – x 0 5 1 4 2 3 3 2 4 1 5 0 Organizamos uma tabela como a indicada abaixo (note que x + y = 5 ⇔ y = 5 – x) Portanto, R = ( ) ( ) ( ) ( ) ( ) ( ){ }0,5,1,4,2,3,3,2,4,1,5,0 sendo D(R) = Im (R)= { }5,4,3,2,1,0 Atividade 2 Considere a seguinte relação: ( ){ }4/, 2 =+×∈= yxINZyxR . Determine: a) Todos os pares ordenados de R. b) D(R) c) Im(R) 4. Inversa de uma Relação Se R é uma relação de A em B (R⊂(A×B)) ,então está definida uma relação S de B em A pela condição: Dicas de Estudo A palavra inversa em matemática tem vários usos que podem fazê-lo confundir conceitos. No caso da Relação Inversa, algumas vezes chamada mais apropriadamente Relação Recíproca, o tipo de inversão mencionado é o mais simples de todos: trocar a ordem dos elementos do par ordenado. Livro_M06_grafica.indd 22Livro_M06_grafica.indd 22 4/12/2007 16:32:254/12/2007 16:32:25 23 xRy ⇔ ySx Isto é, S contém todos os pares ordenados inversos dos pares ordenados de R. Por exemplo: R= ( ) ( ) ( ){ }fedcba ,,,,, ⇔ S = ( ) ( ) ( ){ }efcdab ,,,,, A relação S assim definida é denominada Relação Inversa de R sendo deno- tada por R -1(lê-se: Inversa de R). É claro que: (R-1)-1 = R (A inversa da inversa de R é a própria R); D(R-1) = Im (R) Im(R-1) = D(R) Atividade 3 Obtenha R -1 no caso da atividade 2 acima. Indique seu Domínio e Imagem: 5. Composição de Relações Suponhamos que A, B e C sejam conjuntos não vazios e sejam dadas as relações R ⊂ A×B e S ⊂ B×C. Podemos definir uma relação T ⊂ A × C de modo que: xTy ,se e somente se, existe z ∈ B tal que xRz e zSy. Por exemplo, sendo { }3,2,1=A e { }dcbaB ,,,= e {∆=C , }, dadas R = ( ) ( ){ }ba ,2,,1 ⊂ A×B e S = ( ){ ( ,,, aa ∆ )} então: T = SoR = ( ){ ( ,1,,1 ∆ )} Atividade 4 Sejam A = B = C = IN e considere R = ( ){ }42, 2 =+∈ yxINyx e S = ( ){ }25, 222 =+∈ yxINyx I M P O R T A N T E O teorema 5 ao lado é conhecido como Teorema de Euclides, mais importante matemático grego da antiguidade. Sem “Elementos” são considerados o texto matemático mais consultado no mundo. Livro_M06_grafica.indd 23Livro_M06_grafica.indd 23 4/12/2007 16:32:254/12/2007 16:32:25 24 Determine R e S explicitamente e em seguida obtenha: a) SR o b) RS o Você deve ter notado que, mesmo no caso de A=B=C, a composta RS o pode ser diferente da composta RoS. Entendendo a obtenção de compos- tas como sendo uma operação (Composição de Relações), diríamos que tal operação é não comutativa. Entretanto, é fácil mostrar que ela é associativa, isto é: (RoS) oT = Ro (SoT). De fato, considere R, S e T relações em A e seja (x,y)∈ (RoS)oT. Isto é, existe z ∈ A tal que xTz e z(RoS) y. Desta última condição, existe t ∈ A tal que zSt e tRy. Ora de xTz e zSt segue-se que x (SoT)t como tRy, vem que x(Ro(SoT))y, ou seja, (x,y)∈ (RoS)oT. De modo análogo se mostra que: Ro(SoT).⊂ (RoS)oT. Também considerando IA a diagonal de A 2 ,é claro que, qualquer que seja a relação R em A, vale : RoIA = IA oR = R Isto é, IA é uma espécie de elemento neutro da Composição de Relações em A. O exemplo abaixo indica uma outra propriedade da Composição de aplica- ções. Considere R e S as relações em Z expostas na atividade 4. Isto é: R = ( ) ( ){ }0,4,2,0 S = ( ) ( ) ( ) ( ){ }3,4,4,3,0,5,5,0 . Assim tem-se: SoR = ( ){ }5,4 RoS = ( ) ( ){ }0,3,2,5 Por outro lado, determinando as inversas de todas as relações, tem-se: R-1 = ( ) ( ){ }4,0,0,2 S-1 = ( ) ( ) ( ) ( ){ }4,3,3,4,5,0,0,5 . (SoR) -1 = ( ){ }4,5 I M P O R T A N T E Quando A = B uma relação de A em B é simplesmente dita relação em A. Boa parte do estudo de matemática no ensino elementar trata do estudo das relações em IR, conjunto dos números reais. Para estas, a representação gráfica no plano cartesiano deve receber um estudo especial. Livro_M06_grafica.indd 24Livro_M06_grafica.indd 24 4/12/2007 16:32:254/12/2007 16:32:25 25 (RoS) -1 = ( ) ( ){ }3,0,5,2 Você pode notar que: (SoR) -1 = R-1o S-1 e (RoS) -1 = S-1oR-1 Uma regrinha de fácil memorização diz que a Inversa da Composta de duas relações é igual à Composta da Inversa na ordem inversa. Este fato é geral e fácil de demonstrar. (Tente!!) Atividade 5: Sejam R = ( ){ }923, 2 =+∈ yxINyx e S = ( ) ( ) ( ){ }1,1,5,3,1,0 Determine R, explicitamente, e obtenha: a) RoS b) (RoS) -1 c) SoR d) R-1 e) S-1o R-1 f) S-1 Resumo 1. Relações são conjuntos de pares ordenados; 2. Quando dizemos que R é uma relação de A em B, isto significa que R ⊂ A×B. Neste caso, o Domínio de R é o conjunto dos primeiros elementos de seus pares ordenados, enquanto a Imagem
Compartilhar