Estudante

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 grafos orientados 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 Reflexivo Transitivo

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 R ser 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 (por contradiçã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 5