A maior rede de estudos do Brasil

Grátis
54 pág.
Apostila Matemática Discreta

Pré-visualização | Página 1 de 12

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
ÍNDICE
1 TEORIA DOS CONJUNTOS............................................................................................................4
1.1 RELAÇÃO DE PERTINÊNCIA............................................................................................................4
1.2 ALGUNS CONJUNTOS IMPORTANTES..............................................................................................4
1.3 RELAÇÃO DE INCLUSÃO ................................................................................................................5
1.4 IGUALDADE DE CONJUNTOS ..........................................................................................................6
1.5 PERTINÊNCIA X INCLUSÃO.............................................................................................................6
2 INTRODUÇÃO À LÓGICA MATEMÁTICA ................................................................................7
2.1 CONECTIVOS LÓGICOS ..................................................................................................................7
2.1.1 Negação ................................................................................................................................7
2.1.2 Conjunção.............................................................................................................................8
2.1.3 Disjunção..............................................................................................................................8
2.1.4 Condicional (Implicação) .....................................................................................................8
2.1.5 Bicondicional........................................................................................................................9
2.2 FÓRMULAS BEM-FORMADAS.........................................................................................................9
2.3 TABELAS-VERDADE PARA WFFS ....................................................................................................9
2.4 EQUIVALÊNCIA............................................................................................................................10
2.5 QUANTIFICADORES......................................................................................................................11
3 ÁLGEBRA DE CONJUNTOS ........................................................................................................13
3.1 OPERAÇÃO DE UNIÃO..................................................................................................................13
3.1.1 Propriedades da União.......................................................................................................14
3.2 OPERAÇÃO DE INTERSEÇÃO.........................................................................................................15
3.2.1 Propriedades da Interseção................................................................................................16
3.3 OPERAÇÃO COMPLEMENTO .........................................................................................................16
3.3.1 Propriedades de DeMorgan ...............................................................................................17
3.4 OPERAÇÃO DE DIFERENÇA ..........................................................................................................17
3.5 CONJUNTO DAS PARTES...............................................................................................................18
3.6 PRODUTO CARTESIANO ...............................................................................................................18
3.7 UNIÃO DISJUNTA.........................................................................................................................19
4 RELAÇÕES ......................................................................................................................................20
4.1 RELAÇÃO BINÁRIA ......................................................................................................................20
4.2 ENDORRELAÇÃO COMO GRAFO ...................................................................................................21
4.3 RELAÇÃO COMO MATRIZ.............................................................................................................21
4.4 PROPRIEDADES DAS RELAÇÕES ...................................................................................................22
4.4.1 Relação Reflexiva ...............................................................................................................22
4.4.2 Relação Irreflexiva .............................................................................................................23
4.4.3 Relação Simétrica...............................................................................................................24
4.4.4 Relação Anti-Simétrica .......................................................................................................24
4.4.5 Relação Transitiva..............................................................................................................25
4.5 FECHOS DE RELAÇÕES.................................................................................................................25
4.5.1 Fecho Reflexivo ..................................................................................................................26
4.5.2 Fecho Simétrico ..................................................................................................................26
4.5.3 Fecho Transitivo.................................................................................................................26
4.6 RELAÇÃO DE ORDEM...................................................................................................................26
4.6.1 Elemento Mínimo................................................................................................................28
4.6.2 Elemento Minimal...............................................................................................................28
4.6.3 Elemento Máximo ...............................................................................................................28
4.6.4 Elemento Maximal ..............................................................................................................28
4.7 RELAÇÃO DE EQUIVALÊNCIA.......................................................................................................29
4.7.1 Congruência em Z...............................................................................................................30
4.8 RELAÇÃO INVERSA......................................................................................................................30
4.9 COMPOSIÇÃO DE RELAÇÕES ........................................................................................................31
4.9.1 Composição de Relações como Produto de Matrizes .........................................................32
5 TIPOS DE RELAÇÕES...................................................................................................................33
Matemática Discreta
Márcia Rodrigues Notare
3
5.1 RELAÇÃO FUNCIONAL .................................................................................................................33
5.2 RELAÇÃO INJETORA ....................................................................................................................33
5.3 RELAÇÃO TOTAL.........................................................................................................................34
5.4 RELAÇÃO SOBREJETORA .............................................................................................................34