Matemática Discreta

Matemática Discreta (MD) é a cadeira do primeiro semestre onde aprendes a escrever matemática com rigor e a provar que uma afirmação está certa. A matéria divide-se em dois blocos. No primeiro, a lógica proposicional e a lógica de primeira ordem dão-te uma linguagem para representar frases e um método para as provar. No segundo, os conjuntos, as relações, as funções, os inteiros e as recorrências aplicam essas técnicas a objetos que vais usar no resto do curso, da análise de algoritmos à criptografia.

Como estudar por estas páginas

Cada página segue o mesmo plano: primeiro a necessidade, depois a definição precisa, depois um exemplo pequeno resolvido até ao fim. Lê pela ordem se for a primeira vez, porque cada tema usa o vocabulário dos anteriores. Se estiveres a rever, salta diretamente para o tema do teste.

• Lógica proposicional: frases atómicas, conetivas, tabelas de verdade e equivalências.
• Provas em lógica proposicional: regras de inferência, condicionais, completude de conetivas e mapas de Karnaugh.
• Quantificadores: variáveis, tradução com $\forall$ e $\exists$, múltiplos quantificadores e provas.
• Conjuntos e relações: operações, produto cartesiano, relações binárias e as suas propriedades.
• Ordens parciais e funções: ordens, diagramas de Hasse, funções, composição, inversas e cardinalidade.
• Inteiros e congruências: divisão, mdc, primos, aritmética modular e resolução de congruências.
• Indução e recorrências: indução simples e forte, sequências, relações de recorrência e a equação característica.

O que deves conseguir fazer no fim

Traduzir frases da língua portuguesa para lógica e avaliar a sua verdade num modelo. Provar uma fórmula com regras de inferência, por casos ou por contradição. Distinguir uma ordem parcial de uma relação de equivalência e ler um diagrama de Hasse. Decidir se uma função é injetiva, sobrejetiva ou bijetiva. Calcular o mdc com o algoritmo de Euclides, resolver uma congruência linear e verificar um dígito de controlo. Provar uma propriedade por indução e resolver uma recorrência linear de primeira ou segunda ordem.

Fontes e âmbito

Estas páginas resumem a cadeira de Matemática Discreta da LEIC na FEUP, primeiro ano, primeiro semestre. O âmbito segue os slides teóricos e as folhas de exercícios da equipa docente do Departamento de Engenharia Informática (material de 2019/2020, cadeira então designada MDIS no MIEIC), cruzados com as notas de estudo públicas SofiaViP para MD. Os livros de referência da cadeira são Language, Proof and Logic de Barker-Plummer, Barwise e Etchemendy (lógica) e Discrete Mathematics with Graph Theory de Goodaire e Parmenter (conjuntos, números, recorrências). Foram ainda consultados repositórios públicos de exercícios de estudantes da FEUP para confirmar os tipos de problemas pedidos.

Em concreto:

• Slides teóricos e folhas de exercícios de MDIS da FEUP (autoria dos docentes, via repositório público xico2001pt/feup-mdis, consultado em setembro de 2026). Definem o programa: lógica proposicional, lógica de primeira ordem, conjuntos, relações, ordens parciais, funções, inteiros, congruências, indução e recorrências.
• Exercícios resolvidos de MDIS 2018/19 (repositório público dmfrodrigues/feup-mdis-ex, consultado em setembro de 2026). Confirmam o estilo dos testes, incluindo o uso das ferramentas LPL (Tarski’s World, Fitch, Boole).
• Resumos MD 1 e 2, MD 3 e MD 4 da SofiaViP (notas de estudante, sem data de edição visível, consultadas em setembro de 2026). Cobrem os mesmos grandes temas e serviram para confirmar a ênfase dada a cada um.
• Ficha histórica da unidade curricular no SIGARRA (ocorrência de 2018/19 e ocorrência de 2019/20, via READMEs dos repositórios acima).

Os exemplos, os valores numéricos e o texto destas páginas são originais e foram verificados de forma independente. Os pormenores de avaliação em vigor (número de testes, pesos, regras de frequência) mudam de ano para ano, por isso confirma-os sempre na página atual da cadeira no SIGARRA e no Moodle. Nada aqui substitui os enunciados oficiais.