Estruturas Discretas - Unidade v - Relações - 2015

8/15/2019 Estruturas Discretas - Unidade v - Relações - 2015

1/8

ESTRUTURAS DISCRETAS - PROF: Carlos Augusto Ribeiro

UNIDADE V – RELAÇÕES

5.1. PRODITO CARTESIANO

Dados dois conjuntos A e B, não vazios, chama-se produto cartesiano de A por B o

conjunto formado por todos os “pares ordenados” (x, y) com x ∈ A e y ∈ B

!epresenta-se por A x B ("#-se$ “A cartesiano B” ) e sim%o"icamente temos$

A x B= { ( x , y )/ x∈ A e x∈B }

Exemplo: &ejam A ' -, *, + e B ' , .emos$

A x B '

/r0fico 1artesiano$

x

OBSERVAÇÕES:

1!" &e A ≠ B, então A x B ≠ B x A ( o produto cartesiano não 2 comutativo)

#!" &e A ' ∅ ou B ' ∅ , define-se A x B ' ∅

$!" 3 produto cartesiano A x A 2 indicado por A e 2 chamado de 4uadrado 1artesiano

&im%o"icamente A2= {( x , y )/ x , y∈ A }

5x$ &e A ' a, %, então A '

%!" &e os conjuntos A e B t#m respectivamente m e & e"ementos, o produto cartesiano Ax B tem m.& e"ementos e o 6uadrado cartesiano A tem m# e"ementos

5!" 1hama-se p'o()*o +,'*e,&o de & conjuntos A+, A, A7, , An , o conjunto cujos

e"ementos são todas as n-up"as (x+, x, x7, , xn), com x+∈ A+, x

∈ A , , xn

∈ An &im%o"icamente$

Página 1


2/8

A1 x A2 x A3 x … x A n={( x1 , x2, x3, … , xn)/ x1∈ A1, x2∈ A2 … , xn∈ An }

5x$ &ejam os conjuntos A ' +, , B ' ,7) e 1 '7,,8 Determine A x B x 1

5.#. RELAÇ/O BIN0RIA

1hama-se relação binária de A em B todo su%conjunto ! de A x B

R 'el,23o 4&', (e A em B ⇔ R⊂ A x B

A defini9ão esta%e"ece 6ue toda re"a9ão 2 um conjunto de pares ordenados

:ara indicar 6ue o par (x, y) pertence ; re"a9ão !, escrevemos x R ( "# < se$ “ x

re"aciona-se com y se=undo !) &e (x, y) ∉ !, escrevemos x ! y

3s conjuntos A e B são denominados, respectivamente, conjunto de partida e

conjunto de chegada da re"a9ão !

Exemplo:

," Dados os conjuntos A ' -+, *, +, , 7 e B ' *, ,

1omo 6ua"6uer su%conjunto de A x B 2 uma re"a9ão de A em B, então são exemp"os

de re"a9>es$

! + ' (-+, *), (, ), (7,*)

! ' (*, *)

! 7 ' (-+,*), (-+,), (-+,), (*,*), (+,+), (,)

! 8 '∅

4" &e A ' , 7, , 8 e B ' +, 7, 8 , 6uais são os e"ementos da re"a9ão

R= {( x , y )∈ A x B/ x


3/8

(" 4uais são os e"ementos da re"a9ão %in0ria ! ' (x, y) ∈ZxZ / x+ y=0

5.$. RELAÇ/O BIN0RIA E6 U6 CON7UNTO

4uando A ' B e ! 2 uma re"a9ão %in0ria de A em B, diz-se 6ue ! 2 uma relação

sobre A, ou ainda, ! 2 uma relação em A

Exemplo: 4uais são os e"ementos da re"a9ão %in0ria em A ' +, , 7 dada pe"adescri9ão x ! y ⇔ x @ y 2 par

5.%. PROPRIEDADES

ma re"a9ão %in0ria em um conjunto A pode ter determinadas propriedades

Destaca-se a se=uir as principais$

," Re8lex9,: Diz-se 6ue ! 2 ref"exiva se todo e"emento de A se re"aciona consi=omesmo

(∀ x )( x∈ A⇒ xRx)

5xemp"os$

CA re"a9ão ! ' (a, a), (a, %), (a, c), (%, %), (%, c), (c, c) so%re A ' a, %, c

A re"a9ão ! em dada pe"a descri9ão x ! y ⇔ x ≤ y

4" Sm*'+,: Diz-se 6ue ! 2 sim2trica 6uando, estando x re"acionado com y, temostam%2m y re"acionado com x

(∀ x , y∈ A )( xRy⇒ yRx )

5xemp"os$

C A re"a9ão ! ' (a, a), (a, %), (%, a), (%, %) so%re A ' a, %, c

C A re"a9ão ! de perpendicu"aridade definida so%re o conjunto A das retas do espa9o

Página 3


4/8

+" T',&*9,: Diz-se 6ue ! 2 transitiva 6uando, estando x re"acionado com y e yre"acionado com z, então x est0 re"acionado com z

(∀ x , y , z∈ A )( xRy e yRz⇒ xRz )

5xemp"os$

C A re"a9ão ! ' (a, a), (a, %), (%, c),(a, c), (%, %)so%re A 'a, %, c

C A re"a9ão ! de seme"han9a definida so%re o conjunto A dos triEn=u"os do espa9o

(" A&*-m*'+,: Diz-se 6ue ! 2 anti-sim2trica 6uando, dados dois e"ementos distintos

x, y ∈ A, então x não se re"aciona com y ou y não re"aciona com x

(∀ x , y∈ A )( x ≠ y⇒ xRy ou yRx)

56uiva"entemente, diz-se 6ue ! 2 anti-sim2trica 6uando est0 satisfeita a condi9ão$

(∀ x , y∈ A )( xRy e yRx⇒ x= y )

5xemp"os$

C A re"a9ão ! ' (a, a), (%, %), (a, %), (a, c) so%re A ' a, %, c

C A re"a9ão de divisi%i"idade so%re F

5.5. E;ERC


5/8

+" &e uma re"a9ão ! em A 2 anti-sim2trica e se (a, %) e (%, a) pertencem a !, o 6ue tem6ue ser verdadeH

(" A re"a9ão ! ' (+, ) 2 transitivaH

=$. .este cada re"a9ão %in0ria no conjunto dado A para ver se 2 ref"exiva, sim2trica,

anti-sim2trica ou transitiva

," A ' FG x!y ⇔ x@y 2 par 4" A ' @ G x!y ⇔ x | y c) A = {0, 1}; x!y ⇔ x

= y2 d) A = conj. de todas as retas no pano; x!y ⇔ x ! paraea a y

o" coincide co# y

=%. :ode uma re"a9ão so%re um conjunto A ≠∅ ser sim2trica e anti-sim2tricaH :ode

uma re"a9ão so%re A não ser sim2trica nem anti-sim2tricaH Iustifi6ue

=5. &ejam A e B dois conjuntos com m e n e"ementos, respectivamente Determine onJmero de re"a9>es de A em B

5.>. RELAÇÕES DE E?UIVAL@NCIA

5.>.1. DEFINIÇ/O:

ma re"a9ão ! so%re um conjunto A não vazio 2 chamada relação de

equivalência sobre A se, e somente se, ! 2 ref"exiva, sim2trica e transitiva, isto 2, se são

verdadeiras as senten9as$

i) (∀ x )( x∈ A⇒ xRx) ii)

(∀ x , y∈ A )( xRy⇒ yRx ) iii)

(∀ x , y , z∈ A )( xRy e yRz⇒ xRz )

Exemplo:

," A re"a9ão ! ' (a, a), (%, %), (c, c), (a, c), (c, a) 2 uma re"a9ão de e6uiva"#nciaem A ' a, %, c

4" &eja . o conjunto de todos os triEn=u"os no p"ano A re"a9ão ! em . definida por “ x 2 seme"hante a y” 2 uma re"a9ão de e6uiva"#ncia em .

+" &eja A o conjunto de todas as retas do p"ano A re"a9ão ! em A definida por

“ x 2 para"e"a a y”, isto 2, “x KK y” ( x ' y ou x ∩ y ' ∅ ) 2 uma re"a9ão de

e6uiva"#ncia em A

(" A re"a9ão ! em definida definida pe"a senten9a ” 5|( x− y ) ” 2 uma re"a9ão

de e6uiva"#ncia em

Página $


6/8

e" A re"a9ão de i=ua"dade so%re % ( x!y ⇔ x ' y )

5.>.#. CLASSES DE E?UIVAL@NCIA

&eja ! uma re"a9ão de e6uiva"#ncia so%re A Dado a ∈ A, chama-se classe

de equivalência determinada por a, módulo R, o su%conjunto á de A contitudo

pe"os e"ementos x tais 6ue x!a 5m sm%o"os$ á={ x∈ A / xRa }

OBSERVAÇ/O: 3 conjunto das c"asses de e6uiva"#ncia mLdu"o ! ser0 indicado porAR e chamado conjunto quociente de A por R.

Exemplo: Fa re"a9ão de e6uiva"#ncia ! ' (a, a), (%, %), (c, c), (a, c), (c, a) temos$

á ' a, cG b́=¿ %G ć ' c, a e AK! ' a, c, %

5.. RELAÇÕES DE ORDE6

5..1. DEFINIÇ/O: ma re"a9ão ! so%re um conjunto A não vazio 2 chamada relação de ordem

sobre A se, e somente se, ! 2 ref"exiva, anti-sim2trica e transitiva, isto 2, se são

verdadeiras as senten9as$

i) (∀ x )( x∈ A⇒ xRx) ii)

(∀ x , y∈ A )( xRy e yRx⇒ x= y)

iii) (∀ x , y , z∈ A )( xRy e yRz⇒ xRz )

Exemplo:

A re"a9ão ! de divisi%i"idade so%re F$ x!y ⇔ x| y 2 uma re"a9ão de ordem pois$

(&x) ( x ∈ N ⇒ x| x )

(&x, y ∈ F) ( x| y e y| x⇒ x= y¿

(&x, y, z ∈ F) ( x| y e y| z⇒ x| z¿

4uando ! 2 uma re"a9ão de ordem so%re A, para exprimirmos 6ue (a, %) ∈ !

usaremos a nota9ão , ≼ 4 R", 6ue se "#$ “ a precede % na re"a9ão !”

Página '


7/8

:ara exprimirmos 6ue (a, %) ∈ ! e a ≠ % usaremos a nota9ão ,≺ 4 R", 6ue

se "#$ “ a precede estritamente % na re"a9ão !”

5..#. ELE6ENTOS CO6PAR0VEIS ORDE6 TOTAL ORDE6 PARCIAL

&eja A um conjunto so%re o 6ua" se definiu uma re"a9ão de ordem ≼ ( A, () Dois

e"ementos , e 4 de A dizem-se comparáveis 6uando se tem a ≼ % ou b≼ a &e

todos os e"ementos de A são dois a dois compar0veis, diz-se 6ue ≼ 2 uma relação de

ordem total so%re A ou 6ue A 2 um conjunto totalmente ordenado pe"a re"a9ão de

ordem≼; e se nem todos os e"ementos de A são dois a dois compar0veis, diz-se 6ue ≼

2 uma relação de ordem parcial so%re A ou 6ue A 2 um conjunto parcialmente

ordenado pe"a re"a9ão de ordem≼

Exemplo:

," A re"a9ão ! de ordem so%re % definida por x!y ⇔ x ≤ y 2 uma re"a9ão de ordem

tota", denominada ordem ha%itua", pois$

(∀ x )( x∈ R⇒ x ≤ x)

(∀ x , y∈ R )( x ≤ y e y ≤ x⇒ x= y )

(∀ x , y , z∈ R )( x ≤ y e y ≤ z⇒ x ≤ z)

(&x, y) ( x , y∈ R⇒ x ≤ y ou y ≤ x)

4" A re"a9ão ! de divisi%i"idade so%re F$ x!y ⇔ x| y 2 uma re"a9ão de ordem parcia"

5.. E;ERCes de e6uiva"#ncia so%re A ' a, %, cH! + ' (a, a), (a, %), (%, a), (%, %), (c, c)

! ' (a, a), (a, %), (%, a), (%, %), (%, c)

! 7 ' (a, a), (%, %), (%, c), (c, %), (a, c), (c, a)

! ' AxA

=#. 4uais das se=uintes re"a9>es definem uma re"a9ão de e6uiva"#ncia em F H

a) x!y ⇔ ∃ M ∈Z K x < y ' 7M %) x| y c) x ≤ y d) x @ y ' +*

Página )


8/8

=$. :ara a re"a9ão de e6uiva"#ncia! ' (+,+), (, ), (+, ), (,+), (+, 7), (7, +), (7,), (,7), (7,7), (, ), (8,8), (, 8), (8, )

Determine o conjunto 3́ e 4́

=%. &eja A ' x ∈Z K * ≤ x ≤10 e ! a re"a9ão so%re A definida por

x!y ⇔ * M ∈Z K x-y ' M Determinar o conjunto-6uociente AK!

=5. &eja A ' +, , 7$a) Determine uma re"a9ão de e6uiva"#ncia ! em A com cinco e"ementos

%) Determine 1́ , 2́e 3́ para essa re"a9ão

c) Determine o conjunto 6uociente AR para essa re"a9ão

=>. Nerifi6ue se a re"a9ão ! definida por x!y ⇔ y| x

2 uma re"a9ão de ordem tota"

so%re o conjunto A ' , , O, , n,

=. Dizer se cada um dos se=uintes su%conjuntos de F 2 ou não tota"mente ordenado pe"a re"a9ão de divisi%i"idade$

a) , , ? %) 7, +8, 8 c) +8, 8 , 7* d) F

Página +

Documents

Estruturas Discretas - Unidade v - Relações - 2015