---
# System prepended metadata

title: Matemática Discreta

---

# 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 ![](https://i.imgur.com/s2Nrrjh.png) uma coleção de conjuntos inderada em I. Definimos
    *    a __interseção__ de todos os ![](https://i.imgur.com/9PlOjCF.png) como o conjunto formado pelos elementos comuns a todos os ![](https://i.imgur.com/QQuRVNL.png). Reperesentamos por ![](https://i.imgur.com/ZiBV1KJ.png)
    *    a __união__ de todos os ![](https://i.imgur.com/9PlOjCF.png) como o conjunto formado pelos elementos que pertencem a pelo menos um dos conjuntos ![](https://i.imgur.com/9PlOjCF.png). Representamos por ![](https://i.imgur.com/OLd5fKV.png)
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 
    *    ![](https://i.imgur.com/oxnQVuq.png)
    *    ![](https://i.imgur.com/SSi74Ab.png)
3. Leis de Morgan. Seja X,Y ⊂ Ω. Tem-se 
    *    ![](https://i.imgur.com/uUhQTN8.png)
    *    ![](https://i.imgur.com/prqz9Mp.png)

## 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 A![](https://i.imgur.com/NTV1P4c.png)B
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  A![](https://i.imgur.com/NTV1P4c.png)B=(A∪B) \ (A∩B)
2. Sejam A, B, C ⊂ Ω. Temos:
    *    ![](https://i.imgur.com/SpEeFQo.png)
    *    ![](https://i.imgur.com/doqcSuk.png)
    *    ![](https://i.imgur.com/lilDlFv.png) A diferença simétrica é comutativa
    *    ![](https://i.imgur.com/MnNTpFW.png) A intresseção é distributiva em relação à diferença simétrica
    *    ![](https://i.imgur.com/AlBXtlU.png) 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)
    *  ![](https://i.imgur.com/4gDUvBw.png)
4. Seja Ω um conjunto universal. O conjunto P(Ω) com a soma defenida por A+B:= ![](https://i.imgur.com/vx83BIS.png) e com o produto definido por A.B=A∩B é um anel, isto é, (P(Ω)), +![](https://i.imgur.com/356dC4Q.png), ![](https://i.imgur.com/A7nwxgz.png)) é 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 ![](https://i.imgur.com/2GGQu1T.png)
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  ![](https://i.imgur.com/tnPQNb9.png)
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  ![](https://i.imgur.com/GVV6uc8.png)
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 ![](https://i.imgur.com/jHT0L2a.png) que satisfaz:
    *    Os conjuntos Ai são não vazios
    *    Os conjuntos Ai são disjuntos dois a dois, isto é, ![](https://i.imgur.com/9EbfP7c.png) para todo i≠j
    *    A união dos conjuntos Ai, é X, isto é,  ![](https://i.imgur.com/fZEMj7I.png)

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 ![](https://i.imgur.com/8xxXPTn.png), se for necessário evidenciar qual a relação de equivalência considerada. De forma mais suscinta temos  ![](https://i.imgur.com/zdeiLsN.png)  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 é  ![](https://i.imgur.com/Yqnyngo.png)


__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 ![](https://i.imgur.com/MzqMnRJ.png) que verifica 
    *    R ⊂ ![](https://i.imgur.com/MzqMnRJ.png) (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 ![](https://i.imgur.com/D0qnzs9.png)  Assim, se, por exemplo A={1,2,3}, temos ![](https://i.imgur.com/tStbh0k.png)={(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 ![](https://i.imgur.com/PizsAFW.png)


## Aula 7 
__Proposições:__
1. Seja R uma relação defenida em A. O fecho simétrico de R é uma relação ![](https://i.imgur.com/hdGpdr5.png)
2. Seja R uma relção definida em A. O *fecho transitivo* R é a relação  ![](https://i.imgur.com/e0zGYmM.png)
3. Seja A um conjunto com n elementos. Seja R uma relação definida em A. O fecho transitivo de R é a relação  ![](https://i.imgur.com/GiGlO31.png)

## 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,![](https://i.imgur.com/AvYQytR.png)), 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,![](https://i.imgur.com/UHsiP5D.png)) um poset e a,b∈A. Os elementos a e b dizem-se __comparáveis__ se a![](https://i.imgur.com/CtquTVB.png)b ou b![](https://i.imgur.com/DWPtk41.png)a. Por outro lado, se a e b são elementos tais que nem a![](https://i.imgur.com/seFSaGU.png)b e nem b![](https://i.imgur.com/yuyxTue.png)a então dizem-se __incomparáveis__.
5. Seja (A,![](https://i.imgur.com/6VUdnLe.png)) um c.p.o.. Se quaisquer dois elementos são comparáveis, (A,![](https://i.imgur.com/DHxT4tE.png)) diz-se um __conjunto totalmente ordenado__ ou __cadeia__ e a relação de ordem diz-se __total__.
6. Sejam (A,![](https://i.imgur.com/RQ5lThy.png)) um c.p.o. e B⊂A. Em B podemos sonsiderar a __ordem induzida__ pela ordem de A,![](https://i.imgur.com/5waahrq.png), através de:
    *    Dados x,y ∈ B dizemos x ![](https://i.imgur.com/5waahrq.png)y se e só se x![](https://i.imgur.com/RQ5lThy.png)y
7. Sejam (A,![](https://i.imgur.com/RQ5lThy.png)) um c.p.o. e x,y,z∈A. Dizemos que x é __coberto__ por y se ![](https://i.imgur.com/1GtbpZd.png) e não existe z∈A tal que ![](https://i.imgur.com/LcW3zb2.png). Representamos por ![](https://i.imgur.com/TYRoveP.png)



__Proposições:__
1. (N,|)é uma c.p.o.
2. Sejam (A,![](https://i.imgur.com/RQ5lThy.png)) um c.p.o. e B⊂A. (B,![](https://i.imgur.com/5waahrq.png)) é um c.p.o.

## Aula 9
__Definições:__
1. Seja (A,![](https://i.imgur.com/RQ5lThy.png)) um poset
    *   Um elemento a∈A diz-se um __máximo__ se para qualquer x∈X temos ![](https://i.imgur.com/z0mmD0H.png)

    *   Um elemento b∈A diz-se __mínimo__ se para qualquer x∈X temos ![](https://i.imgur.com/q7T6o5N.png)

2. Seja (A,![](https://i.imgur.com/GfVfm0y.png)) um poset

    *    Um elemento a ∈ A diz-se um __elemento maximal__ se para qualquer x∈X temos ![](https://i.imgur.com/z0mmD0H.png) ou x e a são incomparáveis.
    *  Um elemento b ∈ A diz-se um __elemento minimal__ se para qualquer x ∈ X temos ![](https://i.imgur.com/EvKPrhM.png) ou x e b são incomparáveis.
3. Seja (A,![](https://i.imgur.com/3zGSink.png)) um poset. Seja B um subconjunto de A.

    *    Um elemento a∈A diz-se um __majorante__ de B se ![](https://i.imgur.com/z0mmD0H.png) para qualquer x∈B
    *    Um elemento b∈A diz-se um __minorante__ se para cada qualquer x∈X temos ![](https://i.imgur.com/q7T6o5N.png)

4. Sejam (A,![](https://i.imgur.com/3zGSink.png)) um poset e B um subconjunto de A.  Se ![](https://i.imgur.com/YKYJLub.png) tem elemento mínimo este elemento diz-se o __supremo__ de B. Se ![](https://i.imgur.com/vGXQIr7.png) tem um elemento máximo este elemento diz,se o __ínfimo__ de B.




__Proposições:__
1. Seja (A,![](https://i.imgur.com/3zGSink.png)) 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,![](https://i.imgur.com/BYERCdi.png)) 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,![](https://i.imgur.com/3zGSink.png)) um reticulado e a,b ∈ A. As seguintes afirmações são equivalentes:

    *    a![](https://i.imgur.com/3zGSink.png)b
    *    a∧b=a
    *    a∨b=b
2. Seja (A,![](https://i.imgur.com/zOELLRF.png)) 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,![](https://i.imgur.com/zOELLRF.png)) um reticulado e a,b,c ∈ A. Tem-se
    * 
   


