Gabarito_comentado_lista_1_2011.2_finalizado_

Prévia do material em texto

Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
Curso: Licenciatura em Computação - EAD 
Disciplina: Matemática Discreta - LC01- MD 
Professor formador: Ricardo Freitas 
Semestre 2011.2 
 
Lista 1: Gabarito comentado 
 
Parte 1 
 
Questão 1: a) Para cada alfabeto o conjunto de todas as palavras é infinito e formado por 
qualquer justaposição finita de elementos do alfabeto (com ou sem repetição). Assim, 
listando alguns elementos de ∗∑ teremos, por exemplo, 
 { }, , , ,..., , , , , , , , , , ,...a b c x y z ab xu casa pato aaad rfrf ssε∗∑ = , 
 e para Dígitos* teremos, 
 Dígitos* { },0,1, 2,3,4,5,6,7,8,9,10,122,876,7777,1000,008,345,...ε= . 
 
b) I) Como uma linguagem é um conjunto de palavras sobre um alfabeto, concluímos que 
essa afirmação é falsa, uma vez que para compor um texto em português também são 
necessários símbolos do tipo ^, ~, ´, ` para acentuação e símbolos do tipo ?, ! , :, ;, - para 
pontuação. Assim, { }, , ,..., , ,a b c x y z∑ = não possui elementos suficientes para definir a 
linguagem portuguesa. 
II) Essa afirmação é verdadeira, visto que qualquer número natural é uma justaposição 
dos dígitos de 0 a 9, ou seja, os elementos de Dígitos { }0,1, 2,3,4,5,6,7,8,9= são 
suficientes para compor qualquer número natural. 
III) Essa afirmação é falsa, uma vez que o conjunto Dígitos* contém a palavra vazia ε 
que não tem significado algum no contexto dos números naturais. No entanto, observe 
que 008=8, 00075=75 no contexto do conjunto dos naturais. 
 
Questão 2: Para listarmos todos os subconjuntos de { }, ,A a b c= basta escrevermos o 
conjunto das partes de A, ou seja, ( ) { } { } { } { } { } { } { }{ }, , , , , , , , , , , ,P A a b c a b a c b c a b c= ∅ . 
Assim, cada elemento de ( )P A é um subconjunto de A . 
Para { }{ }, , ,T a b c D= , primeiro observamos que { },b c é um elemento de T e que b e c 
isoladamente não representam elementos de T . Da mesma forma D é um elemento de 
T , mas o fato de que { }0,1D = não nos permite concluir que 0 e 1 isoladamente sejam 
elementos de T . Dessa forma temos que: 
 ( ) { } { }{ } { } { }{ } { } { }{ } { }{ }{ }, , , , , , , , , , , , , , , ,P T a b c D a b c a D b c D a b c D= ∅ , onde { }0,1D = . 
Observe que tanto ( )P A como ( )P T possuem 32 8= elementos, uma vez que o número 
de subconjuntos de um conjunto é dado por 2n onde n é o número de elementos do 
conjunto (ver teoria dos conjuntos). 
 
 
 Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
 Questão 3: a) A T⊂ é falso, pois os elementos b e c de A não são elementos de T 
conforme discutido na questão anterior. 
 b) { },b c T⊂ é falso, pois { },b c é um elemento (e não subconjunto) de T . 
 c) { },b c T∈ é verdadeiro conforme item anterior. 
 d) 1 T∈ é falso, pois 1 isoladamente não é elemento de T . 
 e) { }0,1 T∈ é verdadeiro, pois { }0,1 D= e D é elemento de T . 
 f) { }, ,a b c A⊆ é verdadeiro, pois { }, ,A a b c= (todo conjunto está contido nele mesmo). 
 g) { },a D T⊆ é verdadeiro, pois { },a D é subconjunto de T , isto é, { },a D é elemento 
de ( )P T conforme listado na questão anterior. 
 h) D∅ ⊆ é verdadeiro, pois o conjunto vazio é subconjunto de qualquer conjunto 
(observe que { }0,1D = é um conjunto quando considerado isoladamente). 
 i) A a⊃ é falso, pois a é um elemento (e não subconjunto) de A . 
 j) { },A a c⊃ é verdadeiro, pois { },a c é subconjunto de A , isto é, { },a c é elemento de 
( )P A conforme listado na questão anterior. 
 k) { }{ } ( ), ,b c D P T∈ é verdadeiro, pois { }{ }, ,b c D é elemento de ( )P T conforme 
listado na questão anterior. 
 l) { } T∅ ∈ é falso, pois não existe o elemento { }∅ explicitado na listagem dos 
elementos de T . 
 
Questão 4: Como não foi explicitado o conjunto numérico Universo que abrange os 
valores de x , podemos supor o mais amplo possível, ou seja, � . 
a) Essa proposição significa “existe algum número x real tal que 2x x= ”. Portanto, é 
verdadeira. Basta tomar x=0 ou x=1. Podemos também resolver a equação 2x x= e obter 
esses valores como solução. A negação da mesma é ( )( )2x x x∀ ≠ que significa “para 
todo número x real temos 2x x≠ ” que, obviamente é falsa. 
b) Como a equação 2x x+ = não apresenta solução alguma (os termos x se cancelam e 
obtemos 0 2= que é uma igualdade falsa) temos que essa proposição é falsa para 
qualquer x ∈� . Sua negação é ( )( )2x x x∀ + ≠ que é verdadeira. 
c) Essa proposição é falsa, pois x x= (o valor absoluto de x é igual ao próprio x ) 
apenas para os reais não negativos, ou seja, 0x ≥ . Sua negação é ( )( )x x x∃ ≠ . 
 
Questão 5: a) ∩ =� � � é verdadeira, pois � , conjunto dos racionais, está contido em 
� , conjunto dos reais e da teoria dos conjuntos temos que A B B A A⊆ ⇒ ∩ = . 
 b) I∩ = ∅� I=irracionais é verdadeira. De fato, os conjuntos dos racionais e dos 
irracionais são disjuntos (Não existe número racional e irracional ao mesmo tempo). 
c) ( ) ( ) ( )A B C A B A C∩ ∪ = ∩ ∪ ∩ é verdadeira. Para provar a igualdade entre dois 
conjuntos, em geral, provamos a inclusão nos dois sentidos, ou seja, 
M N M N N M= ⇔ ⊆ ∧ ⊆ . Neste caso, no entanto, fica mais fácil mostrar usando 
equivalências. Assim, 
 
 Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
( ) ( )x A B C x A x B C∈ ∩ ∪ ⇔ ∈ ∧ ∈ ∪ (definição de intersecção) 
⇔ ( )x A x B x C∈ ∧ ∈ ∨ ∈ (definição de união) 
( ) ( )x A x B x A x C⇔ ∈ ∧ ∈ ∨ ∈ ∧ ∈ (distributividade do ∧ com relação ao ∨ ) 
( ) ( )x A B x A C⇔ ∈ ∩ ∨ ∈ ∩ (definição de interseção) 
( ) ( )x A B A C⇔ ∈ ∩ ∪ ∩ (definição de união). 
Portanto, ficou provado que ( ) ( ) ( )x A B C x A B A C∈ ∩ ∪ ⇔ ∈ ∩ ∪ ∩ o que nos dá 
( ) ( ) ( )A B C A B A C∩ ∪ = ∩ ∪ ∩ . Observe que foi utilizada a distributividade do ∧ com 
relação ao ∨ previamente estudado na teoria de lógica e que é provada por tabelas-
verdade. (Pode-se provar também usando diagramas de Venn) 
 d) ( )A A B B∩ ∪ = é falsa. Basta tomar um contra-exemplo: Para A={1,2,3} e B={3,4,5} 
temos ( )A A B A∩ ∪ = que é o resultado correto (verifique!). Esta propriedade da 
interseção é chamada de absorção ( A absorve A B∪ pela interseção). Também vale 
( )A A B A∪ ∩ = ( A absorve A B∩ pela união). 
e) A A∪ ∅ = é verdadeira, pois ∅ é o elemento neutro da união. 
f) A A∪ = ∅∼ é falso. Por exemplo, no universo { }1, 2,3,4,5U = , tomando { }1,2A U= ⊂ 
temos { }3, 4,5A U A= − =∼ . Sendo assim, { }1, 2,3,4,5A A U∪ = =∼ que é um resultado 
sempre válido (verifique!). 
g) A A∩ = ∅∼ é verdadeira, pois A e A∼ são disjuntos, por definição. 
h) A B B A− = − é falsa. Basta tomar A={1,2,3} e B={3,4,5} . { } { }1, 2 4,5A B B A− = ≠ = − . 
 i) { } ( ) { } { }{ },1 , 1A P A= ∅ ⇒ = ∅ é falso. Observe que ( ) { } { } { }{ }, , 1 , 1,P A = ∅ ∅ ∅ (o símbolo 
∅ é um elemento de A e também representa o conjunto vazio, subconjunto de A !). 
 
Questão 6: a) A relação vazia não relaciona elemento algum entre os conjuntos e, 
portanto não possui elementos. Assim, tanto seu domínio quanto sua imagem são vazias, 
ou seja, o conjunto ∅ . 
b) ,C < é uma notação simplificada para a endorrelação : C C< → . Nesse caso o 
primeiro elemento do par deve ser menor que o segundo e ambos estão no conjunto C . 
Assim, ,C < = { }0,1 , 0,2 , 1, 2 . Seu domínio de definição é o conjunto formado pelos 
primeiros elementos dos pares, ou seja, { }0,1 e seu conjunto imagem, pelos segundos 
elementos dos pares, ou seja, { }1,2 . 
c) A relação : A B= → relaciona os elementos que são iguais em A e B. Sendo assim, a 
mesma fica definida pelo conjunto { },a a , ou seja, o único elemento é o par ,a a . 
Portanto, seu domínio é { }a e sua imagem também é { }a . 
d) A B× é o produto cartesiano entre A e B , portanto seus elementos envolvem todos 
os pares ordenados possíveis do produto cartesiano. Neste caso { }, , ,A B a a a b× = , 
com domínio A e imagem B . 
 
 
 Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
Questão 7: Primeiro lembramos que para a representação de uma relação como matriz 
devemos ter número de linhas n igual ao número de elementos do conjunto de 
partida e número de colunas m igual ao número de elementos do contradomínio, 
gerando assim, m n⋅ posições ou células. Cada uma dessas posições da matriz contém 
um valor lógico (verdadeiro ou falso) de acordo a relação entre os elementos. Assim, se 
um elemento do conjunto de partida está relacionado com um elemento do contradomínio 
pela lei da relação colocamos V (ou 1) nessa posição. Caso contrário, colocamos F (ou 
0) nessa posição. Dessa forma, para as relações pedidas teremos as seguintes 
representações por matrizes: 
 
 
∅
a
a b
0 0
<
0
2
2
0 1
1
1
1
10
0 0
0 0 0
=
a
a b
1 0
A B×
a
a b
1 1
a) b)
c) d)
∅
a
a b
0 0
∅
a
a b
0 0
<
0
2
2
0 1
1
1
1
10
0 0
0 0 0
<
0
2
2
0 1
1
1
1
10
0 0
0 0 0
=
a
a b
1 0
=
a
a b
1 0
A B×
a
a b
1 1
A B×
a
a b
1 1
a) b)
c) d)
 
 
 
Como somente as endorrelações podem ser representadas por grafos (pois estes 
relacionam elementos de um mesmo conjunto), temos para o item b a seguinte 
representação: 
 
 
 
 
 
 
 
No grafo, cada elemento do conjunto é representado como um círculo denominado nodo 
e cada par ,x y da relação é representado por uma seta, arco ou aresta, com origem 
em x e destino em y . 
 
Questão 8: Lembrando que a dual de uma relação é a relação que se obtém trocando-
se os elementos dos pares ordenados da relação original, podemos facilmente determinar 
os pares de uma relação dual. 
a) A relação : A B∅ → tem para relação dual : B A∅ → que também é uma relação vazia 
(não contém pares ordenados). 
0
1 2
 
 Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
b) A dual da relação ,C < é a relação { }1,0 , 2,0 , 2,1 que pode ser indicada por 
,C > . 
c) A relação dual de : A B= → é a relação : B A= → definida pelo conjunto { },a a (a dual 
de uma relação de igualdade é sempre igual à relação de igualdade). 
d) A relação { }, , ,B A a a b a× = é a dual da relação { }, , ,A B a a a b× = . 
 
 
 
 
 
Diagramas de Venn: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Questão 9: a) é funcional (cada elemento de A se relaciona com zero elemento de B e, 
portanto com no máximo 1 elemento de B!), injetiva (cada elemento de B se relaciona 
com zero elemento de A e, portanto com no máximo 1 elemento de A!), não é total (o 
domínio de definição não é o conjunto A!), não é sobrejetora ( a imagem não é B!) , não é 
monomorfismo ( é injetora mas não é total), não é epimorfismo (é funcional, mas não 
sobrejetora), não é isomorfismo (não é epimorfismo, nem monomorfismo). 
b) não é funcional (0 se relaciona com 1 e 2, ou seja, mais de um elemento de B!), não é 
injetora (2 se relaciona com 0 e 1, ou seja, mais de um elemento de A!), não é total ( o 
domínio de definição não é C), não é sobrejetora ( a imagem não é C). Por conseqüência 
não é monomorfismo, nem epimorfismo e nem isomorfismo. 
c) é funcional (a se relaciona com a, ou seja, com no máximo um elemento de B), é 
injetora (o elemento a de B se relaciona apenas com o elemento a de A), é total ( domínio 
é igual a A), não é sobrejetora ( imagem não é igual a B), é monomorfismo (total e 
injetora ao mesmo tempo), não é epimorfismo ( é funcional, mas não sobrejetora) e 
portanto não é isomorfismo. 
B A
a
b
a
∅
B A
a
b
a
= B A
a
b
a
B A×B A
a
b
a
B A×
C C
1
0
>
2
1
0
2
a) b )
c) d )
 
 Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
d) não é funcional (a em A se relaciona com a e b em B, ao mesmo tempo), é injetora 
(cada elemento de B está relacionado com no máximo um elemento de A), é total 
(domínio =A), é sobrejetora (imagem=B), é monomorfismo (total e injetora), não é 
epimorfismo (não é funcional) e finalmente não é isomorfismo. 
 
 
Parte 2 
 
 
Questão 1: a) é função parcial, pois vimos que é funcional (cada elemento de A se 
relaciona com zero elemento de B e, portanto com no máximo 1 elemento de B!), é função 
parcial injetora (cada elemento de B se relaciona com zero elemento de A e, portanto com 
no máximo 1 elemento de A!), não é função parcial sobrejetora ( a imagem não é B!) , 
não é monomorfismo ( é injetora mas não é total), não é epimorfismo (é funcional, mas 
não sobrejetora), não é isomorfismo (não é epimorfismo, nem monomorfismo). Seu 
domínio e sua imagem são vazias, ou seja, o conjunto ∅ . Observe que essas 
conclusões já foram obtidas na questão 10 da lista 1 item a, mas olhando como relação. 
b) é função total, pois é funcional e é total (a se relaciona com a, ou seja, com no 
máximo um elemento de B e o domínio é igual a A), é função injetora (o elemento a de B 
se relaciona apenas com o elemento a de A), não é função sobrejetora ( imagem não é 
igual a B), é monomorfismo (total e injetora ao mesmo tempo), não é epimorfismo ( é 
funcional, mas não sobrejetora) e portanto não é isomorfismo. Seu domínio é { }a e sua 
imagem também é { }a . Essas conclusões também já foram obtidas na questão 10 item c 
da lista anterior. 
c) não é função parcial, pois não é funcional (a em A se relaciona com a e b em B, 
ao mesmo tempo), não sendo função parcial então não pode ser função total (por 
definição). Sendo assim, as outras características só podem ser definidas em termos de 
relações como foi visto no item d da questão 10 da lista 1, ou seja, é relação injetora 
(cada elemento de B está relacionado com no máximo um elemento de A), é relação 
sobrejetora (imagem=B), é relação de monomorfismo (relação total e injetora), não é 
relação de epimorfismo (não é funcional) e finalmente não é relação de isomorfismo. O 
domínio é A e a imagem é B , enquanto relações. 
 d) não é função parcial, pois não é funcional (0 se relaciona com 1 e 2, ou seja, 
mais de um elemento de B!), não é função total pois não é parcial. Mas uma vez as 
outras características são definidas em termos de relações. Assim, é relação injetora (2 se 
relaciona com 0 e 1, ou seja, mais de um elemento de A!), não é relação total ( o domínio 
de definição não é C), não é relação sobrejetora ( a imagem não é C). Por conseqüência 
não é relação de monomorfismo, nem de epimorfismo e nem de isomorfismo. Seu 
domínio é o conjunto { }0,1 e sua imagem, o conjunto{ }1,2 , enquanto relações. Compare 
com item b da questão 10 da lista 1. 
e) é função parcial, pois é funcional. Não é função total, pois o domínio não é C. 
Além disso, enquanto função parcial é injetora, sobrejetora, não monomorfismo (injetora, 
mas não total), é epimorfismo (funcional e sobrejetora) e não é isomorfismo. Seu domínio 
é { }0,1 e sua imagem é { },a b . 
 
 
 Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
Questão 2: Porque para elementos da forma ,0x ∈ ×� � , teremos ,0
0
xdiv x = e 
elementos dessa forma (frações com denominadores nulos) não pertencem a � 
(contradomínio da função parcial ,div x y ). Assim, :div × →� � � não é total porque seu 
domínio não abrange todos os pares de ×� � . Observe que, no entanto, sua imagem é 
� e esta função é injetora, sobrejetora,epimorfismo (funcional e sobrejetora) e não 
monomorfismo (não é total). 
Para exemplificar vejamos alguns possíveis pares que satisfazem :div × →� � � : 
1
1 2 0 1 31,2 , 2,4 , 0,4 , 3,0 ?, 0,0 ?, , 2
2 4 4 3 2
→ → → → → → , onde as interrogações 
indicam que não há elementos em � que se relacionem. 
 
Questão 3: Dados { }A a= , { },B a b= e { }0,1, 2C = , use diagramas de Venn para 
determinar a composição das funções parciais { }0, , 1, :a b C B→ e : B A= → . 
Como B é contradomínio da função parcial { }0, , 1,a b e domínio da função parcial = , 
então podemos montar somente a composição: 
 { }0, , 1, :a b C A= →� 
Assim, primeiro consideramos os pares de { }0, , 1,a b e em seguida o único par de = 
que é ,a a para concluímos os pares de { }0, , 1, :a b C A= →� . 
Em diagramas: 
 
 
 
 
 
 
 
 
 
 
 
 
 
Logo temos que a função parcial { }0, , 1, :a b C A= →� tem como elemento apenas o 
par 0,a . 
 
Questão 4: a) ,≤� é reflexiva, pois para todo n ∈� temos n n≤ (satisfazendo a 
definição de reflexibilidade!). Não é irreflexiva, pois todo elemento de � se relaciona 
com ele mesmo. Não é simétrica, pois existem elementos 1n , 2n ∈� tais que 1 2n n≤ não 
implica 2 1n n≤ (basta tomar, por exemplo, 1 e 2). É anti-simétrica, pois para quaisquer 
B A
a
b
a
=C
1
0
2
{ }0, , 1,a b
{ }0, , 1,a b= �
B A
a
b
a
=C
1
0
2
{ }0, , 1,a b
{ }0, , 1,a b= �
 
 Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
1n , 2n ∈� temos que 1 2 2 1 1 2n n n n n n≤ ∧ ≤ ⇒ = . É transitiva, pois para quaisquer 1n , 
2 3,n n ∈� temos que 1 2 2 3 1 3n n n n n n≤ ∧ ≤ ⇒ ≤ (por exemplo, 1 2 2 3 1 3≤ ∧ ≤ ⇒ ≤ ). 
b) Lembrando que 2 :A A A→ onde { }0,1,2A = equivale ao produto cartesiano 
{ }0,0 , 0,1 , 0, 2 , 1,0 , 1,1 , 1, 2 , 2,0 , 2,1 , 2, 2A A× = , observamos que é reflexiva 
(todo elemento se relaciona com ele mesmo), não é irreflexiva (existem elementos que 
se relacionam com ele mesmo), é simétrica, pois ,a b A∀ ∈ tem-se aRb bRa→ (por 
exemplo, 0,1 e 1,0 A A∈ × ). Não é anti-simétrica, pois aRb e bRa não implica a b= 
(por exemplo, 0 1R , 1 0R em A A× e, no entanto 0 1≠ ). É transitiva, pois para cada par de 
elementos , , ,a b b c A A∈ × temos que o par ,a c também pertence a A A× . 
c) ( ) ,P A ⊆ é reflexiva (todo elemento de ( )P A está contido nele mesmo), não é 
irreflexiva (existem elementos de ( )P A que estão contidos neles mesmos), não é 
simétrica (obviamente, ( ),X Y P A∈ e X Y⊆ não implica que Y X⊆ ), é anti-simétrica, 
pois X Y Y X X Y⊆ ∧ ⊆ ⇒ = e é transitiva, ou seja, X Y Y Z X Z⊆ ∧ ⊆ ⇒ ⊆ . 
d) ( ) ,P A ⊂ é não reflexiva, pois ⊂ significa contido propriamente, ou seja, não permite 
X X⊂ . É irreflexiva, pois para todo ( )X P A∈ , X X⊄ . Não é simétrica (mesmo motivo 
do item c). É anti-simétrica, pois não ocorre X Y Y X⊂ ∧ ⊂ simultaneamente o que leva 
a implicação X Y Y X X Y⊂ ∧ ⊂ ⇒ = a ser verdadeira (condicional do tipo F F→ é V ). É 
transitiva, por motivo similar ao do item anterior. Nesse caso, X Y Y Z X Z⊂ ∧ ⊂ ⇒ ⊂ . 
e) ,X = é reflexiva (óbvio), é não irreflexiva (também óbvio), é simétrica (na relação 
de igualdade os elementos dos pares são iguais e, portanto podem ser invertidos, 
mantendo-se a relação) é anti-simétrica (se trocamos a ordem na igualdade a mesma é 
mantida). É transitiva (óbvio). 
f) ,X ≠ Não é reflexiva, mas é irreflexiva (óbvio). É simétrica ( a b b a≠ ⇒ ≠ ). Não é 
anti-simétrica, pois a b≠ , b a≠ e a não é igual a b . Não é transitiva, pois a b≠ e 
b a≠ , mas a a= . 
 
Questão 5: Fecho reflexivo: é a união de R com o conjunto { }, /a a a A∈ . Em outras 
palavras, “forçamos” (estendemos) a relação R a ser reflexiva, introduzindo os pares (e 
somente esses) que garantem a reflexibilidade de R . Como em R não existe nenhum par 
da forma ,a a introduziremos todos os que podem ser obtidos a partir de A . Assim, 
FECHO-{reflexiva} (R) = { }, 1,2 , 1,5 , , 2,3 , , 3,4 , ,1,1 2,2 3,3 4,4 5,5 . 
Fecho simétrico: é a união de R com o conjunto { }, / ,b a a b R∈ . Em outras palavras, 
“forçamos” (estendemos) a relação R a ser simétrica, introduzindo os pares (e somente 
esses) que garantem a simetria de R . Como em R não existem “pares simétricos” 
introduziremos para cada par ,a b presente em R o seu respectivo simétrico ,b a . 
Assim, 
FECHO-{simétrica} (R) = { }1, 2 , 1,5 , , 2,3 , , 3, 4 , ,2,1 3,2 4,3 5,1 
 
Fecho transitivo: O FECHO-{transitivo} (R) é construído como segue: 
 
 Universidade do Estado da Bahia – UNEB 
 Gerência de Educação a Distância - GEAD 
 Cursos de Licenciatura a Distância 
 
 
 
i) Se a,b R∈ , então a,b ∈ FECHO-{transitivo} (R) (ou seja, os elementos de R são 
todos mantidos) 
ii) Se a,b ∈ FECHO-{transitiva} (R) e b,c ∈ FECHO-{transitivo} (R), então a,c ∈ 
FECHO-{transitivo} (R) (“forçamos” a transitividade apenas para pares da forma a,b e 
b,c presentes em R . 
iii) Os únicos elementos de FECHO-{transitiva} (R) são os construídos como acima. 
Essa definição é denominada definição indutiva ou definição recursiva que foi 
trabalhada na atividade da pesquisa 1: Indução e recursão. O FECHO-{transitiva} (R) 
também é denotado por R+ . Assim, 
FECHO-{transitiva} (R) = { }R 1,2 , , , 1,5 , 2,3 , , 3,4+ = 1,3 1,4 2,4 
Observe que o par 1,4 surge como conseqüência do surgimento do par 1,3 que 
juntamente com o par 3,4 R∈ permite o aparecimento de 1,4 em R+ . 
 
Fecho reflexivo e transitivo: É a junção dos fechos reflexivos e transitivos. Assim, 
FECHO-{reflexiva, transitiva} (R) = 
{ }R , 1,2 , , , 1,5 , , 2,3 , , , 3,4 , ,∗ = 1,1 1,3 1,4 2,2 2,4 3,3 4,4 5,5 . 
 
Questão 6: a) ,≤� é de ordem parcial ampla, pois é reflexiva, anti-simétrica, e 
transitiva (propriedades que definem uma ordem parcial ampla!). Também é conexa, 
pois para a,b , a b b a a b∀ ∈ ≤ ∨ ≤ ∨ =� (observe a definição de relação conexa). Sendo 
assim, mais geralmente ela é de ordem conexa ampla. 
b) Lembrando que 2 :A A A→ onde { }0,1,2A = equivale ao produto cartesiano 
{ }0,0 , 0,1 , 0, 2 , 1,0 , 1,1 , 1, 2 , 2,0 , 2,1 , 2, 2A A× = , observamos que não é de 
ordem parcial ampla (não é anti-simétrica), nem é de ordem parcial estrita (não é 
irreflexiva, nem anti-simétrica). Sendo assim, não pode ser conexa ampla nem conexa 
estrita. No entanto, é conexa, pois satisfaz a definição de conexidade que diz que 
a,b A, aRb bRa a b∀ ∈ ∨ ∨ = . 
c) ( ) ,P A ⊆ é de ordem parcial ampla, pois é reflexiva, anti-simétrica, e transitiva 
(propriedades que definem uma ordem parcial ampla!). Observe que é não conexa! 
d) ( ) ,P A ⊂ é de ordem parcial estrita, pois é irreflexiva, anti-simétrica, e transitiva 
(propriedades que definem uma ordem parcial estrita!). Também não é conexa. 
e) ,X = é de ordem parcial ampla. Observe que não é conexa (a menos que X seja 
unitário!). 
f) ,X ≠ Não é de ordem parcial nem ampla nem estrita (não é anti-simétrica). Mas é 
conexa.