7ª Lista de Exercícios - Fundamentos de Matemática para Computação

UFG Instituto de Informática Fundamentos de Matemática para Computação CCESSI Professores Erika Coelho Elisângela Silva Dias e Julliano Rosa Nascimento1 7a Lista de Exercícios 20212 Relações 1 Liste os pares ordenados na relação R de A 1 2 3 4 5 para B 0 1 2 3 em que a b R se e somente se a a b b a b 4 c a b d ab e mdca b 1 f mmca b 2 2 Seja A o conjunto A 1 2 3 e as relações R 1 3 2 1 3 2 e S 1 2 2 3 em A Determine a S R b R S c R R d S S e S R1 f R1 g S1 3 Para cada uma destas relações no conjunto 1 2 3 4 decida se ela é reflexiva se é simétrica se é antissimétrica e se é transitiva a 2 2 2 3 2 4 3 2 3 3 3 4 b 1 1 1 2 2 1 2 2 3 3 4 4 c 2 4 4 2 d 1 2 2 3 3 4 e 1 1 2 2 3 3 4 4 f 1 3 1 4 2 3 2 4 3 1 3 4 4 Determine se a relação R no conjunto de todos os números inteiros é reflexiva simétrica antissimétrica eou transitiva em que x y R se e somente se a x y b x é um múltiplo de y c x e y são ambos negativos ou ambos não negativos d xy 1 5 Para cada item exiba um exemplo de relação sobre 1 2 3 4 que satisfaça as propriedades mencionadas a reflexiva simétrica não antissimétrica e não transitiva b reflexiva não simétrica antissimétrica e não transitiva c reflexiva não simétrica não antissimétrica e transitiva d não reflexiva simétrica não antissimétrica e transitiva e não reflexiva não simétrica antissimétrica e transitiva 6 Seja a relação R a b ab no conjunto dos inteiros positivos Encontre a R1 b R 7 Sejam as seguintes relações no conjunto dos números inteiros R1 a b a b R2 a b a b R3 a b a b R4 a b a b R5 a b a b R6 a b a b Determine 1email erikacoelho elisangelasd jullianonascimentoufgbr a R2 R4 b R3 R6 c R6 R3 d R3 R6 e R6 R3 f R2 R1 g R2 R2 h R3 R5 8 Sejam R S e T relações definidas em conjuntos apropriados Mostre que a S R T S T R T b S R T S R S T c S R T S T R T d S R T S R S T 9 Sendo A um conjunto qualquer e R e S relações sobre A encontre um contraexemplo para cada uma das afirmações abaixo a R R R b idA R R1 c R R é uma relação transitiva d Se S R é reflexiva então S e R são reflexivas e Se S R é reflexiva então S e R são reflexivas f Se R e S são antissimétricas R S é antissimétrica g Se S R é transitiva então S e R são transitivas h Se R e S são transitivas então R S é transitiva 10 Sendo A um conjunto qualquer e R e S relações sobre A demonstre as afirmações abaixo a idA R R b R R1 é uma relação simétrica c R R1 é uma relação antissimétrica d R é reflexiva se e somente se R1 é reflexiva e R é simétrica se e somente se R1 é simétrica f Se R é uma relação antissimétrica então R1 é antissimétrica g Se R é simétrica então R é simétrica h Se S é uma relação transitiva tal que R S então R R S 11 Responda Verdadeiro ou Falso Justifique as afirmações demonstre ou exiba um contraexemplo Sendo A um conjunto qualquer e R S duas relações sobre A a idA R1 R b Se R é reflexiva então R R R c Se R é simétrica e R S é antissimética então S é antissimética d Se R e S são transitivas então R S é transitiva 12 Encontre a inversa das seguintes relações a R a ba b b R a bab c R é a relação de todos os estados do Brasil que consiste em pares a b em que o estado a faz fronteira com o estado b 13 Quais destas relações em 0 1 2 3 são relações de equivalência Determine as propriedades de uma relação de equivalência que faltam para as outras a 0 0 1 1 2 2 3 3 b 0 0 0 2 2 0 2 2 2 3 3 2 3 3 c 0 0 1 1 1 2 2 1 2 2 3 3 d 0 0 1 1 1 3 2 2 2 3 3 1 3 2 3 3 e 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 2 3 3 14 Seja R uma relação sobre A Mostre que se R é uma relação de equivalência então R R1 R 15 S R é um poset se S for o conjunto de todas as pessoas no mundo e a b R em que a e b são pessoas se a a não é mais baixo que b b a pesa mais que b c a b ou a é um descendente de b d a e b não tem um amigo em comum 16 Quais destas relações em 0 1 2 3 são ordenações parciais Determine as propriedades de uma ordem parcial que faltam para as outras a 0 0 1 1 2 2 3 3 b 0 0 1 1 2 0 2 2 2 3 3 2 3 3 c 0 0 1 1 1 2 2 2 3 3 d 0 0 1 1 1 2 1 3 2 2 2 3 3 3 e 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 2 3 3 17 Quais destes são posets a Z b Z c Z d Z 18 Responda a estas questões para o poset X X 1 2 4 1 2 1 4 2 4 3 4 1 3 4 2 3 4 a Desenhe o diagrama de Hasse b Encontre os elementos maximais c Encontre os elementos minimais d Indique caso exista o elemento máximo e Indique caso exista o elemento mínimo f Indique quais são os elementos comparáveis e quais não são 19 Seja A 1 2 3 4 5 a Exiba todas as relações de equivalência sobre A que possuem exatamente duas classes de equivalência b Considerando R 1 4 2 1 2 2 2 4 3 1 3 2 4 3 5 5 exiba a relação R1 R c Justifique porque R não é uma relação de equivalência d Justifique porque R1 R não é uma relação de equivalência 20 Seja A 0 2 3 4 6 8 9 10 25 Considere o conjunto parcialmente ordenado A a Desenhe o diagrama de Hasse b Destaque os elementos minimais e maximais Se tiver exiba o elemento máximo eou o elemento mínimo c Indique a largura e dê um exemplo de uma anticadeia de maior comprimento d Indique a altura e dê um exemplo de uma cadeia de maior comprimento