questionario de redes

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.

Simétrico
Reflexivo
Transitivo

R
Não
Não
Não

S
Sim
Não
Não

R‫׫‬S
Não
Sim
Não

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
2) ሺ‫ݕ ,ݔ׌‬ሻ ൫ሺ‫ݕ ,ݔ‬ሻ ‫ ٿ ܴ ב‬ሺ‫ݔ ,ݕ‬ሻ ‫ܴ א‬൯, neg 1
3) ሺ‫ݔ ,ݕ‬ሻ ‫ ,ܴ ב‬def de ‫.׎‬
4) ሺ‫ݕ ,ݔ‬ሻ ‫ ٿ ܴ ב‬ሺ‫ݔ ,ݕ‬ሻ ‫ ,ܴ א‬Particularização Existencial (PE) de 2
5) ሺ‫ݕ ,ݔ‬ሻ ‫ ٿ ܴ ב‬ሺ‫ݔ ,ݕ‬ሻ ‫ ٿ ܴ א‬ሺ‫ݔ ,ݕ‬ሻ ‫ ,ܴ ב‬conjunção 3 e 4
6) contradição
Transitividade: R é transitiva.
Prova (por contradição):
1)‫ ׽‬ሺ‫ݖ ,ݕ ,ݔ׊‬ሻ ሺ‫ ݖܴݕ ٿ ݕܴݔ‬՜