Lista de Exercícios Matematica Discreta - Relacoes UFMG

Lista de Exercícios 8 Relações UFMGICExDCC DCC111 Matemática Discreta Ciências Exatas Engenharias 2o Semestre de 2014 Definição 1 Composição de relações Seja R uma relação do conjunto A para um conjunto B e S uma relação do conjunto B para um conjunto C A composição de R e S é a relação formada por pares ordenados a c onde a A c C para os quais existe um elemento b B tal que a b R e b c S A composição de R e S é representada por S R Definição 2 Relação Irreflexiva Seja R uma relação definida no conjunto A Uma relação R é chamada irreflexiva se a A a a R Definição 3 Relação Assimétrica Seja R uma relação do conjunto A para um conjunto B Uma relação R é chamada assimétrica se a b R então b a R Nesse sentido uma relação assimétrica é antisimétrica e irreflexiva Definição 4 Relação Complementar Seja R uma relação do conjunto A para um conjunto B A relação complementar R é o conjunto de pares ordenados a ba b R Lista de Relações As relações abaixo estão definidas no conjunto 1 2 3 4 A R1 2 2 2 3 2 4 3 2 3 3 3 4 B R2 1 1 1 2 2 1 2 2 3 3 4 4 C R3 2 4 4 2 D R4 1 2 2 3 3 4 E R5 1 1 2 2 3 3 4 4 F R6 1 3 1 4 2 3 2 4 3 1 3 4 1 Como foi dito na introdução do material de relações o mundo está povoado por relações família emprego governo negócios etc O exemplo abaixo mostra isso Antes de começar uma reunião sobre o relacionamento entre duas empresas parceiras num determinado negócio dois homens começam uma conversa onde um deles fala sobre sua relação familiar A seguir está o relato o que esse homem fez Há alguns anos atrás eu conheci uma jovem viúva com uma filha já nos seus quase 20 anos Nós nos casamos Mais tarde meu pai se casou com minha enteada Depois disso minha enteada teve um filho Isso não foi nada até minha esposa e eu termos um filho Apresente um diagrama que mostre as relações dessa estória bizarra Este é apenas um exercício de curiosidade 2 Determine se cada relação da lista de relações acima é a Reflexiva b Irreflexiva c Simétrica d Antisimétrica e Assimétrica f Transitiva g Relação de equivalência 1 h Relação de ordem parcial 3 Determine a relação R para cada relação da lista de relações acima 4 Determine se cada relação R da lista de relações acima é a Reflexiva b Irreflexiva c Simétrica d Antisimétrica e Assimétrica f Transitiva 5 Determine a composição das relações Ri R2 i 1 6 6 Seja A 2 3 4 5 6 7 8 e defina a relação binária R em A como x y A xRy xy Desenhe o grafo dirigido da relação R 7 Seja A 2 4 e B 6 8 10 e defina as relações binárias R e S como x y A B xRy xy x y A B xSy y 4 x Liste os pares ordenados que estão em A B R S R S R S 8 Mostre se a relação binária D é reflexiva simétrica transitiva Seja a relação D definida sobre R como x y R xDy xy 0 9 Determine se a relação R no conjunto de todas as páginas Web é reflexiva simétrica antisimétrica e transitiva onde x y R sse a Todas as pessoas que visitam a página Web x também visitam a página Web y b Não existem links comuns na página Web x e na página Web y c Existe pelo menos um link em comum na página Web x e na página Web y d Existe uma página Web que inclui links para a página Web x e para a página Web y 10 Qual é a composição das relações R e S onde R é a relação de 1 2 3 para 1 2 3 4 com R 1 1 1 4 2 3 3 1 3 4 e S é a relação de 1 2 3 4 para 0 1 2 com S 1 0 2 0 3 1 3 2 4 1 11 Seja o conjunto A 0 1 Quantas relações binárias distintas podem ser definidas sobre o conjunto A 12 Liste as relações do exercício 13 Determine se cada relação do exercício é a Reflexiva b Irreflexiva c Simétrica d Antisimétrica e Assimétrica f Transitiva 14 Determine a relação complementar das relações do exercício 15 Considere as relações dos exercícios e Faça uma tabela como a que está abaixo indicando se cada uma das seis propriedades é verdadeira ou falsa Utilizando essa tabela tente estabelecer uma relação entre as propriedades de R e de R 2 Propriedades de R Propriedades de R Relação Reflexiva Irreflexiva Simétrica Antisimétrica Assimétrica Transitiva Reflexiva Irreflexiva Simétrica Antisimétrica Assimétrica Transitiva 1 n 16 Quantas relações binárias existem em um conjunto com n elementos que são a Simétricas b Antisimétricas c Assimétricas d Irreflexivas e Reflexivas e simétricas f Nem reflexivas nem irreflexivas 17 Liste os pares ordenados nas relações de equivalência produzidos pelas partições do conjunto 0 1 2 3 4 5 a 0 1 2 3 4 5 b 0 1 2 3 4 5 c 0 1 2 3 4 5 3