Matemática Discreta

Matemática Discreta

(Parte 1 de 5)

Jose Sousa Pinto Universidade de Aveiro, 1999

Topicos de Matematica Discreta Texto de Apoio - 2005/2006

Departamento de Matematica UNIVERSIDADE DE AVEIRO

Estudar Matematica ... em memoria de Sousa Pinto

O bom desempenho em qualquer disciplina de Matematica depende em primeira analise

1. da capacidade de ler atenta e interessadamente os textos disponıveis, por forma a poder interpretar correcta e rigorosamente as materias neles expostas. Este resultado nao se consegue, em geral, com uma so leitura; frequentemente sao necessarias duas, tres ou mais leituras variando este numero de leitor para leitor. Nao se aprende matematica sem ler Matematica!

2. da capacidade de escrever correctamente em Portugues sobre temas de Matematica, usando uma linguagem precisa e clara. Na apresentacao da resolucao de um problema devem ser enunciados com precisao os resultados usados; o rigor das demonstracoes e o cuidado prestado a sua redaccao sao elementos importantes para a apreciacao das respostas.

Nao responde correctamente a uma questao de Matematica quem se limita a efectuar uma serie de calculos sem explicar a sua razao de ser, as suas origens (proximas) e para que servem no respectivo contexto. Nao se aprende Matematica sem escrever Matematica!

Quem comunica por escrito devera faze-lo em Lıngua Portuguesa, de uma forma que possa ser claramente entendida por qualquer pessoa minimamente familiarizada com as materias sobre as quais discursa. E estrita obrigacao de quem comunica faze-lo de forma correcta dentro da “norma” da lıngua portuguesa. Isto significa, em particular, que

• devem ser usadas frases completas e gramaticalmente correctas, por forma a serem produzidas afirmacoes claras relativamente as quais se possa dizer sem qualquer ambiguidade que sao verdadeiras ou falsas (mas nao ambas as coisas).

• nao deve ser usada notacao matematica incorrecta nem formas de escrita estenografica – as palavras existem para facilitar a comunicacao e a sua grafia nao deve, por isso, ser adulterada. E preciso respeitar nao so a sintaxe, mas tambem a ortografia e as regras de pontuacao da lıngua portuguesa. A “norma” da lıngua portuguesa e do conhecimento geral dos portugueses (letrados) – os dialectos (naturais ou artificiais) so sao reconhecidos por alguns, geralmente poucos!

• deve explicar-se sempre o que se esta a fazer.

• devem ligar-se as ideias e as formulas matematicas por partıculas adequadas que explicitem o encadeamento dos raciocınios feitos.

• e preciso ter muita atencao com a apresentacao: se o trabalho realizado revelar falta de cuidado de sentido estetico e de rigor, nao se justifica que alguem gaste tempo para tentar entender o seu conteudo. Alem disso, qualquer texto sera sempre valorizado pela originalidade da exposicao!

Quem apresenta um trabalho nao pode partir do princıpio que quem o esta a ler entende o que realmente se passou na mente de quem o escreveu. A resposta (escrita) a um problema e um dialogo com um interlocutor invisıvel. A comunicacao escrita pode nao ser simples, mas e certamente da maior importancia para a vida do dia a dia de quem tem de agir em sociedade. Dispor de boa capacidade de comunicacao escrita e muitas vezes de importancia crucial para um bom desempenho em muitas situacoes da vida real: a comunicacao escrita (assim como a oral) aproxima-se muito de uma arte e e como tal que deve ser encarada, mesmo em textos cientıficos!

Jose Sousa Pinto, Universidade de Aveiro, 1999

Indice Geral

1.1 Teoria (intuitiva) de Conjuntos1
1.1.1 Operacoes com conjuntos6
1.2 Elementos de Teoria da Deducao1
1.2.1 Conjectura e demonstracao13
1.2.2 Logica proposicional17
1.2.2.1 Tautologias e contradicoes21
1.2.3 Teoremas e demonstracoes25
1.2.4 Logica com quantificadores31
1.2.4.1 Variaveis e conjuntos32
1.2.4.2 Os quantificadores universal e existencial3
1.3 Relacoes e Aplicacoes42
1.3.1 Produto cartesiano de conjuntos42
1.3.1.1 Representacao de relacoes45
1.3.2 Particoes e relacoes de equivalencia46
1.3.3 Relacoes de ordem49
1.3.4 Funcoes5
1.4 Algebras de Boole61
1.4.1 Operacoes booleanas fundamentais62
1.4.2 Funcoes booleanas70

1 Introducao a Logica e Teoria de Conjuntos 1

2.1 Axiomatica dos Numeros Naturais7
2.1.1 Conceito de axiomatica7
2.1.2 Os axiomas de Dedekind-Peano79
2.1.3 Aritmetica dos numeros naturais81
2.1.4 O conjunto ordenado (IN,≤)87
2.2 Inducao Matematica – Aplicacoes8

2 Numeros Naturais, Inducao e Calculo Combinatorio 7 i

2.3 Introducao ao Calculo Combinatorio96
2.3.1 Arranjos, permutacoes e combinacoes103
2.3.2 O binomio de Newton1
2.3.2.1 O teorema binomial de Newton116
2.3.2.2 O teorema multinomial120
2.4 Numeros Cardinais Transfinitos124
2.4.1 Conjuntos equipotentes124
2.4.2 Cardinais transfinitos127
2.4.2.1 O primeiro numero transfinito, ℵ0127
2.4.2.2 O segundo numero transfinito, ℵ1130
2.4.2.3 Numeros cardinais transfinitos superiores133

2.2.1 Formas equivalentes do princıpio de inducao finita . . 92

3.1 Introducao135
3.1.1 Relacoes de recorrencia e equacoes de diferencas141
3.2 Funcoes Geradoras143
3.2.1 Relacoes de recorrencia e funcoes geradoras153
3.2.2 Relacoes de recorrencia lineares homogeneas157
3.2.3 Relacoes de recorrencia lineares nao homogeneas167

3 Relacoes de Recorrencia e Funcoes Geradoras 135 3.2.2.1 Equacao caracterıstica com raızes multiplas . 161

4.1 Introducao173
4.1.1 Definicoes basicas174
4.1.2 Caminhos de um grafo180
4.1.3 Graus dos vertices de um grafo182
4.2 Representacao de Grafos por Matrizes185
4.2.1 Matriz de adjacencia de um grafo186
4.2.2 Matriz de incidencia de um grafo191
4.3 Caminhos Eulerianos e Hamiltonianos195
4.4 Arvores e Florestas199

4 Teoria dos Grafos 173 iv

Capıtulo 1

Introducao a Logica e Teoria de Conjuntos

1.1 Teoria (intuitiva) de Conjuntos

A teoria dos conjuntos foi criada relativamente recentemente por Georg Cantor (1845-1918) que definiu conjunto como sendo “uma coleccao de objectos claramente distinguıveis uns dos outros, chamados elementos, e que pode ser pensada como um todo”. E claro que se nao se tiver definido previamente o que se entende por “coleccao” esta nao sera uma definicao rigorosa para o termo “conjunto”. A fim de evitar definicoes circulares, conjunto e elemento de um conjunto sao duas nocoes que nao se definem; um conceito quando e definido, e-o em termos de outros conceitos mais simples e nao e habitual considerar conceitos logicamente mais simples que os de “conjunto” e “elemento de um conjunto”. Conjunto e elemento de um conjunto sao assim termos primitivos que se admite serem do conhecimento de toda a gente (pelo menos de toda a gente que estuda Matematica). Esta seccao destina-se a relembrar conceitos baseados na nocao de conjunto aqui considerado de forma intuitiva. Trata-se de um conceito de extraordinaria importancia pois grande parte da matematica dos nossos dias pode ser construıda a partir dele. Por este facto, o estudo da construcao de conceitos de matematica a partir da nocao primitiva de conjunto e muitas vezes se designado por Fundamentos de Matematica.

Um conjunto designa-se geralmente por uma letra maiuscula, 1 reservando-se as letras minusculas para os seus elementos. A expressao simbolica significa que “x e elemento de A”. A negacao de x ∈ A representa-se simbolicamente por x 6∈ A e le-se “x nao pertence a A” (ou “x nao e elemento de A”). Um conjunto pode ser descrito em extensao (quando o numero dos seus elementos for finito e suficientemente pequeno) enumerando explicitamente todos os seus elementos colocados entre chavetas e separados por vırgulas ou em compreensao, enunciando uma propriedade caracterizadora dos seus elementos (isto e, uma propriedade que os seus e so os seus elementos possuam).

(1) Conjunto das vogais descrito em extensao; (2) Conjunto dos numeros naturais pares

P = {p ∈ IN : p = 2q para algum q ∈ IN} descrito em compreensao.

Conjunto universal e conjunto vazio. Intuitivamente poderia parecer razoavel que se considerasse como conjunto qualquer coleccao de objectos (reais ou imaginarios). Tal atitude, porem, conduz a situacoes paradoxais, como se deu conta o filosofo ingles Bertrand Russel, por volta de 1901.

Bertrand Russel comeca por observar que se se adoptar a concepcao intuitiva de conjunto entao pode dizer-se que alguns conjuntos sao membros de si proprios enquanto outros nao o sao. Um conjunto de elefantes, por exemplo, nao e um elefante e, portanto, nao e um elemento de si proprio; no entanto, o conjunto de todas as ideias abstractas e, ele proprio, uma ideia abstracta, pelo que pertence a si proprio. As propriedades “ser membro de si proprio” e “nao ser membro de si proprio” parecem assim ser propriedades

1Nao tem que ser assim: trata-se de uma mera convencao para facilitar o estudo.

perfeitamente adequadas para definir conjuntos. Mas, como se vera, estas propriedades conduzem a criacao de um paradoxo.

Suponha-se (se possıvel) que se define o conjunto A como sendo o conjunto de todos os conjuntos que nao sao membros de si proprios, isto e,

Coloca-se entao a questao de saber se A e ou nao elemento de si proprio. Se A nao for membro de si proprio, A 6∈ A, entao satisfaz a propriedade definidora de A e, portanto, A ∈ A; se A pertence a si proprio, A ∈ A entao nao satisfaz a propriedade definidora de A e, portanto, A 6∈ A. De cada uma das possıveis hipoteses pode deduzir-se a sua negacao, o que constitui um paradoxo.

Para eliminar possibilidades deste tipo supor-se-a, de ora em diante, que os conjuntos considerados sao todos constituıdos por elementos de um conjunto U suficientemente grande, chamado conjunto universal ou universo do discurso.

A ideia de um conjunto universal estara sempre presente mesmo quando nao seja explicitamente mencionado. Em Matematica ha conjuntos que constituem muito frequentemente os universos do discurso sendo, por isso, conveniente dispor de nomes para eles. Alguns exemplos de tais conjuntos, dos mais importantes, sao:

Os sımbolos Ø ou { } usam-se para denotar o conjunto vazio (conjunto sem elementos) que pode ser descrito em compreensao por {x : x 6= x}.

Conjuntos finitos e infinitos. Embora nao seja este o lugar adequado para dar definicoes rigorosas sobre os termos “finito” e “infinito”, procurarse-a esclarecer, por meio de alguns exemplos, o seu significado.

Um conjunto diz-se finito se for possıvel contar os seus elementos, ou seja, se for o conjunto vazio ou se for possıvel estabelecer uma correspondencia bijectiva entre os seus elementos e os elementos de um conjunto da forma {1,2,3,...,n} para algum n ∈ IN. Dir-se-a infinito no caso contrario. O conjunto dos numeros inteiros positivos inferiores a 100 e um conjunto finito enquanto que o conjunto de todos os numeros inteiros positivos e um conjunto infinito. De modo semelhante, e finito o conjunto de todos os planetas do sistema solar ou o conjunto de todos os numeros primos menores que

10103 ; pelo contrario, como mais a frente se mostrara, e infinito o conjunto de todos os numeros primos.

Se A for um conjunto finito, designar-se-a por cardinalidade de A o numero dos seus elementos, o qual se representa por card(A). Um conjunto com cardinalidade igual a 1 diz-se singular.

Quando um conjunto e infinito, e impossıvel defini-lo em extensao (indicando explicitamente os seus elementos); logo, se um conjunto puder ser definido em extensao, entao certamente sera um conjunto finito. Por vezes para definir certos conjuntos infinitos usa-se uma notacao parecida com a definicao de um conjunto em extensao: e o caso de

Note-se contudo que as reticencias representam a quase totalidade dos elementos de IN qualquer que seja o numero de elementos que aparecem no inıcio.

Igualdade de conjuntos. Dois conjuntos sao iguais se e so se tiverem os mesmos elementos.

Se um conjunto A for igual a um conjunto B escreve-se A = B. Para verificar se dois conjuntos sao iguais basta verificar se todo o elemento de A e elemento de B e se todo o elemento de B e elemento de A. Se todo o elemento de A for tambem elemento de B (independentemente do facto de todo o elemento de B poder ser ou nao elemento de A) dir-se-a que o conjunto A esta contido no conjunto B, o que se denota por A ⊆ B; neste caso tambem se diz que A e subconjunto de B. Se os conjuntos A e B forem iguais entao ter-se-a A ⊆ B e, simultaneamente, B ⊆ A; reciprocamente, se A ⊆ B e B ⊆ A se verificarem simultaneamente entao tem-se A = B. Se for A ⊆ B e A 6= B dir-se-a que A e um subconjunto proprio ou uma parte propria de B e escreve-se A ⊂ B. De acordo com estas definicoes resulta que quaisquer que sejam os conjuntos A e B

Considere-se a prova de, por exemplo, Ø ⊆ A qualquer que seja o conjunto A. A unica forma de mostrar que esta inclusao e falsa e verificar que Ø possui um elemento que nao pertence a A; ora como Ø nao possui elementos entao aquela relacao verifica-se sempre.

1. Mostrar que os conjuntos Ø, {Ø} e {{Ø}} sao distintos dois a dois. 2. Mostrar que se A for um subconjunto do conjunto vazio entao A = Ø. 3. Dado um conjunto arbitrario A,

(a) sera A membro do conjunto {A}? (b) sera {A} membro do conjunto {A}? (c) sera {A} um subconjunto de {A}?

4. Dados os conjuntos

indicar, para cada um deles, uma propriedade que o especifique completamente.

5. Indicar quais dos conjuntos que se seguem sao iguais:

6. Determinar em extensao os seguintes conjuntos

7. Dizer quais dos conjuntos que se seguem sao finitos e quais sao infinitos.

(a) O conjunto das linhas do plano que sao paralelas ao eixo x′. (b) O conjunto das letras do alfabeto. (c) O conjunto dos multiplos de 5. (d) O conjunto dos animais existentes na Terra. (e) O conjunto das raızes da equacao

1.1.1 Operacoes com conjuntos

Sendo A,B dois conjuntos, denota-se por A ∪ B a uniao (ou reuniao) de A com B, que e o conjunto cujos elementos sao os elementos de A e os elementos de B. Mais geralmente, se A1,A2,...,An forem conjuntos entao a sua uniao

i=1Ai ≡ A1 ∪ A2 ∪∪ An

e o conjunto constituıdo pelos elementos que pertencem pelo menos a um dos

A interseccao de dois conjuntos A e B, denotada por A ∩ B, e o conjunto cujos elementos pertencem simultaneamente a A e B. Analogamente, se

i=1Ai ≡ A1 ∩ A2 ∩∩ An

As definicoes de uniao e interseccao de conjuntos estendem-se, de forma natural, a famılias infinitas de conjuntos. Assim, dada uma famılia arbitraria de conjuntos {Aα}α∈I (onde I denota um conjunto de ındices)

Dois conjuntos A e B dizem-se disjuntos se e so se for A ∩ B = Ø, isto e, se nao possuirem elementos comuns.

A diferenca de A e B e o conjunto A\B definido por ou seja e o conjunto constituıdo pelos elementos de A que nao pertencem a B. Se, em particular, se fizer A = U, o universo do discurso, entao ao conjunto U\B = {x : x 6∈ B} da-se o nome de conjunto complementar de B e denota-se por Bc.

Conjunto das partes de um conjunto. Podem construir-se conjuntos cujos elementos sao eles proprios, no todo ou em parte, conjuntos. Assim, por exemplo, a letra x, o conjunto {a,b}, o conjunto {Ø} e o numero 4 podem constituir um novo conjunto que e o seguinte

Dado um conjunto arbitrario, e possıvel construir novos conjuntos cujos elementos sao partes do conjunto inicial. Em particular, sendo A um conjunto qualquer, denota-se por P(A) o conjunto constituıdo por todos os subconjuntos (proprios ou improprios) de A, isto e,

Seja, por exemplo, A = {a,b,c}; entao

Diagramas de Venn. As operacoes com conjuntos podem ser representadas pictoricamente pelos chamados diagramas de Venn que, embora nao sirvam de prova formal, permitem visualizar e conjecturar muitos resultados sobre conjuntos.

O conjunto universal e representado pelo interior de um rectangulo no qual sao representados por cırculos os varios conjuntos com os quais se esta a operar. Assim, por exemplo, e um diagrama de Venn com tres conjuntos A,B e C onde se pode realcar (com tracejado) o resultado das varias operacoes realizadas com eles.

Nota 1.2 Os diagramas de Venn tornam-se de difıcil ou mesmo impossıvel utilizacao quando o numero de conjuntos a considerar for superior ou igual a 4.

Exercıcios 1.1.2 : 1. Qual e a cardinalidade dos seguintes conjuntos

2. Determinar a cardinalidade do conjunto

4. Sejam A, B e C tres conjuntos quaisquer contidos no universo U. Verificar as seguintes igualdades:

5. Em que circunstancias sao verdadeiras as igualdades que se seguem

6. O facto de ser A ∪ B = D implica que seja D\B = A? Se nao, o que pode concluir-se do facto de ser A ∪ B = D e D\B = A?

8. Mostrar que

(a) se A ⊆ C e B ⊆ C entao A∪B ⊆ C. (b) se C ⊆ A e C ⊆ B entao C ⊆ A∩B.

9. Determinar os conjuntos das partes dos conjuntos

1. Descrever os elementos do conjunto P(P(P(Ø))). 12. Mostrar que

Em que condicoes se verificam as igualdades nas duas ultimas alıneas? 13. Determinar o conjunto das partes do conjunto das partes do conjunto {a}.

Concluir-se-a esta seccao com os dois teoremas que se seguem que relacionam varias das operacoes que se podem realizar com conjuntos.

Demonstracao: Uma forma de mostrar a veracidade destas igualdades consiste em verificar que cada um dos seus membros esta contido no outro. Far-se-a esta verificacao para a primeira alınea deixando a outra a cargo do leitor interessado, como exercıcio.

(Parte 1 de 5)

Comentários