{"id":636,"date":"2004-10-27T00:00:00","date_gmt":"2004-10-26T22:00:00","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"636","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/636\/","title":{"rendered":"Che cosa sono i diagrammi di Hasse, e come si costruiscono?"},"content":{"rendered":"<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Il diagramma di Hasse \u00e8 uno strumento grafico volto a<br \/>\nrappresentare relazioni di ordine tra elementi di un insieme parzialmente<br \/>\nordinato.  Rivediamo brevemente le definizioni necessarie per fornire una<br \/>\ndescrizione formale del diagramma di Hasse. <\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><br \/><\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><b>Ordinamento parziale<\/b><\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Sia <i>X<\/i> un insieme finito e <b>R<\/b> una relazione<br \/>\nbinaria definita sugli elementi di <i>X<\/i>.  Indichiamo con <i>x<\/i>,<br \/>\n<i>y<\/i>, <i>z<\/i> etc. i generici elementi di <i>X<\/i>.  <b>R<\/b> \u00e8<br \/>\ndetta <i>ordinamento parziale<\/i> sugli elementi di <i>X<\/i> se \u00e8: <\/font><\/p>\n<ul><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><\/p>\n<li>\n<p align=\"justify\"><i>riflessiva<\/i>, cio\u00e8 <i>x<\/i><b>R<\/b><i>x<\/i><br \/>\nper ogni <i>x<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/in.gif\"\/>\u00a0<i>X<\/i>;<\/p>\n<\/li>\n<li>\n<p align=\"justify\"><i>antisimmetrica<\/i>, cio\u00e8<br \/>\n<i>x<\/i><b>R<\/b><i>y<\/i> e <i>y<\/i><b>R<\/b><i>x<\/i> valgono assieme se e solo<br \/>\nse <i>x<\/i>\u00a0=\u00a0<i>y<\/i>;<\/p>\n<\/li>\n<li><i>transitiva<\/i>, cio\u00e8 ogni volta che <i>x<\/i><b>R<\/b><i>y<\/i> e<br \/>\n<i>y<\/i><b>R<\/b><i>z<\/i> si ha anche <i>x<\/i><b>R<\/b><i>z<\/i>.<\/p>\n<\/li>\n<p><\/font><\/ul>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><br \/><\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><b>Poset<\/b><\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Siano <i>X<\/i> un insieme finito e <b>R<\/b> una relazione<br \/>\nd&#8217;ordine parziale sugli elementi di <i>X<\/i>.  La coppia<br \/>\n<i>P<\/i>\u00a0=\u00a0(<i>X<\/i>,\u00a0<b>R<\/b>) \u00e8 allora detta<br \/>\n<i>insieme finito parzialmente ordinato<\/i> o <i>poset<\/i>. <\/font><\/p>\n<p align-justify=\"\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Per esempio,<br \/>\n<i>P<\/i>\u00a0=\u00a0({1,\u00a02,\u00a03,\u00a04},\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/le.gif\"\/>) \u00e8 un poset la cui relazione d&#8217;ordine definisce una<br \/>\nstruttura di ordinamento totale (cio\u00e8, dati due qualsiasi elementi<br \/>\n<i>x<\/i> e <i>y<\/i> di <i>X<\/i> vale sempre almeno una tra<br \/>\n<i>x<\/i><b>R<\/b><i>y<\/i> e <i>y<\/i><b>R<\/b><i>x<\/i>). <\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><br \/><\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><b>Copertura<\/b><\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Sia <i>P<\/i>\u00a0=\u00a0(<i>X<\/i>,\u00a0<i>R<\/i>) un poset e<br \/>\nsiano <i>x<\/i>, <i>y<\/i> e <i>z<\/i> elementi di <i>X<\/i>.  Si dice che<br \/>\n<i>y<\/i> \u00e8 una <i>copertura<\/i> di <i>x<\/i>, se si ha<br \/>\n<i>x<\/i><b>R<\/b><i>y<\/i> e non esiste alcun elemento <i>z<\/i> tale che<br \/>\n<i>x<\/i><b>R<\/b><i>z<\/i> e <i>z<\/i><b>R<\/b><i>y<\/i>. <\/font><\/p>\n<p align-justify=\"\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0In altri termini,<br \/>\n<i>y<\/i> \u00e8 una copertura di <i>x<\/i> se <i>x<\/i><b>R<\/b><i>y<\/i> e non<br \/>\nesiste alcun elemento <i>z<\/i> che si &#8220;frapponga&#8221; nella relazione di<br \/>\nordinamento tra <i>x<\/i> e <i>y<\/i>. Costruiamo per esempio un poset definendo<br \/>\nsull&#8217;insieme {1,\u00a02,\u00a03,\u00a04,\u00a05,\u00a06,\u00a07,\u00a08} la<br \/>\nrelazione <i>x<\/i><b>R<\/b><i>y<\/i>\u00a0&lt;==&gt;\u00a0<i>x<\/i> divide<br \/>\n<i>y<\/i>. Allora: <\/font><\/p>\n<ul><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><\/p>\n<li>8 \u00e8 una copertura di 4;\n<\/li>\n<li>4 \u00e8 una copertura di 2;\n<\/li>\n<li>\n<p align=\"justify\">8 non \u00e8 una copertura di 2 perch\u00e9,<br \/>\nnonostante che 2<b>R<\/b>8, esiste l&#8217;elemento 4 che si frappone tra 8 e 2 nella<br \/>\nrelazione di ordinamento parziale.\n<\/p>\n<\/li>\n<p><\/font><\/ul>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><br \/><\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><b>Diagramma di Hasse<\/b><\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Il diagramma di Hasse consente di rappresentare graficamente<br \/>\nla relazione d&#8217;ordine tra gli elementi di un poset ed \u00e8 costruito nel<br \/>\nmodo seguente: <\/font><\/p>\n<ol><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><\/p>\n<li>\n<p align=\"justify\">se <i>x<\/i> e <i>y<\/i> sono elementi di <i>X<\/i> e<br \/>\n<i>x<\/i><b>R<\/b><i>y<\/i>, allora <i>x<\/i> \u00e8 collocato nel diagramma al<br \/>\ndi sotto di <i>y<\/i>;\n<\/p>\n<\/li>\n<li>\n<p align=\"justify\">si disegna nel diagramma un segmento tra <i>x<\/i> e<br \/>\n<i>y<\/i> se e solo se <i>y<\/i> \u00e8 una copertura di <i>x<\/i>.\n<\/p>\n<\/li>\n<p><\/font><\/ol>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Il diagramma di Hasse consente di identificare la relazione<br \/>\ndi ordinamento parziale perch\u00e9 illustra graficamente la chiusura<br \/>\ntransitiva della relazione di copertura. <\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><br \/><\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><b>Esempio<\/b><\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Usiamo le definizioni date per costruire il diagramma di<br \/>\nHasse del poset costituito dall&#8217;insieme potenza di {1,\u00a02,\u00a03} e dalla<br \/>\nrelazione di sottoinsieme &#8220;<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>&#8220;.  Iniziamo<br \/>\nscrivendo l&#8217;insieme <i>X<\/i>, potenza dell&#8217;insieme {1,\u00a02,\u00a03},<br \/>\nricordando che esso ha per elementi tutti i sottoinsiemi di<br \/>\n{1,\u00a02,\u00a03} (compresi l&#8217;insieme vuoto e l&#8217;insieme {1,\u00a02,\u00a03}<br \/>\nstesso): <\/font><\/p>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<i>X<\/i>\u00a0=\u00a02<sup>{1,2,3}<\/sup>\u00a0=\u00a0<font size=\"+1\">{<\/font><img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/emptyset.gif\"\/>, {1}, {2}, {3}, {1, 2}, {2,<br \/>\n3}, {1, 3}, {1, 2, 3}<font size=\"+1\">}<\/font><\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Dimostriamo quindi che <i>P<\/i> \u00e8 un poset.  Si<br \/>\nverifica facilmente che la relazione definisce un ordinamento parziale:<br \/>\ninfatti la relazione di sottoinsieme <img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/> \u00e8:<br \/>\n<\/font><\/p>\n<ul><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><\/p>\n<li>\n<p align=\"justify\"><i>riflessiva<\/i>: per ogni <i>A<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>\u00a0{1,\u00a02,\u00a03} si ha per forza<br \/>\n<i>A<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>\u00a0<i>A<\/i>, e questo equivale<br \/>\nproprio a dire che <i>x<\/i><b>R<\/b><i>x<\/i> per ogni <i>x<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/in.gif\"\/>\u00a0<i>X<\/i>;<\/p>\n<\/li>\n<li>\n<p align=\"justify\"><i>antisimmetrica<\/i>: dire che <i>x<\/i> e <i>y<\/i> sono<br \/>\ndue elementi di <i>X<\/i> tali che <i>x<\/i><b>R<\/b><i>y<\/i> e<br \/>\n<i>y<\/i><b>R<\/b><i>x<\/i> significa parlare di due sottoinsiemi <i>A<\/i> e<br \/>\n<i>B<\/i> di {1,\u00a02,\u00a03} tali che <i>A<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>\u00a0<i>B<\/i> e <i>B<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>\u00a0<i>A<\/i>.  Questo pu\u00f2 avvenire<br \/>\nsolamente se <i>A<\/i>\u00a0=\u00a0<i>B<\/i>, cio\u00e8 se<br \/>\n<i>x<\/i>\u00a0=\u00a0<i>y<\/i>.<\/p>\n<\/li>\n<li>\n<p align=\"justify\"><i>transitiva<\/i>: dire che <i>x<\/i>, <i>y<\/i> e <i>z<\/i><br \/>\nsono elementi di <i>X<\/i> tali che <i>x<\/i><b>R<\/b><i>y<\/i> e<br \/>\n<i>y<\/i><b>R<\/b><i>z<\/i> significa parlare di tre sottoinsiemi <i>A<\/i>,<br \/>\n<i>B<\/i> e <i>C<\/i> di {1,\u00a02,\u00a03} tali che <i>A<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>\u00a0<i>B<\/i> e <i>B<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>\u00a0<i>C<\/i>.  Ma allora<br \/>\n<i>A<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>\u00a0<i>C<\/i>, cio\u00e8<br \/>\n<i>x<\/i><b>R<\/b><i>z<\/i>.<\/p>\n<\/li>\n<p><\/font><\/ul>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Costruiamo ora il diagramma di Hasse del poset <i>P<\/i>.<br \/>\nDovremo prima di tutto collocare in qualche posizione tutti gli elementi di<br \/>\n<i>X<\/i>, cio\u00e8 tutti i possibili sottoinsiemi di {1,\u00a02,\u00a03},<br \/>\nseguendo la regola 1; decideremo poi quali di questo unire con segmenti<br \/>\nseguendo la regola 2.  Le regole viste in precedenza si traducono cos\u00ec:<br \/>\n<\/font><\/p>\n<\/p>\n<ol><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><\/p>\n<li>l&#8217;insieme <i>A<\/i> appare al di sotto dell&#8217;insieme <i>B<\/i> se e solo se<br \/>\n<i>A<\/i>\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/subseteq.gif\"\/>\u00a0<i>B<\/i>;<\/p>\n<\/li>\n<li><i>A<\/i> e <i>B<\/i> sono uniti da un segmento se e soltanto se <i>B<\/i><br \/>\n\u00e8 una copertura di <i>A<\/i>, cio\u00e8 se e soltanto se non ci sono<br \/>\ninsieme <i>C<\/i> contenuti propriamente in <i>B<\/i> e contenenti propriamente<br \/>\n<i>A<\/i>, cio\u00e8 se e soltanto se <i>B<\/i> si ottiene a partire da<br \/>\n<i>A<\/i> aggiungendo un solo elemento dell&#8217;insieme {1,\u00a02,\u00a03} non<br \/>\ncontenuto in <i>A<\/i> (lasciamo al lettore la verifica di quest&#8217;ultima<br \/>\naffermazione).<\/p>\n<\/li>\n<p><\/font><\/ol>\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Il grafico risultante \u00e8 quindi il seguente: <\/font><\/p>\n<p align=\"center\">\n<p><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\"><img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/hasse\/image001.gif\"\/><\/p>\n<p>Diagramma di Hasse di 2<sup>{1,2,3}<\/sup> (<a target=\"_blank\" href=\"http:\/\/planetmath.org\/encyclopedia\/HasseDiagram.html\">fonte<\/a>)<\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">Notiamo che, per esempio, il grafico non contiene l&#8217;arco<br \/>\n{1}\u2013-{1,\u00a02,\u00a03} perch\u00e9 {1,\u00a02,\u00a03} contiene {1}, ma<br \/>\nnon ne \u00e8 una copertura: esistono infatti altri due elementi {1,\u00a02}<br \/>\ne {1,\u00a03} che si frappongono tra i due nella relazione di inclusione<br \/>\nall&#8217;interno del poset <i>P<\/i>. <\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Affermavamo che il<br \/>\ndiagramma di Hasse consente di visualizzare graficamente la relazione di<br \/>\nordine parziale in termini della chiusura transitiva della relazione di<br \/>\ncopertura: \u00e8 infatti sufficiente seguire gli archi tra gli elementi per<br \/>\ndeterminare tutte le coppie possibili della relazione di inclusione. In<br \/>\nparticolare, \u00e8 piuttosto semplice riconoscere il tipo di ordinamento<br \/>\nche caratterizza il poset, perch\u00e9 <i>il diagramma di Hasse assume<br \/>\nstruttura lineare nel caso di ordinamento totale e non lineare nel caso di<br \/>\nordinamento parziale<\/i>. <\/font><\/p>\n<p align=\"justify\"><font size=\"2\" face=\"Verdana, Arial, Helvetica, sans-serif\">\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Ricordiamo che, come<br \/>\ngi\u00e0 accennato in precedenza, una relazione binaria <b>R<\/b><br \/>\nsull&#8217;insieme <i>X<\/i> \u00e8 detta <i>ordinamento totale<\/i> (o lineare) se<br \/>\n(<i>X<\/i>,\u00a0<b>R<\/b>) \u00e8 un poset e se per ogni coppia <i>x<\/i>,<br \/>\n<i>y<\/i> di elementi in <i>X<\/i> esiste in <i>P<\/i> almeno una delle due<br \/>\nrelazioni <i>x<\/i><b>R<\/b><i>y<\/i> e <i>y<\/i><b>R<\/b><i>x<\/i>.  Un esempio di<br \/>\nordinamento totale \u00e8 il poset<br \/>\n<i>P<\/i>\u00a0=\u00a0({1,\u00a02,\u00a03,\u00a04},\u00a0<img decoding=\"async\" alt=\"\" src=\"..\/..\/esperti\/mat\/img\/le.gif\"\/>): al lettore l&#8217;esercizio di disegnarne il diagramma di<br \/>\nHasse e di verificarne la struttura lineare. <\/font><\/p>\n","protected":false},"excerpt":{"rendered":"<p>[&#8230;]<\/p>\n","protected":false},"author":180,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[65],"tags":[],"class_list":["post-636","post","type-post","status-publish","format-standard","hentry","category-algebra"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/636","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/180"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=636"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/636\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=636"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=636"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=636"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}