MCTB019-17 Matemática Discreta 2026-2
Professor Jair Donadelli --- email jair.donadelli @ ufabc.edu.br — sala 546-2 bloco A
Matemática Discreta (porém, exuberante) expõe o aluno aos princípios, técnicas e metodologias associadas a problemas em estruturas matemáticas discretas. O objetivo dessa disciplina é desenvolver no aluno a capacidade de construir demonstrações com uso de notação adequada e argumentação logicamente fundamentada, de entender a necessidade do rigor formal ao se argumentar, de interpretar problemas de contagem em termos matemáticos, aplicar técnicas combinatórias, conhecer noções de cardinalidade em geral, reconhecer as diferenças entre estruturas discretas e contínuas e, em particular, desenvolver a capacidade de elaborar provas indutivas.
| Horários: | Sala: |
|---|---|
| Diurno QUI 8-10h, SEG 10-12h | A-108-0 |
| Noturno QUI 19-21h, SEG 21-23h | A-101-0(2ª), S-212- 0(5ª) |
| Recomendação: | T-P-I: |
| Funções de Uma Variável | T-P-E-I: 4-0-0- |
ÍNDICE:
Programação da disciplinaEmentaBibliografia básicaCalendário e cronogramaAulasBibliografia complementarAtendimentoMonitoriaAvaliaçãoRecuperaçãoLinks (provas antigas e outros)
Programação da disciplina
Ementa
Elementos de lógica clássica de primeira ordem. Teoria intuitiva dos conjuntos. Relações e grafos. Relações de equivalência. Relações de ordem. Funções. Técnicas de demonstração: prova direta, prova por contradição. Indução finita. Relações de recorrência. Cardinalidade: conjuntos finitos e infinitos; conjuntos enumeráveis e não enumeráveis. Princípios de contagem e combinatória. Princípio de inclusão e exclusão. Princípio das casas dos pombos.
Bibliografia básica
GRIMALDI, R.P. Discrete and combinatorial mathematics : an applied introduction. [510 GRIMdi5]
ROSEN, K.H. Matemática discreta e suas aplicações. 6ªEdição [510 ROSEma6]
Calendário e cronograma
Reposição dos feriados: 
Aulas
| Semana | Tema principal | Tópicos | Referências | Atividades |
|---|---|---|---|---|
| 01 | Linguagem | Noções da Lógica: sentenças e conectivos; predicados e quantificadores; implicação lógica; argumentos. Abordagem intuitiva de conjuntos. | - Seções 1.1 a 1.5, 2.1 e 2.2 de [Rosen 6ªed] Cap 2, Seções 3.1-3.3 de [Grimaldi] -Notas de aula | Exercícios (Rosen 6ªed., respostas no livro) §1.1: 9,13,19,43, 45; §1.2: 7,18,28,41,57; §1.3: 7,15,17,21,25,39,52,53; §1.4: 1,3,13,25,31,39,47; §1.5: 11,13,15,17,19,23,25,34; §2.1: 3,8,15,35; §2.2: 45,47; Lista de exercícios da semana |
| 02 | Demonstrações | Métodos de prova (ênfase em | - Seções 1.6 e 1.7 de [Rosen 6ªed] -Notas de aula | Exercícios (Rosen 6ªed., respostas no livro) §2.2: 5 a 13,23; §1.6: 7,11,13,23,25,31,35,39 §1.7 : 3,13,19,33. Videoaulas de BM sobre demonstrações Lista de exercícios da semana |
| 03 | Indução e Boa ordem em | Princípios de indução. Princípio da Boa Ordem. Indução em inteiros limitados inf. Provas usando indução. Armadilhas em provas por indução. Provas usando boa ordem. Variantes do PIF. Definições recursivas. | Seções 4.1-4.3 de [Rosen 6ªed] e de [Grimaldi]; -Notas de aula | Exercícios (Rosen 6ªed., respostas no livro) §4.1: 3,9,19,35,41,53,79 §4.2: 11,27,29,36 Lista de exercícios da semana |
| 04 | Conjuntos, Relações e Funções | Conjuntos de modo axiomático-informal. Dedução do PIF em ZFC Par ordenado e produto cartesiano: definição a partir dos axiomas. Relações; Rel. binárias e propriedades. Funções e propriedades. | -Notas de aula Seções iniciais dos caps. 2 e 8 de [Rosen 6ªed] [Halmos] | slide Exercícios (Rosen 6ªed., respostas no livro) §2.1: 5,6,7,9,21,23,27,28,30,32,37; §2.2: 29,49,50,51,53,57; §2.3:1,5,12,13,15,16,23,31,36,39,67,76; §8.1:1,3,5,7,23; §8.4: 29 Lista de exercícios da semana |
| 05 | Relações de equivalência | Relações de equivalência, Partições de conjuntos e equivalência entre eles. | Seções 8.5 de [Rosen 6ªed] ou 7.4 de [Grimaldi]. (notas de aula da semana passada) | Exercícios (Rosen 6ªed., respostas no livro) §8.4: 1,3,19,21 §8.5: 1,3,7,11,17,18,35,43,47-51. Lista de exercícios da semana |
| 06 | Relações de ordem | Ordens parciais e totais. Cadeias; anticadeias; máximo e maximal. minimo e minimal. Diagrama de Hasse. | -notas de aula -Seções 8.6 de [Rosen 6ªed] ou 7.3 de [Grimaldi]. slides | Exercícios: 1,12,13,15,23,33,53,54,55,56,57,60,65 do Rosen Lista de exercícios da semana |
| 07 | Avaliação | semanas 01 - 05 | ||
| 08 | Relação bem fundada e Indução | Indução em conjuntos bem ordenados. Relações bem fundadas e indução bem fundada. | Notas de aula | Exercícios: 27, 29, 33, 34, 35, 41,43,44,45,46,36, 48, 50, 51, 56 da seção 4.3 do Rosen; exercícios das notas de aula. Lista de exercícios da semana |
| 09 | Cardinalidade e contagem | Bijeções, cardinalidade, conjuntos finitos, enumeráveis e infinitos. Princípio das gavetas (ou casa dos pombos). | 1.1, 3.3, 5.5 e Ap. 3 de [Grimaldi]; final da seção 2.4, 5.1 e 5.2 de [Rosen]; Notas de aula | Exerc.: 31,33,37,42,45,47 de §2.4 de [Rosen]; 21,29,33,35,37,39,41, 45 de §5.1 de [Rosen]; o máximo que conseguir de §5.2 de [Rosen] Lista de exercícios da semana |
| 10 | Contagem e Combinatória | Princípios aditivo e multiplicativo. Combinação, arranjo, permutação. Solução inteira de equações. Inclusão--exclusão; | Cap 1 de [Grimaldi], Cap 5 de [Rosen]. Notas de aula | exercícios.: 3,7,11,19,23,29,35,43,44 de §5.3 de [Rosen] ; 9, 11, 13, 15, 17, 21, 27, 31, 37 de §5.4 de [Rosen]. 7,15,21, 23,30,31, 39, 42, 49,50,53,63 de §5.5 de [Rosen] Lista de exercícios da semana |
| 11 | Contagem e Combinatória | binômio de Newton; coeficiente multinomial; relações de equivalência, classe de equivalência e contagem. | [Grimaldi], Cap 5 de [Rosen]. Notas de aula | Lista de exercícios da semana |
| 12 | Avaliação (5ª-f) | semanas 06 - 11 | ||
| 13 semana de reposição | Avaliações substitutiva (17/09) e recuperativa(19/09) | |||
Bibliografia complementar
Matosek, J. e Nesetril, J.I. An Invitation to Discrete Mathematics [510 MATOin2]
Velleman, Daniel J How to prove it : a structured approach 2. ed. [511.3 VELh2]
Mitchel T. Keller e William T. Trotter Applied Combinatorics [aqui]
Halmos, Paul R. Teoria ingênua dos conjuntos [511.322HALt]
Ronald L Graham; Donald E Knuth; Oren Patashnik.Matemática concreta 2. ed. [510 GRAHma2]
Material de apoio
R. Bianconi, Como ler e estudar matemática?
Fernando Q. Gouvêa e Shai Simonson, How to Read Mathematics (uma tradução "rápida e grosseira", segundo o tradutor, aqui).
Atendimento
professor: 546-2 bloco A em qualquer horário, caso precise evitar desencontros combine um horário por email. Por motivos burocráticos reservo os seguinte horários 2ª 12h-13h, 5ª 10h-12h, 6ª 16h-18h.
Monitoria
monitores: Leonardo e Pedro; locais e horários de atendimento.
Avaliação
2 provas.
As avaliações são individuais, presenciais e sem consulta.
Os critérios de avaliação incluem, de acordo com os objetivos da disciplina
Apresentação clara, legível, discursiva, uniforme e objetiva.
Construção correta e em ordem dos argumentos.
Atendimento às normas de correção ortográfica e gramatical.
Observância às orientações específicas da atividade quando for o caso.
Serão atribuídos conceitos nas atividades avaliativas e o resultado é definido como segue:
Recuperação
Tem direito ao exame recuperação, o qual engloba todo o conteúdo da disciplina, aqueles que foram aprovado com D ou reprovado com F e obtiveram frequência mínima. O resultado do exame é um conceito que compõe com o conceito final M obtido na avaliação regular da disciplina como segue:
O aluno deve manifestar interesse em fazer a recuperação de acordo com as instruções que serão enviadas pelo siga em momento apropriado durante a disciplina.
Links (provas antigas e outros)
Material antigo: Provas, listas, slides, Notas de aulas
Matemática discreta, entrada no wikipedia (em inglês, a página em português não está boa).
Lásló Lovász, Discrete and Continuous: Two sides of the same?.
The Banach–Tarski Paradox (Video)
Foolproof: A Sampling of Mathematical Folk Humor Paul Renteln and Alan Dundes. [pdf]