Oferecer aos alunos conhecimentos básicos de lógica, análise combinatória, aritmética e álgebras booleanas, habilitando-os a compreenderem os problemas matemáticos e computacionais normalmente encontrados na análise de algoritmos, mas também na análise e design de circuitos lógicos, programação linear, teoria de códigos e criptografia.
Introdução à matemática discreta; lógica e cálculo proposicional; teoria elementar dos conjuntos; relações e funções; álgebras booleanas; princípios de contagem; teoria elementar dos números.
Matemática discreta: ênfase em números inteiros e estruturas finitas (conjuntos finitos, estruturas algébricas, grafos) em oposição aos números reais e estruturas infinitas (a reta real, cálculo diferencial); algoritmos e o computador digital como estruturas discretas. Lógica e cálculo proposicional: proposições; conectivos lógicos elementares; tabelas verdade; tautologias e contradições; equivalência lógica; álgebra de proposições; declarações condicionais; argumentos e falácias; quantificadores e negação de declarações quantificadas; estratégias de demonstração: direta, da contraposição, por contradição. Teoria elementar dos conjuntos: conjuntos e elementos; diagramas de Venn; operações sobre conjuntos; álgebra de conjuntos; classes de conjuntos, conjuntos potência e partições; correspondências um-a-um e conjuntos infinitos; princípio da indução finita. Relações e funções: pares ordenados e produtos cartesianos; relações, domínio e imagem; composições de relações; tipos de relações; relações de equivalência; relações de ordem parcial, DAGs e ordem topológica; funções injetoras, sobrejetoras e bijetoras. Álgebras booleanas: álgebra booleana; o princípio da dualidade; formas booleanas; tabelas verdade e funções booleanas; formas disjuntivas mínimas; mapas de Karnaugh. Princípios de contagem: arranjos; permutações com e sem repetições; combinações com e sem repetições; o teorema binomial e aplicações; o princípio do pombal e aplicações; o princípio da inclusão-exclusão e aplicações. Teoria elementar dos números: números; aritmética nas bases binária (em complementos de 1 e 2), octal e hexadecimal; aritmética modular; MMC, MDC e o algoritmo de Euclides; o teorema chinês do resto.
Bibliografia Básica: GERSTING, Judith L., Mathematical Structures for Computer Science: Discrete Mathematics and its applications, W. H. Freeman; Seventh, 2014 LIPSCHUTZ, S., LIPSON, M. Matemática Discreta. Coleção Schaum. 3a. ed. São Paulo: Bookman, 2004. ROSEN, K. H. Discrete Mathematics, and Its Applications. 7a. ed. New York: McGraw-Hill, 2012. SCHEINERMAN, E. R. Matemática Discreta: Uma Introdução. Trad. 3a. ed. amer. São Paulo: Cengage Learning, 2016. Bibliografia Complementar: AHO, A. V., ULLMAN, J. D. Foundations of Computer Science: C Edition. New edition. New York: W. H. Freeman, 1994. CARVALHO, P. C. P., MORGADO, A. C. O. Matemática Discreta. 2a. ed. (Coleção PROFMAT). Rio de Janeiro: SBM, 2015. GRAHAN, R. L., KNUTH, D. E., PATASHNIK, O. Matemática Concreta -- Fundamentos para Ciências da Computação. 2a. ed. São Paulo: LTC, 1995. MENEZES, P. B. Matemática Discreta para Computação e Informática. 4a. ed. Porto Alegre: Bookman, 2013. SILVA, F. S. C., FINGER, M., MELO, A. C. V. Lógica para Computação. 2a. ed. São Paulo: Cengage Learning, 2017. VELLEMAN, D. J. How to Prove It: A Structured Approach. 3a. ed. New York: Cambridge University Press, 2019.
