LK-Fund.CC-relacoes.pdf

Prévia do material em texto

Fundamentos Matema´ticos para Computac¸a˜o
Sistemas de Informac¸a˜o
Luis Antonio Kowada
UFF-Instituto de Computac¸a˜o
2017-2
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 1 / 8
Relac¸o˜es
Conceitos importantes
O que e´ uma relac¸a˜o de A para B?
Uma relac¸a˜o bina´ria (ou simplesmente relac¸a˜o) de A com B e´ um
sub-conjunto de A× B.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 2 / 8
Relac¸o˜es
Propriedades de relac¸o˜es
Uma relac¸a˜o R ⊆ A× A pode ter (ou na˜o) alguma(s) das seguintes
propriedades:
Poss´ıveis propriedades de uma relac¸a˜o R
Dados a, b e c ∈ A,
reflexiva (a, a) ∈ R
sime´trica se (a, b) ∈ R enta˜o (b, a) ∈ R
transitiva se (a, b) ∈ R e (b, c) ∈ R enta˜o (a, c) ∈ R
Relac¸a˜o de Equivaleˆncia
Uma relac¸a˜o R que e´ reflexiva, sime´trica e transitiva e´ chamada Relac¸a˜o
de Equivaleˆncia
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 3 / 8
Func¸a˜o
Conceitos fundamentais
Definic¸a˜o
Uma relac¸a˜o f ⊆ A× B na qual ∀a ∈ A∃!b ∈ B tal que (a, b) ∈ R e´
chamada func¸a˜o, denotada por f : A→ B. O conjunto A e´ chamado de
dom´ınio da func¸a˜o e B e´ o contra-dom´ınio da func¸a˜o. Se (a, b) ∈ f , enta˜o
dizemos que b e´ imagem de a sob f , denotando b por f (a). O conjunto
formado por todas as imagens de elementos de A sob f e´ chamado
conjunto imagem ou imagem de f .
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 4 / 8
Func¸a˜o
Tipos de Func¸a˜o
Func¸a˜o Sobrejetora
Uma func¸a˜o f : A→ B e´ chamada sobrejetora (ou sobrejetiva), se B e´ o
conjunto imagem de f .
Func¸a˜o Injetora
Uma func¸a˜o f : A→ B e´ chamada injetora (ou injetiva), se nenhum
elemento de B e´ imagem de dois elementos distintos de A sob f .
Func¸a˜o Bijetora
Uma func¸a˜o f : A→ B e´ chamada func¸a˜o bijetora (ou func¸a˜o bijetiva),
(ou simplesmente bijec¸a˜o) se ela for simultaneamente injetora e
sobrejetora.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 5 / 8
Func¸a˜o
Composic¸a˜o de func¸o˜es
Func¸a˜o composta
Dadas uma func¸a˜o f : A→ B e uma func¸a˜o g : B → C , a func¸a˜o
composta g ◦ f e´ a func¸a˜o de A→ C g ◦ f := g(f (x)).
Teorema
A composic¸a˜o de duas func¸o˜es bijetoras e´ uma func¸a˜o bijetora.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 6 / 8
Func¸a˜o
Composic¸a˜o de func¸o˜es
Func¸a˜o composta
Dadas uma func¸a˜o f : A→ B e uma func¸a˜o g : B → C , a func¸a˜o
composta g ◦ f e´ a func¸a˜o de A→ C g ◦ f := g(f (x)).
Teorema
A composic¸a˜o de duas func¸o˜es bijetoras e´ uma func¸a˜o bijetora.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 6 / 8
Func¸a˜o
Func¸a˜o inversa
Definic¸a˜o
Dada uma func¸a˜o f : A→ B, se existir uma func¸a˜o g : B → A, tal que
∀x ∈ A, g(f (x) = x e ∀x ′ ∈ B, f (g(x) = x enta˜o g e´ chamada de func¸a˜o
inversa de f , denotada por f −1.
Teorema
Dada uma func¸a˜o f : A→ B, existe a func¸a˜o f −1 se e somente se f for
bijetora.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 7 / 8
Func¸a˜o
Func¸a˜o inversa
Definic¸a˜o
Dada uma func¸a˜o f : A→ B, se existir uma func¸a˜o g : B → A, tal que
∀x ∈ A, g(f (x) = x e ∀x ′ ∈ B, f (g(x) = x enta˜o g e´ chamada de func¸a˜o
inversa de f , denotada por f −1.
Teorema
Dada uma func¸a˜o f : A→ B, existe a func¸a˜o f −1 se e somente se f for
bijetora.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 7 / 8
Func¸a˜o
Permutac¸a˜o
Definic¸a˜o
Uma func¸a˜o f : A→ A bijetora e´ chamada de permutac¸a˜o de A.
Teorema
Ha´ |A|! permutac¸o˜es poss´ıveis de um conjunto A.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 8 / 8
Func¸a˜o
Permutac¸a˜o
Definic¸a˜o
Uma func¸a˜o f : A→ A bijetora e´ chamada de permutac¸a˜o de A.
Teorema
Ha´ |A|! permutac¸o˜es poss´ıveis de um conjunto A.
Luis Antonio Kowada (UFF-IC) Fundamentos Matema´ticos para Computac¸a˜o 2017-2 8 / 8
	Relações e Funções