Matemática discreta

Matemática discreta

(Parte 1 de 14)

Universidade de Caxias do Sul

Centro de Ciências Exatas e Tecnologia Departamento de Informática

Matemática Discreta Márcia Rodrigues Notare

Caxias do Sul, julho de 2003.

Matemática Discreta

Márcia Rodrigues Notare 2

1 TEORIA DOS CONJUNTOS4
1.1 RELAÇÃO DE PERTINÊNCIA4
1.2 ALGUNS CONJUNTOS IMPORTANTES4
1.3 RELAÇÃO DE INCLUSÃO5
1.4 IGUALDADE DE CONJUNTOS6
1.5 PERTINÊNCIA X INCLUSÃO6
2 INTRODUÇÃO À LÓGICA MATEMÁTICA7
2.1 CONECTIVOS LÓGICOS7
2.1.1 Negação7
2.1.2 Conjunção8
2.1.3 Disjunção8
2.1.4 Condicional (Implicação)8
2.1.5 Bicondicional9
2.2 FÓRMULAS BEM-FORMADAS9
2.3 TABELAS-VERDADE PARA WFFS9
2.4 EQUIVALÊNCIA10
2.5 QUANTIFICADORES1
3 ÁLGEBRA DE CONJUNTOS13
3.1 OPERAÇÃO DE UNIÃO13
3.1.1 Propriedades da União14
3.2 OPERAÇÃO DE INTERSEÇÃO15
3.2.1 Propriedades da Interseção16
3.3 OPERAÇÃO COMPLEMENTO16
3.3.1 Propriedades de DeMorgan17
3.4 OPERAÇÃO DE DIFERENÇA17
3.5 CONJUNTO DAS PARTES18
3.6 PRODUTO CARTESIANO18
3.7 UNIÃO DISJUNTA19
4 RELAÇÕES20
4.1 RELAÇÃO BINÁRIA20
4.2 ENDORRELAÇÃO COMO GRAFO21
4.3 RELAÇÃO COMO MATRIZ21
4.4 PROPRIEDADES DAS RELAÇÕES2
4.4.1 Relação Reflexiva2
4.4.2 Relação Irreflexiva23
4.4.3 Relação Simétrica24
4.4.4 Relação Anti-Simétrica24
4.4.5 Relação Transitiva25
4.5 FECHOS DE RELAÇÕES25
4.5.1 Fecho Reflexivo26
4.5.2 Fecho Simétrico26
4.5.3 Fecho Transitivo26
4.6 RELAÇÃO DE ORDEM26
4.6.1 Elemento Mínimo28
4.6.2 Elemento Minimal28
4.6.3 Elemento Máximo28
4.6.4 Elemento Maximal28
4.7 RELAÇÃO DE EQUIVALÊNCIA29
4.7.1 Congruência em Z30
4.8 RELAÇÃO INVERSA30
4.9 COMPOSIÇÃO DE RELAÇÕES31
4.9.1Composição de Relações como Produto de Matrizes32

ÍNDICE 5 TIPOS DE RELAÇÕES...................................................................................................................3

Matemática Discreta

Márcia Rodrigues Notare 3

5.1 RELAÇÃO FUNCIONAL3
5.2 RELAÇÃO INJETORA3
5.3 RELAÇÃO TOTAL34
5.4RELAÇÃO SOBREJETORA.............................................................................................................34
5.5MONOMORFISMO......................................................................................................................... 35
5.6 EPIMORFISMO35
5.7 ISOMORFISMO35
6 FUNÇÕES PARCIAIS E TOTAIS37
6.1 FUNÇÃO PARCIAL37
6.2 FUNÇÃO TOTAL37
7 CARDINALIDADE DE CONJUNTOS38
7.1 CARDINALIDADE FINITA E INFINITA38
7.2 CARDINALIDADE DOS CONJUNTOS NÃO-CONTÁVEIS39
7.3 CARDINAL39
8 INDUÇÃO MATEMÁTICA41
8.1 PRIMEIRO PRINCÍPIO DE INDUÇÃO MATEMÁTICA41
9 RECURSÃO E RELAÇÕES DE RECORRÊNCIA47
9.1 DEFINIÇÕES RECORRENTES47
9.2 SEQÜÊNCIAS DEFINIDAS POR RECORRÊNCIA47
10 ESTRUTURAS ALGÉBRICAS49
10.1 OPERAÇÕES49
10.2 PROPRIEDADE DAS OPERAÇÕES BINÁRIAS49
10.3 GRUPÓIDES50
10.4 SEMIGRUPOS50
10.5 MONÓIDES51

Matemática Discreta

Márcia Rodrigues Notare 4

1 TEORIA DOS CONJUNTOS

Definição de Conjunto: um conjunto é uma coleção de zero ou mais objetos distintos, chamados elementos do conjunto, os quais não possuem qualquer ordem associada. Em outras palavras, é uma coleção não-ordenada de objetos.

Exemplo: A = {branco, azul, amarelo}

Em um conjunto, a ordem dos elementos não importa e cada elemento deve ser listado apenas uma vez.

Podemos definir um conjunto de diferentes formas:

Denotação por Extensão: os elementos são listados exaustivamente. Exemplo: Vogais = {a, e, i, o, u}

Denotação por Compreensão: definição de um conjunto por propriedades comuns aos objetos. De forma geral, escreve-se {x | P(x)}, onde P(x) representa a propriedade. Exemplo: Pares = {n | n é par}, que representa o conjunto de todos os elementos n, tal que n é um número par.

Ainda podemos especificar um conjunto omitindo alguns elementos que estão implícitos na notação adotada. Veja exemplos:

Dígitos = {0, 1, 2, 3,, 9}
Pares = {0, 2, 4, 6,}

1.1 Relação de Pertinência

- Se a é elemento de um conjunto A, então podemos escrever:

Aa∈ e dizemos que a pertence ao conjunto A.

- Se a não é elemento de um conjunto A, então podemos escrever:

Aa∉ e dizemos que a não pertence ao conjunto A.

Exemplo: Considerando o conjunto Vogais = {a, e, i, o, u}, podemos dizer que: - e ∈ Vogais

- m ∉ Vogais

Considerando o conjunto B = {x | x é brasileiro}, temos que: - Pelé ∈ B

- Bill Gates ∉ B

1.2 Alguns Conjuntos Importantes

O Conjunto Vazio é um conjunto que não possui elementos e pode ser denotado por ∅ ou { }.

Ainda temos:

Matemática Discreta

Márcia Rodrigues Notare 5

- N, que representa o conjunto dos números naturais; - Z, que representa o conjunto dos números inteiros;

- Q, que representa o conjunto dos números racionais;

- I, que representa o conjunto dos números irracionais;

- R, que representa o conjunto dos números reais;

- C, que representa o conjunto dos números complexos.

Definição de Alfabeto: um alfabeto é um conjunto finito, ou seja, um conjunto que pode ser denotado por extensão. Os elementos de uma alfabeto são chamados de símbolos ou caracteres.

Definição de Palavra: uma palavra sobre um alfabeto é uma seqüência finita de símbolos do alfabeto, justapostos.

ε palavra vazia Σ alfabeto

Σ* conjunto de todas as palavras possíveis sobre o alfabeto Σ

Exemplos:

- ∅ é um alfabeto - {a, b, c, d} é uma alfabeto

- N não é um alfabeto

- ε é uma palavra sobre {a, b, c]

- ε é uma palavra sobre ∅

Aplicações na Computação

Chamamos de Linguagem Formal a um conjunto de palavras sobre um alfabeto. Portanto, podemos entender que uma linguagem de programação é o conjunto de todos os seus possíveis programas e que um programa é uma palavra da linguagem de programação.

1.3 Relação de Inclusão

(Parte 1 de 14)

Comentários