apostila de estruturas algébricas

Prévia do material em texto

Pontifícia Universidade Católica do Rio Grande do Sul
Faculdade de Matemática - Departamento de Matemática
Este material é de apoio para a disciplina de Estruturas Algébricas, oferecida ao curso de Informática da Pontifícia
Universidade Católica do Rio Grande do Sul, não tendo a pretensão de esgotar os assuntos aqui abordados, mas sim de
enfocar os aspectos importantes para o uso em Informática.
O relato de quaisquer erros ou outras sugestões e criticas construtivas será sempre bem-vindo.
Não alterar este material!
EEssttrruuttuurraass AAllggéébbrriiccaass
© Prof. M.Sc. Guilherme Luís Roëhe Vaccaro
e-mail: vaccaro@mat.pucrs.br
Prof. M.Sc. Eliane Allgayer Canto
Versão deste material: 1.3.5
Porto Alegre, agosto de 2001.
Estruturas Algébricas i
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
SSuummáárriioo
1 Relações de A em B ____________________________________________________________1
1.1 Relação de A em B__________________________________________________________2
1.1.1 Definição ______________________________________________________________2
1.1.2 Notação _______________________________________________________________2
1.1.3 Comentários ___________________________________________________________2
1.2 Exemplos _________________________________________________________________3
1.2.1 Exemplos Intuitivos ______________________________________________________3
1.2.2 Exemplos Conceituais____________________________________________________3
1.2.3 Mais um Exemplo Importante ______________________________________________3
1.3 Domínio e Imagem de uma Relação ____________________________________________3
1.3.1 Definições _____________________________________________________________3
1.3.2 Comentários ___________________________________________________________4
1.4 Exemplos _________________________________________________________________4
1.5 Representação Gráfica de Relações ____________________________________________4
1.5.1 Exemplos com Conjuntos Discretos _________________________________________4
1.5.2 Exemplos com Conjuntos Contínuos ________________________________________5
1.5.3 Exemplos com Conjuntos Discretos e Contínuos_______________________________5
1.5.4 Um Exemplo Importante __________________________________________________7
1.6 Operações Com Relações ____________________________________________________7
1.7 Um Exemplo Importante______________________________________________________7
2 Funções ______________________________________________________________________9
2.1 Comentários Iniciais _________________________________________________________9
2.2 O Conceito de Função _______________________________________________________9
2.2.1 Formalização do Conceito de Função ______________________________________10
2.2.2 Observação___________________________________________________________10
2.2.3 Notação de Função_____________________________________________________11
2.3 Resumo _________________________________________________________________11
2.4 Exemplos ________________________________________________________________11
2.4.1 Exemplo 1 ____________________________________________________________11
2.4.2 Exemplo 2 ____________________________________________________________11
2.4.3 Exemplo 3 ____________________________________________________________12
2.4.4 Exemplo 4 ____________________________________________________________12
2.4.5 Exemplo 5 ____________________________________________________________13
2.5 Domínio, Imagem e Contradomínio de uma Função _______________________________13
2.5.1 Definições ____________________________________________________________13
2.5.2 Observações __________________________________________________________14
Estruturas Algébricas ii
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
2.5.3 Funções Reais e Funções de Variável Real__________________________________14
2.5.4 Maior domínio de uma função_____________________________________________15
2.5.5 Determinação da Imagem de uma Função na Prática __________________________16
2.6 Gráfico de uma Função _____________________________________________________17
2.6.1 Definição _____________________________________________________________17
2.6.2 Exemplos_____________________________________________________________17
2.6.3 Observação: Gráfico x Representação Gráfica _______________________________17
2.7 Funções Inversíveis ________________________________________________________17
2.7.1 Um Exemplo Inicial _____________________________________________________17
2.7.2 Funções Injetoras (1 Para 1)______________________________________________20
2.7.3 Exemplos_____________________________________________________________20
2.7.4 Teorema _____________________________________________________________22
2.7.5 Funções Sobrejetoras ___________________________________________________23
2.7.6 Exemplos_____________________________________________________________23
2.7.7 Funções Bijetoras ______________________________________________________24
2.7.8 Exemplos_____________________________________________________________25
2.7.9 Um Teorema Importante _________________________________________________27
3 Relações em A _______________________________________________________________29
3.1 Definição_________________________________________________________________29
3.2 Exemplos ________________________________________________________________29
3.2.1 Um Exemplo Intuitivo ___________________________________________________29
3.2.2 Outros Exemplos Intuitivos _______________________________________________30
3.2.3 Exemplos Conceituais___________________________________________________30
3.2.4 Outro Exemplo Conceitual _______________________________________________30
3.2.5 Mais um Exemplo Importante _____________________________________________30
3.2.6 Um Último Exemplo ____________________________________________________31
3.3 Propriedades das Relações em A _____________________________________________31
3.3.1 Reflexividade__________________________________________________________31
3.3.2 Exemplos Intuitivos _____________________________________________________31
3.3.3 Irreflexividade _________________________________________________________34
3.3.4 Transitividade _________________________________________________________37
3.3.5 Simetria ______________________________________________________________40
3.3.6 Assimetria ____________________________________________________________43
3.3.7 Anti-Simetria __________________________________________________________45
3.3.8 Uma Observação Importante!_____________________________________________49
3.3.9 Exercícios ____________________________________________________________49
4 Relações de Equivalência em A __________________________________________________50
4.1 Definição_________________________________________________________________50
4.2 Exemplos ________________________________________________________________50
Estruturas Algébricas iii
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
4.2.1 Um Exemplo Intuitivo ___________________________________________________50
4.2.2 Um Exemplo Fundamental _______________________________________________50
4.2.3 Outro Exemplo Importante _______________________________________________51
4.2.4 Um Último Exemplo ____________________________________________________52
4.3 Classes de Equivalência ____________________________________________________52
4.3.1 Definição de Classe de Equivalência _______________________________________52
4.3.2 Exemplo _____________________________________________________________52
4.3.3 Exemplo _____________________________________________________________535 Relações de Ordem em A _______________________________________________________55
5.1 Definição_________________________________________________________________55
5.2 Exemplos ________________________________________________________________55
5.2.1 Um Exemplo Intuitivo ___________________________________________________55
5.2.2 Outro Exemplo Intuitivo__________________________________________________56
5.2.3 Exemplos Importantes __________________________________________________56
5.2.4 Outro Exemplo Importante _______________________________________________57
5.3 Ordem Total x Ordem Parcial_________________________________________________57
5.3.1 Definições ____________________________________________________________57
5.3.2 Exemplos_____________________________________________________________58
5.3.3 Mais Um Exemplo ______________________________________________________58
5.4 Diagrama de Hasse: Representação Gráfica de Relações de Ordem em Conjuntos
Discretos ______________________________________________________________________59
5.4.1 Exemplo _____________________________________________________________59
5.4.2 Exemplo _____________________________________________________________59
5.4.3 Exemplo _____________________________________________________________60
5.4.4 Exemplo _____________________________________________________________60
5.4.5 Exemplo _____________________________________________________________60
5.4.6 Exemplo _____________________________________________________________60
5.4.7 Exemplo _____________________________________________________________61
5.4.8 Observação: Tabela Booleana ____________________________________________61
6 Elementos Notáveis em Conjuntos Ordenados ______________________________________62
6.1 Observação Básica ________________________________________________________62
6.2 Elementos Notáveis ________________________________________________________62
6.2.1 Cotas Inferiores e Cotas Superiores de M ___________________________________62
6.2.2 Mínimo e Máximo de M__________________________________________________63
6.2.3 Ínfimo e Supremo de M__________________________________________________64
6.3 Exemplos ________________________________________________________________65
Exemplo: Visualização dos Conceitos de Elementos Notáveis Através do Diagrama de
Hasse em Conjuntos Discretos ___________________________________________________65
6.3.2 Exemplo: Ordem Natural_________________________________________________66
6.3.3 Exemplo: Ordem Oposta_________________________________________________66
Estruturas Algébricas iv
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
6.3.4 Exercício _____________________________________________________________67
7 Reticulados (Lattices) __________________________________________________________68
7.1 Definição_________________________________________________________________68
7.1.1 Observações __________________________________________________________68
7.1.2 Exemplo Inicial ________________________________________________________68
7.1.3 Tabela de Ínfimos e Tabela de Supremos ___________________________________69
7.1.4 Exemplos_____________________________________________________________69
7.1.5 Observação Importante__________________________________________________70
7.1.6 Exemplos_____________________________________________________________71
7.1.7 Exercícios Importantes __________________________________________________72
7.2 Notação de Supremo e de Ínfimo em Reticulados_________________________________73
7.3 Propriedades Fundamentais dos Reticulados ____________________________________73
7.3.1 Lema (Propriedades Básicas, versão notação intuitiva)_________________________73
7.3.2 Teorema (Propriedades Fundamentais, versão notação intuitiva) _________________74
7.3.3 Lema (Propriedades Básicas, versão notação usual) __________________________76
7.3.4 Teorema (Propriedades Fundamentais, versão notação usual)___________________76
7.4 Definição de Reticulado Através de Propriedades_________________________________77
7.5 Outras Classificações para Reticulados_________________________________________77
7.5.1 Reticulados Limitados ___________________________________________________77
7.5.2 Reticulados Distributivos_________________________________________________79
7.5.3 Reticulados Complementados ____________________________________________82
7.5.4 Reticulados Unicamente Complementados __________________________________82
8 Álgebras Booleanas____________________________________________________________85
8.1 Definição_________________________________________________________________85
8.1.1 Observações __________________________________________________________85
8.1.2 Exemplo _____________________________________________________________85
8.1.3 Exemplo _____________________________________________________________85
8.2 Propriedades das Álgebras Booleanas _________________________________________86
8.3 Exemplos de Aplicações das Álgebras Booleanas em Informática____________________87
8.3.1 Exemplo: Álgebra dos Comutadores _______________________________________87
8.3.2 Exemplo: Álgebra das Proposições ________________________________________87
8.3.3 Exemplo: Álgebra dos Conjuntos __________________________________________88
8.3.4 Exemplo: Simplificação de Polinômios Booleanos _____________________________89
9 Exercícios ___________________________________________________________________92
9.1 Relações de A em B________________________________________________________92
9.2 Funções _________________________________________________________________93
9.3 Relações em A ____________________________________________________________96
9.4 Elementos Notáveis em Conjuntos Ordenados ___________________________________99
10 Respostas dos Exercícios ____________________________________________________103
Estruturas Algébricas v
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
10.1 Relações de A em B_______________________________________________________103
10.2 Funções ________________________________________________________________106
10.3 Relações em A ___________________________________________________________112
10.4 Elementos Notáveis, Reticulados & Álgebras Booleanas __________________________122
Estruturas Algébricas 1
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
11 RReellaaççõõeess ddee AA eemm BB
Uma relação, em termos práticos, é uma forma de associação de entidades através de um certo
critério. Os termos “relação” ou “relacionamento” são comumente utilizados entre pessoas para
indicar algum tipo de “ligação”. Exemplos comuns de sinônimos do termo “relação” entre pessoas são
“falar”, “ser amigo” ou “namorar”. Poderíamos sistematizar estes exemplos da seguinte forma:
§ a pessoa “x” relaciona-se com a pessoa “y” se e somente se “x fala com y”
§ a pessoa “x” relaciona-se com a pessoa “y” se e somente se “x é amiga com y”
§ a pessoa “x” relaciona-se com a pessoa “y” se e somente se “x namora com y”
Observe-se, no entanto, que cada frase acima representa uma relação diferente. Isto porque “falar” e
“namorar” não são, obviamente, a mesma coisa. Isto é: o critério que define a relação mudou!
Observe-se ainda que, dependendo do critério que utilizamos para definir uma relação, certas
associações podem existir, ou não. Por exemplo, se Pedro é amigo de João e estivermos associando
pessoas através da relação “x é amiga de y” então Pedro e João estarão relacionados. No entanto, se
a relação fosse “x namora com y” dificilmente diríamos que Pedro e João estariam relacionados...
No entanto, uma relação pode ser muito mais genérica do que usada comumente. O conceitode
relação compreende qualquer tipo de associação entre entidades, tais como:
§ pessoas;
§ objetos;
§ entes matemáticos, como números, conjuntos e funções;
§ etc.
Um cuidado imprescindível, porém, é o de que sempre relacionemos tais entes através de um critério
bem definido. Isto significa, por exemplo, que não teria sentido criarmos relações como estas:
§ a pessoa “x” relaciona-se com o número “y” se e somente se “x come y”;
§ o objeto “x” relaciona-se com a pessoa “y” se e somente se “x é dono de y”.
No entanto, fariam sentido relações como estas:
§ a pessoa “x” relaciona-se com o número “y” se e somente se “y é o número de matrícula de x”;
§ o objeto “x” relaciona-se com a pessoa “y” se e somente se “x é usado por y”.
Cuidado!
Dizer, por exemplo, “x é dono de y” não é o mesmo que dizer “y é dono de x”. A associação que
fazemos está vinculada aos tipos de entes com os quais estamos lidando. No exemplo em questão, x
é um objeto e y é uma pessoa. Assim, “x é dono de y” não tem sentido pois um objeto não pode ser
dono de uma pessoa. No entanto, “y é dono de x” tem sentido e poderá ser uma proposição
verdadeira ou falsa, dependendo de quem seja “y” e de qual objeto seja “x”. Mesmo assim, se
representarmos por “y” uma pessoa e por “x” um objeto, as relações “x é dono de y” e “y é dono de x”
não serão a mesma!
Ainda: observe que uma relação é sempre uma associação entre elementos de um certo tipo com
elementos de um outro (eventualmente do mesmo) tipo. Nos exemplos acima estaríamos
relacionando:
§ pessoas com pessoas
§ pessoas com números
Estruturas Algébricas 2
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
§ objetos com pessoas
Ou seja, uma relação que associa pessoas com objetos é obrigatoriamente diferente de uma relação
que associa objetos com pessoas.
A seguir, colocaremos um pouco de Matemática neste conceito...
11..11 RReellaaççããoo ddee AA eemm BB
11..11..11 DDeeffiinniiççããoo
Dados A e B conjuntos, chama-se de relação de A em B, qualquer subconjunto do produto cartesiano
A x B.
Em notação lógica:
R é relação de A em B Û R Í A x B
Observações:
§ O primeiro conjunto do produto cartesiano, A, é denominado conjunto de origem da relação;
§ O segundo conjunto do produto cartesiano, B, é denominado conjunto de destino (ou
contradomínio) da relação.
11..11..22 NNoottaaççããoo
Para representar a proposição “x relaciona-se com y pela relação R” escreve-se x R y ou ( x, y ) Î R.
Assim:
x relaciona-se com y por R Û x R y Û ( x, y ) Î R
11..11..33 CCoommeennttáárriiooss
Uma relação, em termos algébricos, pode ser compreendida de duas formas:
§ Uma relação é uma forma de associação entre elementos de um conjunto com elementos
de outro conjunto:
Esta é a interpretação mais usual na prática, e que nos permite sistematizar e organizar a forma
como os elementos de um conjunto relacionam-se com elementos de outro conjunto
§ Uma relação de A em B é um subconjunto de um produto cartesiano A x B:
Esta compreensão dá fundamento matemático ao conceito de relação. Podemos representar a
associação de elementos de um conjunto A com elementos de um conjunto B através de um par
ordenado, onde a primeira componente do par será destinada a um elemento do conjunto A e a
segunda componente do par, a um elemento do conjunto B. Assim, uma relação de A em B é
formada por associações do tipo
( elemento de A , elemento de B )
Ora, pares ordenados deste tipo são obtidos através do produto cartesiano de A com B. Como
sabemos, A x B é o conjunto formado por TODOS os pares da forma
( elemento de A , elemento de B )
Uma relação é a seleção de ALGUNS (eventualmente TODOS) destes pares segundo algum
critério.
Estruturas Algébricas 3
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
11..22 EExxeemmppllooss
11..22..11 EExxeemmppllooss IInnttuuiittiivvooss
Sejam: A : conjunto das pessoas
B : conjunto dos objetos
Então podem-se definir:
R Í A x B, x R y Û x possui y
S Í A x B, x S y Û x usa y
T Í A x B, x T y Û x não possui y
11..22..22 EExxeemmppllooss CCoonncceeiittuuaaiiss
Sejam: A = { 1, 2, 3 }
B = { 0, 1 }
Então podem-se definir, por exemplo, as seguintes relações:
R Í A x B, x R y Û x = y +1
S Í A x B, x S y Û (x ¹ y) Ù (y < 1)
T Í A x B, x T y Û x + y > 0
W Í A x B, x W y Û x + y < 0
Com efeito, estas relações podem ser representadas na forma de conjuntos de pares ordenados:
R = { ( x, y ) / x = y + 1 } = { ( 1, 0 ), ( 2, 1 ) }
S = { ( x, y ) / (x ¹ y) Ù (y < 1) } = { ( 1, 0 ), ( 2, 0 ), ( 3, 0 ) }
T = { ( x, y ) / x + y > 0 } = { ( 1, 0 ), ( 1, 1 ), ( 2, 0 ), ( 2, 1 ), ( 3, 0 ), ( 3, 1 ) }
W = { ( x, y ) / x + y < 0 } = Æ
11..22..33 MMaaiiss uumm EExxeemmpplloo IImmppoorrttaannttee
Todas as funções de A em B são relações de A em B. Isto porque funções são relações muito
especiais que associam, para cada x Î A, um único y Î B.
11..33 DDoommíínniioo ee IImmaaggeemm ddee uummaa RReellaaççããoo
Partindo da concepção de relação como uma representação da associação de elementos de um
conjunto com elementos de outro conjunto, é desejável distinguir quais elementos, em cada conjunto,
foram efetivamente associados. Esta distinção pode ser obtida através dos conceitos de Domínio,
Imagem e Contradomínio de uma relação.
11..33..11 DDeeffiinniiççõõeess
Seja R Í A x B (isto é, R é uma relação de A em B). Então definem-se:
Dom(R) = { x Î A / ( $ y Î B )( ( x, y ) Î R ) }
Im(R) = { y Î B / ( $ x Î A )( ( x, y ) Î R ) }
Estruturas Algébricas 4
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
11..33..22 CCoommeennttáárriiooss
O domínio da relação R Í A x B representa o conjunto dos elementos de A que efetivamente foram
associados a algum elemento de B e que, portanto constam em um ou mais pares ordenados da
relação. Da mesma forma, a imagem da relação R Í A x B representa o conjunto dos elementos de B
que efetivamente foram associados a algum elemento de A.
11..44 EExxeemmppllooss
Nos exemplos apresentados anteriormente, temos:
§ Dom(R) = { 1, 2 } Im(R) = { 0, 1 }
§ Dom(S) = { 1, 2, 3 } Im(S) = { 0 }
§ Dom(T) = { 1, 2, 3 } Im(T) = { 0, 1 }
§ Dom(W) = Æ Im(W) = Æ
11..55 RReepprreesseennttaaççããoo GGrrááffiiccaa ddee RReellaaççõõeess
Uma relação pode ser representada através de um gráfico cartesiano, onde são adotadas as
seguintes convenções:
§ O conjunto de origem da relação é representado no eixo horizontal
§ O conjunto de destino da relação é representado no eixo vertical
11..55..11 EExxeemmppllooss ccoomm CCoonnjjuunnttooss DDiissccrreettooss
Sejam A = { -1, 0, 1 }
B = { 2, 4, 6 }
Sejam as relações:
R = A x B
S Í A x B, x S y Û 4x +y > 0
T Í A x B, x T y Û y = 4+2x
W Í A x B, x W y Û y £ 4+2x
As representações gráficas das relações acima são:
Estruturas Algébricas 5
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
11..55..22 EExxeemmppllooss ccoomm CCoonnjjuunnttooss CCoonnttíínnuuooss
Sejam A = [ -1, 1 ]
B = [ 2, 6 ]
Para comparação usaremos as mesmas relações do exemplo anterior:
R = A x B
S Í A x B, x S y Û 4x +y > 0
T Í A x B, x T y Û y = 4+2x
W Í A x B, x W y Û y £ 4+2x
Neste caso, as representações gráficas das relações acima ficam:
11..55..33 EExxeemmppllooss ccoomm CCoonnjjuunnttooss DDiissccrreettooss ee CCoonnttíínnuuooss
Sejam A = { -1, 0, 1 }
B = [ 2, 6 ]
Para comparação usaremos as mesmas relações do exemplo anterior:
R = A x B
S Í A x B, x S y Û 4x +y > 0
Estruturas Algébricas 6
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
T Í A x B, x T y Û y = 4+2x
W Í A x B, x W y Û y £ 4+2x
Neste caso, as representações gráficasdas relações acima ficam:
Observe o que aconteceria se definíssemos relações com as mesmas leis, mas de B em A:
R* = B x A
S* Í B x A, y S* x Û 4x +y > 0
T* Í B x A, y T* x Û y = 4+2x
W* Í B x A, y W* x Û y £ 4+2x
Nesta situação os gráficos das relações seriam:
Estruturas Algébricas 7
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Ou seja, as relações são diferentes!
11..55..44 UUmm EExxeemmpplloo IImmppoorrttaannttee
Seja a relação R definida em R x R por x R y Û y2 = x2. A representação gráfica desta relação é dada
pelo gráfico a seguir:
Note, no entanto, que seu gráfico sugere uma outra definição para
R.
Com efeito, podemos descrever a mesma relação através da
proposição
( y = x ) Ú ( y = – x ).
Isto é verdadeiro porque
y2 = x2 Û ( y = x ) Ú ( y = – x ).
Assim,
x R y Û y2 = x2.
11..66 OOppeerraaççõõeess CCoomm RReellaaççõõeess
Da concepção de que uma relação é um subconjunto de um produto cartesiano (e, portanto, um
conjunto!), devemos observar que todos os resultados válidos em teoria de conjuntos são também
válidos para as relações. Em particular, podemos criar novas relações a partir das operações de:
§ união de conjuntos ( È )
§ interseção de conjuntos ( Ç )
§ diferença de conjuntos ( - )
§ complementação de conjuntos ( ‘ )
Alguns cuidados devem ser tomados:
1. O conjunto universo, no caso de operações com relações de A em B, é o produto cartesiano
A x B;
2. Como no caso de conjuntos quaisquer, somente podem ser operadas relações dentro de um
mesmo conjunto universo; ou seja, duas relações somente podem ser operadas se ambas forem
de A em B, por exemplo.
Isto significa que, dadas duas relações de A em B, denominadas R e S temos que:
União: ( R Í A x B ) Ù ( S Í A x B ) Û ( R È S Í A x B )
Interseção: ( R Í A x B ) Ù ( S Í A x B ) Û ( R Ç S Í A x B )
Diferença: ( R Í A x B ) Ù ( S Í A x B ) Û ( R - S Í A x B )
Complementação: ( R Í A x B ) Û ( R’ Í A x B )
Observe-se que RÈS, RÇS, R–S e R’ também são relações de A em B!
11..77 UUmm EExxeemmpplloo IImmppoorrttaannttee
De modo a elucidar melhor os conceitos vistos acima, observemos o seguinte exemplo:
Estruturas Algébricas 8
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Sejam as relações
R Í R x R, x R y Û x2 + y2 £ 1
S Í R x R, x S y Û x £ y
Suas representações gráficas são:
Então definem-se as relações, de R em R:
RÈS Í R x R, x RÈS y Û (x2 + y2 £ 1 ) Ú ( x £ y )
RÇS Í R x R, x RÇS y Û (x2 + y2 £ 1 ) Ù ( x £ y )
S–R Í R x R, x S–R y Û (x2 + y2 > 1 ) Ù ( x £ y )
R’ Í R x R, x R’ y Û x2 + y2 > 1
Os gráficos das relações definidas pelas operações entre R e S são:
Estruturas Algébricas 9
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
22 FFuunnççõõeess
22..11 CCoommeennttáárriiooss IInniicciiaaiiss
O conceito de função é fundamental em muitas áreas do conhecimento. Na verdade, muitas
atividades e instrumentos são baseados no conceito de função. Exemplos comuns são
computadores, bons softwares, calculadoras, interruptores de luz, cronômetros, etc.
Há diversos aspectos importantes no conceito de função:
§ Função é uma relação. Isto significa que uma função deve ser entendida como um tipo de
associação entre elementos de um ou mais conjuntos e que segue a uma lei específica. Além
disso, isto significa que todos os resultados conhecidos para relações são válidos para funções.
§ Uma das principais características de uma função é sua capacidade de representar
transformações, ou seja, uma função pode ser entendida como um mecanismo que, sob certas
condições predefinidas, transforma entradas em saídas. Na realidade, esta é uma de suas
principais utilidades, uma vez que permite que o efeito da transformação de um grande número
de dados seja compreendido mais facilmente.
22..22 OO CCoonncceeiittoo ddee FFuunnççããoo
De modo geral, designamos pelo nome de “função” uma relação f que transforma, de forma única,
elementos de um conjunto A em elementos de um conjunto B.
Para que esta correspondência seja bem determinada é necessário que se defina qual é a condição
de “bom funcionamento” de uma função:
A cada elemento do conjunto de entradas deve estar relacionado um único elemento do conjunto de
saídas.
Vamos escrever esta condição de bom funcionamento em linguagem lógica:
( " x Î A ) ( $! y Î B ) ( y = f ( x ) )
Uma análise mais detalhada de tal condição de “bom funcionamento” permite-nos dividi-la em duas
idéias fundamentais:
1 – Para cada entrada x deve existir pelo menos uma resposta y associada.
2 – Para cada entrada x não podem existir duas respostas diferentes
A
input
B
output
Conjunto de Entradas Conjunto de Saídas
Estruturas Algébricas 10
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Na prática as seguintes situações poderiam ser encontradas:
§ Somente uma saída para cada entrada: Este caso é
representativo de uma função, pois cumpre as condições de
“bom funcionamento” descritas anteriormente.
§ Uma saída para múltiplas entradas: Note que este caso
também representa uma função. As restrições de “bom
funcionamento” indicam que cada entrada tem de ter
somente uma resposta associada, mas não impedem que
várias entradas resultem na mesma resposta!
No entanto, as situações que serão descritas a seguir NÃO representam funções!
§ Somente uma entrada associada a diversas saídas
§ Várias entradas associadas simultaneamente a várias
saídas
Estes casos obviamente contradizem a condição de “bom funcionamento”. Isto porque não é
possível determinar o que acontecerá (qual a resposta que será dada)! Pode-se compreender
melhor porque este comportamento não é interessante através dos seguintes exemplos:
Imagine que você guia um automóvel. Que tal se, ao girar o volante para a direita,
você nunca tivesse certeza se o carro irá neste sentido?!?
Imagine que você utiliza um determinado software. Que tal se, ao repetir
a mesma operação, você nunca souber se o software funcionará ou
travará seu computador?!?
22..22..11 FFoorrmmaalliizzaaççããoo ddoo CCoonncceeiittoo ddee FFuunnççããoo
Formalmente, pode-se escrever:
Sejam A e B conjuntos. Dizemos que f : A ® B é uma função de A em B se e só se:
I. ( " x Î A ) ( $ y Î B )( y = f(x) ) (condição de existência)
II. ( " x1, x2 Î A )( x1 = x2 ® f(x1) = f (x2) ) (condição de unicidade)
22..22..22 OObbsseerrvvaaççããoo
A condição de unicidade pode ser escrita a partir de sua proposição contrapositiva:
( " x1, x2 Î A )( f(x1) ¹ f (x2) ® x1 ¹ x2)
Como resultado, podemos escrever:
Sejam A e B conjuntos. Dizemos que f : A ® B é uma função de A em B se e só se:
I. ( " x Î A )( $ y Î B )( y = f(x) )
II. ( " x1, x2 Î A )( f(x1) ¹ f (x2) ® x1 ¹ x2)
Estruturas Algébricas 11
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
22..22..33 NNoottaaççããoo ddee FFuunnççããoo
Ao definirmos uma função – e verificarmos que as condições de “bom funcionamento” são
satisfeitas – podemos adotar a seguinte notação compacta:
)x(fyx
BA:f
=
®
a
que deve ser lida da seguinte forma:
esta é a função f, que relaciona elementos “x” do conjunto A (entradas) com elementos “y” do
conjunto B (respostas) através da lei y = f(x).
22..33 RReessuummoo
)x(fyx
BA:f
=
®
a
Û f é função de A em B Û
Û ( " x Î A )( $! x Î B )( y = f(x) ) Û
Û ( " x Î A )( $ y Î B )( y = f(x) ) Ù ( " x1, x2 Î A )( x1 = x2 ® f(x1) = f(x2) ) Û
Û ( " x Î A )( $ y Î B )( y = f(x) ) Ù ( " x1, x2 Î A )( f(x1) ¹ f(x2) ® x1 ¹ x2 )
22..44 EExxeemmppllooss
22..44..11 EExxeemmpplloo 11
Sejam P: conjunto de países, C: conjunto de cidades.
Podemos definir uma função f: P ® C através da lei “f(x) éa capital política de x”.
Isto pode ser escrito da seguinte forma: 
 xde política capital a é )x(fx
CP:f
a
®
Esta relação é realmente uma função porque cada país só pode ter uma capital política.
22..44..22 EExxeemmpplloo 22
2xyx
:f
=
®
a
RR
 é função.
Solução:
Para verificar esta afirmação é necessário que sejam verdadeiras as duas condições descritas
anteriormente.
1a Parte: Condição de existência: ( " x Î A )( $ y Î B )( y = f(x) )
Que, neste caso deve ser escrita como: ( " x Î R )( $ y Î R )( y = x2 )
Prova: Seja x Î R.
x Î R Þ x2 Î R.
Chamando de y a expressão x2, temos:
y = x2 Þ y Î R.
Estruturas Algébricas 12
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Logo, ( " x Î R )( $ y Î R )( y = x2 ) Û V
2a Parte: Condição de unicidade: ( " x1, x2 Î A )( x1 = x2 ® f(x1) = f(x2) )
Que, neste caso deve ser escrita como: ( " x1, x2 Î R )( x1 = x2 ® x1
2 = x2
2 )
Prova: Sejam x1, x2 Î R tais que x1 = x2
Então: x1
2 = x1.x1 = x2 .x2 = x2
2
Logo, x1 = x2 Þ x1
2 = x2
2
Logo, ( " x1, x2 Î R )( x1 = x2 Þ x1
2 = x2
2 ).
Conclusão final: Como valem as condições de unicidade e existência, então 2xyx
:f
=
®
a
RR
 é função.
22..44..33 EExxeemmpplloo 33
Verifique se f: R ® R definida por xy = é função.
Solução:
1a Parte: Condição de existência: ( " x Î A )( $ y Î B )( y = f(x) )
Que, neste caso deve ser escrita como: ( " x Î R )( $ y Î R )( xy = )
Esta proposição é falsa, pois, por exemplo,
($ x Î R)( x = -1 )( 1- Ï R ) Û ($ x Î R)( x = -1 )( $/ y Î R )( xy = )
Logo, não vale a condição de existência.
Conclusão final: Como não vale a condição de existência, então f: R ® R definida por xy = não é
função.
22..44..44 EExxeemmpplloo 44
xyx
);0[:f
=
®+¥
a
R
 é função.
Solução:
1a Parte: Condição de existência: ( " x Î A )( $ y Î B )( y = f(x) )
Que, neste caso deve ser escrita como: ( " x Î [ 0; +¥ ) )( $ y Î R )( xy = )
Prova: Seja x Î [ 0; +¥ ).
x Î [ 0; +¥ ) Þ x ³ 0 Û x Î R.
Chamando de y a expressão x , temos:
y = x Þ y Î R.
Logo, ( " x Î R )( $ y Î R )( y = x ) Û V
2a Parte: Condição de unicidade: ( " x1, x2 Î A )( x1 = x2 ® f(x1) = f(x2) )
Que, neste caso deve ser escrita como: ( " x1, x2 Î R )( x1 = x2 ® 21 xx = )
Ou, melhor ainda, como: ( " x1, x2 Î R )( 21 xx ¹ ® x1 ¹ x2 )
Estruturas Algébricas 13
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Prova: Sejam x1, x2 Î R tais que 21 xx ¹
Então: x1 = 11 x.x ¹ 22 x.x = x2 , pois 1x ³ 0 Ù 2x ³ 0.
Logo, 21 xx ¹ Þ x1 ¹ x2.
Logo, ( " x1, x2 Î R )( 21 xx ¹ Þ x1 ¹ x2 ).
Conclusão final: Como valem ambas as condições, então f: R ® R definida por xy = é função.
22..44..55 EExxeemmpplloo 55
Verifique se 1yx 22 =+ , x Î [ -1; 1 ], y Î R é função.
Solução:
Note que a expressão 1yx 22 =+ não está na forma adequada para ser utilizada nestes raciocínios.
Portanto, é necessário primeiro transformá-la, isolando y:
1yx 22 =+ Û 22 x1y -= Û ( 2x1y -= ) Ú ( 2x1y --= ).
Pela proposição acima, já torna-se claro que teremos problemas, pois como y Î R, será igualmente
válido que assuma valores tanto positivos como negativos. Isto nos faz desconfiar que a condição de
unicidade falhará... Então, para poupar trabalho, começaremos por ela:
1a Parte: Condição de unicidade: ( " x1, x2 Î A )( x1 = x2 ® f(x1) = f(x2) )
Esta proposição é falsa, pois, por exemplo, escolhendo x1 = x2 = 0, poderíamos ter:
x1 = 0 Þ 101x1y
2
1
2 =-=-= Þ 11y ==
x2 = 0 Þ 101x1y
2
2
2 =-=-= Þ 11y -=-=
Logo, ( $ x1, x2 Î [ -1; 1 ] )( x1 = x2 = 0 )( x1 = x2 Ù f(x1) ¹ f(x2) ).
Conclusão final: Como não vale a condição de unicidade, então 1yx 22 =+ , x Î [ -1; 1 ], y Î R não é
função.
22..55 DDoommíínniioo,, IImmaaggeemm ee CCoonnttrraaddoommíínniioo ddee uummaa FFuunnççããoo
22..55..11 DDeeffiinniiççõõeess
Seja f uma relação de A em B. Como visto anteriormente, as definições de domínio, imagem e
contradomínio de f serão dadas por:
Dom(f) = { x / x Î A Ù ( $ y Î B )( y = f(x) ) }
Im(f) = { y / y Î B Ù ( $ xÎ A )( y = f(x) ) } =
= { f(x) Î B / x Î A }
C(f) = B
Como toda a função também é uma relação (só que é um tipo muito especial de relação, que cumpre
as condições de “bom funcionamento” vistas anteriormente), as definições acima também podem ser
utilizadas para a determinação de seu domínio, de sua imagem e de seu contradomínio.
Estruturas Algébricas 14
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
22..55..22 OObbsseerrvvaaççõõeess
§ Note que estas definições são “cópia” das definições utilizadas para relações.
§ Na realidade, no caso de uma função, para se poder escrever a notação f: A ® B, deve-se ter
certeza de que
Dom(f) = A.
Por quê? Vejamos:
Para f: A ® B ser função , deve valer que
( " x Î A ) ( $ y Î B ) ( y = f ( x ) ) Ù ( " x1 , x2 Î A )( x1 = x2 ® f( x1 ) = f( x2 ) )
Note que a primeira parte da proposição acima diz que ( " x Î A )( $ y Î B )( y = f ( x ) ).
Isto significa que se f é função, então ( " x Î A )( $ y Î B )( y = f ( x ) ) Û V
Mas esta também é a condição que é usada na definição do domínio que foi apresentada acima:
Dom(f) = { x / x Î A Ù ( $ y Î B )( y = f( x ) ) }.
Então Dom(f) = A.
§ Note que a observação anterior só é válida para o domínio de uma função! Ou seja:
Nem sempre será verdade que Im(f) = B!!!
§ No entanto, sempre será verdade que
Im(f) Í B
Ou ainda
Im(f) Í C(f)
§ Cabe ainda notar que outra forma de definir a imagem de uma função seria escrever
Im(f) = { f(x) / xÎ A }
22..55..33 FFuunnççõõeess RReeaaiiss ee FFuunnççõõeess ddee VVaarriiáávveell RReeaall
Especial atenção é necessária a certos detalhes da nomenclatura de funções. Um destes detalhes
que comumente passa desapercebido à primeira vista é a diferença entre as denominações “função
real” e “função de variável real”:
§ função de variável real é toda aquela cuja variável de entrada é um número real. Por exemplo,
são funções de variável real:
f: R ® R, f(x) = x2
f: [ 0; +¥ ) ® R, f(x) = ln(x)
f: R ® [ -1; 1 ], f(x) = sen(x)
f: R ® Z, f(x) = ëxû
f: R ® I, f(x) = 3 + i.x (onde i = 1- )
§ função real é toda aquela cuja resposta é sempre um número real. Por exemplo, são funções
reais:
f: R ® R, f(x) = x2
f: [ 0; +¥ ) ® R, f(x) = ln(x)
f: R ® [ -1; 1 ], f(x) = sen(x)
Da mesma forma que se definem funções reais e funções de variável real pode-se definir “funções
inteiras” e “funções de variável inteira”, etc. Por exemplo:
Estruturas Algébricas 15
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
f: R ® Z, f(x) = ëxû é uma função inteira
f: Z ® R, f(x) = 
2
x
 é uma função de variável inteira
Note-se ainda que estas classificações não são excludentes! Por exemplo:
f: R ® R, f(x) = x2
f: [ 0; +¥ ) ® R, f(x) = ln(x)
f: R ® [ -1; 1 ], f(x) = sen(x)
são exemplos de funções reais de variável real!
22..55..44 MMaaiioorr ddoommíínniioo ddee uummaa ffuunnççããoo
Em aplicações do conceito de função, como ocorre no Cálculo, é comum subentender o domínio da
função, pois é dada maior ênfase ao aspecto de transformação que a lei da função traz. Assim,
adota-se como domínio da função o maior intervalo possível de valores de entrada que
produzam uma saída real. Isto é o que chamamos maior domínio de uma função. Por questões de
comodidade e simplificação, isto é o que comumente (e erroneamente) é denominado como “o
domínio” da função em Cálculo.
22..55..44..11 EEmm RReessuummoo......
Maior domínio de uma função é o maior intervalo de valores de entrada que produzam uma
resposta válida dentro do conjunto de saídas.
Domínio de uma função é o conjunto A (veja a observação no item 2.2).
22..55..44..22EExxeemmppllooss
Encontre o maior domínio real que torna cada uma das expressões abaixo funções reais:
(a). x)x(f =
Solução: O maior domínio é x Î [ 0; +¥ ).
Justificativa: x Î R Û x ³ 0 Ù x Î R. Então o maior domínio real
é x Î [ 0; +¥ ).
(b). 
x
1
)x(f =
Solução: O maior domínio é x Î ( -¥; 0 ) È ( 0; +¥ ).
Justificativa: 
x
1
 Î R Û x ¹ 0 Ù x Î R. Então o maior domínio real é
x Î ( -¥; 0 ) È ( 0; +¥ ).
Estruturas Algébricas 16
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
(c). )xln()x(f =
Solução: O maior domínio é x Î ( 0; +¥ ).
Justificativa: ln(x) Î R Û x > 0 Ù x Î R. Então o maior domínio real
é x Î ( 0; +¥ ).
(d). xe)x(f =
Solução: O maior domínio é x Î R.
Justificativa: ex Î R Û x Î R. Então o maior domínio real é x Î R.
(e). 
1x
1x
)x(f
+
-
=
Solução: O maior domínio é x Î ( -¥; -1 ) È ( -1; +¥ ).
Justificativa: 
1x
1x
+
-
 Ï R Û x + 1 = 0 Û x = -1. Então o maior
domínio real é x Î ( -¥; -1 ) È ( -1; +¥ ).
22..55..55 DDeetteerrmmiinnaaççããoo ddaa IImmaaggeemm ddee uummaa FFuunnççããoo nnaa
PPrrááttiiccaa
Encontrar a imagem de uma função pode ser uma tarefa complexa caso não sejam conhecidas
informações adicionais da função. Isto porque a predição do conjunto de respostas que uma função
efetivamente pode dar depende do conhecimento de seu comportamento. Assim, para se poder
determinar a imagem de uma função deve-se recorrer a outros ramos da ciência Matemática, tais
como o Cálculo para a determinação operacional de imagens de funções. Também são úteis
informações algébricas com respeito ao comportamento da função. Por exemplo, dada uma função
real f, então temos os seguintes casos:
$ min(f) Ù $ max(f) Þ Im(f) = [ min(f); max(f) ]
$/ min(f) Ù $ max(f) Þ Im(f) = ( -¥; max(f) ]
$ min(f) Ù $/ max(f) Þ Im(f) = [ min(f); +¥ )
$/ min(f) Ù $/ max(f) Þ Im(f) = R
Ainda, se soubermos que uma função é inversível, ou seja, que tem outra função como inversa
poderemos ter outras alternativas para determinar a imagem de uma função, como veremos adiante.
Estruturas Algébricas 17
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
22..66 GGrrááffiiccoo ddee uummaa FFuunnççããoo
22..66..11 DDeeffiinniiççããoo
Dada uma função f: A ® B, y = f(x), chamamos de gráfico de f o conjunto
Gráfico(f) = { ( x, f(x) ) / x Î A }
22..66..22 EExxeemmppllooss
22..66..22..11 EExxeemmpplloo 11
Sabendo que f: ( 0; +¥ ) ® R, 
x
1
)x(f = é função, encontre o gráfico de f.
Solução: O gráfico de f é o conjunto
G(f) = { ( x, 
x
1
 ) / x > 0 }
22..66..22..22 EExxeemmpplloo 22
A representação gráfica ao lado não representa o gráfico de uma função.
Observe que os pontos ( x, y ) desta representação gráfica satisfazem a
equação x2 + y2 = 22, x Î [ -2; 2 ], y Î [ -2; 2 ].
Ocorre que, para cada valor de x haverá dois pares correspondentes
associados, o que é conflitante com as condições de “bom
funcionamento” que definem uma função.
22..66..33 OObbsseerrvvaaççããoo:: GGrrááffiiccoo xx RReepprreesseennttaaççããoo GGrrááffiiccaa
Alguns autores acham por bem fazer a seguinte distinção:
§ Gráfico de uma função é um conjunto de pares ordenados.
§ Representação gráfica de uma função é uma forma de “desenhar” o gráfico.
A razão de tal distinção é que um mesmo gráfico pode ser representado de diversas formas
diferentes. Ou seja, o mesmo gráfico pode ter diferentes representações gráficas.
22..77 FFuunnççõõeess IInnvveerrssíívveeiiss
22..77..11 UUmm EExxeemmpplloo IInniicciiaall
Sejam A = B = { 1, 2, 3 }. Suponha que queiramos determinar todas as funções de A em B. Com um
pouco de pensar chegaríamos às seguinte 27 funções (representadas por diagramas de Venn):
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
Estruturas Algébricas 18
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
Estruturas Algébricas 19
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Quais destas funções seriam capazes de satisfazer à seguinte propriedade:
“f: A ® B é uma função tal que existe uma função g: B ® A para a qual g(y) = x se e só se f(x) = y” ?
Analisando os gráficos acima veríamos que as funções que satisfazem tal questão são:
Isto nos leva a duas questões importantes:
(a). Por que as demais 21 funções não satisfazem à questão levantada?
(b). Quais as propriedades que estas 6 funções possuem em comum?
Para respondermos a estas questões podemos começar observando que a
função
f: { 1,2,3 } ® { 1, 2, 3 } definida por f(1) = 2, f(2) = 1 e f(3) = 2
não responde à questão formulada por dois motivos:
( $ y Î B )( y = 3 )( " x Î A )( y ¹ f(x) )
( $ x1, x2 Î A )( x1 = 1 Ù x2 = 3 )( f(x1) = f(x2) Ù x1 ¹ x2 )
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
1
2
3
1
2
3
A B
Estruturas Algébricas 20
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Não é difícil observar que todas as 21 funções não selecionadas falham em pelo menos uma das
situações assinaladas para a função f acima.
Por que estas observações são importantes para a definição das funções g: B ® A?
Usando a negação das proposições acima podemos determinar as propriedades que as 6 funções
selecionadas cumprem. As condições são:
(1) ( " y Î B )( $ x Î A )( y = f(x) )
(2) ( " x1, x2 Î A )( f(x1) ¹ f(x2) Ú x1 = x2 )
Usando a equivalência lógica p ® q Û Ø p Ú q, podemos reescrever a segunda propriedade na
forma equivalente a dada acima.
(2) ( " x1, x2 Î A )( f(x1) = f( x2 ) ® x1 = x2 )
Finalmente, observe que:
§ Usando estas duas propriedades é possível resolver o problema.
§ Estas são as condições que definem uma função de B em A!!!
22..77..22 FFuunnççõõeess IInnjjeettoorraass ((11 PPaarraa 11))
22..77..22..11 DDeeffiinniiççããoo
Sejam A e B conjuntos e f: A ® B uma função.
Dizemos que:
f é injetora de A em B Û ( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 )
22..77..22..22 OObbsseerrvvaaççõõeess
§ Note que isto é o mesmo que ( " x1, x2 Î A )( x1 ¹ x2 ® f(x1) ¹ f(x2) )
§ Note que isto NÃO é o mesmo que ( " x1, x2 Î A )( x1 = x2 ® f(x1) = f(x2) )
22..77..33 EExxeemmppllooss
22..77..33..11 EExxeemmpplloo 11
Mostre que y = x2, x Î R não é injetora.
Solução: Para verificar que a expressão acima não é injetora precisamos mostrar que a proposição
( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 )
falha para alguma combinação de valores x1 e x2 que satisfaçam à premissa f(x1) = f(x2).
Isto pode ser feito genericamente ou através de um exemplo:
1o modo: genericamente.
Sejam x1, x2 Î R tais que f(x1) = f(x2).
f(x1) = f(x2) Û x1
2 = x22 Û | x1 | = | x2 | Û ( x1 = x2 ) Ú ( x1 = -x2 ).
Então não se pode garantir que, necessariamente, x1 = x2.
Logo, ( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 ) Û F.
2o modo: através de um exemplo.
Estruturas Algébricas 21
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Sejam x1, x2 Î R tais que f(x1) = f(x2).
Por exemplo, escolhendo x1 = 2 e x2 = -2, temos que
f(x1) = f(x2), pois
x1
2 = 22 = 4, x2
2 = (-2)2 = 4
Mas x1 ¹ x2.
Logo, ( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 ) Û F.
22..77..33..22 EExxeemmpplloo 22
Mostre que y = x2, x ³ 0 é injetora.
Solução: Para verificar que a expressão acima é injetora precisamos mostrar que a proposição
( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 )
vale para todas as combinações possíveis de valores x1 e x2 que satisfaçam à premissa f(x1) = f(x2):
Sejam x1, x2 Î [ 0; +¥ ) tais que f(x1) = f(x2).
f(x1) = f(x2) Û x1
2 = x2
2 Û | x1 | = | x2 | Û ( x1 = x2 ) Ú ( x1 = -x2 ).
Como x1 ³ 0 Ù x2 ³ 0 Þ ( x1 = -x2 Û F ).
Então ( x1 = x2 ) Ú ( x1 = -x2 ) Û ( x1 = x2 ) Ú F Û ( x1 = x2 ).
Logo, ( " x1, x2 Î [ 0; +¥ ) )( x1
2 = x2
2 Þ x1 = x2 ).
22..77..33..33 EExxeemmpplloo 33
Mostre que xy = , x ³ 0 é injetora.
Solução: Para verificar que a expressão acima é injetora precisamos mostrar que a proposição
( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 )
vale para todas as combinações possíveis de valores x1 e x2 que satisfaçam à premissa f(x1) = f(x2):
Sejam x1, x2 Î [ 0; +¥ ) tais que 21 xx = .
21 xx = Þ ( ) ( )2221 xx = .
Como ( ) xx 2 = , então ( ) ( )2221 xx = Û | x1 | = | x2 | Û ( x1 = x2 ) Ú ( x1 = -x2 ).
Como x1 ³ 0 Ù x2 ³ 0 Þ ( x1 = -x2 Û F ).
Então ( x1 = x2 ) Ú ( x1 = -x2 ) Û ( x1 = x2 ) Ú F Û ( x1 = x2 ).
Logo, ( " x1, x2 Î [ 0; +¥ ) )( 21 xx = Þ x1 = x2 ).
22..77..33..44 EExxeemmpplloo 44
Mostre que y = -x2 + 5x - 6, x Î R não é injetora.
Solução: Esta função não pode ser injetora pois possui duas raízes
reais diferentes.
Com efeito, sabemos que as raízes desta função são x = 2 e x = 3.
Isto significa que
( $ x1, x2 Î R )( x1 = 2 Ù x2 = 3 )( f(x1) = f(x2) = 0 Ù x1 ¹ x2 ).
Logo, f não é injetora!
Estruturas Algébricas 22
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
22..77..33..55 EExxeemmpplloo 55
Mostre que y = | x |, x Î R não é injetora.
Solução: Sejam x1, x2 Î R tais que | x1 | = | x2 |.
| x1 | = | x2 | Û ( x1 = x2 ) Ú ( x1 = -x2 ).
Então não se pode garantir que, necessariamente, x1 = x2.
Logo, ( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 ) Û F.
22..77..44 TTeeoorreemmaa
Seja f uma função real. Então:
f estritamente crescente Þ f injetora
f estritamente decrescente Þ f injetora
Prova: Será apresentada a versão para uma função estritamente crescente1.
Seja f uma função real e estritamente crescente.
Então: ( " x1, x2 Î Dom(f) )( x1 < x2 Þ f(x1) < f(x2) ) .
Precisamos mostrar que ( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 ) é verdadeira.
Isto pode ser mais facilmente feito mostrando que a proposição contrapositiva
( " x1, x2 Î A )( x1 ¹ x2 ® f(x1) ¹ f(x2) )
é verdadeira. Para tanto:
Sejam x1, x2 Î Dom(f) tais que x1 ¹ x2.
x1 ¹ x2 Û ( x1 < x2 ) Ú ( x1 > x2 ).
Como f estritamente crescente,
( x1 < x2 ) Ú ( x1 > x2 ) Þ ( f(x1) < f(x2) ) Ú ( f(x2) < f(x1) ) Û f(x1) ¹ f(x2).
Então, x1 ¹ x2 Þ f(x1) ¹ f(x2).
Logo, f é injetora!
22..77..44..11 OObbsseerrvvaaççõõeess
§ Note que a recíproca das implicações não é necessariamente verdadeira!
Isto significa que:
Se uma função não é estritamente crescente não se pode afirmar que ela não seja injetora!
Se uma função não é estritamente decrescente não se pode afirmar que ela não seja injetora!
Por exemplo, observe o gráfico da função ao lado, que é definida
por
f: [ 0; + ¥ ) ® [ 0; + ¥ ), 
î
í
ì
>
££-
=
2xx
2x0x2
)x(f
Ela é injetora, mas não é estritamente crescente!
 
1 A versão para uma função estritamente decrescente é semelhante e pode ser facilmente demonstrada seguindo os passos
aqui apresentados.
Estruturas Algébricas 23
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
§ Note que sempre é possível fazer as seguintes afirmações contrapositivas:
f não é injetora Þ f não é estritamente crescente
f não é injetora Þ f não é estritamente decrescente.
22..77..44..22 EExxeemmpplloo
Mostre que y = ln(x), x > 0 é injetora.
Solução:
Como sabemos, a função logaritmo natural é estritamente crescente.
Logo, é injetora!
22..77..55 FFuunnççõõeess SSoobbrreejjeettoorraass
22..77..55..11 DDeeffiinniiççããoo
Sejam A e B conjuntos, f : A ® B uma função.
Dizemos que:
f é sobrejetora de A em B Û ( " y Î B )( $ x Î A )( y = f(x) )
22..77..55..22 OObbsseerrvvaaççããoo
Note que dizer que uma função é sobrejetora é o mesmo que mostrar que Im(f) = C(f).
Os seja, para qualquer função sempre será verdade que Im(f) Í C(f).
Mas somente para as funções sobrejetoras poderemos escrever Im(f) = C(f).
22..77..66 EExxeemmppllooss
22..77..66..11 EExxeemmpplloo 11
Mostre que y = x2, x Î R, y Î R não é sobrejetora.
Solução: Para mostrarmos que a lei acima não define uma função sobrejetora, basta encontrarmos
algum valor no conjunto das respostas (isto é, o contradomínio da função) que não tenha entrada
associada (ou seja, não pertença à imagem da função).
Para facilitar vamos chamar a função acima de f: Seja f: R ® R definida por f(x) = x2.
Por exemplo, seja y = -1.
Temos que y Î R, mas ( $/ x Î R )( x2 = -1 ).
Logo, ($ y Î R )( y = -1 )( $/ x Î R )( x2 = y ).
Logo, (" y Î B )( $ x Î A )( y = f(x) ) Û F.
Logo, f não é sobrejetora.
22..77..66..22 EExxeemmpplloo 22
Mostre que f: R ® [ 0; +¥ ), f(x) = x2 é sobrejetora.
Solução: Precisamos mostrar que a proposição
(" y Î [ 0; +¥ ) )( $ x Î R )( y = x2 )
é sempre válida. Para isto:
Estruturas Algébricas 24
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Seja y Î [ 0; +¥ ).
y Î [ 0; +¥ ) Û y ³ 0.
Como ( " x Î R )( x2 ³ 0 ), então chamando y = x2 temos que
(" y Î [ 0; +¥ ) )( $ x Î R )( y = x2 )
Logo, f é sobrejetora.
22..77..66..33 EExxeemmpplloo 33
y = x2, x Î R, y Î ( 0; +¥ ) é função sobrejetora?
Solução: Não é função, pois Im(f) Í/ C(f)!
22..77..77 FFuunnççõõeess BBiijjeettoorraass
22..77..77..11 DDeeffiinniiççããoo
Sejam A e B conjuntos, f : A ® B uma função.
Dizemos que f é bijetora se e só se f é sobrejetora e injetora.
Isto é:
f bijetora Û f injetora Ù f sobrejetora
Ou seja:
f bijetora Û ( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 ) Ù ( " y Î B )( $ x Î A )( y = f(x) )
22..77..77..22 TTeeoorreemmaa
Seja f uma função de A em B. Então
f bijetora Û f inversível
Isto é, f possui uma função inversa, denotada por f-1, de B em A.
Assim, respondemos à questão formulada no início desta seção:
“f: A ® B é uma função tal que existe uma função f-1: B ® A para a qual f-1(y) = x se e só se f(x) = y”.
Prova: Seja f: A ® B função bijetora. Seja f-1: B ® A tal que f-1(y) = x quando f(x) = y.
Precisamos mostrar que f-1 também é uma função!
Pelas hipóteses, é sabido que f cumpre todas as seguintes condições:
( " x Î A ) ( $ y Î B )( y = f(x) ) (condição de existência)
( " x1, x2 Î A )( x1 = x2 ® f(x1) = f (x2) ) (condição de unicidade)
( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 ) (injetora)
( " y Î B )( $ x Î A )( y = f(x) ) (sobrejetora)
Usando as condições de unicidade e injetividade pode-se escrever:
( " x1, x2 Î A )( x1 = x2 « f(x1) = f (x2) )
Isto significa que a associação entre valores x Î A e valores y = f(x), y Î B é única! Dessa forma,
lembrando que
f-1(y) = x quando f(x) = y
pode-se escrever
Estruturas Algébricas 25
Vedadaa alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
( " y1, y2 Î B )( f
-1(y1) = f
-1(y2) « y1 = y2 )
Mas: ( " y1, y2 Î B )( f
-1(y1) = f
-1(y2) « y1 = y2 ) Û
Û ( " y1, y2 Î B )( f
-1(y1) = f
-1(y2) ® y1 = y2 ) Ù ( " y1, y2 Î B )( y1 = y2 ® f
-1(y1) = f
-1(y2) )
Destas propriedades pode-se concluir que f-1 é injetora e cumpre a condição de unicidade:
( " y1, y2 Î B )( f
-1(y1) = f
-1(y2) ® y1 = y2 ) ( f
-1 é injetora )
( " y1, y2 Î B )( y1 = y2 ® f
-1(y1) = f
-1(y2) ) ( f
-1 cumpre a condição de unicidade )
Da mesma forma, partindo da sobrejetividade de f e usando que f-1(y) = x quando f(x) = y, pode-se
escrever:
( " y Î B )( $ x Î A )( y = f(x) ) Û ( " y Î B )( $ x Î A )( f-1(y) = x )
que é a condição de existência para f-1.
Logo, f-1: B ® A é função.
Logo, f bijetora Û f possui função inversa.
22..77..77..33 UUmmaa OObbsseerrvvaaççããoo IImmppoorrttaannttee!!!!!!
A notação utilizada para a representação da função inversa é um tanto infeliz, mas foi difundida por
diversos livros e fontes. Então CUIDADO!
§ f-1 significa a função inversa de f.
§ Isto NADA TEM A VER com a função 
f
1
 (denominada “inverso da função f”)
22..77..88 EExxeemmppllooss
22..77..88..11 EExxeemmpplloo 11
Verifique se f: [ 0; +¥ ) ® [ 0; +¥ ), x)x(f = é inversível e determine a lei que representa sua
inversa.
Solução: Para verificarmos que a f dada é inversível, precisamos verificar se f é bijetora:
1a parte: f é injetora?
Como a expressão x)x(f = define uma função estritamente crescente,
então f é injetora.
2a parte: f é sobrejetora?
Precisamos mostrar que a proposição
( " y Î [ 0; +¥ ) )( $ x Î [ 0; +¥ ) )( xy = )
é sempre verdadeira. Para tanto:
Seja y Î [ 0; +¥ ).
y Î [ 0; +¥ ) Þ y ³ 0 Û xy = para algum x ³ 0.
Então, ( $ x Î [ 0; +¥ ) )( xy = ).
Logo, f é sobrejetora.
Conclusão geral: como f é injetora e sobrejetora, então f é inversível.
Determinação da inversa: Queremos encontrar a expressão da função inversa de f:
Estruturas Algébricas 26
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Sabemos que: 
x)x(fx
);0[);0[:f
=
+¥®+¥
a
Então, chamando y = f(x) temos: xy = Û x = y2
A função inversa de f será dada por: 
21
1
y)y(fy
);0[);0[:f
=
+¥®+¥
-
-
a
Observação:
Note-se que a letra usada para designar a variável independente na expressão da função inversa
pouca importância tem!!! Na verdade, o que efetivamente importa é a transformação que a expressão
indica que a função realiza. Na prática, isto significa que, por exemplo,
2y)y(gy
);0[);0[:g
=
+¥®+¥
a 2t)t(ht
);0[);0[:h
=
+¥®+¥
a 2x)x(vx
);0[);0[:v
=
+¥®+¥
a
são todas a mesma função e, conseqüentemente, são todas expressões válidas para designar a
função inversa de f.
22..77..88..22 EExxeemmpplloo 22
Encontre condições sobre os conjuntos A e B de modo que a relação f Í A x B definida por 2x
1
y =
seja uma função real inversível.
Solução: Precisamos definir os conjuntos A e B da forma mais ampla possível e, além disso, garantir
que as seguintes propriedades sejam válidas:
( " x Î A ) ( $ y Î B )( y = f(x) ) ( f satisfaz à condição de existência )
( " x1, x2 Î A )( x1 = x2 ® f(x1) = f (x2) ) ( f satisfaz à condição de unicidade )
( " y Î B )( $ x Î A )( y = f(x) ) ( f é sobrejetora )
( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 ) ( f é injetora )
Para f satisfazer às condições de existência e unicidade, é fácil verificar que a única restrição
evidente é que 0 Ï A. Assim,
A Í R – { 0 }.
Da mesma forma, para que f seja sobrejetora teremos y > 0. Assim, uma das restrições para que f
seja inversível é que
B Í ( 0; +¥ )
Finalmente, precisamos encontrar condições para que f seja injetora, isto é, que satisfaça à condição
( " x1, x2 Î A )( f(x1) = f(x2) ® x1 = x2 )
Para isto: sejam x1, x2 Î A tais que 2
2
2
1 x
1
x
1
= .
Então: 2
2
2
1 x
1
x
1
= Û 22
2
1 xx = Û ( x1 = x2 ) Ú ( x1 = -x2 ).
Vemos então que há um conflito com a injetividade de f caso A possua
elementos com mesmo valor absoluto. Neste caso, podemos, por
exemplo sugerir que A só possua valores positivos (ou só negativos...).
Assim, a solução para este problema é:
Estruturas Algébricas 27
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
A Í R – { 0 } e A não pode possuir dois elementos com mesmo valor absoluto e sinais opostos
B = ( 0; +¥ )
Comentários:
Note que as seguintes escolhas para os conjuntos A e B sempre satisfazem às condições acima
determinadas:
1a Possibilidade: 2a Possibilidade:
A = ( 0; +¥ ) A = ( -¥; 0 )
B = ( 0; +¥ ) B = ( 0; +¥ )
3a Possibilidade: 4a Possibilidade: (bem diferente!!!)
A = [ -2; 0 ) È ( 2; +¥ ) A = ( -2; -1 ) È (
2
1
; 
3
2
)
B = ( 0; +¥ ) B = (
4
1
; 1 ) È (
4
9
; 4 )
5a Possibilidade:
etc.
22..77..99 UUmm TTeeoorreemmaa IImmppoorrttaannttee
Seja f uma função inversível e f-1 sua função inversa.
Então: Dom(f) = Im(f-1)
Im(f) = Dom(f-1)
Prova: Para facilitar, digamos que f é uma função inversível de A em B, ou seja: f: A ® B.
Como conseqüência, f-1: B ® A também é inversível.
f é inversível Û f é bijetora Û f é injetora Ù f é sobrejetora.
Mas:
Estruturas Algébricas 28
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
f é sobrejetora Þ Im(f) = B.
f-1 é sobrejetora Þ Im(f-1) = A.
Como:
Dom(f) = A
Dom(f-1) = B,
temos que ( Dom(f) = Im(f-1) ) Ù ( Im(f) = Dom(f-1) )
Estruturas Algébricas 29
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
33 RReellaaççõõeess eemm AA
Um caso particular de relação é obtido quando relacionamos entre si elementos de um mesmo
conjunto. Neste caso, teremos uma relação que associa um elemento de um certo conjunto A com
outro(s) elemento(s) do próprio conjunto A. Relações deste tipo são denominadas relações de A em
A, ou, simplesmente, relações em A.
Relações desta natureza são importantes, por exemplo, para a identificação de informações de
mesma natureza ou para a ordenação de estágios de um determinado processo. A definição de
relações dentro de um único conjunto permite definir critérios de “varredura” do conjunto. A
identificação de quais relações são adequadas para cada propósito depende da identificação de
diversas propriedades, típicas das relações em A, e que as relações podem (ou não) ter.
33..11 DDeeffiinniiççããoo
Seja A um conjunto. Então R é relação de A em A se e somente se R é subconjunto do produto
cartesiano de A com A.
Em notação lógica:
R é relação em A Û R Í A x A
33..22 EExxeemmppllooss
33..22..11 UUmm EExxeemmpplloo IInnttuuiittiivvoo
Seja A um conjunto de etapas necessários para a geração de uma aplicação computacional. Por
exemplo,
A = { análise, projeto, implementação, testes, finalização }.
Na prática, estas etapas não ocorrem todas ao mesmo tempo, podendo ser classificadas de maneira
temporal da seguinte forma:
Em termos matemáticos, podemos descrever esta situação através de uma relação definida no
conjunto A da seguinte forma:
R Í A x A, R = { ( análise, análise ), ( análise, projeto ), ( projeto, projeto ),
 ( projeto, implementação ), ( implementação, projeto ),
 ( implementação, implementação ), ( implementação, testes ),
 ( testes, implementação ), ( testes, testes ), ( testes, finalização ),
 ( finalização, finalização ) }
análise projeto implementação testes finalização
Estruturas Algébricas 30
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
33..22..22 OOuuttrrooss EExxeemmppllooss IInnttuuiittiivvooss
Seja A um conjunto de pessoas. Neste conjunto podem-se definirdiversas relações. Por exemplo:
R Í A x A, x R y Û x tem o mesmo nome que y
S Í A x A, x S y Û x é parente de y
T Í A x A, x T y Û x é namorado de y
Observe-se que, neste exemplo, as pessoas identificadas pelas variáveis “x” e “y” devem sempre
pertencer ao conjunto A especificado!
33..22..33 EExxeemmppllooss CCoonncceeiittuuaaiiss
Seja A = { a, b, c }. Podem-se definir, por exemplo, as seguintes relações:
R Í A x A, R = { ( a, a ), ( a, b ), ( a, c ) }
S Í A x A, S = { ( a, a ), ( b, b ), ( c, c ) }
T Í A x A, T = { ( a, a ), ( a, b ), ( b, a ), ( b, c ) }
W Í A x A, W = { ( a, a ), ( a, b ), ( a, c ), ( b, a ), ( b, b ), ( b, c ), ( c, a ), ( c, b ), ( c, c ) }
Estas mesmas relações podem ser descritas por compreensão:
R Í A x A, x R y Û x = a
S Í A x A, x S y Û x = y
T Í A x A, x T y Û ( ( x = a ) Ù ( y ¹ c ) ) Ú ( ( x = b ) Ù ( y ¹ b ) )
W Í A x A, W = A x A
33..22..44 OOuuttrroo EExxeemmpplloo CCoonncceeiittuuaall
Pode-se definir relações muito interessantes e importantes dentro do conjunto dos números reais. Por
exemplo:
R Í R x R, x R y Û x £ y ( esta relação é denominada de “ordem natural” )
S Í R x R, x S y Û x | y ( x | y significa “x divide y”, isto é, “x é divisor de y”, ou ainda,
 ( $ a Î Z )( y = a.x ) )
33..22..55 MMaaiiss uumm EExxeemmpplloo IImmppoorrttaannttee
Dado o conjunto M = { ¡, o }, pode-se criar o conjunto das partes de M, denotado por P(M), que é
formado por todos os subconjuntos de M:
P(M) = { Æ, { ¡ }, { o }, { ¡, o } }
Este conjunto é importante, pois permite definir relações entre os subconjuntos de M. Assim, fazendo
A = P(M), podem-se definir, por exemplo, as relações:
§ R Í A x A, x S y Û x = y
Neste caso: S = { ( Æ, Æ ), ( { ¡ }, { ¡ } ), ( { o }, { o } ) , ( { ¡, o }, { ¡, o } ) }
§ S Í A x A, x R y Û x Í y
Então:
R = { ( Æ, Æ ), ( Æ, { ¡ } ), ( Æ, { o } ), ( Æ, { ¡, o } ),
 ( { ¡ }, { ¡ } ), ( { ¡ }, { ¡, o } ), ( { o }, { o } ), ( { o }, { ¡, o } ), ( { ¡, o }, { ¡, o } ) }
§ T Í A x A, x T y Û x ¹ y
Estruturas Algébricas 31
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Neste caso:
T = A x A – R, ou ainda,
T = { ( Æ, { ¡ } ), ( Æ, { o } ) , ( Æ, { ¡, o } ), ( { ¡ }, Æ ), ( { ¡ }, { o } ), ( { ¡ }, { ¡, o } ),
 ( { o }, Æ ), ( { o }, { ¡ } ), ( { o }, { ¡, o } ), ( { ¡, o }, Æ ), ( { ¡, o }, { ¡ } ),
 ( { ¡, o }, { o } ) }
Observe-se que, neste caso, as variáveis “x” e “y” representam conjuntos pertencentes a P(M).
33..22..66 UUmm ÚÚllttiimmoo EExxeemmpplloo
Uma relação em um dado conjunto A pode ser estabelecida independentemente da natureza dos
elementos de A. Isto significa que podemos relacionar pessoas com pessoas, objetos com objetos,
números com números, conjuntos com conjuntos, pares ordenados com pares ordenados, registros
de bancos de dados semelhantes, etc.
Para elucidar isto, sejam M = { 2, 3 } e N = { 0, 1 }. Com estes conjuntos formaremos um conjunto A
através do produto cartesiano:
A = { ( 2, 0 ), ( 2, 1 ), ( 3, 0 ), ( 3, 1 ) }
Em A podemos definir diversas relações. Por exemplo:
§ R Í A x A, ( x, y ) R ( z, w ) Û x + y > z + w
Neste caso: R = { ( ( 2, 1 ), ( 2, 0 ) ), ( ( 3, 0 ), ( 2, 0 ) ),
 ( ( 3, 1 ), ( 2, 0 ) ), ( ( 3, 1 ), ( 2, 1 ) ), ( ( 3, 1 ), ( 3, 0 ) ) }
§ S Í A x A, x S y Û x = y
Neste caso: S = { ( ( 2, 0 ), ( 2, 0 ) ), ( ( 2, 1 ), ( 2, 1 ) ),
 ( ( 3, 0 ), ( 3, 0 ) ), ( ( 3, 1 ), ( 3, 1 ) ) }
Observe-se que na definição de R as variáveis “x”, “y”, “z” e “w” foram utilizadas para representar
componentes dos pares ordenados; no entanto, na definição de S as variáveis “x” e “y” representam
diretamente pares ordenados.
33..33 PPrroopprriieeddaaddeess ddaass RReellaaççõõeess eemm AA
As relações em A são importantes por possuírem diversas propriedades interessantes. Através das
propriedades que uma determinada relação possui podem definir finalidades particulares para a
relação, conforme veremos mais adiante.
33..33..11 RReefflleexxiivviiddaaddee
Seja R uma relação definida em um conjunto A. Então:
R é reflexiva em A Û ( " x Î A )( ( x, x ) Î R )
33..33..22 EExxeemmppllooss IInnttuuiittiivvooss
Suponhamos que A seja um conjunto de pessoas. Podem-se definir, por exemplo, as seguintes
relações:
R Í A x A, x R y Û x tem o mesmo peso que y
S Í A x A, x S y Û x tem o mesmo tipo de computador que y
T Í A x A, x T y Û x namora com y
Estruturas Algébricas 32
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
Neste caso:
§ Para testar a reflexividade em R, devemos verificar se a proposição x R x, ou seja “x tem o
mesmo peso que x” é verdadeira para qualquer pessoa x do conjunto A. Como toda pessoa tem
seu próprio peso (ou seja, pesa o mesmo que ela própria...), então R será reflexiva.
§ Para testar a reflexividade em S, devemos verificar se a proposição x S x, ou seja “x tem o
mesmo tipo de computador que x” é verdadeira para qualquer pessoa x do conjunto A. Para as
pessoas que tem computador, isto será, obviamente, verdadeiro. No entanto, esta proposição não
é sempre verdadeira, pois algumas pessoas não tem computador! Logo S não será reflexiva.
§ Para testar a reflexividade em T, devemos verificar se a proposição x T x, ou seja “x namora com
x” é verdadeira para qualquer pessoa x do conjunto A. Ora, uma pessoa não pode namorar com
si própria. Logo T não será reflexiva.
Observação:
Observe que há uma sutil, mas importante diferença entre os casos representados pelas relações S e
T. No caso de S, algumas pessoas relacionar-se-ão com si próprias, enquanto outras, não. Já no
caso de T, nenhuma pessoa relacionar-se-á com si própria.
33..33..22..11 EExxeemmppllooss eemm uumm CCoonnjjuunnttoo DDiissccrreettoo
Operaremos com o conjunto dos números naturais, ou seja, A = N. Neste conjunto podem-se definir,
por exemplo, as relações:
R Í N x N, x R y Û x £ y
S Í N x N, x S y Û x é divisor de y
T Í N x N, x T y Û x < y
Das relações acima temos que:
§ R é reflexiva, pois ( " x Î N )( x £ x ) é sempre verdadeira (isto é, é uma tautologia).
§ S é reflexiva pois, dado x Î N, então
x = 1.x Û ( $ 1 Î Z )( x = 1.x ) Û x | x. Logo S é reflexiva.
§ T não é reflexiva, pois ( " x Î N )( x < x ) Û f.
33..33..22..22 EExxeemmppllooss eemm uumm CCoonnjjuunnttoo CCoonnttíínnuuoo
Podemos definir, por exemplo, as seguintes relações no conjunto dos números reais:
R Í R x R, x R y Û x £ y
S Í R x R, x S y Û x2 > y
T Í R x R, x T y Û x ¹ y
Então:
§ R é reflexiva pois qualquer número real será sempre menor ou igual a si mesmo. Formalmente
isto significa que ( " x Î R )( x £ x ) é uma tautologia. Logo R é reflexiva.
§ S não é reflexiva, pois, sendo x Î R, então
x S x Û x2 > x Û x2 – x > 0 Û x.(x–1) > 0 Û
 Û ( ( x > 0 ) Ù ( x – 1 > 0 ) ) Ú ( ( x < 0 ) Ù ( x – 1 < 0 ) ) Û
 Û ( ( x > 0 ) Ù ( x > 1 ) ) Ú ( ( x < 0 ) Ù ( x < 1 ) ) Û
 Û ( x < 0 ) Ú ( x > 1 )
Isto significa que a proposição só é válida para x < 0 ou para x > 1. Portanto, a proposição não é
válida para x Î [ 0 ; 1 ]. Logo a proposição não é sempre verdadeira. Logo S não é reflexiva.
Estruturas Algébricas 33
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
§ T não é reflexiva pois a proposição ( " x Î R )( x ¹ x ) é sempre falsa!
33..33..22..33 CCoommeennttáárriiooss
Relações que são reflexivas possuem a particular característica de garantir que todos os elementos
do conjunto origem (na nossa notação, o conjunto A) participem pelo menos uma vez da relação. Na
realidade, a Reflexividade é mais forte que isto! A definição de Reflexividade diz que cada elemento
do conjunto origem deve relacionar-se com si próprio, o que traz à tona as seguintes idéias:
§ Uma relação reflexiva está presente mesmo quando se está operandocom apenas um elemento
do conjunto origem. Por exemplo, a relação entre pessoas definida por “a pessoa x tem o mesmo
peso que a pessoa y” é reflexiva. Assim, se estivermos nos referindo a qualquer pessoa em um
dado momento, como uma pessoa tem sempre seu próprio peso, automaticamente a relação
estará presente e disponível para ser referida ou utilizada;
§ No caso de interpretarmos uma relação como um processo de “transmissão de informações” ou
como uma sucessão de estágios, a Reflexividade traduz a característica de se poder estacionar
em um determinado estágio. Por exemplo, se definíssemos, no conjunto
A = { análise, implementação, testes },
a relação R através do seguinte diagrama:
a reflexividade desta relação traduz a importante idéia de que, estando na fase de análise,
podemos continuar “por mais um período” na mesma fase. Da mesma forma, estando na fase de
implementação, podemos continuar por “mais um período” na fase de implementação; e o
mesmo vale para a fase de testes, pois a reflexividade, como sabemos, somente é válida se
todos os elementos do conjunto origem tiverem a característica de se relacionarem consigo.
§ Como, em uma relação reflexiva todos os elementos relacionam-se com si próprios, isto significa,
em particular, que todos os elementos aparecem pelo menos uma vez como primeiro elemento
de um par ordenado da relação. Assim, todos os elementos do conjunto origem relacionam-se
com algum elemento e, portanto, o domínio de uma relação reflexiva será o próprio conjunto
origem! Assim:
(R Í A x A) Ù (R reflexiva) Þ Dom(R) = A
§ Da mesma forma, todos os elementos de uma relação reflexiva aparecerão, pelo menos uma vez
como segundo elemento de um par ordenado da relação. Isto significa que todos os elementos do
conjunto origem foram relacionados com algum elemento e, portanto, a imagem de uma relação
reflexiva será o próprio conjunto origem! Assim:
(R Í A x A) Ù (R reflexiva) Þ Im(R) = A
§ Geometricamente, a Reflexividade pode ser visualizada quando para todos os elementos x do
conjunto origem, A, a reta y = x, estiver presente no gráfico da relação. Por exemplo:
A = [ -2, 2 ]
§ R Í [ -2, 2 ] x [ -2, 2 ], x R y Û x £ y
§ S Í [ -2, 2 ] x [ -2, 2 ], x S y Û x ¹ y
§ T Í [ -2, 2 ] x [ -2, 2 ], x T y Û x2 + y2 > 1
análise implementação testes
Estruturas Algébricas 34
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
R é reflexiva, pois todos os pontos da reta y = x para x Î A estão presentes no gráfico de R.
S não é reflexiva, pois nenhum ponto da reta y = x para x Î A está presente no gráfico de S.
T não é reflexiva, pois alguns pontos da reta y = x para x Î A não estão no gráfico de T.
33..33..33 IIrrrreefflleexxiivviiddaaddee
Seja R uma relação definida em um conjunto A. Então:
R é irreflexiva em A Û ( " x Î A )( ( x, x ) Ï R )
33..33..33..11 EExxeemmppllooss IInnttuuiittiivvooss
Para melhor comparação e entendimento, usaremos os mesmos exemplos da seção anterior. Assim,
suponhamos que A seja um conjunto de pessoas. As relações anteriormente definidas foram:
R Í A x A, x R y Û x tem o mesmo peso que y
S Í A x A, x S y Û x tem o mesmo tipo de computador que y
T Í A x A, x T y Û x namora com y
Neste caso:
§ Para testar a irreflexividade em R, devemos verificar se a proposição ( x , x ) Ï R, ou seja “x não
tem o mesmo peso que x” é verdadeira para qualquer pessoa x do conjunto A. Se preferirmos,
podemos pensar que a proposição “x tem o mesmo peso que x” deverá ser sempre falsa... Como
toda pessoa tem seu próprio peso (ou seja, pesa o mesmo que ela própria...), então a proposição
“x não tem o mesmo peso que x” nunca será verdadeira. Logo R não é irreflexiva.
§ Para testar a irreflexividade em S, devemos verificar se a proposição ( x , x ) Ï S, ou seja “x não
tem o mesmo tipo de computador que x” é verdadeira para qualquer pessoa x do conjunto A. Ora,
há pessoas que não possuem computador e, portanto, nesta situação específica a proposição
seria falsa. No entanto, para as pessoas que tem computador, isto será, obviamente, verdadeiro.
Concluímos então que a proposição em questão não será sempre verdadeira. Logo S não é
irreflexiva.
§ Para testar a irreflexividade em T, devemos verificar se a proposição ( x , x ) Ï T, ou seja “x não
namora com x” é verdadeira para qualquer pessoa x do conjunto A. Ora, uma pessoa não pode
namorar com si própria, o que significa que a proposição em questão é sempre verdadeira. Logo
T é irreflexiva.
Observação:
Novamente, há uma sutil, mas importante diferença entre os casos representados pelas relações R e
S. No caso de R, nenhuma pessoa relacionar-se-á com si própria. Já no caso de S, algumas pessoas
relacionar-se-ão com si próprias, enquanto outras, não.
Estruturas Algébricas 35
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
33..33..33..22 EExxeemmppllooss eemm uumm CCoonnjjuunnttoo DDiissccrreettoo
Novamente, usaremos os mesmos exemplos apresentados para a identificação da propriedade de
Reflexividade. Neste caso, tínhamos A = N e as relações apresentadas foram:
R Í N x N, x R y Û x £ y
S Í N x N, x S y Û x é divisor de y
T Í N x N, x T y Û x < y
Então:
§ R não é irreflexiva, pois
( " x Î N )( Ø( x £ x ) ) Û ( " x Î N )( x > x ) Û f.
Isto é, a propriedade de Irreflexividade nunca se cumprirá para R. Logo, R não é irreflexiva.
§ S não é irreflexiva, pois se escolhermos, por exemplo, x = 1, então
x é divisor de x Û 1 é divisor de 1 Û 
1
1
 Î Z.
Como ( 
1
1
 = 1 ) Ù ( 1 Î Z ) então 1 é divisor de si próprio, o que significa que
( " x Î N )( Ø( x é divisor de x ) ) Û f. Logo, S não é irreflexiva.
§ T é irreflexiva, pois ( " x Î N )( Ø( x < x ) ) Û ( " x Î N )( x ³ x ) Û v.
Logo T é irreflexiva.
33..33..33..33 EExxeemmppllooss eemm uumm CCoonnjjuunnttoo CCoonnttíínnuuoo
No mesmo espírito das seções anteriores, usaremos os mesmos exemplos apresentados para a
verificação da propriedade de Reflexividade:
R Í R x R, x R y Û x £ y
S Í R x R, x S y Û x2 > y
T Í R x R, x T y Û x ¹ y
Então:
§ R não é irreflexiva pois ( " x Î R )( Ø( x £ x ) ) Û ( " x Î R )( x > x ) Û f. Na realidade, para a
relação aqui apresentada, nenhum número real poderá cumprir a proposição de irreflexividade.
Logo R não é irreflexiva.
§ S não é irreflexiva, pois, sendo x Î R, então já havíamos descoberto (item 3.1.3) que
x S x Û ( x < 0 ) Ú ( x > 1 )
Então, tomando, por exemplo, x = 2 teremos:
x = 2 Þ 22 = 4 Ù 4 > 2 Þ x2 > x Û x S x
Logo a proposição em questão não é sempre verdadeira. Logo S não é irreflexiva.
§ T é irreflexiva pois devemos verificar se ( " x Î R )( Ø( x ¹ x ) ) é verdadeira. Mas
( " x Î R )( Ø( x ¹ x ) ) Û ( " x Î R )( x = x ) Û v.
Logo T é irreflexiva.
Estruturas Algébricas 36
Vedada a alteração ou o uso sem o consentimento prévio dos autores © Vaccaro & Canto
33..33..33..44 CCoommeennttáárriiooss
Relações Irreflexivas podem ser entendidas como o extremo oposto das Relações Reflexivas, já que
nenhum elemento do conjunto origem relaciona-se com si mesmo. No entanto, deve-se ter em mente
que existem relações que não são reflexivas nem são irreflexivas.
Neste caso também é possível dar uma interpretação geométrica para a Irreflexividade. Ela pode ser
visualizada quando para todos os elementos x do conjunto origem, A, a reta y = x, não estiver
presente no gráfico da relação. Usando convenientemente os exemplos apresentados anteriormente:
A = [ -2, 2 ]
§ R Í [ -2, 2 ] x [ -2, 2 ], x R y Û x £ y
§ S Í [ -2, 2 ] x [ -2, 2 ], x S y Û x ¹ y
§ T Í [ -2, 2 ] x [ -2, 2 ], x T y Û x2 + y2 > 1
§ R não é irreflexiva, pois todos os pontos da reta y = x para x Î A estão presentes no gráfico de R.
§ S é irreflexiva, pois nenhum ponto da reta y = x para x Î A está presente no gráfico de S.
§ T não é irreflexiva, pois alguns pontos