# Matemática Discreta

Lógica, conjuntos, números inteiros, indução e recorrências, com exemplos resolvidos.

Página: https://resumos.rgo.pt/cadeiras/md/

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](https://resumos.rgo.pt/cadeiras/md/logica-proposicional/): frases atómicas, conetivas, tabelas de verdade e equivalências.
*   [Provas em lógica proposicional](https://resumos.rgo.pt/cadeiras/md/provas-proposicionais/): regras de inferência, condicionais, completude de conetivas e mapas de Karnaugh.
*   [Quantificadores](https://resumos.rgo.pt/cadeiras/md/quantificadores/): variáveis, tradução com $\forall$ e $\exists$, múltiplos quantificadores e provas.
*   [Conjuntos e relações](https://resumos.rgo.pt/cadeiras/md/conjuntos-relacoes/): operações, produto cartesiano, relações binárias e as suas propriedades.
*   [Ordens parciais e funções](https://resumos.rgo.pt/cadeiras/md/ordens-funcoes/): ordens, diagramas de Hasse, funções, composição, inversas e cardinalidade.
*   [Inteiros e congruências](https://resumos.rgo.pt/cadeiras/md/inteiros-congruencias/): divisão, mdc, primos, aritmética modular e resolução de congruências.
*   [Indução e recorrências](https://resumos.rgo.pt/cadeiras/md/inducao-recorrencia/): 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](https://github.com/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](https://github.com/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](https://drive.google.com/drive/folders/1PZYhtsUc6mDA96jnVR4wiLWWxNWeovdK) (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](https://sigarra.up.pt/feup/pt/ucurr_geral.ficha_uc_view?pv_ocorrencia_id=419984) e [ocorrência de 2019/20](https://sigarra.up.pt/feup/pt/ucurr_geral.ficha_uc_view?pv_ocorrencia_id=436426), 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.