Estruturas Discretas 21/22

Sumários

12-10-2021 (Aula 1)

Apresentação da unidade curricular e modelo de avaliação.
Noção de proposição e valor booleano.
Operadores booleanos e suas propriedades. ( $\neg, \vee, \wedge, \rightarrow, \leftrightarrow, \oplus$ )
Primeiras leis de De Morgan.
Tabelas de verdade

A matéria dada corresponde às secções 2.1 e 2.2 do livro do Grimaldi ou 1.1, 1.2 e 1.3 do Rosen.

15-10-2021 (Aula 2)

Formas normais conjuntiva e disjuntiva
Demonstrações directas e por redução ao absurdo
Quantificadores universal ( $\forall$ e existencial ( $\exists$ ) e suas propriedades
Segundas leis de De Morgan

A matéria dada corresponde às secções 2.4 e 2.5 do livro do Grimaldi ou 1.4, 1.5 e 1.7 do Rosen.

19-10-2021 (Aula 3)

Noção de conjunto num universo
Propriedades da inclusão ( $\subseteq$ )
Complementar, reunião e intersecção ( $\cup, \cap$ ).
Cardinalidade de um conjunto finito
Propriedades da complementação, reunião e intersecção

Capítulo 3 do livro do Grimaldi ou 2.1 e 2.2 do Rosen.

22-10-2021 (Aula 4)

O conjunto dos subconjuntos de um conjunto ( $2^A$ ).
Diferença de conjuntos ( $A\setminus B$ ) e diferença simétrica ( $A\Delta B$ ).

Capítulo 3 do livro do Grimaldi ou 2.1 e 2.2 do Rosen.

26-10-2021 (Aula 5)

Relações sobre conjuntos
Reverso de uma relação. Composição de relações
Noção de função, de injectividade e de sobrejectividade
Relações binárias
Relações reflexivas, anti-reflexivas, simétricas, anti-simétricas e transitivas
Relações de equivalência

Capítulo 5 do livro do Grimaldi ou 9.1 do Rosen.

29-10-2021 (Aula 6)

Relações de equivalência e partições
Representações de relações
Contrapartidas matriciais das operações sobre relações
Fechos de realações
Fecho simétrico, reflexivo e transitivo de realações.

Capítulo 7.4 do livro do Grimaldi ou 9.3, 9.4 e 9.5 do Rosen.

02-11-2021 (Aula 7)

Representações matriciais e por grafos dirigidos de relações
Respectivo cálculo de fechos reflexivos, simétricos e transitivos
Relações de ordem parcial e suas representações por diagramas de Hasse

Capítulo 7.1 e 7.2 do livro do Grimaldi ou 9.3, 9.4 e 9.6 do Rosen.

02-11-2021 (Aula 8)

Indução finita e sua equivalência com o princípio de Dirichlet

Capítulo 4.1 do livro do Grimaldi ou 5.1 e 5.2 do Rosen.

09-11-2021 (Aula 9)

Exemplos de aplicação do princípio de indução finita.
Noção de divisibilidade e congruência módulo.

Capítulo 4.1 do livro do Grimaldi ou 5.1 e 5.2 do Rosen.

12-11-2021 (Aula 10)

O máximo divisor comum e suas propriedades
O Teorema Fundamental da Aritmética

Capítulo 4.3,4.4 e 4.5 do livro do Grimaldi ou 4.2 e 4.3 do Rosen.

16-11-2021 (Aula 11)

O algoritmo de Euclides para determinar \{(a,b)\}, a sua versão estendida e provas das respectivas correcções.

Capítulo 4.4 do livro do Grimaldi ou 4.3 do Rosen.

19-11-2021 (Aula 12)

Noções de Anel, Domínio de Integridade e Corpo. Suas propriedades.

Capítulo 14.1 e 14.2 do livro do Grimaldi.

23-11-2021 (Aula 13)

O corpo finito $\mathbb{Z}_p$

Capítulo 14.3 do livro do Grimaldi.

26-11-2021 (Aula 14)

Propriedades do símbolo binomial $\binom{n}{k}$

Capítulo 6.4 do livro do Rosen.

30-11-2021 (Aula 15)

$\mathbb{Z}_n$ e $\mathbb{Z}_n^*$ e os processos criptográficos.

3-12-2021 (Aula 16)

Cardinalidade do produto cartesiano, da reunião e do conjunto quociente como base do cálculo combinatório.

Capítulos 1.1 e 1.2 do livro do Grimaldi ou Capítulos 6.1 e 6.2 do livro do Rosen.

7-12-2021 (Aula 17)

Combinações com repetição e suas aplicações.

Capítulo 1.4 do livro do Grimaldi ou Capítulo 6.5 do livro do Rosen.

10-12-2021 (Aula 18)

O princípio da Inclusão/ Exclusão.

Capítulos 8.1-3 do livro do Grimaldi ou Capítulos 8.5 e 8.6 do livro do Rosen.

14-12-2021 (Aula 19)

Funções geradoras (ordinárias).

Capítulos 9.1-2 do livro do Grimaldi

17-12-2021 (Aula 20)

Noção de grafo e de digrafo
Sub-grafo de um grafo
Isomorfismo de grafos
Complementar de um grafo
Percurso (walk), pista (trail) e caminho (path) num grafo.