# Matemática Discreta
## Aula 1
__Defenição:__
1. Um __conjunto__ é uma coleção de objetos de natureza qualquer.
2. Sejam A e B conjuntos. Dizemos que A está __contido__ em B se todo o elemento de A pertence a B.
3. Sejam A e B conjuntos. Dizemos que A é __igual__ a B se A⊂B e B⊂A.
4. Um conjunto __vazio__ é um conjunto que não tem elementos. Representamos por ∅
5. Sejam A, B conjuntos. Definimos
* a __intresseção__ de A e B como conjunto formado pelos elementos comuns a A e B. Representamos por A∩B;
* a __união__ de A e B como o conjunto formado pelos elementos que pertencem a pelo menos um dos conjuntos A e B. Representamos por A∪B;
6. Seja I um conjunto de índices. Seja  uma coleção de conjuntos inderada em I. Definimos
* a __interseção__ de todos os  como o conjunto formado pelos elementos comuns a todos os . Reperesentamos por 
* a __união__ de todos os  como o conjunto formado pelos elementos que pertencem a pelo menos um dos conjuntos . Representamos por 
7. Sejam A, B conjuntos. Definimos __diferença__ entre conjuntos A e B, ou __complementar__ de B em A ao conjunto dos elementos de A que não pertencem a B. Representamos por A\B.

__Proposições:__
1. O conjunto vazio é um subconjunto de qualquer conjunto i.e., temos sempre ∅⊂A para qualquer conjunto de A.
2. Propriedade distributiva. Sejam A,B,C conjuntos de Ω. Tem-se
* 
* 
3. Leis de Morgan. Seja X,Y ⊂ Ω. Tem-se
* 
* 

## Aula 2
__Defenições:__
1. Seja X um conjunto. O conjunto constituido por todos os subconjuntos de X diz-se o conjunto __potência de X__, ou conjunto das partes de X. Representamos por P(X)
2. Sejam A,B ⊂ Ω. Define-se a __diferença simétrica__ entre os conjuntos A e B como conjuntos (A\B) ∪ (B\A) e representa-se por AB
3. Qualquer conjunto S onde esteja defenida uma soma e um produto que verifiquem as propriedades S1,...,S5,P1 e D diz-se um anel. Dizemos que (S,+,.) é um anel

__Proposições:__
1. Sejam A, B ⊂ Ω. Tem-se AB=(A∪B) \ (A∩B)
2. Sejam A, B, C ⊂ Ω. Temos:
* 
* 
*  A diferença simétrica é comutativa
*  A intresseção é distributiva em relação à diferença simétrica
*  A diferença simétrica é associativa
3. Sejam a,b,c ∈ Z. Em Z a soma(+) e oproduto (.) verificam
* a+b ∈ Z (Fecho da soma)
* a+(b+c)=(a+b)+c (Associetividade da soma)
* Existe 0 ∈ Z tal que a+0=0+a (Existência de inverso aditivo ou simétrico (b:=-a))
* a+b=b+a (Comutatividade da soma)
* a.b ∈ Z (Fecho do Produto)
* a.(b.c)=(a.b).c (Associetividade do produto)
* 
4. Seja Ω um conjunto universal. O conjunto P(Ω) com a soma defenida por A+B:=  e com o produto definido por A.B=A∩B é um anel, isto é, (P(Ω)), +, ) é um anel.

## Aula 3

__Definições:__
1. Sejam A,B conjuntos. O conjunto de todos os pares ordenados (a,b) tais que a ∈ A e b ∈ B diz-se o __produto cartesianos__ de A por B e representamos por AxB. Mais sucintamente temos 
2. Sejam A,B conjuntos. Chamamos __relação binária__ de A para B a qualquer subconjunto do produto cartesiano AxB. Representamos esse subconjunto por R. No caso em que A=B, dizemos que R é uma relação binária defenida em A.
3. Sejam A,B conjuntos. Se R é uma relação binária de A para B, defenimos a __relação inversa__ de R como o subconjunto 
4. Sejam A,B,C conjuntos. Se R é uma relação binária de A para B, e S é uma relação binária de B para C, definimos a __composição__ como a relação de A para C dada por 
Representamos por SºR e diz-se "S após R"
5. Seja A um conjunto e R uma relação definida em A. Dizemos que R é
* __refletiva__ se para cada a∈A temos (a,a)∈R;
* __simétrica__ se para cada a,b ∈ R também (b,a)∈R;
* __transitiva__ se para cada a,b,c∈A com (a,b)∈ R e (b,c)∈R também (a,c)∈R

## Aula 4
__Defenições:__
1. Seja X um conjunto não vazio. Uma participação de X é uma coleção A formada por subconjuntos  que satisfaz:
* Os conjuntos Ai são não vazios
* Os conjuntos Ai são disjuntos dois a dois, isto é,  para todo i≠j
* A união dos conjuntos Ai, é X, isto é, 

2. Seja X um conjunto não vazio e R uma relação de equivalência defenida em X. Seja b∈ X. O conjunto de todos os elementos de X que estão em relação com b diz-se a __classe de equivalência__ de b e representa-se por [b], ou por , se for necessário evidenciar qual a relação de equivalência considerada. De forma mais suscinta temos  O elemento b diz-se o __representante__ da classe [b]
3. Seja X um conjunto não vazio e R uma relação de equivalência defenida em X. Chama-se conjunto __quociente__ de X segundo R ao conjunto formado pelas classes de equivalência de todos os elementos de X. Representa-se por X/R, isto é 

__Proposições:__
1. Seja A um conjunto não vazio e R uma relação de equivalência defenida em A. Sejam a,b∈A. Tem-se:
* a∈[a]
* (a,b)∈R⇔[a]=[b]
* (a,b)∉R⇔[a]∩[b]=∅
## Aula 5
__Proposições:__
1. Seja A um conjunto não vazio e R uma relação de equivalência defenida em A. O conjunto quociente de A por R é uma participação de A.

## Aula 6
__Defenições:__
1. Seja R uma relação defenida num conjunto A. O __fecho__ da relação R com respeito a uma propriedade P é uma relação  que verifica
* R ⊂  (o fecho contém a relação R)
* clP ( R) verifica a propriedade P
* se S é qualquer relação que contém a relação R e verifica a propriedade P então clP ( R)⊂ S (clP ( R) é a mais pequena relação que contém R e verifica P).

2. Seja A um conjunto. A relação {(a,a): a∈A} diz-se a relação identidade, ou relação diagonal. Representamos por  Assim, se, por exemplo A={1,2,3}, temos ={(1,1),(2,2),(3,3)}

__Proposições:__
1. Seja A um conjunto não vazio, e A uma participação de A. Em A definimos a relação R dezendo que (x,y)∈R se e só se x,y∈Ai para algum Ai∈A. R assim definida é uma relação de equivalência.
2. Seja R uma relação defenida em A. O *fecho refletivo* de R é a relação 

## Aula 7
__Proposições:__
1. Seja R uma relação defenida em A. O fecho simétrico de R é uma relação 
2. Seja R uma relção definida em A. O *fecho transitivo* R é a relação 
3. Seja A um conjunto com n elementos. Seja R uma relação definida em A. O fecho transitivo de R é a relação 

## Aula 8
__Defenições:__
1. Seja A um conjunto e R uma relação defenida em A. Dizemos que R é __anti simétrica__ se para cada a, b∈A com (a,b)∈R e (b,a)∈R temos a=b
2. Seja A um conjunto de R e uma relação defenida em A. Dizemos que R é uma __relação de ordem parcial__ em A se R é refletivva, anti simétrica e transitiva.
3. Um conjunto A munido com uma relação de ordem parcial ≤, (A,), diz-se um __conjunto parcialmente ordenado__. Abreviamos por c.p.o..(Também se usa o acrónimo inglês, "poset", de parcially ordered set).
4. Seja (A,) um poset e a,b∈A. Os elementos a e b dizem-se __comparáveis__ se ab ou ba. Por outro lado, se a e b são elementos tais que nem ab e nem ba então dizem-se __incomparáveis__.
5. Seja (A,) um c.p.o.. Se quaisquer dois elementos são comparáveis, (A,) diz-se um __conjunto totalmente ordenado__ ou __cadeia__ e a relação de ordem diz-se __total__.
6. Sejam (A,) um c.p.o. e B⊂A. Em B podemos sonsiderar a __ordem induzida__ pela ordem de A,, através de:
* Dados x,y ∈ B dizemos x y se e só se xy
7. Sejam (A,) um c.p.o. e x,y,z∈A. Dizemos que x é __coberto__ por y se  e não existe z∈A tal que . Representamos por 

__Proposições:__
1. (N,|)é uma c.p.o.
2. Sejam (A,) um c.p.o. e B⊂A. (B,) é um c.p.o.

## Aula 9
__Definições:__
1. Seja (A,) um poset
* Um elemento a∈A diz-se um __máximo__ se para qualquer x∈X temos 

* Um elemento b∈A diz-se __mínimo__ se para qualquer x∈X temos 

2. Seja (A,) um poset

* Um elemento a ∈ A diz-se um __elemento maximal__ se para qualquer x∈X temos  ou x e a são incomparáveis.
* Um elemento b ∈ A diz-se um __elemento minimal__ se para qualquer x ∈ X temos  ou x e b são incomparáveis.
3. Seja (A,) um poset. Seja B um subconjunto de A.

* Um elemento a∈A diz-se um __majorante__ de B se  para qualquer x∈B
* Um elemento b∈A diz-se um __minorante__ se para cada qualquer x∈X temos 

4. Sejam (A,) um poset e B um subconjunto de A. Se  tem elemento mínimo este elemento diz-se o __supremo__ de B. Se  tem um elemento máximo este elemento diz,se o __ínfimo__ de B.

__Proposições:__
1. Seja (A,) um poset. O máximo, se existe, é unico. (Da mesma forma que o mínimo)

## Aula 10
__Defenições:__
1. Um c.p.o. (A,) diz-se um reticulado se para cada par de elementos x,y ∈ A existe supremo e ínfimo

__Proposições:__
1. (Lema da conexão) Sejam (A,) um reticulado e a,b ∈ A. As seguintes afirmações são equivalentes:

* ab
* a∧b=a
* a∨b=b
2. Seja (A,) um reticulado. Para quaisquer a,b,c ∈ A, ∨ e ∧ verificam;
* a∨b=b∨a; a∧b=b∧a (Comutatividade)
* a∨a=a; a∧a=a (Idenpotência)
* a∧(a∨b)=a; a∨(a∧b)=a (Absorção)
* (a∨b)∨c=a∨(b∨c) (Associatividade)
* (a∧b)∧c=a∧(b∧c) (Associatividade)
## Aula 11
1. Seja (A,) um reticulado e a,b,c ∈ A. Tem-se
*