DC-UFRPE/Bacharelado em Ciência da Computação/Matemática Discreta 1

Programa da Disciplina

Nome:	MATEMÁTICA DISCRETA I
Código:	14203
Departamento:	Departamento de Computação (DC)
Área:	Computação
Carga-horária total:	60 horas
Créditos:	4
Pré-requisitos:	Nenhum

Ementa

• Lógica proposicional.
• Lógica de predicados de primeira ordem.
• Técnicas de demonstração básicas: direta, por contraposição, por redução ao absurdo, por casos. Provas existenciais construtivas e não-construtivas. Teoria dos conjuntos. Relações n-árias, binárias, de equivalência e de ordem.
• Funções e seqüências: injetividade e sobrejetividade.
• Cardinalidade: prova por diagonalização.
• Teoria dos números: divisibilidade, números primos, algoritmo da divisão (teorema) e aritmética modular.
• Definições recursivas e provas por indução.
• Aplicações na Computação nas áreas de: Inteligência Artificial, Métodos Formais, Bancos de Dados, Análise de Algoritmos e Criptografia.

Equivalências

06203 - MATEMÁTICA DISCRETA

Conteúdo

• 1. Lógica Proposicional e Técnicas de Demonstração
• 1.1 Proposições e Operadores Lógicos
• 1.2 Tabela-Verdade
• 1.3 Equivalências lógicas
• 1.4 Regras de inferência
• 1.5 Prova Direta e Por Contradição
• 2. Lógica de Predicados de 1ª Ordem
• 2.1 Predicados e quantificadores
• 2.2 Equivalências lógicas
• 2.3 Regras de inferência
• 2.4 Revisão dos métodos de prova
• 2.5 Prova existencial
• 3. Teoria dos Conjuntos.
• 3.1 Tipos e Representações
• 3.2 Pertinência e Continência
• 3.3 Igualdade de conjuntos
• 3.4 Operações entre conjuntos
• 4. Funções e Seqüências.
• 4.1 Representações
• 4.2 Funções injetivas, sobrejetivas e bijetivas.
• 4.3 Sequências e somatórios.
• 4.4 Cardinalidade de conjuntos infinitos
• 5. Relações.
• 5.1 Relações binárias e n-árias
• 5.2 Propriedades das relações em um conjunto
• 5.3 Relações de ordem
• 5.4 Relações de equivalência
• 6. Introdução a Teoria dos Números
• 6.1 Axiomas 6.2 Divisão e MDC
• 6.2 Números primos 6.4 Noções de Aritmética Modular
• 7. Indução e Recursão
• 7.1 Definições recursivas de funções e seqüências
• 7.2 O princípio da indução
• 7.3 Provas por indução fraca
• 7.4 Provas por indução forte

Bibliografia Básica

• GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação. 5a edição. Rio de Janeiro: LTC, 2004.
• SCHEINERMAN, E. R. Matemática Discreta: Uma Introdução. Segunda edição. São Paulo: Cengage Learning, 2011.
• MILIES, C. P.; COELHO, S. P. Números: uma introdução à matemática. 3a edição. São Paulo: EDUSP, 2001.

Bibliografia Complementar

• ROSEN, K. H. Matemática Discreta e suas Aplicações. Sexta edição. São Paulo: McGraw-Hill, 2009.
• MENEZES, Paulo Blauth. Matemática discreta para computação e informática. 2. ed. Porto Alegre: Sagra Luzzatto, 2005.
• SILVA, F. S. C. da; FINGER, M.; MELO, A. C. V. de. Lógica para computação. São Paulo: Thomson, 2006.
• PATASHNIK, O.; GRAHAM, R. L.; KNUTH, D. E. Matemática Concreta: Fundamentos para a Ciência da Computação. Segunda edição. Rio de Janeiro: LTC, 1995.
• LOVÁSZ, L., PELIKÁN, J., VESZTERGOMBI, K. Matemática Discreta. Sociedade Brasileira de Matemática, 2006