Funções

Prévia do material em texto

Func¸o˜es
Renata de Freitas e Petrucio Viana
Instituto de Matema´tica e Estat´ıstica, UFF
Abril de 2011
Suma´rio
• Relac¸o˜es funcionais, totais, injetivas, sobrejetivas.
• Func¸o˜es.
• Bijec¸o˜es.
Dana Scott
• Um dos pais da
semaˆntica denotacional
para programas.
• Preˆmio Turing em 1976.
Dana Stewart Scott
(1932 – ****)
Relac¸o˜es funcionais
Programas (determin´ısticos) podem ser vistos como func¸o˜es.
444
444Programa
sa´ıda
entrada
//
Relac¸o˜es funcionais
Definic¸a˜o Seja R ⊆ A× B. Dizemos que R e´ funcional se, para
todos a ∈ A, b, c ∈ B,
(a, b), (a, c) ∈ R =⇒ b = c .
A B
a
b++
a
c33
������������������� 9
99
99
99
99
99
99
99
99
99
A´lgebra
Proposic¸a˜o Seja R ⊆ A× A.
R e´ funcional se, e somente se, R−1 ◦ R ⊆ IA.
Relac¸o˜es totais
Definic¸a˜o Seja R ⊆ A× B. Dizemos que R e´ total se,
para todo a ∈ A, existe b ∈ B tal que (a, b) ∈ R.
A B
a ?//
������������������� 9
99
99
99
99
99
99
99
99
99
A´lgebra
Proposic¸a˜o Seja R ⊆ A× A.
R e´ total se, e somente se, IA ⊆ R ◦ R−1.
Relac¸o˜es injetivas
Definic¸a˜o Seja R ⊆ A× B. Dizemos que R e´ injetiva se, para
todos a, c ∈ A, b ∈ B,
(a, b), (c , b) ∈ R =⇒ a = c .
A B
a
b
''
c
b77
������������������� 9
99
99
99
99
99
99
99
99
99
A´lgebra
Proposic¸a˜o Seja R ⊆ A× A.
R e´ injetiva se, e somente se, R ◦ R−1 ⊆ IA.
Relac¸o˜es sobrejetivas
Definic¸a˜o Seja R ⊆ A× B. Dizemos que R e´ sobrejetiva se,
para todo b ∈ B, existe a ∈ A tal que (a, b) ∈ R.
A B
? b//
������������������� 9
99
99
99
99
99
99
99
99
99
A´lgebra
Proposic¸a˜o Seja R ⊆ A× A.
R e´ sobrejetiva se, e somente se, IA ⊆ R−1 ◦ R.
Funcional
R−1 ◦ R ⊆ IA
Total
IA ⊆ R ◦ R−1
Injetiva
R ◦ R−1 ⊆ IA
Sobrejetiva
IA ⊆ R−1 ◦ R
oo //
oo //
OO
R−1
��
OO
R−1
��
dd
$$J
JJ
JJ
JJ
JJ
JJ
JJ
JJ
JJ
JJ
JJ
zz
::ttttttttttttttttttttt
⊆−1
Proposic¸a˜o Seja R ⊆ A× B. Temos que R−1 ⊆ B × A e
R e´ funcional se, e somente se, R−1 e´ injetiva.
RA B
a
b++
a
c33
������������������� 9
99
99
99
99
99
99
99
99
99
R−1A B
b
a
ww
c
a gg
������������������� 9
99
99
99
99
99
99
99
99
99
Proposic¸a˜o Seja R ⊆ A× B. Temos que R−1 ⊆ B × A e
R e´ injetiva se, e somente se, R−1 e´ funcional.
RA B
a
b
''
c
b77
������������������� 9
99
99
99
99
99
99
99
99
99
R−1A B
b
a ss
b
c kk
������������������� 9
99
99
99
99
99
99
99
99
99
Proposic¸a˜o Seja R ⊆ A× B. Temos que R−1 ⊆ B × A e
R e´ total se, e somente se, R−1 e´ sobrejetiva.
R
A B
a ?//
������������������� 9
99
99
99
99
99
99
99
99
99
R−1
A B
?a oo
������������������� 9
99
99
99
99
99
99
99
99
99
Proposic¸a˜o Seja R ⊆ A× B. Temos que R−1 ⊆ B × A e
R e´ sobrejetiva se, e somente se, R−1 e´ total.
R
A B
? b//
������������������� 9
99
99
99
99
99
99
99
99
99
R−1
A B
b? oo
������������������� 9
99
99
99
99
99
99
99
99
99
Relac¸o˜es bijetivas
Definic¸a˜o Seja R ⊆ A× B. Dizemos que R e´ bijetiva se for
funcional, total, injetiva e sobrejetiva.
Quando uma relac¸a˜o R e´ bijetiva, dizemos tambe´m que R e´ uma
bijec¸a˜o.
Proposic¸a˜o Seja R ⊆ A× B. Temos que R e´ bijetiva se, e
somente se, R satisfaz as seguintes condic¸o˜es:
(a) para todo a ∈ A, existe um u´nico b ∈ B tal que (a, b) ∈ R, e
(b) para todo b ∈ B, existe um u´nico a ∈ A tal que (a, b) ∈ R.
Bijec¸a˜o e cardinalidade
Exerc´ıcios
1. Exerc´ıcios do Menezes
(Paulo B. Menezes, Matema´tica Discreta para Computac¸a˜o e
Informa´tica, 2a. edic¸a˜o, Sagra Luzzatto / Instituto de Informa´tica da
UFRGS, Porto Alegre, 2006).
2. Exerc´ıcios do Scheinerman
(E.R. Scheinerman, Matema´tica Discreta, Thomson, Sa˜o Paulo, 2006).
3. Exerc´ıcios da Lista 15.