07/08/2013 2 Diagrama de Hasse β’ 1, 2, 3, 4, 6, 8, 12 , | RELAÇÕES: DIAGRAMA DE HASSE, ELEMENTOS MAXIMAIS E MINIMAIS, RETICULADOS 8 12 4 6 2 3 Matemática Discreta Prof. João Paulo Lima Universidade Federal Rural de Pernambuco Departamento de Estatística e Informática 1 Copyright © 2006 by The McGraw-Hill Companies, Inc. All rights reserved. 3 Elementos Maximais Elementos Maximais β’ Dado o poset π, βΌ β’ Um elemento π₯ β π é maximal em π, βΌ 4 2, 4, 5, 10, 12, 20, 25 , | são maximais? β’ 12, 20 e 25 são elementos maximais β’ Ex: quais elementos do poset se não existe nenhum elemento maior que ele β’ Não existe π¦ β π tal que π₯ βΊ π¦ 12 20 4 10 2 5 25 5 Elementos Minimais Elementos Minimais β’ Dado o poset π, βΌ β’ Um elemento π₯ β π é minimal em π, βΌ nenhum elemento menor que ele 6 β’ Ex: quais elementos do poset se não existe 2, 4, 5, 10, 12, 20, 25 , | são minimais? β’ 2 e 5 são elementos minimais β’ Não existe π¦ β π tal que π¦ βΊ π₯ 12 20 4 10 2 5 25 1 07/08/2013 7 8 Maior Elemento Maior Elemento β’ Dado o poset π, βΌ β’ Ex: quais dos posets abaixo possuem maior elemento? β’ Um elemento π₯ β π é o maior elemento de π, βΌ se ele β’ Resposta: π e π for maior que todos os outros elementos β’ π¦ βΌ π₯ para todo π¦ β π β’ Quando existe, o maior elemento é único 9 10 Menor Elemento Menor Elemento β’ Dado o poset π, βΌ β’ Ex: quais dos posets abaixo possuem menor elemento? β’ Um elemento π₯ β π é o menor elemento de π, βΌ se ele β’ Resposta: π e π for menor que todos os outros elementos β’ π₯ βΌ π¦ para todo π¦ β π β’ Quando existe, o menor elemento é único 11 12 Cotas Superiores Cotas Superiores β’ Upper Bounds β’ Ex: quais são as cotas superiores dos subconjuntos β’ Dado o poset π, βΌ π, π, π , π, π e π, π, π, π no poset a seguir? β’ Dado um subconjunto π΄ de π β’ Cotas superiores de π, π, π : π, π, π, π β’ Um elemento π₯ β π é cota superior (upper bound) de π΄ se β’ Cotas superiores de π, π : nenhuma ele é maior ou igual a todos os elementos de π΄ β’ π¦ βΌ π₯ para todo π¦ β π΄ β’ Cotas superiores de π, π, π, π : π, π, π 2 07/08/2013 13 14 Cotas Inferiores Cotas Inferiores β’ Lower Bounds β’ Ex: quais são as cotas inferiores dos subconjuntos π, π, π , π, π e π, π, π, π no poset a seguir? β’ Dado o poset π, βΌ β’ Dado um subconjunto π΄ de π β’ Cotas inferiores de π, π, π : π β’ Um elemento π₯ β π é cota inferior (lower bound) de π΄ se β’ Cotas inferiores de π, π : π, π, π, π, π, π ele é menor ou igual a todos os elementos de π΄ β’ π₯ βΌ π¦ para todo π¦ β π΄ β’ Cotas inferiores de π, π, π, π : π 15 16 Menor Cota Superior Menor Cota Superior β’ Dado o poset π, βΌ β’ Ex: qual a menor cota superior do subconjunto π, π, π no poset a seguir? β’ Dado um subconjunto π΄ de π β’ Um elemento π₯ β π é a menor cota superior de π΄ se ele é β’ Cotas superiores de π, π, π : π, π uma cota superior de π΄ menor que todos as outras cotas superiores de π΄ β’ π¦ βΌ π₯ para todo π¦ β π΄ β’ π₯ βΌ π§ para todo π§ que é cota superior de π΄ β’ Quando existe, a menor cota superior é única β’ Menor cota superior de π, π, π : π 17 18 Maior Cota Inferior Maior Cota Inferior β’ Dado o poset π, βΌ β’ Ex: qual a maior cota inferior do subconjunto π, π, π no β’ Dado um subconjunto π΄ de π poset a seguir? β’ Um elemento π₯ β π é a maior cota inferior de π΄ se ele é β’ Cotas inferiores de π, π, π : π, π uma cota inferior de π΄ maior que todos as outras cotas inferiores de π΄ β’ π₯ βΌ π¦ para todo π¦ β π΄ β’ π§ βΌ π₯ para todo π§ que é cota inferior de π΄ β’ Quando existe, a maior cota inferior é única β’ Maior cota inferior de π, π, π : π 3 07/08/2013 19 20 Reticulado Reticulado β’ Dado o poset π, βΌ β’ Ex: quais dos posets abaixo são reticulados? β’ Se todo par de elementos de π possui menor cota β’ Resposta: π e π superior e maior cota inferior, então π, βΌ é um reticulado 4
Download
