Conjuntos, Relações e Funções

Prévia do material em texto

Capítulo III
CONJUNTOS, RELAÇÕES E FUNÇÕES
–p. 1/37
Conjuntos, Relações e Funções
Conjuntos
– p. 2/37
Conjuntos
Dois conjuntos são iguais se,
e somente se, têm os mesmos elementos.
– p. 3/37
Conjuntos
A ⊆ B sse x ∈ A ⇒ x ∈ B
A = B sse A ⊆ B e B ⊆ A
– p. 4/37
Conjuntos
O conjunto vazio designa-se por ∅ ou { }.
O conjunto universal designar-se-á por E, a menos que
seja explicitado o contrário.
A cada conjunto E e a cada condição S(x) corresponde
um conjunto A cujos elementos são exatacmente os
elementos de A para os quais S(x) acontece:
A = {x ∈ E |S(x)}
ou
A = {x |S(x)}
– p. 5/37
Conjuntos
Operações entre conjuntos
Operação
Intersecção ∩ x ∈ A ∩ B ⇔ x ∈ A ∧ x ∈ B
Reunião ∪ x ∈ A ∪ B ⇔ x ∈ A ∨ x ∈ B
Complementação .c x ∈ Ac ⇔ ¬(x ∈ A)
Diferença − x ∈ A − B ⇔ x ∈ A ∧ ¬(x ∈ B)
– p. 6/37
Conjuntos
Lista síntese da relação entre operações lógicas e
operações entre conjuntos:
equivalência identidade
implicação inclusão
conjunção intersecção
disjunção reunião
negação complementação
– p. 7/37
Conjuntos
conjunto universal condição universal
conjunto vazio condição vazia
– p. 8/37
Tabela PC
A ∪ Ac = E Lei da complementação
A ∩ Ac = ∅ Lei da exclusão
A ∩ E = A Leis da identidade
A ∪ ∅ = A
A ∪ E = E Leis da absorção
A ∩ ∅ = ∅
A ∪ A = A Leis da idempotência
A ∩ A = A
(Ac)c = A Lei da dupla complementação
A ∪ B = B ∪ A Leis da comutatividade
A ∩ B = B ∩ A
– p. 9/37
(A ∪ B) ∪ C = A ∪ (B ∪ C) Leis da associatividade
(A ∩ B) ∩ C = A ∩ (B ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Leis da distributividade
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
(A ∩ B)c = Ac ∪ Bc Leis de De Morgan
(A ∪ B)c = Ac ∩ Bc
– p. 10/37
Conjuntos
⋃
i∈I
Ai
x ∈
⋃
i∈I
Ai se e só se x ∈ Ai para algum i ∈ I.
⋂
i∈I
Ai
x ∈
⋂
i∈I
Ai se e só se x ∈ Ai para todo o i ∈ I.
– p. 11/37
Conjuntos
Se I = {1, 2, ..., n}, podemos escrever
n⋃
i=1
Ai
n⋂
i=1
Ai
– p. 12/37
Conjuntos
Exemplos.
⋃
1≤i≤3
{1i, 2i, 3i} = {1, 2, 3, 4, 9, 8, 27}
⋂
1≤i≤3
{1i, 2i, 3i} = {1}
⋃
n∈N\{0}
] − n, n[= R
⋂
n∈N\{0}
] −
1
n
,
1
n
[= {0}
– p. 13/37
Conjuntos
Exercício: Determine
⋂
n∈N\{0}
] −
1
n
,
1
n
[.
– p. 14/37
Conjuntos
Dois conjuntos A e B dizem-se disjuntos se
A ∩ B = ∅
Dados conjuntos Ai, i ∈ I, dizemos que eles são
disjuntos dois a dois se para quaisquer i, j ∈ I, com
i $= j, se tem
Ai ∩ Aj = ∅
– p. 15/37
Conjuntos
Exercício: Em cada uma das seguintes alíneas, diga,
justificando, se os conjuntos são ou não disjuntos dois a
dois.
(a) {2, 3, 5}, {4, 6, 8}, {11, 22}
(b) {2, 3, 5}, {2, 4, 6}, {1, 7, 9}
– p. 16/37
Conjuntos
O cardinal de um conjunto finito: número de elementos
do conjunto.
#A cardA |A|
Se A e B são conjuntos finitos, tem-se
card(A ∪ B) = cardA + cardB − card(A ∩ B) .
Para A1, ..., An disjuntos dois a dois,
card(A1 ∪ ... ∪ An) = cardA1 + ... + cardAn
– p. 17/37
Conjuntos
Sejam A e B conjuntos. O produto cartesiano de A por
B, designa-se por
A × B
e é dado por
A × B = {(a, b) : a ∈ A ∧ b ∈ B} .
Exemplo. A = {1, 2} , B = {a, b, c}
– p. 18/37
Conjuntos
Produto cartesiano de n conjuntos:
A1 × A2 × ... × An =
= {(a1, a2, ..., an) : a1 ∈ A1 ∧ a2 ∈ A2 ∧ ... ∧ an ∈ An}
Por definição, An = A × A × ... × A.
{1, 2}× {a, b, c}× {x, y} =
= {(1, a, x), (1, a, y), (1, b, x), (1, b, y), (1, c, x),
(1, c, y), (2, a, x), (2, a, y), (2, b, x), (2, b, y), (2, c, x),
(2, c, y)}
– p. 19/37
Conjuntos
Se A1, A2, ..., An são conjuntos finitos, então
card(A1 × A2 × ... × An) =
= cardA1 × cardA2 × ... × cardAn
– p. 20/37
Conjuntos
Seja A um conjunto. O conjunto potência de A ou
conjunto das partes de A, designado por
IPA
ou
2A
é o conjunto de todos os subconjuntos de A.
– p. 21/37
Conjuntos
Exemplo. IP({1, 2}) = { ∅, {1}, {2}, {1, 2} }.
Se A é finito, tem-se que
card(IPA) = 2cardA
– p. 22/37
Conjuntos, Relações e Funções
Relações
–p. 23/37
Relações
Exemplo.
Uma empresa vende os produtos x, y, z e w.
Os clientes são considerados do tipo a, b ou c de acordo
com certos parâmetros
Registo das vendas num certo dia:
Cliente Tipo Produto Preço
J. Costa a x 50
A. Santos c y 15
C. Cardoso b y 15
H. Barros a w 30
– p. 24/37
Relações
Cliente Tipo Produto Preço
J. Costa a x 50
A. Santos c y 15
C. Cardoso b y 15
H. Barros a w 30
C = {clientes} T = {a, b, c} P = {produtos}
D = {preços dos produtos}
A relação R ⊆ C × T × P × D é constituída por:
(J. Costa, a, x, 50)
(A. Santos, c, y, 15)
(C. Cardoso, b, y, 15)
(H. Barros, a, w, 30)
– p. 25/37
Relações
A1, A2, ..., An conjuntos
Uma relação R sobre A1 × A2 × ... × An é dada por um
subconjunto de A1 × A2 × ... × An.
Como R é uma relação constituída por n-uplos, R diz-se
uma relação n-ária.
– p. 26/37
Relações
Relações Binárias
A e B conjuntos
Uma relação (binária) R de A para B é um subconjunto
de A × B.
(x, y) ∈ R:= x é R-relacionado com y
Para exprimir que R é uma relação de A paraB,
escrevemos
R : A ↔ B
– p. 27/37
Relações
R : A ↔ B
A é o conjunto de partida de R
B é o conjunto de chegada de R
– p. 28/37
Relações
A relação universal de A para B é
A × B
.
Exemplo:
A = conjunto dos alunos de Matemática Discreta;
B = {curso de Engenharia Informática}
R = {(x, y) : x frequenta o curso y}
– p. 29/37
Relações
A relação vazia não contém nenhum par.
Exemplo:
A = conjunto dos alunos de Matemática Discreta;
B =
{curso de Eng. Mecânica, curso de Eng. Electrotécnica}
xRy := x frequenta o curso y
– p. 30/37
Relações
Exemplo:
P = {províncias de Portugal}
C = {cidades portuguesas}
x está R-relacionado com y se e só se a província x
contém a cidade y.
Os pares (Beira Alta, Viseu) e (Algarve, Faro) pertencem
a R.
O par (Minho, Viseu) não pertence a R.
– p. 31/37
Relações
Notações:
(x, y) ∈ R
xRy
x R-relacionado com y
x "Ry (x não está R-relacionado com y)
– p. 32/37
Relações
Representações de relações finitas
Matrizes booleanas
– p. 1/??
Representações de uma relações
Matrizes booleanas
A = {a1, a2, ..., am}
B = {b1, b2, ..., bn}
Matriz de uma relação R : A ↔ B:
MR = (aR
ij)
tal que
aR
ij =
{
0 se ai "Rbj
1 se aiRbj
.
– p. 2/??
Representações de uma relações
Exemplo:
Sejam A = {2, 3, 4, 5} e B = {1, 2, 3}.
Consideremos os elementos de A e B ordenados pela
ordem natural.
Seja R a relação “é múltiplo de".
A matriz desta relação é





1 1 0
1 0 1
1 1 0
1 0 0





– p. 3/??
Representações de uma relações
Representação gráfica
a1 • ! • b1
a2 • ! • b2
• b3
"
"
"
"
"
"
"
"
"
""#
$$$$$$$$$$$%
representa a relação {(a1, b1), (a1, b3), (a2, b2), (a2, b3)}
de {a1, a2} para {b1, b2, b3}.
– p. 4/??
Relações
R : A ↔ B
Domínio de R:
domR = {x ∈ A : ∃y∈B(x, y) ∈ R}
Contradomínio de R:
cdomR = {y ∈ B : ∃x∈A(x, y) ∈ R} .
– p. 5/??
Relações
Novas relações a partir de relações dadas:
Relação inversa de R : X ↔ Y :
R−1 : Y ↔ X
constituída por todos os
pares (y, x) tais que (x, y) ∈ R
yR−1x sse xRy
(R−1)−1 = R .
– p. 6/??
Relações
R, S : A ↔ B
x(R ∩ S)y ⇔ xRy ∧ xSy
x(R ∪ S)y ⇔ xRy ∨ xSy
x(R − S)y ⇔ xRy ∧ x (Sy
x(Rc)y ⇔ x (Ry
– p. 7/??
Relações
Se R : A ↔ B e S : C ↔ D são duas relações tais que
A ⊆ C, B ⊆ D e R ⊆ S, dizemos que:
S é uma extensão de R
R é uma restrição de S.
– p. 8/??
Relações
R : X ↔ Y S : Y ↔ Z
A composição de R e S é a relação
R · S : X ↔ Z
é dada por
x(R · S)z ⇔ ∃y∈Y (xRy ∧ ySz) .
– p. 9/??
Relações
A composição de relações é associativa:
(R · S) · T = R · (S · T )
– p. 10/??
Relações
Operações booleanas com matrizes
Soma booleana de duas matrizes booleanas A = (aij) e
B = (bij) da mesma ordem:
A
∨
B = (aij ∨ bij)
Produto booleano de uma matriz booleana A = (aij)
m × n por uma matriz booleana B = (bij) n × p:
A # B =
(
n
∨
k=1
aik ∧ bkj
)
– p. 11/??
Relações
R : X ↔ Y S : Y ↔ Z
MR MS
Matriz da composição R · S:
MR·S = MR " MS
– p. 12/??
Relações
Relações sobre um conjunto
Relação identidade sobre A:
IA = {(x, x) : x ∈ A}
Se R é uma relação sobre um conjunto A, abreviamos
R · R por R2,R · R · R por R3, etc.
– p. 13/??
Relações
Propriedades das relações
Seja R uma relação sobre um conjunto X.
R diz-se:
reflexiva, se, para todo o x ∈ X, xRx;
irreflexiva, se, para todo o x ∈ X, x "Rx;
simétrica, se, para cada x e y em X, xRy ⇒ yRx;
– p. 14/??
Relações
Propriedades das relações
Seja R uma relação sobre um conjunto X.
R diz-se:
anti-simétrica, se, para cada x e y em X,
se x != y, xRy ⇒ y !Rx; ou seja,
se xRy e yRx então x = y;
transitiva, se, para cada x, y e z em X, xRy ∧ yRz ⇒ xRz.
– p. 15/??
Relações
Exercício: Caracterize a matriz de uma relação (sobre
um conjunto finito)
(i) reflexiva; (ii) irreflexiva; (iii) simétrica;
(iv) anti-simétrica.
– p. 16/??
Relações
Fechos
Seja R uma relação sobre um conjunto A.
Fecho reflexivo de R: denota-se por R(r) e é a menor
relação reflexiva em A que contém R.
Fecho simétrico: denota-se por R(s) e é a menor relação
simétrica que contém R.
Fecho transitivo denota-se por R+ e é a menor relação
transitiva que contém R.
Por R∗ denotamos a menor relação reflexiva e transitiva
contendo R.
– p. 17/??
Relações
Facilmente se concluem as seguintes igualdades:
R(r) = R ∪ IA
R(s) = R ∪ R−1
R+ = R ∪ R2 ∪ R3 ∪ ... ∪ Rm, supondo |A| = m.
R∗ = R+ ∪ R0,onde R0 = IA.
– p. 18/??
Relações
Uma relação R sobre um conjunto diz-se uma
relação de equivalência se for reflexiva, simétrica e
transitiva.
– p. 1/8
Relações
Exemplos: No conjunto {−3,−2, 0, 1, 2, 3, 4, 5}, considere
as relações:
1) xRy sse |x| = |y|
2) xSy sse x − y é par
– p. 2/8
Relações
Uma partição dum conjunto S é uma família
(Ai)i∈I
de subconjuntos de S, tal que
cada elemento de S está em exactamente um dos
conjuntos Ai;
ou seja, para cada s ∈ S, existe um e só um i ∈ I tal que
s ∈ Ai.
– p. 3/8
Relações
Teorema. Seja R uma relação de equivalência em S, e
seja [x] o conjunto de todos os y ∈ S R-relacionados com
x, i.e., [x] = {y : yRx}.
Então os subconjuntos [x] de S determinam uma
partição de S.
Reciprocamente, toda a partição de um conjunto S
determina uma relação de equivalência.
Aos conjuntos
[x] = {y : yRx}
determinados por uma relação de equivalência R
chamamos
classes de equivalência
da relação R.
– p. 4/8
Relações
R relação de equivalência no conjunto A
[x] = {y ∈ A |xRy}
[x] é a classe de equivalência de x.
Exemplo
A = {1, 2, 3}, R = IA ∪ {(1, 2), (2, 1)}
Classes de equivalência: {1, 2}, {3} (formam uma
partição do conjunto A)
{1, 2} é a classe de equivalência de 1 e de 2
{3} é a classe de equivalência de 3
– p. 5/8
Relações
Exemplo
Z, xRy := x − y é par
classe de equivalência de 1:
[1] = {números inteiros ímpares}
classes de equivalência de R:
{números inteiros ímpares}
{números inteiros pares}
(formam uma partição de Z)
– p. 6/8
Relações
Exemplo.
R no conjunto dos números inteiros Z tal que aRb se e só
se |a| = |b|.
É uma relação reflexiva, simétrica e transitiva, sendo
portanto uma relação de equivalência.
As classes de equivalência são ...?
[a] = {−a, a}, para cada inteiro a
– p. 7/8
Relações
Seja n um inteiro positivo.
Dois números inteiros a e b dizem-se
congruentes módulo n
escrevendo-se
a ≡ b (modn)
quando
a − b é múltiplo de n.
Exercício Verifique que a relação de congruência é uma
relação de equivalência. Quais são as classes de
equivalência?
– p. 8/8
Relações
Ordens parciais
–p. 1/21
Relações
Uma relação R sobre um conjunto S diz-se uma ordem
parcial (fraca) se for
reflexiva
anti-simétrica
transitiva
R diz-se uma ordem parcial estrita se for
irreflexiva
anti-simétrica
transitiva
Se R é uma relação de ordem parcial no conjunto A
(A,R) ou simplesmente A diz-se um
conjunto parcialmente ordenado (ou poset)
– p. 2/21
Relações
Se R é uma ordem parcial estrita, então R(r) é uma
ordem parcial fraca.
Exemplo:
A relação < entre números inteiros é uma relação de
ordem estrita.
O seu fecho reflexivo é a relação ≤.
– p. 3/21
Relações
Se R é uma ordem parcial estrita, então R(r) é uma
ordem parcial fraca.
E ao contrário:
Se R é uma ordem parcial em A, então R − IA é uma
ordem parcial estrita.
– p. 4/21
Relações
Uma ordem parcial R sobre A diz-se uma
ordem total
ou
ordem linear
se
∀x, y ∈ A (xRy ou yRx).
(A,R) é um conjunto totalmente ordenado ou cadeia.
Exemplos
– p. 5/21
Relações
Seja ! uma ordem parcial em A;
≺ é a correspondente ordem parcial estrita,
≺=! −IA
$ := (≺)−1
% := (!)−1
Se (A,!) é um conjunto parcialmente ordenado, (A,%)
também é um conjunto parcialmente ordenado e diz-se o
dual de (A,!).
– p. 6/21
Relações
Seja (A,!) um conjunto parcialmente ordenado.
x é um predecessor de y
y é um sucessor de x
}
:= x ≺ y
x é um predecessor imediato de y := x ≺ y e não exis-
tem elementos entre
x e y
:= não existe nen-
hum z ∈ A tal que
x ≺ z ≺ y
– p. 7/21
Relações
Um conjunto parcialmente ordenado pode ser
representado por um diagrama de Hasse:
representamos os elementos do conjunto e sempre que
x é um predecessor imediato de y ligamos x a y por um
arco com x situado num nível inferior a y.
– p. 8/21
Relações
Caso mais simples: uma cadeia.
Exemplo Diagrama de Hasse do conjunto {1, 2, 3} com a
relação ≤ habitual:
• 1
• 2
• 3
– p. 9/21
Relações
Exemplo Diagrama de Hasse do poset (IPA, ⊆), onde
A = {a, b}:
∅
{b}{a}
A
!
!!
"
"
!
!
"
"
– p. 10/21
Relações
Conjuntos parcialmente ordenados bem-fundados
Seja (A,!) um conjunto parcialmente ordenado.
< x1, x2, ... >
diz-se uma sequência estritamente decrescente se
satisfizer xi " xi+1 para todo i.
Um poset (A,!) diz-se bem-fundado se não tiver
sequências estritamente decrescentes infinitas.
– p. 11/21
Relações
Exemplos.
Exemplos de sequências estritamente decrescentes no
poset (ZZ,≤):
< 2, 1,−2,−10 >
< 4, 2, 0, −2, −4, −6, · · · >
(ZZ,≤) tem sequências estritamente decrescentes
infinitas pelo que não é bem-fundado.
(IN,≤) é bem-fundado.
– p. 12/21
Relações
Exemplos:
Exemplo de uma sequência estritamente decrescente no
poset (IPA, ⊆), onde A = {a, b, c}:
< A, {a, b}, {b}, { } > .
Todo o poset sobre um conjunto finito é bem-fundado.
– p. 13/21
Relações
Exemplos:
A sequência
< IN − {0, 1}, IN − {0, 1, 2}, ... >
onde o i-ésimo termo é
IN − {0, 1, ..., i}
é uma sequência estritamente decrescente infinita.
Portanto, (IPIN,⊆) não é bem-fundado.
– p. 14/21
Relações
Ordens parciais em produtos cartesianos
(A1,≤1) e (A2,≤2) dois posets
A relação " definida por
(x1, x2) " (y1, y2) sse xi ≤i yi para i = 1, 2
é uma ordem parcial em A1 × A2.
– p. 15/21
Relações
Ordens parciais em produtos cartesianos
Exemplo: (A1,≤1) = (A2,≤2) = (N,≤)
(N,≤) é um conjunto totalmente ordenado (ou cadeia).
Com esta ordem, será N × N um conjunto totalmente
ordenado?
– p. 16/21
Relações
Analogamente para (Ai,≤i), i = 1, 2, . . . , n, se induz uma
ordem em
A1 × A2 × · · ·× An
(x1, x2, . . . , xn) ≤ (y1, y2, . . . , yn) sse xi ≤i yi, para cada i
– p. 17/21
Relações
Ordens parciais em produtos cartesianos
(A1,≤1) e (A2,≤2) dois posets
Ordem lexicográfica:
(x1, x2) "l (y1, y2) sse x1 <1 y1 ou x1 = y1 e x2 ≤2 y2
– p. 18/21
Relações
(A1,≤1), (A2,≤2) e (A3,≤3) posets
Ordem lexicográfica em A1 × A2 × A3:
(x1, x2, x3) #l (y1, y2, y3)
sse
(x1 <1 y1)∨(x1 = y1∧x2 <2 y2)∨(x1 = y1∧x2 = y2∧x3 ≤3 y3)
– p. 19/21
Relações
Analogamente se define ordem lexicográfica em
produtos cartesianos
A1 × A2 × · · ·× An
Se (Ai,≤i), i = 1, 2, . . . , n, são conjuntos totalmente
ordenados, então A1 × A2 × · · ·× An é um conjunto
totalmente ordenado com a ordem lexicográfica.
– p. 20/21
Relações
Exercício: Ordene pela ordem crescente lexicográfica os
seguintes elementos de R4 considerando R com a ordem
total usual:
(1,−3,−1, 0), (−1/2, 1, 5, 2), (0,
√
2, 3,−4), (0,−1, 3, 5)
– p. 21/21
Relações
Funções
–p. 1/32
Funções
Uma relação binária
f ⊆ A × B
diz-se uma
função
se
para cada x ∈ A existir um e um só y ∈ B tal que (x, y) ∈ f .
Isto é, cada elemento de A tem uma e uma só imagem.
– p. 2/32
Funções
Notações:
f : A → B
(x, y)∈ f
f(x) = y
f : x %→ y
– p. 3/32
Funções
função f : A → B
domínio:
domf = A
contradomínio:
cdomf = {y ∈ B |∃x ∈ A(y = f(x))}
– p. 4/32
Funções
Algumas funções importantes
1. Função identidade: IA : A → A definida por f(x) = x
para todo o x ∈ A (coincide com a relação
identidade).
2. Função constante: todos os elementos do domínio
têm a mesma imagem.
– p. 5/32
Funções
3. Função característica: A característica de um
número real x é o maior número inteiro que é menor
ou igual a x e denota-se por [x].
Por exemplo,
[−
3
2
] = −2
[−0.24] = −1
[2.5] = 2
– p. 6/32
Funções
4. Função módulo n: Dados um número inteiro x e um
inteiro positivo n, existem um inteiro y e um natural r
com 0 ≤ r < n, tais que
x = yn + r
sendo y e r únicos.
y é o quociente da divisão de x por n
r é o resto da divisão de x por n
Facilmente se conclui que y = [xn ].
O resto da divisão de x por n diz-se x módulo n e
representa-se por
xmodn
– p. 7/32
Funções
Exemplos:
8mod3=2
-8mod3=1
Exercício (para casa): Justificar as duas igualdades.
– p. 8/32
Funções
A igualdade seguinte relaciona a função módulo n com a
função característica:
xmodn = x − [x/n]n .
Exercício (para casa): Justificar.
– p. 9/32
Funções
Uma função f : A → B diz-se:
injectiva, se quaisquer dois elementos distintos do
domínio têm imagens diferentes, i.e.,
∀x, x′∈A (f(x) = f(x′) → x = x′)
sobrejectiva, se todo o elemento do conjunto de
chegada é imagem de algum elemento do domínio,
expresso doutro modo, se
∀y∈B ∃x∈A (f(x) = y)
bijectiva, se for injectiva e sobrejectiva, ou seja,
∀y∈B ∃1
x∈A (f(x) = y)
– p. 10/32
Funções parciais
Uma relação binária f ⊆ A × B diz-se uma função
parcial se para cada x ∈ A existir quando muito um y ∈ B
tal que (x, y) ∈ f .
Qual a diferença relativamente à definição de função?
– p. 11/32
Funções parciais
Claro que uma função é, em particular, uma função
parcial.
De uma função parcial podemos obter uma função
restringindo o conjunto de partida ao domínio da função
parcial.
– p. 12/32
Funções
Composição de funções
A composição de funções define-se como a das
relações.
Dadas duas funções f : A → B e g : B → C, a relação
composição de f com g é sempre uma função.
Mas ATENÇÃO: a notação usada para as funções é
diferente da usada para as relações.
– p. 13/32
Funções
Tal como a composição de relações, a composição de
funções é associativa:
(f · g) · h = f · (g · h)
– p. 14/32
Funções
Podemos considerar uma composição de funções mais
geral do que a descrita acima:
basta que
cdom(f) ⊆ dom(g)
Ou seja,
basta que f(x) ∈ Dg, para todo o x ∈ Df .
x f(x)! !! g(f(x))! !!
g·f
""
– p. 15/32
Funções parciais
Composição de funções parciais
Dadas funções parciais
f de A em B
g de B em C
a composição g · f das duas é a função parcial de A em
C tal que
dom(g · f) = {x ∈ A |x ∈ domf e f(x) ∈ domg }
e que a cada x do seu domínio faz corresponder g(f(x)).
– p. 16/32
Funções parciais
Exemplo:
f, g : IR → IR
f(x) = x + 1
g(y) = 1/y.
Composição:
g(f(x)) =
1
x + 1
dom(g · f) =?
– p. 17/32
Funções
Visto que uma função é uma relação, podemos falar da
sua relação inversa.
Por exemplo, a relação
{(1, 2), (2, 3), (3, 3)}
é uma função de X = {1, 2, 3} em X
e a sua relação inversa é
{(2, 1), (3, 2), (3, 3)}
Mas esta relação não é uma função: a 3 correspondem
duas "imagens"!
– p. 18/32
Funções
Uma função f tem inversa, ou é invertível, se a sua
relação inversa for uma função, que se diz então a
função inversa de f
.
– p. 19/32
Funções
É evidente que uma função não injectiva não tem
inversa. (Porquê?)
Uma função que não seja sobrejectiva também não tem
inversa. (Porquê?)
– p. 20/32
Funções
Portanto, podemos concluir que uma função para ter
inversa tem de ser bijectiva.
A recíproca também é verdadeira.
Ou seja:
Uma função é invertível sse for bijectiva.
– p. 21/32
Funções
Se f : A → B é uma função bijectiva,
f−1 : B → A
define-se fazendo corresponder a cada y ∈ B o único x
de A tal que f(x) = y.
– p. 22/32
Funções
Se uma função f : A → B é bijectiva, a sua inversa,
f−1 : B → A, também o é. Além disso,
f · f−1 = IB
f−1 · f = IA
– p. 23/32
Funções
“Funções inversas"de funções não bijectivas...
Se uma função f : A → B é injectiva mas não
sobrejectiva, podemos considerar uma inversa parcial.
Exemplo:
f : [−π/2, π/2] → IR
f(x) = sin x
é injectiva mas não é sobrejectiva;
no entanto, restringindo o conjunto de chegada de f a
[−1, 1], obtemos a inversa
g : [−1, 1] → [−π/2, π/2]
que a cada x ∈ [−1, 1] faz corresponder arcsinx.
– p. 24/32
Funções
Cardinal de um conjunto
Dois conjuntos finitos têm o mesmo cardinal sse existir
uma função bijectiva entre eles.
Vamos estender a noção de cardinal a conjuntos
infinitos.
– p. 25/32
Funções
Cardinal de um conjunto
A relação ∼ entre conjuntos dada por
A ∼ B ⇔ (existe uma função bijectiva de A para B)
é uma relação de equivalência.
Dois conjuntos são equipotentes se pertencerem à
mesma classe de equivalência dessa relação.
– p. 26/32
Funções
Dizemos que dois conjuntos A e B têm o mesmo
cardinal sse forem equipotentes.
Escreve-se então
cardA =cardB.
– p. 27/32
Funções
car(IN)=card({n ∈ IN : n é par})
f : N → {números naturais pares}
n %→ 2n
é bijectiva
– p. 28/32
Funções
card({n ∈ IN : n é par});
card({números naturais ímpares} =card(IN)
card({números naturais múltiplos de 3} =card(IN)
Exercício: Indique funções que justifiquem estas
afirmações.
Determine outros subconjuntos de IN que têm o mesmo
cardinal que IN.
– p. 29/32
Funções
Para mostrar que card(ZZ+ × ZZ+) =cardIN, podemos
usar a diagonalização de Cantor.
– p. 30/32
Funções
cardQ =cardIN
cardIR >cardIN
– p. 31/32
Funções
Um conjunto infinito A diz-se numerável se
cardA =cardIN.
Exemplos de conjuntos numeráveis: IN, ZZ, Q, etc.
O conjunto IR é um exemplo de conjunto não numerável.
– p. 32/32
	small Relac c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes parciais
	small Func c~oes parciais
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes parciais
	small Func c~oes parciais
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes
	small Func c~oes