Estudante

Disponível somente no TrabalhosFeitos
  • Páginas : 15 (3578 palavras )
  • Download(s) : 0
  • Publicado : 19 de novembro de 2012
Ler documento completo
Amostra do texto
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO - CEUNES

ALGORITMOS E FUNDAMENTOS DA TEORIA DE COMPUTAÇÃO LISTAS DE EXERCÍCIOS

Professor: Luís Otávio Rigo Alunos: André de Mattos Ferraz Eliezer de Souza da Silva Lucas Dias Serqueira Mateus Vieira Costa

Algoritmos e Fundamentos da Teoria de Computação Lista 01 1) Suponha que R = {(a; c), (c; e), (e; e), (e; b), (d; b), (d; d)}. Desenhe grafosorientados representando cada uma das seguintes relações: a) R

b) R-1

c) R

R-1

d) R

R-1

2) Sejam R e S relações binárias sobre A = {1, ... ,7} com as representações gráficas mostradas a seguir.

a) Indique se R e S são (i) simétricas, (ii) reflexivas e (iii) transitivas; b) b) Repita (a) para a relação R união S. R Não Não Não S Sim Não Não R S Não Sim Não

Simétrico ReflexivoTransitivo

3) Desenhe gráficos orientados representando relações dos seguintes tipos: a) Reflexiva, transitiva e anti-simétrica.

b) Reflexiva, transitiva e nem simétrica nem anti-simétrica.

4) Seja A um conjunto não-vazio, e que propriedades de R? Por definição (

seja o conjunto vazio. Quais são as

Reflexividade: R não é reflexiva. Prova (por contradição): 1) , , por hipótese de Rser reflexiva 2) , , def de . 3) , , Particularização Universal (PU) de 1 4) , , PU de 2 5) , , , conjunção 3 e 4 6) contradição Simetria: R é simétrica. Prova (por contradição): 1) , , , , hipótese de contradição, R não é simétrica , , , , neg 1 2) , def de . 3) , 4) , , , Particularização Existencial (PE) de 2 5) , , , , conjunção 3 e 4 6) contradição Transitividade: R é transitiva. Prova (porcontradição): 1) , , , hipótese de contradição, R não é transitiva 2) , , , Eq da implicação 1 3) , , 4) , PE 3

5) , DeMorgan 4 6) , Simplificação 5 7) , def de . 8) , conj 6, 7 9) contradição Anti-Simetria: R é anti-simétrica. Prova (por contradição): 1) , , hipótese de contradição, R não é anti-simétrica 2) , , , Eq da implicação 1 3) , , , neg 2 4) , PE 3 5) , DeMorgan 4 6) , Simplificação 57) , def de . 8) , conj 6, 7 9) contradição 5) Seja f: A -> B. Demonstre que a seguinte relação R é de equivalência em A : (a; b) somente se f(a) = f(b). Reflexiva: f(a) = f(a); Simétrica: f(a) = f(b) f(b) = f(a) Transitiva: f(a) = f(b) e f(b) = f(c) f(a) = f(c) aRb e bRc aRc 6) Seja R A x A uma relação binária, conforme definida abaixo. Em que casos R é uma relação de ordem parcial? Em que casosR _e uma relação de ordem total? a) A = os inteiros positivos; (a, b) R se, e somente se, b é divisível por a. Não é ordem total por não apresentar a relação de totalidade sobre os inteiros: nem (2,3), nem (3,2) pertencem a R. (a,a) pertence a R, portanto é reflexiva. Se a é divisível por b, então a>b ou a=b, se temos aRb e bRa, significa que (a>b ou a=b) e (b>a ou b=a), ou seja a=b, portanto R éanti-simétrico. A transitividade neste caso é trivial. Portanto R é uma ordem parcial. 7) Sejam R1 e R2 duas relações de ordem parcial quaisquer sobre o mesmo conjunto A. Demonstre que R1 R2 é uma relação de ordem parcial. Suponhamos e ordens parciais. , | , , - Reflexividade: , e , portanto , - Anti-Simetria Seja dois pares (x,y) e (y,x) pertencentes a . Comos eles pertencem a intersecção dedois conjuntos eles pertencem aos conjuntos individualmente, ou seja, , , , , , , , . Como tanto quanto são antissimétricos, concluimos que x=y, o que prova que é antissimétrico. - Transitividade: , hipotese 1. , , hipotese 2. , 3. , , simp 1 4. , , simp 1 R, se, e

5. 6. 7. 8. 9.

, , , , ,

, simp 2 , simp 2 , transitividade de R1, 3, 5 , transitividade de R2, 4, 6 , conj, 7,8 (c.q.d.)

8)a) Prove que, se S for uma coleção qualquer de conjuntos, então RS = {(A;B) : A;B uma relação de ordem parcial. i) ii) Reflexividade A Rs A porque A A Anti-Simétrica A B e B A (A,B S) x A x B ou x B x A = B Rs é anti-simétrica Transitividade A BeB C x A x B x B x C x A x C A C Rs é transtiva

S, e A

B} é

A

iii)

Rs é uma relação de ordem parcial.
, , b) Seja S = . Desenhe um grafo...
tracking img