Baixe o app para aproveitar ainda mais
Prévia do material em texto
WELINGTON SANTOS MATEMÁTICA DISCRETA Código Logístico 59915 Fundação Biblioteca Nacional ISBN 978-65-5821-012-2 9 7 8 6 5 5 8 2 1 0 1 2 2 Matemática Discreta Welington Santos IESDE BRASIL 2021 © 2021 – IESDE BRASIL S/A. É proibida a reprodução, mesmo parcial, por qualquer processo, sem autorização por escrito do autor e do detentor dos direitos autorais. Projeto de capa: IESDE BRASIL S/A. Imagem da capa: devotchkah/a_slowik/envatoelements Todos os direitos reservados. IESDE BRASIL S/A. Al. Dr. Carlos de Carvalho, 1.482. CEP: 80730-200 Batel – Curitiba – PR 0800 708 88 88 – www.iesde.com.br CIP-BRASIL. CATALOGAÇÃO NA PUBLICAÇÃO SINDICATO NACIONAL DOS EDITORES DE LIVROS, RJ S239m Santos, Welington Matemática discreta / Welington Santos. - 1. ed. - Curitiba [PR] : Iesde, 2021. 136 p. : il. Inclui bibliografia ISBN 978-65-5821-012-2 1. Matemática. 2. Lógica simbólica e matemática. 3. Teoria dos conjun- tos. 4. Análise combinatória. 5. Funções (Matemática). I. Título. 21-69713 CDD: 510 CDU: 51 Welington Santos Doutor e Mestre em Matemática pela Universidade Federal do Paraná (UFPR). Graduado em Licenciatura em Matemática pela Universidade Estadual de Ponta Grossa (UEPG). Participou de programa de doutoramento sanduíche na Universidade de Maryland, EUA. Tem experiência na área de Matemática com ênfase em Teoria algébrica dos códigos corretores de erros, Teoria de invariantes, Self-dual codes, Decodificação fracionária e Teoria de matróides. Tem experiência em ensino superior, ministrando aulas no formato presencial e a distância. SUMÁRIO 1 Fundamentos de lógica matemática e métodos de demonstração 9 1.1 Fundamentos de lógica matemática 9 1.2 Demonstração direta e demonstração por contraposição 20 1.3 Demonstração por contradição 24 1.4 Demonstração por absurdo 25 1.5 Demonstração por indução finita 26 2 Teoria de conjuntos 30 2.1 Noção intuitiva de conjuntos 30 2.2 Descrição e igualdade de conjuntos 31 2.3 Subconjuntos 34 2.4 Operações com conjuntos 36 3 Conjuntos numéricos 47 3.1 Conjunto dos números naturais 47 3.2 Conjunto dos números inteiros 51 3.3 Conjunto dos números racionais 54 3.4 Números reais e cardinalidade 56 3.5 Aritmética modular 58 4 Relações 61 4.1 Produto cartesiano e par ordenado 61 4.2 Conceito de relação 64 4.3 Relação inversa 68 4.4 Propriedades das relações 69 4.5 Operações e fecho de relações 72 4.6 Relação de ordem e de equivalência 74 5 Funções discretas 80 5.1 Conceito e classificação 80 5.2 Função composta e função inversa 85 5.3 Funções recursivas 89 6 Análise combinatória 92 6.1 Princípios de contagem 92 6.2 Arranjos 97 6.3 Permutações 99 6.4 Combinações 102 6.5 Binômio de Newton 106 6 Matemática Discreta 7 Funções geradoras e partição de um inteiro 112 7.1 Funções geradoras 112 7.2 Operações com funções geradoras 114 7.3 Funções geradoras exponenciais 120 7.4 Sequência de Fibonacci 123 7.5 Partição de um inteiro 124 7.6 Gráfico de uma partição 126 Gabarito 129 APRESENTAÇÃO Esta obra oferece uma abordagem introdutória à matemática discreta, área da matemática dedicada ao estudo de objetos que são formados por elementos desconexos entre si, chamados de elementos discretos. Apresentamos, com detalhes, conceitos fundamentais de teoria de conjuntos, conjuntos numéricos e aritmética modular, diferentes problemas de combinatória e funções úteis para a resolução de problemas de contagem. Para tanto, no primeiro capítulo, discorremos sobre os fundamentos básicos da lógica matemática, apresentando operações entre proposições lógicas e suas implicações nas técnicas de demonstração para resultados matemáticos. A matemática é fundamentada por axiomas, lemas, corolários e teoremas, que são validados por meio das demonstrações. Nesse sentido, ao longo de toda a obra, apresentamos e aplicamos as principais técnicas de demonstração (direta, contraposição, contradição, absurdo e indução) para provar fatos bem conhecidos da matemática. No segundo capítulo, abordamos a teoria fundamental de conjuntos, que embasa toda a matemática discreta, apresentando as técnicas básicas de contagem do número de elementos dos conjuntos e as principais operações entre eles, como a intersecção, a união e a diferença. O terceiro capítulo propõe um estudo aprofundado dos principais conjuntos numéricos, explorando as diferentes propriedades e operações que cada um desses conjuntos possui. Além disso, classificamos os conjuntos numéricos em termos de sua cardinalidade, descrevendo o conceito de conjunto enumerável e não enumerável. Diante da importância da aritmética modular em problemas que envolvem contagem, discorremos detalhadamente sobre essa matéria, que é observada na leitura de um CD e na validação do número do Cadastro de Pessoa Física (CPF). No quarto capítulo, com objetivo de introduzir o conceito de relações entre conjuntos, nos debruçamos sobre a operação de produto cartesiano entre conjuntos. Além disso, apresentamos as principais propriedades das relações entre conjuntos e dois tipos especiais de relação: relação de ordem e de equivalência, que são utilizadas na alocação de frota de empresas aéreas, por exemplo. No quinto capítulo, utilizamos o conceito de relações entre conjuntos para definir funções discretas, apresentando os principais elementos que compõem uma função: domínio, contradomínio e imagem. Exploramos também as principais propriedades operatórias entre funções. Por fim, apresentamos os fundamentos básicos de funções recursivas, apontando sua aplicação para a criação de sequências numéricas, como a famosa sequência de Fibonacci. Vídeo 8 Matemática Discreta No sexto capítulo, nos debruçamos sobre os princípios fundamentais de contagem: princípio da adição, da subtração, da multiplicação e o princípio da casa dos pombos, exibindo exemplos de aplicações para cada um deles. Além disso, o capítulo define, classifica e ilustra diferentes problemas de contagem. Por fim, são exploradas as principais propriedades do binômio de Newton e do teorema multinomial. No capítulo final, abordamos a função geradora ordinária de uma sequência numérica, identificando as relações entre operação com sequências numéricas e funções geradoras. Exibimos, por meio de exemplos, como podemos utilizar funções geradoras para solucionar problemas de contagem. Por fim, as ideias básicas de partição de um número inteiro são apresentadas. O livro também apresenta, ao final de cada capítulo, exercícios cuidadosamente selecionados para que você exercite e explore, na prática, os temas apresentados. Bons estudos! Fundamentos de lógica matemática e métodos de demonstração 9 1 Fundamentos de lógica matemática e métodos de demonstração Você já se perguntou como surgiram as diversas fórmulas da ma- temática, como as famosas fórmulas de Bhaskara e de Pitágoras? Já imaginou o porquê de elas sempre funcionarem? Isso se deve ao fato de que essas (e muitas outras) fórmulas foram demonstradas, isto é, alguém, utilizando um método lógico dedutivo, provou que elas são sempre válidas. Neste capítulo, você irá aprender os principais fundamentos da lógica matemática, por exemplo, qual é o principal objetivo de se estudá-la, o que é um paradoxo, o que é uma proposição e como podemos operar com proposições. Além disso, aprenderá os principais métodos de de- monstrações, isto é, as principais técnicas utilizadas para demonstrar que alguma fórmula ou propriedade é verdadeira. Por fim, você realizará suas primeiras demonstrações matemáticas. 1.1 Fundamentos de lógica matemática Vídeo A lógica matemática teve origem no século IV antes de Cristo na Grécia Antiga, com os trabalhos de Parmênides (530-460 a.C) e Zenão (510-470 a.C), mas ganhou status de ciência apenas após os trabalhos do filósofo Aristóteles (384-322 a.C), em especial na obra Organum, na qual ele estabelece os princípios dela e, poresse motivo, é chamado de pai da lógica matemática. O norte da lógica matemática é a busca pela verdade; sendo assim, possui como objeto de estudo as leis de formação do pensamento e as regras para se aplicar essas leis para investigar a verdade. Outro grande objetivo dessa ciência é entender como podemos utilizar noções previamente estabelecidas como verdadeiras para deduzir novos conhecimentos. Com o objetivo de estudar a verdade, precisamos definir o principal objeto de estudo da lógica matemática: as proposições. 10 Matemática Discreta Definição Uma proposição é uma declaração que pode ser verdadeira ou falsa. De modo mais preciso, poderíamos dizer que uma proposição é um conjunto de símbolos e palavras que exprimem um pensamento, o qual pode ser verdadeiro ou falso. Observe os seguintes exemplos de proposições. Σxemρlo 1 São proposições: • p: Tóquio é a capital da China. • q: Wellington é a capital da Nova Zelândia. • r: 1 + 5 = 6. • s: π < 3. Cada uma das proposições do exemplo anterior exprime um pensamento, al- guns verdadeiros, como os pensamentos expressos nas proposições q e r, e alguns falsos, como nas proposições p e s. Assim, dizemos que as proposições q e r pos- suem valor lógico verdadeiro (V) e a as proposições p e s possuem valor lógico falso (F). É possível escrevermos sentenças que não possuem nem valor lógico verdadei- ro nem valor lógico falso. Essas sentenças não são proposições e são conhecidas como paradoxos. Existem alguns exemplos bem conhecidos, os quais são muito utilizados na música e na literatura. Vejamos: • “O amor é ferida que dói e não se sente” – Luís Vaz de Camões. • “Estou cego e vejo” – Carlos Drummond de Andrade. • “Já estou cheio de me sentir vazio” – Renato Russo. Note que não podemos atribuir um valor lógico verdadeiro ou falso para a frase de Carlos Drummond de Andrade, pois estar cego e ver é um paradoxo. A seguir vamos analisar o paradoxo conhecido como paradoxo do mentiroso. Σxemρlo 2 Considere a seguinte sentença: Esta frase não é verdadeira. Agora, faça a análise desse paradoxo. Fundamentos de lógica matemática e métodos de demonstração 11 Note que, se a sentença é verdadeira, então, pelo seu significado, a sentença é falsa e isso é uma contradição. Semelhantemente, se a sentença for falsa, então o que ela diz não é fato e, assim, a sentença é verdadeira, ou seja, temos novamente uma contradição e, portanto, um paradoxo. A lógica matemática adota alguns axiomas, que são proposições presumida- mente assumidas como verdadeiras, porque se acredita que são de alguma forma razoáveis, por exemplo, o seguinte axioma de Euclides: “pode-se traçar uma única reta ligando dois pontos quaisquer”. Os dois princípios fundamentais da lógica matemática são: Princípio da não contradição Princípio do terceiro excluído Uma proposição não pode ter valor lógico verdadeiro e falso ao mesmo tempo. Por definição, exclui-se a possibilidade de um paradoxo ser uma proposição. Toda proposição ou é verdadeira ou é falsa, não havendo possibilidade de assumir outro valor lógico. Esse princípio diz que toda proposição não abre espaço para interpretação, isto é, ou a proposição é verdadeira ou é falsa; não existe a possibilidade de “talvez” e “depende”. Assim como fazemos com pensamentos, podemos combinar mais de uma proposição para formar uma nova, chamada de proposição composta. Mais preci- samente, dadas proposições simples p, q, r, s, t, ... podemos construir uma nova proposição P(p, q, r, s, t, ...), ou simplesmente P, formada pelas proposições simples que foram dadas. Considere os seguintes exemplos de proposições simples: • p: Welington é professor de matemática. • q: Você é estudante de matemática. • r: Você será professor de matemática. • s: Você será engenheiro. Com essas proposições podemos formar novas proposições compostas, como: • P(p, q): Welington é professor de matemática e você é estudante de matemática. • Q(s, r): Você será engenheiro ou você será professor de matemática. • R(q, r): Se você é estudante de matemática, então você será professor de matemática. • S(p, r): Welington é professor de matemática e você será professor de matemática. Utilizamos algumas palavras para conectar as proposições simples p, q, r, s e produzirmos as proposições compostas P, Q, R, S. Essas palavras são chamadas de conectivos. Na lógica matemática existem cinco conectivos: e, ou, não, se… então, e se, e somente se. O ato de combinar proposições é chamado de operação lógica e os conectivos de operadores. Para cada conector daremos um nome e um símbolo especial. 12 Matemática Discreta O quadro a seguir apresenta as cinco operações lógicas, seus conectivos e res- pectivos símbolos. Quadro 1 Conectivos lógicos e seus símbolos Conectivo Símbolo do conectivo Operação do conectivo e ∧ Conjunção ou ∨ Disjunção não ∼ ou ¬ Negação se… então → Condicional se, e somente se ↔ Bicondicional Fonte: Elaborado pelo autor. Dada uma proposição lógica composta, iremos utilizar o valor lógico das pro- posições simples que a compõem para determinar o seu valor lógico. Isso só será possível se as operações estiverem bem definidas. Para cada conjunto de proposi- ções simples, com seus respectivos valores lógicos, obtemos um único valor lógico possível para a proposição composta. Os valores lógicos das cinco operações lógicas são definidos como segue. 1. Negação A negação da proposição p é a proposição ∼p (não p), cujo valor lógico é definido da seguinte forma: • O valor lógico de ∼p é verdadeiro se o valor lógico de p for falso. • O valor lógico de ∼p é falso se o valor lógico de p for verdadeiro. Podemos organizar essa informação em uma tabela, a qual é chamada de tabela-verdade da proposição ∼p. p ~p V F F V Vejamos no exemplo a seguir como aplicar a tabela-verdade da negação para encontrar o valor lógico de uma proposição composta formada pela negação de uma proposição dada. Σxemρlo 3 Considere a proposição p: Tóquio é a capital da China. Encontre o valor lógico da negação da proposição dada. Fundamentos de lógica matemática e métodos de demonstração 13 Sabemos que p tem valor lógico falso (F); sendo assim, o valor lógico da proposi- ção ~p: Não é verdade que Tóquio é a capital da China tem valor lógico verdadeiro (V). 2. Conjunção A conjunção das proposições p e q é a proposição p ∧ q (p e q), cujo valor lógico é definido da seguinte maneira: • O valor lógico de p ∧ q é verdadeiro se os valores lógicos de p e q são verdadeiros. • O valor lógico de p ∧ q é falso se o valor lógico de p ou de q é falso. A tabela-verdade da proposição p ∧ q é apresentada a seguir: p q p ∧ q V V V V F F F V F F F F Vejamos no exemplo a seguir como aplicar a tabela-verdade da conjunção para encontrar o valor lógico de uma proposição composta formada pela conjunção de duas proposições simples dadas. Σxemρlo 4 Considere as proposições p: Welington é professor de matemática, q: Wellington é capital da Nova Zelândia e s: π < 3. Encontre o valor lógico de p ∧ q, p ∧ s e q ∧ s. Sabemos que p tem valor lógico (V), q tem valor lógico (V) e s tem valor lógico (F). Sendo assim, p ∧ q tem valor lógico (V), p ∧ s tem valor lógico (F), q ∧ s tem valor lógico (F). 3. Disjunção A disjunção das proposições p e q é a proposição p ∨ q (p ou q), cujo valor lógico é definido do seguinte modo: • O valor lógico de p ∨ q é verdadeiro se o valor lógico de p é verdadeiro ou o valor lógico de q é verdadeiro. • O valor lógico de p ∨ q é falso se o valor lógico de p é falso e o valor lógico de q é falso. A tabela-verdade da proposição p ∨ q é apresentada a seguir: 14 Matemática Discreta p q p ∨ q V V V V F V F V V F F F Vejamos no exemplo a seguir como aplicar a tabela-verdade da disjunção para encontrar o valor lógico de uma proposição composta formada pela disjunção de duas proposições simples dadas. Σxemρlo 5 Considere as proposições p: Welington é professor de matemática,q: Wellington é capital da Nova Zelândia e s: π < 3. Encontre o valor lógico de p ∨ q, p ∨ s e q ∨ s. Sabemos que p tem valor lógico (V), q tem valor lógico (V) e s tem valor lógico (F). Sendo assim, p ∨ q tem valor lógico (V), p ∨ s tem valor lógico (V), q ∨ s tem valor lógico (V). 4. Condicional A condicional das proposições p e q é a proposição p → q (se p então q), cujo valor lógico é definido da seguinte forma: • O valor lógico de p → q é verdadeiro se p e q são verdadeiros. • O valor lógico de p → q é verdadeiro sempre que p é falso. • O valor lógico de p → q é falso se p é verdadeiro e q é falso. A seguir representamos a tabela-verdade da proposição p → q. p q p → q V V V V F F F V V F F V Vejamos no exemplo a seguir como aplicar a tabela-verdade da condicional para encontrar o valor lógico de uma proposição composta formada pela condicional p → q de duas proposições simples. Σxemρlo 6 Considere as proposições p: Welington é professor de matemática, q: Wellington é capital da Nova Zelândia e s: π < 3. Encontre o valor lógico de p → q, p → s e s → q. Fundamentos de lógica matemática e métodos de demonstração 15 Sabemos que p tem valor lógico (V), q tem valor lógico (V) e s tem valor lógico (F). Sendo assim, p → q tem valor lógico (V), p → s tem valor lógico (F), s → q tem valor lógico (V). 5. Bicondicional A bicondicional de duas proposições p e q é a proposição p ↔ q (p se, e somente se, q), cujo valor lógico é definido da seguinte maneira: • O valor lógico de p ↔ q é verdadeiro se p e q são verdadeiros. • O valor lógico de p ↔ q é verdadeiro se p e q são falsos. • O valor lógico de p ↔ q é falso se p é verdadeiro e q é falso. • O valor lógico de p ↔ q é falso se p é falso e q é verdadeiro. A seguir, representamos a tabela-verdade da proposição p ↔ q. p q p ↔ q V V V V F F F V F F F V Vejamos no exemplo a seguir como aplicar a tabela-verdade da bicondicional para encontrar o valor lógico de uma proposição composta formada pela bicondi- cional p ↔ q de duas proposições simples. Σxemρlo 7 Considere as proposições p: Welington é professor de matemática, q: Welling- ton é capital da Nova Zelândia e s: π < 3. Encontre o valor lógico de p ↔ q, p ↔ s e s ↔ q. Sabemos que p tem valor lógico (V), q tem valor lógico (V) e s tem valor lógico (F). Sendo assim, p ↔ q tem valor lógico (V), p ↔ s tem valor lógico (F), s ↔ q tem valor lógico (F). Podemos construir tabelas-verdade de proposições compostas forma- das por mais de duas proposições simples. Nesse caso, o número de linhas da tabela-verdade vai depender do número de proposições simples; mais especifica- mente, o número de linhas da tabela-verdade da proposição composta P será 2n, onde n é o número de proposições simples que a compõem. Vejamos um exemplo: 16 Matemática Discreta Σxemρlo 8 Sejam p, q e r três proposições simples, vamos construir a tabela-verdade da proposição composta P(p, q, r): p ∧ r → ~q ∨ r. Primeiro note que o número de linhas da tabela-verdade será 2³. Além disso, teremos as colunas p, q, r, ~q, p ∧ r, ~q ∨ r e P: p ∧ r → ~q ∨ r. Mais precisamente, a tabela-verdade de P(p, q, r) é: p q r ~q p ∧ r ~q ∨ r P V V V F V V V V V F F F F V V F V V V V V V F F V F V V F V V F F V V F V F F F F V F F V V F V V F F F V F V V Observamos que a última coluna da tabela-verdade de P(p, q, r): p ∧ r → ~q ∨ r possui apenas valor lógico verdadeiro. Nesse caso, dizemos que P é uma tautologia. Por outro lado, chamaremos de contradição toda proposição composta P que pos- sui apenas valor lógico falso na última coluna de sua tabela-verdade. Podemos então utilizar a tabela-verdade para verificarmos se uma proposição composta é verdadeira ou não. Para tanto, basta considerarmos o valor lógico da última coluna da linha referente aos valores lógicos das proposições simples que a compõem. Por exemplo, se considerarmos p: Welington é professor de matemática (V), q: Wellington é capital da Nova Zelândia (V) e s: π < 3 (F), teremos que o valor lógico de P(p, q, r): p ∧ r → ~q ∨ r será (V). Basta olharmos para a segun- da linha de sua tabela-verdade. Durante a construção da tabela-verdade do exemplo anterior você deve ter se perguntado: “como saberei qual operação lógica irei realizar primeiro?”. Assim como acontece nas operações com números reais, as operações lógicas possuem uma ordem de preferência para serem realizadas. A ordem de preferência para operações lógicas é a seguinte: negação, conjunção, disjunção, condicional, bicon- dicional, sempre dando preferência para as operações entre parênteses. Fundamentos de lógica matemática e métodos de demonstração 17 Definição Duas proposições compostas P e Q são chamadas de logicamente equivalentes se a tabela-verdade de P ↔ Q é uma tautologia. Nesse caso, escrevemos que P ≡ Q são logicamente equivalentes. A seguir apresentamos dois exemplos de proposições equivalentes. Esses dois exemplos são conhecidos como Leis de De Morgan e são superimportantes. Cons- truiremos a tabela-verdade de uma delas para comprovar que realmente temos uma equivalência lógica. Σxemρlo 9 As seguintes equivalências lógicas são conhecidas como Leis de De Morgan. • ~(p ∨ q) ≡ ~p ∧ ~q. • ~(p ∧ q) ≡ ~p ∨ ~q. Vamos verificar que o segundo item é realmente uma equivalência lógica. Por definição, devemos construir a tabela-verdade de P: ~(p ∧ q) ↔ ~p ∨ ~q e verificar que temos uma tautologia. p q ∼p ∼q p ∧ q ∼(p ∧ q) ∼p ∨ ∼q P V V F F V F F V V F F V F V V V F V V F F V V V F F V V F V V V Observamos que P é uma tautologia; sendo assim, temos a seguinte equivalên- cia: ~(p ∧ q) ≡ ~p ∨ ~q. Como já foi comentado, podemos utilizar a tabela-verdade para analisar o valor lógico de uma proposição composta. A seguir, apresentamos um exemplo de como isso funciona para proposições matemáticas. Σxemρlo 10 Sejam p: π < 3 e q: 1 + 2 = 4 duas proposições matemáticas, vamos analisar o valor lógico de P(p, q): ~p ∧ q ↔ ~q ∧ p. Agora é com você: construa a tabela-verdade para provar que a primeira Lei de De Morgan, apre- sentada no exemplo, realmente é uma equivalência lógica. Desafio 18 Matemática Discreta Inicialmente, vamos traduzir P(p, q) em uma sentença matemática (traduzindo os conectivos para a linguagem formal). Temos que: • ~p: π ≥ 3. • ~q: 1 + 2 ≠ 4. • ~p ∧ q: π ≥ 3 e 1 + 2 = 4. • ~q ∧ p: 1 + 2 ≠ 4 e π < 3. Então, P(p, q): π ≥ 3 e 1 + 2 = 4 se, e somente se, 1 + 2 ≠ 4 e π < 3. Vamos agora construir a tabela-verdade de P(p, q). p q ∼p ∼p ∧ q ∼q ∼q ∧ p P(p, q) V V F F F F V V F F F V V F F V V V F F F F F V F V F V Para analisarmos o valor lógico da proposição composta P(p, q) basta olharmos para os valores lógicos das proposições simples p e q. Sabemos que ambas, p e q, são falsas. Sendo assim, o valor lógico de P(p, q) está na quarta linha de sua tabela-verdade (a linha onde os valores lógicos de p e q são falsos), ou seja, P(p, q) tem valor lógico verdadeiro. Você deve estar se perguntando: “sempre terei que construir a tabela-verdade para provar que uma proposição matemática é verdadeira?”. A resposta para essa questão é não. Nas próximas seções deste capítulo iremos aprender mé- todos e linhas de raciocínio lógico que são utilizados para provar que uma pro- posição matemática é verdadeira. Esses métodos são conhecidos como métodos de demonstração. Antes de iniciarmos o estudo sobre os métodos de demonstração, precisamos estabelecer a estrutura de uma proposição matemática e algumas nomenclaturas. Toda proposição matemática tem sua estrutura formada por uma hipótese, a qual é a premissa que assu- mimos como verdadeira, e por uma tese, uma afirmação que queremos provar utilizando nossa hipótese. Observe a seguinte proposição que estabelece a fórmula de Bhaskara: Seja ax² + bx + c = 0, com a ≠ 0, uma equação do segundo grau, então: x b� � b � ac a � � � � �2 4 2 Nessa proposição, nossa hipótese é “p: ax² + bx + c = 0, com a ≠ 0, é uma equação do segundo grau” e nossa tese é “q:x b b ac a � � � �2 4 2 ”. Fundamentos de lógica matemática e métodos de demonstração 19 As proposições matemáticas recebem nomes especiais conforme seu grau de importância. Como vimos, os axiomas são proposições presumidamente assumidas como verdadeiras, ou seja, que não requerem provas. Observe os seguintes exemplos de axiomas da adição de números reais: • Associatividade: sejam a, b, c ∈ ℝ, tem-se (a + b) + c = a + (b + c). • Comutatividade: sejam a, b ∈ ℝ, tem-se a + b = b + a. Um teorema é uma sentença matemática que pode ser provada como verdadeira. Podemos citar como exemplo o famoso Teorema de Pitágoras: em qualquer triângulo retângulo, o quadrado do comprimento da hipotenusa é igual à soma dos quadrados dos comprimentos dos catetos. Um lema é um teorema de menor importância que pode ser utilizado para demonstrar teoremas mais importantes. Nesse sentido, ao nos depararmos com um teorema complicado, para realizar- mos a sua demonstração de modo simples, o dividimos em vários lemas. Como exemplo, vamos considerar o importantíssimo lema que é utilizado para demons- trar o algoritmo da divisão de números inteiros. Lema – Método de divisão de Euclides Sejam a e b inteiros, tais que a ≥ 0 e b > 0, então existem q e r, quociente e resto respectivamente, tais que a = bq + r e 0 ≤ r < b. Um corolário é uma proposição que pode ser provada diretamente de um teorema mais importante já demonstrado. Tomemos como exemplo o seguinte corolário do Teorema de Pitágoras: seja d a diagonal de um quadrado de lado l, então d = l√2. Estabelecida a estrutura de uma proposição matemática e sua nomenclatura, iremos estudar a seguir os métodos de demonstração. 20 Matemática Discreta 1.2 Demonstração direta e demonstração por contraposiçãoVídeo Podemos representar a fórmula de Bhaskara pela proposição composta p → q, onde p: ax² + bx + c = 0, com a ≠ 0, é uma equação do segundo grau e q: x �b� � b � � ac a � � � �2 4 2 . Demonstrar a fórmula de Bhaskara é, portanto, assumir que p é verdade e provar que q também é verdade. Utilizar uma sequência lógica de pensamentos para, com base na hipótese, pro- var que a conclusão é verdadeira é conhecido como método de demonstração direta. Esse tipo de demonstração consiste em utilizar as particularidades da hi- pótese para provar a tese. Vamos apresentar alguns exemplos de demonstrações diretas, inclusive uma demonstração para a famosa fórmula de Bhaskara. Σxemρlo 11 Considere as definições de números inteiros pares e ímpares: • Um número inteiro n é par se existe um k ∈ ℤ tal que n = 2k. • Um número inteiro m é ímpar se existe um t ∈ ℤ tal que m = 2t + 1. Demonstre os teoremas a seguir: a. Se a e b são dois números inteiros ímpares, então o produto ab é um número ímpar. b. Se a e b são dois números inteiros pares, então o produto ab é um número par. a. Demonstração Considere a e b dois números inteiros ímpares. Pela definição de número inteiro ímpar, sabemos que a = 2t1 + 1 e b = 2t2 + 1. Logo, o produto ab é ab = (2t1 + 1)(2t2 + 1) = 2t12t2 + 2t1 + 2t2 + 1 = 2(2t1t2 + t1 + t2) + 1, ou seja, ab = 2t3 + 1, onde t3 = 2t1t2 + t1 + t2. Isso mostra que ab tem a forma de um número inteiro ímpar. Podemos assim concluir que ab é um número inteiro ímpar. b. Demonstração Sejam a e b dois números inteiros pares, pela definição de número inteiro par, sabemos que a = 2k1 e b = 2k2. Logo, o produto ab é ab = (2k1)(2k2) = 2(2k1k2), ou seja, ab = 2k3, onde k3 = 2k1k2. Isso mostra que ab tem a forma de um número inteiro par. Podemos concluir, portanto, que ab é um número inteiro par. Vamos provar propriedades análogas aos teoremas anteriores, porém com relação à soma de números inteiros. Fundamentos de lógica matemática e métodos de demonstração 21 Σxemρlo 12 Demonstre os seguintes teoremas sobre a soma de números inteiros: a. Se a e b são dois números inteiros ímpares, então a soma a + b é um número inteiro par. b. Se a e b são dois números inteiros pares, então a soma a + b é um número inteiro par. a. Demonstração Considere a e b dois números inteiros ímpares. Pela definição de número inteiro ímpar sabemos que a = 2t1 + 1 e b = 2t2 + 1. Logo, a soma a + b é a + b = (2t1 + 1) + (2t2 + 1) = 2(t1 + t2) + 2 = 2(t1 + t2 + 1), ou seja, a + b = 2k3, onde k3 = t1 + t2 + 1 Isso mostra que a + b tem a forma de um número inteiro par. Podemos assim concluir que a + b é um número inteiro par. b. Demonstração Sejam a e b dois números inteiros pares, pela definição de número inteiro par, sabemos que a = 2k1 e b = 2k2. Logo, a soma a + b é: a + b = (2k1) + (2k2) = 2(k1 + k2), ou seja, a + b = 2k3, onde k3 = k1 + k2 Isso mostra que a + b tem a forma de um número inteiro par. Podemos, portanto, concluir que a + b é um número inteiro par. Vamos agora demonstrar a famosa fórmula de Bhaskara. Teorema (Fórmula de Bhaskara) Seja ax² + bx + c = 0, com a ≠ 0, uma equação do segundo grau, então, x b� � b � � ac a � � � �2 4 2 Demonstração Consideremos a equação ax² + bx + c = 0, com a ≠ 0. Vamos aplicar várias opera- ções nessa equação para chegarmos a nossa tese. ax bx c �2 0� � � � �÷a � � � � a a x b a x c a a ��������������������2 0 � � � � � � �� � � ��x b a x c a 2 + b 4a 2 2 � � � � �x b a x b 4a c a + b 4a � 2 2 2 2 2 22 Matemática Discreta � � � � � � � � � �x b a b ac a2 4 4 2 2 2 � � � � � � � � � �x b a b ac a2 4 4 2 2 2 � � � � � � � � � � �x b a �� b ac a �� 2 4 4 2 2 � � � � � � � � � � �� x b a �� b ac a2 4 2 2 � � � � �x b a b ac a � 2 4 2 2 � x � b b ac a �� � � � � 2 4 2 Sendo assim, utilizamos nossa hipótese para provar que nossa tese é verdadeira, ou seja, a fórmula de Bhaskara é verdadeira. Durante a demonstração da fórmula de Bhaskara você deve ter percebido que há casos em que demonstrar um teorema pelo método direto pode não ser algo simples. Podemos contornar esse fato utilizando o método de demonstração por contraposição. Esse método consiste na seguinte tautologia: P: p → q ↔ ∼q → ∼p. Vamos verificar, por meio de sua tabela-verdade, que P é realmente uma tautologia. p q ~p ~q p → q ∼q → ∼p P V V F F V V V V F F V F F V F V V F V V V F F V V V V V Como todos os valores lógicos da última coluna da tabela-verdade de P são ver- dadeiros, concluímos que P é realmente uma tautologia. Vejamos um exemplo simples de como aplicar o método de demonstração por contraposição. Σxemρlo 13 Considere as proposições p: João é curitibano e q: João é brasileiro, e a proposi- ção composta dada por P: p → q. Aplique o método de demonstração por contra- posição sem usar a tabela-verdade. Fundamentos de lógica matemática e métodos de demonstração 23 A proposição composta P pode ser traduzida como P: Se João é curitibano, en- tão João é brasileiro. Essa proposição é equivalente à proposição Q: ~q → ~p, que traduzida é Q: Se João não é brasileiro, então João não é curitibano. Claramente, P é verdadeira sempre que Q é verdadeira e vice-versa. Vamos agora aplicar o método de demonstração por contraposição para provar o seguinte teorema: Teorema Se a é um número natural e a² é par, então a é um número par. Demonstração Nossa proposição é “p: a² é par → q: a é par”. Vamos demonstrar que a propo- sição equivalente “∼q: a é ímpar → ∼p: a² é ímpar” é verdadeira. Com efeito, se a é ímpar existe k natural tal que a = 2k + 1. Logo, a² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1 = 2k2 + 1, onde k2 = 2k² + 2k, ou seja, a² é um número ímpar, provando que a contrapositiva do teorema é verdadeira. Podemos então concluir que o teorema é verdadeiro. Definição Dizemos que um número a não é múltiplo de b se a divisão de a por b tem resto diferente de zero. Um núme- ro a não é múltiplo de b se a = kb + r, onde 0 < r < b. Por exemplo, 7 não é múltiplo de 3, pois 7 = 2(3) + 1. Vamos demonstrar o seguinte teorema pelo método da contrapositiva. Teorema Se a é um número natural e a³ é múltiplo de três, então a é um múltiplo detrês. Demonstração Nossa proposição é “p: a³ é múltiplo de 3 → q: a é múltiplo de 3”. Vamos de- monstrar que a proposição equivalente “~q: a não é múltiplo de 3 → ∼p: a³ não é múltiplo de 3” é verdadeira. Com efeito, note que se a não é múltiplo de 3, então a = 3k1 + 1 ou a = 3k2 + 2. Analisando ambos os casos: • Se a = 3k1 + 1, temos: a³ = (3k1 + 1)³ = (3k1 + 1)² (3k1 + 1) = 27k1³ + 9k1² + 9k1 + 1 = 3(9k1³ + 3k1² + 3k1) + 1 = 3k3 + 1 Onde k3 = 9k1³ + 3k1² + 3k1. Existe mais de uma maneira de se demons- trar um teorema! Um dos teoremas mais impor- tantes que estudamos e ensinamos para os alunos da educação básica é o Teorema de Pitágoras. Na página Decifrando a Matemática, da Unicamp, você vai encontrar vários caminhos diferentes para a demonstração do Teorema de Pitágoras, além de encontrar boas aborda- gens para o ensino desse teorema. Disponível em: www.ime.unicamp. br/~apmat/teorema-de-pitagoras/. Acesso em: 5 mar. 2021. Saiba mais http://www.ime.unicamp.br/~apmat/teorema-de-pitagoras/ http://www.ime.unicamp.br/~apmat/teorema-de-pitagoras/ 24 Matemática Discreta • Se a = 3k2 + 2, temos: a³ = (3k2 + 2)³ = (3k2 + 2)²(3k2 + 2) = 27k2³ + 18k2² + 36k2 + 6 + 2 = 3(9k2³ + 6k2² + 12k2 + 2) + 2 = 3k4 + 2 Onde k4 = 9k2³ + 6k2² + 12k2. Sendo assim, a³ = 3k3 + 2 ou a³ = 3k4+2, provando que a³ não é múltiplo de três, ou seja, a contrapositiva do teorema é verdadeira. Podemos concluir, portanto, que o teorema é verdadeiro. 1.3 Demonstração por contradição Vídeo Esse método consiste em utilizar uma contradição para mostrar que uma pro- posição é verdadeira e tem como inspiração a seguinte tabela-verdade: p q ~p ∼p → q V V F V V F F V F V V V F F V F Observando as duas primeiras linhas da tabela-verdade, temos que p é verda- deira sempre que ~p → q é verdadeira. Isso significa que para mostrarmos que uma proposição p é verdadeira, basta encontrarmos q, tal que ~p → q é verdadeira. Resumidamente, o método de demonstração por contradição consiste em afirmar a hipótese, negar a tese e chegar a uma contradição. Vejamos alguns exemplos de aplicação do método de demonstração por contradição. Σxemρlo 14 Utilize o método de demonstração por contradição para provar que o único número que, quando somado com ele mesmo, resulta no próprio número é o zero. Queremos demonstrar o seguinte teorema: Se a + a = a, então a = 0. Para isso, vamos utilizar o método da demonstração por contradição. Nossa hipótese p é “a + a = a” e nossa tese q é “a = 0”. Vamos então negar q, ou seja, ~q: a ≠ 0. Suponha então que a + a = a e a ≠ 0. Temos que 2a = a, e como a ≠ 0, podemos realizar a divisão por a (se a = 0, a divisão não pode ser realizada, afinal, não existe divisão por zero). Fundamentos de lógica matemática e métodos de demonstração 25 Finalmente, 2a a a a = . Concluímos que 2 = 1. Isso é uma contradição; logo, não podemos ter a ≠ 0, então a = 0. Agora, vamos utilizar o método de demonstração por contradição para demons- trar o seguinte teorema, que já foi demonstrado pelo método de demonstração direta. Σxemρlo 15 Utilize o método de demonstração por contradição para provar o seguinte teo- rema: Se a e b são dois números inteiros pares, então a soma a + b é um número inteiro par. Nossa hipótese é “p: a e b são números inteiros pares” e nossa tese é “q: a + b é um número inteiro par”. Vamos então negar q, isto é, ∼q: a + b é um número ímpar. Considere que: • a = 2k1 • b = 2k2 • a + b é um número ímpar Logo, a + b = 2k3 + 1, onde, por um lado, a + b = 2k1 + 2k2 e, por outro lado, a + b = 2k3 + 1. Daí, 2k1 + 2k2 = 2k3 + 1 ⇒ 2(k1 + k2 - k3) = 1. Isso nos diz que 1 é um número par, obvia- mente uma contradição, da qual obtemos que a + b é um número par. 1.4 Demonstração por absurdo Vídeo Esse método consiste em assumir que a hipótese e a negação da tese são verdadeiras, para construir uma linha de raciocínio que nos leve a um absur- do. A demonstração por absurdo tem como inspiração a seguinte tautologia P: (p → q) ↔ (p ∧ ∼q) → c, onde c é uma contradição. Essa tautologia pode ser veri- ficada pela tabela-verdade a seguir. p q c ∼q p ∧ ∼q p → q p ∧ ∼q → c P V V F F F V V V V F F V V F F V F V F F F V V V F F F V F V V V Sendo assim, para demonstrar que um teorema é verdadeiro pelo método de demonstração por absurdo: 1. Assumimos que a hipótese e a negação da tese são verdadeiras. 2. Construímos uma linha de raciocínio de modo a encontrarmos um absurdo. 26 Matemática Discreta Considere o seguinte exemplo de aplicação do método de demonstração por absurdo. Σxemρlo 16 Demonstre o seguinte teorema pelo método de demonstração por absurdo: Se a é um número natural e a² é par, então a é um número par. Para demonstrarmos por absurdo o teorema, temos que nossa hipótese é “p: a² é par” e nossa tese “q: a é par”. Suponha que p e ∼q, “a é ímpar”, sejam verdadeiras. Se a é ímpar, a = 2k1 + 1, de onde a² = (2k1 + 1)² = 4k1² + 4k1 + 1 = 2(2k1² + 2k1) + 1 = 2k2 + 1 Onde k2 = 2k1² + 2k 1. Isto é, a² é par e ímpar ao mesmo tempo. Um absurdo! Portanto, o teorema é válido. 1.5 Demonstração por indução finita Vídeo Em matemática discreta os principais problemas de estudo são problemas de contagem em espaços discretos, por exemplo: o espaço formado por todas as ida- des dos cidadãos brasileiros. Desse modo, o principal método de demonstração que utilizamos é o método da indução finita. Esse método é utilizado para de- monstrar teoremas como os seguintes. Teorema A soma dos n primeiros números naturais é n n� ��� �1 2 . Note que o teorema diz que se somarmos, por exemplo, 1 + 2 + 3 + 4 o resultado será 4 4 1 2 4 5 2 20 2 10 �� � � � � � � . Teorema A soma dos quadrados dos n primeiros números naturais é n n n� � � ��� � �� �1 2 1 6 . Utilizando o teorema podemos concluir, por exemplo, que a soma 1² + 2² + 3² é igual a 3 3 1 2 3 1 6 3 4 7 6 14 �� � � � �� � � � �� � � . Mas como podemos demonstrar que esses teoremas são válidos para qualquer número? O método da indução finita consiste nos seguintes passos: Fundamentos de lógica matemática e métodos de demonstração 27 Mostrar que o teorema é válido para o menor n possível que satisfaz a hipótese. Assumir que o teorema é válido para n = k. 1 2 Utilizar o fato de o teorema ser válido para n = k para demonstrar que o teorema é verdadeiro para n = k + 1. 3 Podemos observar pelo passo 3 que a principal ideia da demonstração por indução finita é mostrar que o teorema é sempre válido para o próximo núme- ro. Vamos utilizar o método de indução para demonstrar os teoremas utilizados como exemplos. Teorema A soma dos n primeiros números naturais é n n� ��� �1 2 . Demonstração Vamos inicialmente mostrar que o resultado é válido para n = 1. Se n = 1, temos que 1 = 1 1� ��� � � 1 2 2 2 = 1, provando que o teorema é válido para n = 1. Assumindo que o teorema é válido para n = k, ou seja, assumindo que 1 + 2 + 3 + ... + k = k k� ��� �1 2 Vamos mostrar que o teorema é válido para n = k + 1, ou seja, mostraremos que 1 + 2 + 3 + ... + k + (k + 1) = � k� � k� ��� � �� �1 2 2 De fato, � � � �k� �(k + 1) � k k� � � � k� �1 2 3 1 2 1� � � � � � �� � � �� �... =� k k� � � �� � � �1 2 1 2 ( )k =� k� � � �� � �1 2 2 ( )k Provando assim que 1 + 2 + 3 + ... + k + (k + 1) = k� � k� ��� � �� �1 2 2 . Desse modo, podemos concluir que o teorema é válido. Finalizaremos esta seção com o seguinte teorema: 28 Matemática Discreta Teorema A soma dos quadrados dos n primeiros números naturais é n n� � n� ��� � �� �1 2 1 6 . Demonstração Inicialmente, vamos mostrar que o resultado é válido para n = 1. Se n = 1, temos que 1² = 1 1� � (1)� ��� � �� � � � 1 2 1 6 12 3 6 6 6 ( )( ) = 1, provando que o teorema é válido no caso n = 1. Assumindo que o teorema é válido para n = k, ou seja, assumindo que 1² + 2² + 3² + ... + k² = k k� � k� ��� � �� �1 2 1 6 Mostraremos que o teorema é válido para n = k + 1, ou seja, que 1² + 2² + 3² + ... +k² + (k + 1)² = k� � k� � k� ��� � �� � �� �1 2 2 3 6 De fato, 1² + 2² + 3² + ... + k² + (k + 1)² = k k� � k� ��� � �� �1 2 1 6 + (k + 1)² � �� � �� � � �k� � k� �1 2 1 6 1 6 [ ( )]k k � �� � � �� �k k k1 2 7 6 6 2 � �� � �� � �� �k k k1 2 2 3 6 Provando, assim, que 1² + 2² + 3² + ... + k² + (k + 1)² = k� k� � k� ��� � �� � �� �1 2 2 3 6 . Desse modo, podemos concluir que o teorema é válido. CONSIDERAÇÕES FINAIS Neste capítulo, aprendemos que, para afirmarmos que um teorema ou uma fórmu- la é verdadeira ou não, precisamos realizar um procedimento matemático chamado de demonstração matemática, a qual consiste em provar que o teorema ou a fórmula é verdadeira para qualquer elemento que satisfaça suas hipóteses. Estudamos que é importante conhecermos os diferentes métodos de demonstra- ção, pois podemos utilizar qualquer um deles para mostrar que um teorema ou uma fórmula é verdadeira. Contudo, o ato de construir um raciocínio lógico para demons- trar uma proposição torna-se mais fácil (ou mais difícil) conforme o método escolhido. ATIVIDADES 1. Utilize a técnica de demonstração direta para provar os seguintes teoremas: a) Se a é um número inteiro par e b é um número inteiro ímpar, então a soma a + b é um número inteiro ímpar. b) Se a é um número inteiro par e b um número inteiro ímpar, então o produto ab é um número par. O filme O homem que viu o infinito conta a história do matemático indiano Srinivasa Ramanujan (1887- 1920). No filme, podemos perceber a importância de uma boa escrita matemá- tica, ou seja, saber fazer boas demonstrações. Apesar de ter boas ideias, Ramanujan sofreu muito em sua história como matemático pelo fato de não ter a capacidade de escrever boas demons- trações. Direção Matt Brown. Londres: Animus Films, 2016. Filme Fundamentos de lógica matemática e métodos de demonstração 29 2. Utilize a técnica de demonstração por contraposição para o seguinte teorema: Se a é um número natural e a² é ímpar, então a é um número ímpar. 3. Utilize a técnica de demonstração por contradição para provar o seguinte teorema: Se a é um número inteiro par e b é um número inteiro ímpar, então a soma a + b é um número inteiro ímpar. 4. Utilize a técnica de demonstração por indução para provar o seguinte teorema: Se n é um número natural, 1² + 3² + 5² + ... + (2n - 1)² = n 2n�-�1 2n�+�1 3 � �� � . REFERÊNCIAS FILHO, E. A. Iniciação à lógica matemática. São Paulo: Nobel, 2002. GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: Addison- Wesley, 2004. ROSEN, K. H. Matemática discreta e suas aplicações. 6. ed. São Paulo: McGraw-Hill, 2009. 30 Matemática Discreta 2 Teoria de conjuntos As ideias fundamentais da teoria dos conjuntos e da álgebra dos con- juntos são provavelmente os conceitos mais importantes em todas as áreas da matemática, e isso não é diferente na matemática discreta. Este capítulo apresenta a teoria dos conjuntos. O material é principal- mente elementar. Lembre-se de que, em matemática, elementar não significa simples, mas sim que não requer vários conhecimentos prévios para ser com- preendido. O material elementar pode ser bastante desafiador, e parte deste capítulo talvez exija que você ajuste seu ponto de vista para compreendê-lo. Um ponto em especial no qual este capítulo pode divergir da sua ex- periência anterior com teoria de conjuntos é o fato de realizarmos a de- monstração das propriedades elementares dos conjuntos. Neste capítulo você aprenderá a noção intuitiva de conjuntos, como descrever um conjunto e seus subconjuntos e, por fim, como realizar ope- rações entre conjuntos e as principais propriedades dessas operações. 2.1 Noção intuitiva de conjuntos Vídeo Uma matilha, um cacho de uvas ou um bando de pombos são exemplos de con- juntos. O conceito matemático de um conjunto pode ser expresso por meio desses exemplos. Porém, como definir um conjunto matemático? Um conjunto matemático pode ser definido simplesmente como uma coleção de objetos diferentes, mais precisamente: Definição Um conjunto A é uma coleção de objetos distintos. Vejamos o exemplo a seguir: Σxemρlo 1 São exemplos de conjuntos: • A = {1, 2, 3, 4, 5}. • B = {quadrado, triângulo, circunferência}. • C = {Pedro, Maria, Welington}. • Os conjuntos são denotados por letras maiúsculas A, B, C, … do nosso alfabeto. • Os objetos de um conjunto A são chamados de elementos do conjunto. • Se A é um conjunto formado pelos objetos a, b, c, d, escreve- mos A = {a, b, c, d}. Importante Teoria de conjuntos 31 Precisamos prestar atenção a um fato bem importante na definição de conjun- tos: em um conjunto não é permitida a repetição de elementos. Σxemρlo 2 Não são conjuntos: • A = {1, 1, 2, 3, 4, 5}. • B = {quadrado, triângulo, triângulo, circunferência}. • C = {Pedro, Maria, Welington, Welington}. Note que, no Exemplo 2, A, B e C não são conjuntos pelo fato de existirem repe- tições entre seus elementos. Quando existem repetições de elementos, chamamos A, B e C de multiconjuntos. Um conjunto A = {a, b, c, d, …} com infinitos elementos é chamado de conjunto infinito. • Se a é um elemento do conjunto A, escrevemos a ∈ A e dizemos que a pertence a A. • Se A é um conjunto e b não é um elemento de A, escrevemos b ∉ A e dizemos que b não pertence a A. Importante 2.2 Descrição e igualdade de conjuntos Vídeo A maneira mais básica de se definir um conjunto é listar seus elementos entre chaves, por exemplo: A = {2, 4, 6, 8, 10}, como feito na seção anterior. Também podemos definir um conjunto fornecendo uma regra chamada lei de formação do conjunto, que determina com segurança se um objeto é um membro ou não, por exemplo: B = {x | 0 < x < 1} 1 , lido como “B é o conjunto dos números x, tal que x é maior que zero e menor que um”. Se A é um conjunto descrito por uma regra, dizemos que um elemento b perten- ce a A se b satisfaz a regra que define A. Σxemρlo 3 Considere os seguintes conjuntos e suas leis de formação. • A = {x ∈ ℕ | x = 2t, onde t é um número natural}. • B = {x ∈ ℕ | x = 2t, onde t é um número natural e 1 < t < 10}. Descrevendo os elementos de A, temos que A = {2, 4, 6, …}, ou seja, A é o conjun- to dos números pares. Descrevendo os elementos de B, temos que B = {4, 6, 8, 10, 12, 14, 16, 18}, ou seja, B é o conjunto dos números pares entre 3 e 19. Observamos que A é um conjunto infinito e B é um conjunto finito com oito elementos. Note que, algumas vezes, a regra que define um conjunto não é satisfeita por nenhum elemento. Por exemplo: A = {a ∈ ℕ | a = 2t, onde t é um número natural e 1 < t < 2} O símbolo "|" é lido como tal que (alguns autores usam ":"). 1 32 Matemática Discreta Nesse caso, não existe nenhum elemento que satisfaça a regra de formação do conjunto A. Quando isso acontece, dizemos que o conjunto A é um conjunto vazio. Mais precisamente, temos a seguinte definição de conjunto vazio: Definição Um conjunto que não possui nenhum elemento é chamado de conjunto vazio. Escrevemos ∅ ou { } para representar o conjunto vazio. Σxemρlo 4 São exemplos de conjuntos vazios: • A = {x | x ≠ x}. • B = {x | x é ímpar e múltiplo de dois}. • C = {x | x é um triângulo e possui quatro lados}. • D = {x | x < 0 e x > 0}. • E = {x | x tem 20 anos de idade e x nasceu em 1820}. Na definição de conjuntos não se está exigindo nada com relação à ordem em que seus elementos aparecem, ou seja, a ordem não importa. Isso significa, por exemplo, que os conjuntos A = {1, 3, 4, 7} e B = {3, 1, 4, 7} são iguais. Em geral, po- demos definir a igualdade de dois conjuntos como: Definição Dois conjuntos A e B são iguais se possuem exatamente os mesmos elementos. Em símbolos, escrevemos: A = B ↔ ∀ x, x ∈ A ↔ x ∈ B E lemos: A é igual a B se, e somente se, para todo x, x pertence a A se, e somente se, x pertence a B. Definição Dois conjuntos A e B são diferentes se existe um elemento a ∈ A tal que a ∉ B, ou existe um elemento b ∈ Btal que b ∉ A. Em símbolos, escrevemos: A ≠ B ↔ ∃ a | a ∈ A e a ∉ B, ou ∃ b | b ∈ B e b ∉ A E lemos: A é diferente de B se, e somente se, existe a tal que a pertence a A e a não pertence a B, ou existe b tal que b pertence a B e b não pertence a A A definição de igualdade de conjuntos estabelece que, para provarmos que dois conjuntos A e B são iguais, devemos provar que: 1. Todo elemento de A também é um elemento de B. 2. Todo elemento de B também é um elemento de A. Teoria de conjuntos 33 Vejamos um exemplo. Σxemρlo 5 Prove que os conjuntos A = {x | 2x + 4 = 10} e B = {3} são iguais. Devemos mostrar que todo elemento de A é um elemento de B e que todo ele- mento de B é um elemento de A. Seja a ∈ A, pela definição do conjunto A, a é tal que 2a + 4 = 10. Resolvendo essa equação linear, temos que a = 3, ou seja, a ∈ B, uma vez que 3 ∈ B. Note que 2(3) + 4 = 10, ou seja, 3 satisfaz a definição do conjunto A e, assim, 3 ∈ A, provando que A = B. Definição Para um conjunto finito, a cardinalidade é o número de elementos que ele contém. Em notação simbóli- ca, a cardinalidade de um conjunto A é descrita como |A| ou n(A). Se A é um conjunto com infinitos elementos, dizemos que a cardinalidade de A é infinita e escrevemos |A| = ∞ ou n(A) = ∞. Vejamos o exemplo a seguir: Σxemρlo 6 A cardinalidade do conjunto A = {1, 3, 10, 40, 400} é n(A) = 5, e a cardinalidade do conjunto B = {x | x é um número par} é n(B) = ∞. Chamaremos de conjunto unitário todo conjunto que possui apenas um elemen- to. O conjunto A = {27}, por exemplo, é um conjunto unitário. Quando vamos descrever um conjunto, por exemplo, o conjunto A = {todos os homens que possuem 27 anos de idade}, admitimos a existência de um conjunto maior ao qual pertencem todos os elementos que compõem o conjunto que esta- mos definindo. Esse conjunto maior é chamado de conjunto universo e é denota- do pela letra U. No nosso exemplo, U = {todos os homens}. Σxemρlo 7 Se A = {x ∈ N | x = 2k, onde k é um número natural} é o conjunto dos números naturais pares, o universo U é o conjunto de todos os números naturais. Utilizando a definição de conjunto universo, podemos introduzir um novo con- junto com base em um conjunto dado A. 34 Matemática Discreta Definição Dado um conjunto A e seja U seu conjunto universo, o conjunto dos elementos que pertencem a U e não pertencem a A é chamado de conjunto complementar de A. Denotamos o complementar de A por AC ou C(A). Vejamos no exemplo a seguir: Σxemρlo 8 Se A = {x ∈ ℕ | x = 2k, onde k é um número natural} é o conjunto dos números naturais pares, sabemos que seu universo U é o conjunto de todos os números naturais. Desse modo, pela definição de complementar, temos: AC = {x ∈ ℕ | x ≠ 2k, onde k é um número natural} Ou seja, AC é o conjunto dos números naturais ímpares. Nesta seção, você aprendeu a classificar vários objetos da vida real em termos de conjuntos. Além disso, vimos diferentes maneiras de descrever um conjunto e como podemos considerar um conjunto como parte menor de um conjunto maior (chamado de conjunto universo). Introduzindo a noção de subconjunto, vamos, na próxima seção, explorar o fato de podermos considerar um conjunto como uma parte menor de outro conjunto. 2.3 Subconjuntos Vídeo Consideremos os seguintes conjuntos: A = {capitais brasileiras} e B = {São Paulo, Porto Alegre, Curitiba}. Observamos que todos os elementos do conjunto B também são elementos do conjunto A, pois São Paulo, Porto Alegre e Curitiba são capitais brasileiras. Nesse caso, dizemos que o conjunto B é um subconjunto do conjunto A. O mesmo acontece com os conjuntos C = {0, 10, 7, 8, 79, 5} e D = {0, 7, 5}, onde D é um subconjunto de C. A definição matemática de subconjunto é apresentada a seguir: Definição Um conjunto B é subconjunto de um conjunto A se, e somente se, todo elemento de B for um elemento de A. Vejamos no exemplo a seguir: • Escrevemos B ⊂ A se B é um subconjunto de A. Nesse caso, também dizemos que B está contido em A. • Em símbolos, temos: B ⊂ A ↔ ∀ b ∈ B → b ∈ A • Escrevemos B ⊄ A se B não é subconjunto de A. Nesse caso, dizemos que B não está contido em A. • Todo conjunto A é um subcon- junto do seu universo U. Importante Teoria de conjuntos 35 Σxemρlo 9 a. {⊠, ⊝} ⊂ {⊠, ⨁, ⊟, ⊝}. b. {a, b, c} ⊄ {b, c, d}. c. {x | x é um número natural par} ⊂ {x | x é um número natural}. Podemos representar a inclusão de conjuntos de modo gráfico por meio do Dia- grama de Venn. Seja A um conjunto, U seu universo e B ⊂ A, graficamente temos: A B U Teorema A inclusão de conjuntos satisfaz as seguintes propriedades: a. ∅ ⊂ A para todo conjunto A. b. A ⊂ A (reflexiva). c. Se A ⊂ B e B ⊂ A, então A = B (antissimétrica). d. Se A ⊂ B e B ⊂ C, então A ⊂ C (transitiva). Demonstração O item a pode ser descrito na seguinte proposição: ∀ x ∈ ∅ → x ∈ A Onde temos p: ∀ x ∈ ∅ e q: x ∈ A. Como p é falsa, pois não há elementos em ∅, a proposição é sempre verdadeira, pois p → q é sempre verdadeira. Provando, então, que ∅ ⊂ A. O item b segue do fato de que, se x ∈ A, então x ∈ A. O item c segue da definição de igualdade de conjuntos. Para o item d, temos: seja x ∈ A, então, como A ⊂ B, temos que x ∈ B, mas B ⊂ C, onde x ∈ C, ou seja, A ⊂ C. Pela definição de igualdade de conjuntos, dois conjuntos A e B são iguais se, e somente se, A ⊂ B e B ⊂ A. Importante 36 Matemática Discreta Σxemρlo 10 Considere os conjuntos A = {números naturais}, B = {números naturais pares} e C = {números naturais que dividem 4}. Temos que: a. B ⊂ A e n(B) = n(A) = ∞. b. C ⊂ A e n(C) = 3 < n(A) = ∞. A inclusão de conjuntos e seus complementares está relacionada ao seguinte teorema. Teorema Sejam A e B dois conjuntos e AC e BC seus complementares, se A ⊂ B, então BC ⊂ AC. Demonstração Seja x ∈ BC, então, pela definição de conjunto complementar, temos que x ∉ B. Como A ⊂ B, tem-se que x ∉ A, ou seja, x ∈ AC. Provando, assim, que BC ⊂ AC. Definição Para qualquer conjunto A, definimos o conjunto das partes de A, denotado por ℘(A), como sendo o conjunto formado por todos os subconjuntos de A. Em símbolos: ℘(A) = {B | B ⊂ A} Observamos que, pela definição de conjunto das partes, ∅ ∈ ℘(A) e A ∈ ℘(A) para todo conjunto A. Vejamos um exemplo de como encontrar o conjunto das partes de um conjunto A. Σxemρlo 11 Seja A = {1, 11, 0}, então o conjunto das partes de A é: ℘(A) = {∅, {0}, {1}, {11}, {1,11}, {1,0}, {11,0}, {1,11,0}} No exemplo é possível notar que se n(A) < ∞, então a cardinalidade de ℘(A) também será finita; além disso, teremos que n(℘(A)) > n(A). Na verdade, é possível provar que n(℘(A)) = 2n(A). Obviamente, n(℘(A)) = ∞ se n(A) = ∞. 2.4 Operações com conjuntos Vídeo Em teoria de conjuntos, assim como em todos os tópicos estudados em mate- mática, estamos interessados em definir e compreender operações matemáticas que podem ser realizadas entres seus objetos. Nesta seção vamos definir as princi- pais operações entre conjuntos. Observamos a seguinte proprie- dade elementar da inclusão de conjuntos: Se A ⊂ B, então n(A) ≤ n(B) Importante Teoria de conjuntos 37 Começaremos com a interseção. Definição A interseção entre os conjuntos A e B é o conjunto A∩B formado pelos elementos que estão simultanea- mente em A e B. Em símbolos: A∩B = {x | x ∈ A e x ∈ B} O Diagrama de Venn da interseção de dois conjuntos é dado por: A B A∩B Vejamos um exemplo a seguir: Σxemρlo 12 Sejam A = {1, ∆, ∇} e B = {1, a, ∇, Θ}, então A∩B = {1, ∇}. A definição de interseção de conjuntos pode ser generalizada para uma quanti- dade finita de conjuntos, conforme segue: Definição A interseção entre os conjuntos A 1 , A 2 , …, A n é o conjunto A 1 ∩A 2 ∩…∩A n , formado pelos elementos que estão simultaneamente em A 1 , A 2 , …, A n . Em símbolos: i =1 n iA = A1∩A2∩...∩An = {x | x ∈ A1 e x ∈ Ai, ∀ i = 2, 3, ..., n} Vejamos um exemplo: Σxemρlo 13 Vamos representar as diversas interseções que podem ser estudadas com rela- ção aosconjuntos: A = {01,11, 001, 10, 00, 010}, B = {01, 11, 001, 101, 011, 111} e C = {01,11, 011, 101, 10, 000, 110} 38 Matemática Discreta A B C 00100,010 111 01,11 000,110 10 101,011 Temos que: A∩B∩C = {01, 11} A∩B = {01, 11, 001} A∩C = {01, 11, 10} B∩C = {01, 11, 101, 011} Definição Dois conjuntos A e B são ditos conjuntos disjuntos se A∩B = ∅, ou seja, se A e B não possuem elementos em comum. Σxemρlo 14 Sejam A = {101, 111} e B = {010, 100}, então A∩B = ∅. Apresentaremos a seguir algumas das principais propriedades da interseção entre conjuntos. As propriedades são apresentadas considerando, em geral, a in- terseção entre dois ou três conjuntos, mas podem ser facilmente generalizadas para a interseção de n conjuntos. Teorema Sejam A e B dois conjuntos tais que A ⊂ B, então A∩B = A. Demonstração Vamos mostrar que A∩B ⊂ A e A ⊂ A∩B. De fato, seja x ∈ A∩B, isso significa que x ∈ A e x ∈ B e, como x ∈ A, prova que A∩B ⊂ A. Seja agora y ∈ A, como A ⊂ B, temos que y ∈ B, isto é, y ∈ A∩B, provando que A ⊂ A∩B. Concluímos, então, que A∩B = A. Σxemρlo 15 Sejam A = {1010, 0101} e B = {1010, 1001, 1111, 0101}, então, como A ⊂ B: A∩B = A = {1010, 0101} Teoria de conjuntos 39 Teorema Sejam A e B dois conjuntos quaisquer, então: A∩B ⊂ B e A∩B ⊂ A Demonstração Vamos mostrar apenas a primeira inclusão, já que a segunda é análoga. Seja x ∈ A∩B, então x ∈ A e x ∈ B, onde x ∈ B, provando que A∩B ⊂ B. Σxemρlo 16 Sejam A = {11010, 10110} e B = {11010, 11111, 00000}, então: A∩B = {11010} ⊂ {11010, 11111, 00000} Teorema Sejam A, B e C conjuntos quaisquer, se A ⊂ B, então: C∩A ⊂ C∩B Demonstração Seja x ∈ C∩A → x ∈ C e x ∈ A ⊂ B → x ∈ C e x ∈ B → x ∈ C∩B, onde C∩A ⊂ C∩B. Σxemρlo 17 Sejam A = {101, 111}, B = {101, 111, 110, 001} e C = {001, 111}, então: A ⊂ B e A∩C = {111} ⊂ {111, 001} = B∩C Teorema (propriedades fundamentais da interseção de conjuntos) Sejam A, B e C conjuntos quaisquer e U o conjunto universo, a interseção de conjuntos satisfaz as seguintes propriedades: a. A∩∅ = ∅. b. A∩AC = ∅. c. A∩A = A (idempotente). d. A∩U = A (elemento neutro). e. A∩B = B∩A (comutativa). f. A∩(B∩C) = (A∩B)∩C (associativa). Demonstração Provaremos apenas a propriedade associativa: seja x ∈ A∩(B∩C) ↔ x ∈ A e x ∈ (B∩C) ↔ x ∈ A e (x ∈ B e x ∈ C) ↔ (x ∈ A e x ∈ B) e x ∈ C ↔ x ∈ (A∩B) e x ∈ C ↔ x ∈ (A∩B)∩C, então temos que A∩(B∩C) = (A∩B)∩C. Outra operação importante entre dois ou mais conjuntos é a operação de união, que consiste em reunir elementos para formar um novo conjunto. Mais pre- cisamente, a união de conjuntos é definida como segue: 40 Matemática Discreta Definição A união entre os conjuntos A e B é o conjunto A∪B, formado pela reunião dos elementos de A e B. Em símbolos: A∪B = {x | x ∈ A ou x ∈ B} Vejamos o exemplo a seguir: Σxemρlo 18 Sejam A = {∆, 11, ∇} e B = {1, ∆, 11, α, β}, então: A∪B = {1, ∆, 11, ∇, α, β} A definição de união de conjuntos pode ser generalizada para uma quantidade finita de conjuntos, conforme segue: Definição A união entre os conjuntos A 1 , A 2 , …, A n é o conjunto A 1 ∪A 2 ∪…∪A n , formado por todos os elementos de A 1 , A 2 , …, A n . Em símbolos: i =1 n iA = A1∪A2∪...∪An = {x | x ∈ A1 ou x ∈ Ai, ∀ i = 2, 3, ..., n} Vejamos o exemplo a seguir: Σxemρlo 19 Vamos representar a união dos conjuntos. A = {01, 11, 001, 10, 00, 010}, B = {01, 11, 001, 101, 001, 111} e C = {01, 11, 011, 101, 10, 000, 110} Um ponto importante que devemos notar ao escrever a união de conjuntos é que nunca repetiremos elementos, ou seja, cada elemento deverá aparecer uma única vez no conjunto união. Sendo assim, temos: A∪B∪C = {01, 11, 001, 00, 010, 101, 001, 111, 011, 10, 000, 110} A seguir, apresentaremos algumas das principais propriedades da união de con- juntos. As propriedades são apresentadas considerando, em geral, a união entre dois ou três conjuntos, porém podem ser facilmente generalizadas para a união de n conjuntos. Teoria de conjuntos 41 Teorema Sejam A e B dois conjuntos, então A ⊂ A∪B e B ⊂ A∪B. Demonstração Vamos mostrar que A ⊂ A∪B. De fato, seja x ∈ A, isso significa que x ∈ A ou x ∈ B, isto é, x ∈ A∪B, provando que A ⊂ A∪B. Σxemρlo 20 Sejam A = {∆, ⊗, ⊠} e B = {111, 101}, então A∪B = {∆, ⊗, ⊠, 111, 101} e, claramente, A ⊂ A∪B, assim como B ⊂ A∪B. Teorema Sejam A e B dois conjuntos, então A∪B = B ↔ A ⊂ B. Demonstração De fato, já sabemos que A ⊂ A∪B. Como A∪B = B, temos que A ⊂ B. Agora, sabendo que A ⊂ B, vamos mostrar que A∪B = B. De fato, já sabemos que B ⊂ A∪B, isso significa que basta provarmos que A∪B ⊂ B para termos a igual- dade A∪B = B. Então, se x ∈ A∪B, isso significa que x ∈ A ou x ∈ B, mas A ⊂ B. Em qualquer caso, teremos que x ∈ B; se x ∈ A∪B, temos que x ∈ B, provando que A∪B = B. Σxemρlo 21 Sejam A = {4, 7} e B = {4, 7, 8, 9}, então: A∪B = {4, 7, 8, 9} = B Teorema Sejam A, B e C conjuntos tais que A ⊂ C e B ⊂ C, então A∪B ⊂ C. Demonstração De fato, seja x ∈ A∪B, então, por definição, x ∈ A ou x ∈ B. Como A ⊂ C e B ⊂ C, segue que x ∈ A ⊂ C ou x ∈ B ⊂ C, ou seja, x ∈ C. Provando que A∪B ⊂ C. Teorema (propriedades fundamentais da união de conjuntos) Sejam A, B e C conjuntos quaisquer e U o conjunto universo, a união de conjun- tos satisfaz as seguintes propriedades: a. A∪∅ = A (elemento neutro). b. A∪U = U. c. A∪AC = U. d. A∪A = A (idempotente). e. A∪B = B∪A (comutativa). f. A∪(B∪C) = (A∪B)∪C (associativa). Agora é com você: faça a demons- tração de que B ⊂ A∪B Desafio 42 Matemática Discreta Σxemρlo 22 Sejam A = {α, θ} e B = {101, 111, 110}, então: A∪B = {α, θ, 101, 111, 110} = B∪A Podemos também combinar as operações de união e interseção de conjun- tos para obter um novo conjunto. A combinação das operações de interseção e união de conjuntos satisfaz as seguintes propriedades, que são chamadas de leis de absorção: Teorema Sejam A e B conjuntos, então: A∩(A∪B) = A e A∪(A∩B) = A Demonstração Sabemos que A ⊂ A∪B e, assim, segue do teorema ilustrado no Exemplo 15 que A∩(A∪B) = A. De maneira análoga, temos que A∪(A∩B) = A. Duas propriedades importantes na combinação entre união e interseção de conjuntos são as propriedades de distributividade, que são equivalentes às pro- priedades de distributividade com relação à soma e multiplicação de números reais. A seguir, vamos enunciar e provar as propriedades de distributividade da interseção e união de conjuntos. Teorema Sejam A, B e C conjuntos, então valem as seguintes distributivas: a. A∩(B∪C) = (A∩B)∪(A∩C). b. A∪(B∩C) = (A∪B)∩(A∪C). Demonstração Para provar essas propriedades, utilizaremos as leis distributivas da lógica ma- temática. Vamos provar o item a. Seja x ∈ A∩(B∪C) ↔ x ∈ A e x ∈ B∪C ↔ x ∈ A e (x ∈ B ou x ∈ C) ↔ (x ∈ A e x ∈ B) ou (x ∈ A e x ∈ C) ↔ x ∈ A∩B ou x ∈ A∩C ↔ x ∈ (A∩B)∪(A∩C) Provando que A∩(B∪C) = (A∩B)∪(A∩C). Agora é com você: faça a demons- tração do item b. Desafio Teoria de conjuntos 43 Σxemρlo 23 Considere A = {1, 2}, B = {0, 1, 3, 4} e C = {1, 4, 5}. Note inicialmente que B∩C = {1, 4}, onde A∪(B∩C) = {1, 2, 4}. Por outro lado, temos que A∪B = {0, 1, 2, 3, 4} e A∪C = {1, 2, 4, 5}, onde (A∪B)∩(A∪C) = {1, 2, 4}. Sendo assim, A∪(B∩C) = (A∪B)∩(A∪C). Vamos agora demonstrar um teorema muito importante, conhecido como Leis de De Morgan para conjuntos. Essas leis recebem esse nome porque sua demonstra- ção é feita com base nas Leis de De Morgan da lógica matemática. Teorema (Leis de De Morgan) Sejam A e B conjuntos, então valem as seguintes leis de De Morgan: a. (A∩B)C = AC∪BC. b. (A∪B)C = AC∩BC. Demonstração Vamos provar o item a. Seja x ∈ (A∩B)C ↔ x ∉ A∩B ↔ ~(x ∈ A∩B) ↔ ~(x ∈ A e x ∈ B) ↔ ~(x ∈ A) ou ~(x ∈ B) ↔ x ∉ A ou x ∉ B ↔ x ∈ AC ou x ∈ BC ↔ x ∈ AC∪BC Uma terceira operação importante entre conjuntos é a diferença entre conjun- tos, a qual está definida a seguir. Definição A diferença entre os conjuntos A e B é o conjunto A\B 2 , formado pelos elementos de A que não estão em B. Em símbolos: A\B= {x | x ∈ A e x ∉ B} A diferença entre conjuntos pode ser denotada também por A – B. 2 Vejamos o exemplo a seguir: Σxemρlo 24 Sejam A = {0, 3, 7} e B = {3, 5, 7} dois conjuntos, então: A\B = {0} e B\A = {5} Agora é com você: faça a demons- tração do item b. Desafio A diferença entre dois conjuntos A e B não é comutativa, ou seja, A\B ≠ B\A. Importante 44 Matemática Discreta Teorema Sejam A, B e C conjuntos em um universo U, então valem as seguintes proprie- dades relacionadas com a diferença entre conjuntos: a. A\∅ = A. b. U\A = AC. c. A\A = ∅. d. A\AC = A. e. (A\B)C = AC\B. f. A\B = BC\AC. g. (A\B)\C = A\(B∪C). h. A\(B\C) = (A\B)∪(A∩C). Demonstração Vamos provar apenas o item g. Seja x ∈ (A\B)\C, temos por definição da opera- ção de diferença de conjuntos que: x ∈ (A\B)\C ↔ x ∈ A\B e x ∉ C ↔ (x ∈ A e x ∉ B) e x ∉ C ↔ x ∈ A e (x ∉ B e x ∉ C) ↔ x ∈ A e (~(x ∈ B) e ~(x ∈ C)) ↔ x ∈ A e ~(x ∈ B ou x ∈ C) ↔ x ∈ A e ~(x ∈ B∪C) ↔ x ∈ A\(B∪C) Ou seja, (A\B)\C = A\(B∪C). Para finalizar este capítulo, iremos apresentar alguns exemplos de como pode- mos utilizar operações entre conjuntos para analisar afirmações ou um conjunto de afirmações. Σxemρlo 25 Dado que Pedro é um homem e que todos os homens são mortais, mostre que Welington é mortal. Vamos utilizar a propriedade de que se A ⊂ B e B ⊂ C, então A ⊂ C. Sejam: U: Conjunto de todos os seres vivos. B: Conjunto de todos os seres humanos. C: Conjunto de todos os mortais. A: Conjunto unitário cujo único elemento é Pedro. Temos que A ⊂ B, B ⊂ C. Logo, A ⊂ C, onde Pedro é mortal. Teoria de conjuntos 45 Σxemρlo 26 Em uma escola de 1.000 alunos, 800 gostam de sorvete de chocolate, 700 gos- tam de sorvete de morango e 600 gostam dos dois sabores. Quantos alunos não gostam de nenhum dos dois sabores? Seja U = {Alunos da escola}, A = {Alunos que gostam de sorvete de chocolate} e B = {Alunos que gostam de sorvete de morango}. Vamos construir o Diagrama de Venn após analisar os dados. Temos que n(A∩B) = 600, ou seja, 600 alunos gostam dos sabores chocolate e morango. Para sabermos quantos alunos gostam apenas do sabor chocolate, fazemos a subtração da quantidade de alunos que gostam desse sabor pela quantidade de alunos que gostam de ambos os sabores. Assim: n(A)\n(A∩B) = 800 – 600 = 200 Agora, para determinarmos a quantidade de alunos que gostam apenas do sabor morango, o processo é análogo ao anterior, fazemos: n(B)\n(A∩B) = 700 – 600 = 100 Sabemos que n(U) = 1.000, que é composto pela quantidade de alunos que gos- tam apenas do sabor chocolate, de ambos os sabores, apenas do sabor de moran- go e alunos que não gostam de nenhum dos dois sabores, logo: n(U) = n(A\(A∩B)) + n(A∩B) + n(B\(A∩B)) + n(U\(AUB)) = 200 + 600 + 100 + n(U\(AUB)) Sendo assim, n(U\(AUB)) = 1.000 – 900 = 100, ou seja, 100 alunos não gostam de nenhum dos sabores. O Diagrama de Venn ficará da seguinte forma: Alunos da escola Chocolate e morango 600 Chocolate Morango 100 200 100 Podemos definir outras operações entre conjuntos. Uma operação bem conhe- cida é a diferença simétrica entre conjuntos. Saiba mais sobre essa operação na página Matemática Essencial, da UEL. Disponível em: http://www.uel.br/ projetos/matessencial/basico/medio/ conjuntos.html#sec11. Acesso em: 5 mar. 2021. Saiba mais Sempre que você for resolver um exercício com interseções e uniões de conjuntos, inicie anotando a cardinalidade das interseções e lembre-se de que as subtrações da cardinalidade de cada conjunto com a interseção são realizadas para que não façamos a soma de cada interseção mais de uma vez, ou seja, para determinar a cardinalidade apenas de cada conjunto, sem a interseção. Importante http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11 http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11 http://www.uel.br/projetos/matessencial/basico/medio/conjuntos.html#sec11 46 Matemática Discreta CONSIDERAÇÕES FINAIS Neste capítulo você aprendeu os conceitos fundamentais de teoria de conjuntos, as diferentes formas de descrevê-los e como relacioná-los com objetos da vida real. Pôde entender, ainda, como realizar várias operações básicas entre conjuntos, que estão diretamente relacionadas com fatos e temas de estudos da matemática discreta. Por fim, compreendeu como podemos utilizar a teoria de conjuntos para demons- trar afirmações matemáticas. ATIVIDADES 1. Demonstre a propriedade comutativa da interseção de conjuntos. Mais precisamente, demonstre que dados dois conjuntos A e B, então A∩B = B∩A. 2. Prove que, se A, B e C são conjuntos, então: A∪(B∩C) = (A∪B)∩(B∪C) 3. Verifique a validade da seguinte lei de De Morgan: se A e B são conjuntos, então (A∪B)C = AC∩BC. 4. Prove que, se A e B são conjuntos, então A\B = BC\AC. REFERÊNCIAS IEZZI, G.; MURAKAMI, C. Fundamentos da matemática elementar. São Paulo: Atual, 2013. FILHO, E. A. Teoria elementar dos conjuntos. São Paulo: Nobel, 1980. ROSEN, K. H. Matemática discreta e suas aplicações. São Paulo: McGraw-Hill, 2009. GRIMALDI, R. P. Discrete and combinatorial mathematics: an applied introduction. 5. ed. Boston: Addison- -Wesley, 2004. Conjuntos numéricos 47 3 Conjuntos numéricos Você deve concordar que o conceito fundamental em matemática é a ideia de número. Mais ainda, é provável que a primeira palavra que surge na sua cabeça ao pensar em matemática seja números. A ideia de número se desenvolveu com a capacidade de contar e vem evo- luindo conforme a evolução da matemática como ciência. Da necessidade de contar objetos surgiram os números naturais, que já foram representados por diversas notações até chegar à notação que utilizamos hoje. Com o desenvolvi- mento de novos problemas matemáticos, fez-se necessária a criação de novos conjuntos numéricos: inteiros, racionais, reais e imaginários. Neste capítulo, você vai aprender os principais conjuntos numéricos, suas principais operações e propriedades. Além disso, vai aprender a trabalhar com aritmética modular, uma ferramenta fundamental para que nossos computa- dores realizem tarefas, como executar um vídeo da internet de modo pratica- mente instantâneo. 3.1 Conjunto dos números naturais Vídeo “Deus criou os números naturais, todo o resto é obra do homem”. Essa frase foi dita pelo famoso matemático alemão Leopold Kronecker (1823-1891) para dar ênfase à importância dos números naturais. Na verdade, toda a sistemática dos conjuntos numéricos conhecidos na ma- temática pode ser feita por meio dos números que utilizamos para contar. Esses números são conhecidos como números naturais. Definição Chamamos de conjunto dos números naturais, denotando por , o conjunto formado pelos números 1, 2, 3, …. = {1, 2, 3, …} Assumiremos que já é sabido que podemos realizar duas operações fundamen- tais com números naturais: adição e multiplicação. Essas operações satisfazem al- gumas propriedades bem interessantes, que serão anunciadas em seguida. Teorema A operação da adição de números naturais satisfaz as propriedades a seguir: 48 Matemática Discreta a. Associativa da adição: (a + b) + c = a + (b + c), para todo a, b, c ∈ . b. Comutativa da adição: a + b = b + a, para todo a, b ∈ . Observamos que na definição apresentada o número zero não pertence ao conjunto dos números naturais, já que a criação dos números naturais se dá com o objetivo de contagem, por exemplo, para um pastor contar suas ovelhas. Sendo assim, não incluímos o zero como número natural; afinal, ninguém conta zero ovelhas. Em algumas oportunidades é conveniente trabalhar com o número zero. Sendo assim, vamos denotar por 0 o conjunto dos números naturais unido ao elemento zero, ou seja, 0 = ∪{0}. Nesse caso, chamaremos o zero de elemento neutro da adição em 0, pois para todo a ∈ , temos que a + 0 = a. A multiplicação de números naturais também possui propriedades bem defini- das, a saber: Teorema A operação de multiplicação de númerosnaturais satisfaz as propriedades a seguir: a. Associativa da multiplicação: (ab)c = a(bc), para todo a, b, c ∈ . b. Comutativa da multiplicação: ab = ba, para todo a, b ∈ . c. Elemento neutro da multiplicação: a · 1 = a, para todo a ∈ . d. Distributiva da multiplicação relativamente à adição: a(b + c) = ab + ac, para todo a, b, c ∈ . Outra propriedade importante que os números naturais satisfazem é a proprie- dade conhecida como tricotomiaI, enunciada a seguir. Dados a, b ∈ , pode ocorrer exatamente uma das três alternativas seguintes: • a = b. • Existe p ∈ tal que a = b + p. • Existe q ∈ com b = a + q. Além das suas propriedades operatórias e da propriedade da tricotomia, o con- junto dos números naturais possui outra propriedade muito importante: a orde- nação dos números naturais, que diz que dados dois números naturais diferentes, existe sempre um maior que o outro. A ordenação dos números naturais é chamada de relação de ordem. A relação de ordem no conjunto dos números naturais é definida da seguinte forma: Conjuntos numéricos 49 Definição Dados a, b ∈ , dizemos que a é menor que b, e escrevemos a < b, se existe p ∈ tal que b = a + p. Nessas condições, dizemos que b é maior que a. Também podemos utilizar a notação a ≤ b para dizer que um número a é menor ou igual a um número b, ou seja, quando a = b + p com p ∈ 0. Teorema A relação de ordem dos números naturais satisfaz as propriedades a seguir: a. Transitividade: se a < b e b < c, então a < c. b. Tricotomia: dados a e b, pode ocorrer exatamente uma das alternativas: a = b ou a < b ou b < a. c. Monotonicidade da adição: se a < b, então para todo p ∈ tem-se a + p < b + p. Demonstração Vamos demonstrar apenas os itens a e c. Para o item a, suponhamos que a < b e b < c. Isso significa que existem p, q ∈ tais que b = a + p e c = b + q, em que c = (a + p) + q = a + (p + q), ou seja, a < c. Para o item c, temos que a < b, em que existe q ∈ tal que a + q = b. Sendo assim, (a + p) + q < b + p, ou seja, a + p < b + p. As propriedades do teorema apresentado continuam verdadeiras quando con- sideramos ≤. Além disso, podemos descrever uma propriedade de monotonicidade para multiplicação, mais precisamente: Teorema A relação de ordem dos números naturais satisfaz a seguinte propriedade de monotonicidade da multiplicação: Se a < b e p ∈ , então ap < bp. A demonstração desse fato segue diretamente da propriedade distributiva da multiplicação com relação à soma de números naturais. Outra propriedade importante é a propriedade do corte, ou propriedade do cancelamento, a qual é utilizada com frequência quando estamos fazendo cálculos e comparações de números naturais. A lei do corte para números naturais é dada pelo seguinte teorema: Teorema (lei do corte) Sejam a, b e c números naturais tais que c ≠ 0 e ac = bc. Então, a = b. Demonstração Suponhamos por contraposição que a ≠ b. Por tricotomia, a < b ou b < a. Se a < b, existe m ∈ tal que b = a + m, em que bc = (a + m)c = ac + mc. Logo, ac < bc. Se a > b, existe n ∈ tal que a = b + n, em que ac = (b + n)c = bc + nc. Logo, ac > bc. Sendo assim, se ac = bc, então a = b. Agora é com você: prove o item b. Desafio 50 Matemática Discreta Existem infinitos números naturais, ou seja, a cardinalidade do conjunto dos números naturais é infinita. Esse fato é enunciado e demonstrado no teorema a seguir: Teorema O conjunto dos números naturais tem cardinalidade infinita, isto é, n() = ∞. Demonstração Suponhamos que é um conjunto finito. Então, utilizando a tricotomia para comparar todos os elementos de , dois a dois, obtemos um natural b maior que todos os elementos de . Mas b + 1 também é natural e é maior que b, uma con- tradição, provando que tem cardinalidade infinita. Para encerrar esta seção, demonstraremos um teorema muito importante, pois possui várias aplicações, em especial na computação. Esse teorema é conhecido como teorema fundamental da aritmética e indica que todo número natural pode ser escrito como a multiplicação de números primos. Lembramos que a definição de número primo é dada por: Definição Um número natural p é chamado de número primo quando p ≠ 1 e não existem a, b ∈ tais que p = ab. Entre os cem primeiros números naturais, temos os seguintes números primos: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Teorema (teorema fundamental da aritmética) Se b ∈ , então b pode ser escrito (de maneira única) como o produto de nú- meros primos. Demonstração Vamos utilizar um método de demonstração conhecido como segundo princípio da indução. Seja b ∈ e suponha que todo número natural menor que b pode ser escrito como o produto de fatores primos, então b é primo (nesse caso, b é trivial- mente um produto de fatores primos) ou b = cd, com c < b e d < b. Pela hipótese de indução, c e d podem ser escritos como o produto de fatores primos. Sendo assim, o teorema é válido. Conjuntos numéricos 51 3.2 Conjunto dos números inteiros Vídeo Ao longo do tempo, com o desenvolvimento de novos problemas matemáti- cos, fez-se necessária a ampliação do conjunto dos números naturais de modo que fosse possível, por exemplo, obter a solução de uma equação do tipo x + 3 = 1. Ou seja, foi preciso estender o conjunto dos números naturais para um conjunto que apresentasse entre seus elementos números negativos. Esse conjunto é chamado de conjunto dos números inteiros e é definido da seguinte maneira: Definição Chamamos de conjunto dos números inteiros, denotado por , o conjunto formado pelos números …, -3, -2, -1, 0, 1, 2, 3, …. = {…, -3, -2, -1, 0, 1, 2, 3, …} O conjunto dos números inteiros possui alguns subconjuntos notáveis, a saber: • + = {0, 1, 2, 3, …} = ∪{0}, chamado de conjunto dos números inteiros não negativos. • – = {..., -3, -2, -1, 0}, chamado de conjunto dos números inteiros não positivos. * = {…, -3, -2, -1, 1, 2, 3, …}, chamado de conjunto dos inteiros não nulos. Assim como no caso do conjunto dos números naturais, o conjunto dos nú- meros inteiros também apresenta um número infinito de elementos. Esse fato é sintetizado no seguinte teorema: Teorema O conjunto dos números inteiros possui cardinalidade infinita, isto é, n( ) = ∞. Demonstração Segue desse fato que n() = ∞ e ⊂ . A grande importância dos números inteiros se dá pelo fato de que podemos realizar três das quatro operações fundamentais (adição, subtração e multiplica- ção). Vamos assumir que essas operações já nos são conhecidas. Sendo assim, ire- mos rever apenas algumas notações e propriedades. Existem algumas diferenças básicas nas propriedades operatórias da multiplica- ção e da soma quando consideramos o conjunto dos números inteiros em relação ao conjunto dos números naturais. Podemos citar, por exemplo, a existência de um elemento simétrico da adição, ou seja, dado a ∈ , existe um elemento b ∈ tal que a + b = 0. Nesse caso, denotamos b = -a. A operação de subtração de números inteiros não é simétrica, pois é claro que, por exemplo, 1 - 3 ≠ 3 - 1. A seguir, elencamos algumas propriedades operatórias. Teorema As operações de adição e subtração de números inteiros satisfazem as proprie- dades a seguir: a. Associativa da adição e subtração: (a ± b) ± c = a ± (b ± c), para todo a, b, c ∈ . 52 Matemática Discreta b. Comutativa da adição: a + b = b + a, para todo a, b ∈ . c. Elemento neutro da adição e subtração: a ± 0 = a, para todo a ∈ . Além disso, existem propriedades análogas para a operação de multiplicação de números inteiros. Teorema A operação de multiplicação de números inteiros satisfaz as propriedades a seguir: a. Associativa da multiplicação: (ab)c = a(bc), para todo a, b, c ∈ . b. Comutativa da multiplicação: ab = ba, para todo a, b ∈ . c. Elemento neutro da multiplicação: a · 1 = a, para todo a ∈ . d. Distributiva da multiplicação relativamente à adição e à subtração:
Compartilhar