Reticolo divisibilità
ciaoo a tutti, ho bisogno ancora una volta del vostro aiuto...mi hanno dato un esempio di esame di matematica che dv affrontare... fin ora sono stato in grado di far tutto ma ho visto un esercizio che mi ha spaventato, nn ho mai fatto un esercizio simile, si tratta del reticolo per divisibilità ... l'esercizio m chiede qst:
Assegnato il reticolo D105 dei divisori 105, ordinato per divisibilità
(1) tracciare il diagramma di hasse di D105
(2) determinare gli eventuali cpmplementi di tutti gli elementi di D105
(3) stabilire se il reticolo è distributivo
(4) stabilire se il reticolo è di bool
vorrei capire come si svolge... nn ho mai fatto un esercizio simile... se sareste cosi gentili da svolgere i vari passaggi, ve ne sarei grato ...
Assegnato il reticolo D105 dei divisori 105, ordinato per divisibilità
(1) tracciare il diagramma di hasse di D105
(2) determinare gli eventuali cpmplementi di tutti gli elementi di D105
(3) stabilire se il reticolo è distributivo
(4) stabilire se il reticolo è di bool
vorrei capire come si svolge... nn ho mai fatto un esercizio simile... se sareste cosi gentili da svolgere i vari passaggi, ve ne sarei grato ...
Risposte
Skipt, cosa studi? (i reticoli non li conosco non posso aiutarti, se non sbaglio sono strutture algebriche)
comunque dubito che qualcuno ti risponda, da regolamento , devi postare almeno un tuo tentativo di risoluzione
comunque dubito che qualcuno ti risponda, da regolamento , devi postare almeno un tuo tentativo di risoluzione
ah ekko.... mmmmh ok grazie lo stesso... io studio all'università di scienze matematiche fisiche e naturali, e ho un esame di matematica , uno di qst esercizi riguarda proprio il reticolo di divisibilità.... ossia il diagramma di hasse.... e io sinceramente non lo so fare minimamente
ekko perchè cercavo un vostro aiuto...
hai delle dispense online su questo argomento?
[xdom="Seneca"]Due cose: modifica il titolo inserendolo tutto in minuscolo e cerca di non usare abbreviazioni "da sms" - sono vietate dal regolamento e rendono pesante la lettura dei post.[/xdom]
Un reticolo è un insieme parzialmente ordinato $(P,<=)$ tale che per ogni coppia di elementi $a,b \in P$ esistono l'estremo inferiore $a ^^ b = i nf{a,b}$ e l'estremo superiore $a vv b = s up{a,b}$. Le operazioni $^^$ e $vv$ così definite hanno le seguenti proprietà:
Commutatività
$a ^^ b = b ^^ a$
$a vv b = b vv a$
Idempotenza
$a ^^ a = a = a vv a$
Leggi di assorbimento
$a ^^ (a vv b) = a$
$a vv (a ^^ b) = a$
Se l'insieme $P$ ammette massimo, questo viene indicato con $1$ o $\top$, se ammette minimo questo viene indicato con $0$ o $\bot$. Se un reticolo ammette sia massimo che minimo si dice limitato. Dato un reticolo limitato $P$ e un elemento $a \in P$ il suo complemento (se esiste) è un elemento $a'$ tale che $a ^^ a' = \bot$ e $a vv a' = \top$. Se ogni elemento di $P$ ammette complemento il reticolo si dice complementato. Se per ogni $a,b,c \in P$ sono vere le seguenti ugualianze
$a ^^ (b vv c) = (a ^^ b) vv (a ^^ c)$
$a vv (b ^^ c) = (a vv b) ^^ (a vv c)$
il reticolo si dice distributivo. Un reticolo complementato distributivo si dice booleano.
Per il diagramma di hasse vedi http://it.wikipedia.org/wiki/Reticolo_della_divisibilit%C3%A0
Nel tuo caso il reticolo è l'insieme dei divisori di 105 ordinato mediante la relazione di divisibilità $a <= b <=> a | b$. Hai quindi che $a ^^ b = mcd (a,b)$ e $a vv b = mcm (a,b)$, il massimo è $105$ e il minimo è $1$. Queste sono tutte le informazioni che ti servono. Non dirò più niente finchè non farai almeno un tentativo di risolvere quell'esercizio. Provaci! E se non ci riesci spiegaci con precisione cosa non capisci.
Commutatività
$a ^^ b = b ^^ a$
$a vv b = b vv a$
Idempotenza
$a ^^ a = a = a vv a$
Leggi di assorbimento
$a ^^ (a vv b) = a$
$a vv (a ^^ b) = a$
Se l'insieme $P$ ammette massimo, questo viene indicato con $1$ o $\top$, se ammette minimo questo viene indicato con $0$ o $\bot$. Se un reticolo ammette sia massimo che minimo si dice limitato. Dato un reticolo limitato $P$ e un elemento $a \in P$ il suo complemento (se esiste) è un elemento $a'$ tale che $a ^^ a' = \bot$ e $a vv a' = \top$. Se ogni elemento di $P$ ammette complemento il reticolo si dice complementato. Se per ogni $a,b,c \in P$ sono vere le seguenti ugualianze
$a ^^ (b vv c) = (a ^^ b) vv (a ^^ c)$
$a vv (b ^^ c) = (a vv b) ^^ (a vv c)$
il reticolo si dice distributivo. Un reticolo complementato distributivo si dice booleano.
Per il diagramma di hasse vedi http://it.wikipedia.org/wiki/Reticolo_della_divisibilit%C3%A0
Nel tuo caso il reticolo è l'insieme dei divisori di 105 ordinato mediante la relazione di divisibilità $a <= b <=> a | b$. Hai quindi che $a ^^ b = mcd (a,b)$ e $a vv b = mcm (a,b)$, il massimo è $105$ e il minimo è $1$. Queste sono tutte le informazioni che ti servono. Non dirò più niente finchè non farai almeno un tentativo di risolvere quell'esercizio. Provaci! E se non ci riesci spiegaci con precisione cosa non capisci.
l'ho fatto... mi è uscito così:
105 = 3·5·7
Gli elementi di D105 sono 1, 3, 5, 7, 15, 21, 35, 105, la relazione d'ordine nel reticolo in D105 è "x | y <==> x è divisore di y".
La verifica che | è relazione d'ordine parziale (riflessiva, antisimmetrica, transitiva).
Per ogni coppia di elementi x, y di D105, esiste un massimo confine inferiore, che è x /\ y = MCD(x, y), ed esiste un minimo confine superiore, che è x \/ y = mcm(x, y), quindi (D105, | ) è un reticolo ordinato.
(1)
. . . . .3 –– 15
. . . . / \ . . / \
. . . / . . \ / . . \
. . / . . . / \ . . . \
. / . . . / . . \ . . . \
1 ––– 5 . . 21 –– 105
. \ . . . \ . . / . . . /
. . \ . . . \ / . . . /
. . . \ . . / \ . . /
. . . . \ / . . \ /
. . . . .7 –– 35
(2)
In un reticolo ordinato (L, ≤) dotato di un minimo O e un massimo I. il complemento di un elemento x è un elemento y tale che x /\ y = O, x \/ y = I.
(D105, | ) possiede un minimo elemento, che è 1, ed un massimo elemento, che è 105; il complemento di un elemento x è un elemento y tale che
MCD(x, y) = 1, mcm(x, y) = 105
E' chiaro che ogni elemento x di D105 ha come complemento 105/x.
(4)
Un reticolo ordinato (L, ≤) si dice booleano se è distributivo, se possiede minimo O e massimo I, e se ogni elemento di L possiede un complemento.
Abbiamo visto sopra che (D105, | ) ha tutte queste proprietà,
però l'unica cosa che non riesco a capire è come si fa a capire se un reticolo è distributivo o no... questo non capisco
105 = 3·5·7
Gli elementi di D105 sono 1, 3, 5, 7, 15, 21, 35, 105, la relazione d'ordine nel reticolo in D105 è "x | y <==> x è divisore di y".
La verifica che | è relazione d'ordine parziale (riflessiva, antisimmetrica, transitiva).
Per ogni coppia di elementi x, y di D105, esiste un massimo confine inferiore, che è x /\ y = MCD(x, y), ed esiste un minimo confine superiore, che è x \/ y = mcm(x, y), quindi (D105, | ) è un reticolo ordinato.
(1)
. . . . .3 –– 15
. . . . / \ . . / \
. . . / . . \ / . . \
. . / . . . / \ . . . \
. / . . . / . . \ . . . \
1 ––– 5 . . 21 –– 105
. \ . . . \ . . / . . . /
. . \ . . . \ / . . . /
. . . \ . . / \ . . /
. . . . \ / . . \ /
. . . . .7 –– 35
(2)
In un reticolo ordinato (L, ≤) dotato di un minimo O e un massimo I. il complemento di un elemento x è un elemento y tale che x /\ y = O, x \/ y = I.
(D105, | ) possiede un minimo elemento, che è 1, ed un massimo elemento, che è 105; il complemento di un elemento x è un elemento y tale che
MCD(x, y) = 1, mcm(x, y) = 105
E' chiaro che ogni elemento x di D105 ha come complemento 105/x.
(4)
Un reticolo ordinato (L, ≤) si dice booleano se è distributivo, se possiede minimo O e massimo I, e se ogni elemento di L possiede un complemento.
Abbiamo visto sopra che (D105, | ) ha tutte queste proprietà,
però l'unica cosa che non riesco a capire è come si fa a capire se un reticolo è distributivo o no... questo non capisco
"skipt":
però l'unica cosa che non riesco a capire è come si fa a capire se un reticolo è distributivo o no... questo non capisco
Ci sono tanti modi, ma io ti consiglio di applicare questo risultato
Il prodotto di reticoli distributivi è a sua volta distributivo.
Indichiamo con $2$ il reticolo distributivo ${0,1}$ che ha solo due elementi. Puoi facilmente verificare che il tuo reticolo è isomorfo al prodotto $2 xx 2 xx 2$. Infatti i due reticoli hanno lo stesso diagramma, cioè un cubo.
P.S. Cmq usare le formule è obbligatorio ...
salve,
ho voluto riprendere l'esercizio, è interessante, e quì nel forum sono pochi i thread a riguardo, ho provato a svolgerlo, poichè era rimasto in sospeso.
Potreste per cortesia dirmi se ho fatto bene e potreste darmi qualche consiglio? Grazie mille!
punto 1)
Il diagramma di Hasse del reticolo $D_105$ l'ho fatto così:
punto 2)
In un reticolo, un elemento viene chiamato unità del reticolo se tutti gli altri elementi del reticolo sono $\le$ di esso;
un elemento viene chiamato zero del reticolo se l'elemento è $\le$ ti tutti gli altri. Dove per $\le$ s'intende una particolare relazione d'ordine. Come ad esempio in questo caso la relazione "divide". Perciò l'elemento "più in basso" nel diagramma di Hasse, cioè l'elemento 1 dell'insieme dei divisori, si comporterà come uno zero; mentre quello "più in alto" nel diagramma di Hasse, cioè l'elemento 105 dell'insieme dei divisori, come una unità.
Allora saranno soddisfatte contemporaneamente le seguenti condizioni:
[tex]a \lor 0 = 0 \lor a = a \quad \mbox{ and } \quad a \land 1 = 1 \land a = a, \quad \forall a \in D_{105}[/tex]
Perciò, 0 e 1 ci sono, per vedere se un elemento $a$ ha un complemento $a'$, bisogna verificare se valgano le seguenti:
[tex]a \land a' = 0 \quad \mbox{ and } \quad a \lor a' = 1[/tex]
se ogni elemento del reticolo ha un complemento allora il reticolo è detto: reticolo complementato.
A questo proposito ho fatto una tabella che riassume eventuali complementi,
se le condizioni vengono rispettate allora nella cella corrispondente si troverà un asterisco
[tex]\begin{array}{c|c}
\, & 1 & 3 & 5 & 7 & 15 & 21 & 35 & 105 \\
\hline
1 & - & - & - & - & - & - & - & * \\
\hline
3 & - & - & - & - & - & - & * & - \\
\hline
5 & - & - & - & - & - & * & - & - \\
\hline
7 & - & - & - & - & * & - & - & - \\
\hline
15 & - & - & - & * & - & - & - & - \\
\hline
21 & - & - & * & - & - & - & - & - \\
\hline
35 & - & * & - & - & - & - & - & - \\
\hline
105 & * & - & - & - & - & - & - & - \\
\end{array}[/tex]
perciò,
$1$ ha complemento $105$ e viceversa, infatti, come può essere visto nel diagramma di Hasse, vale la seguente:
[tex]1 \land 105 = 105 \land 1 =0 \quad \mbox{ and } \quad 1 \lor 105 = 105 \lor 1 = 1[/tex]
invece ad esempio $5$ NON ha complemento $15$ e viceversa, in quanto la seguente è:
[tex]5 \land 15 = 15 \land 5 = 5 \ne 0 \quad \mbox{ and } \quad 5 \lor 15 = 15 \lor 5 = 15 \ne 1[/tex]
analogamente si procede per gli altri elementi.
TUTTI gli elementi hanno un complemento, allora il reticolo è detto Complementato.
Punto 3)
se è possibile ottenere dal nostro reticolo un sottoreticolo che abbia una delle seguenti strutture, allora il nostro reticolo NON è distributivo:
poichè NON è possibile ottenere un sottoreticolo che abbia una delle due configurazioni di cui sopra,
allora il nostro reticolo $D_{105}$ è distributivo.
Punto 4)
è un reticolo Booleano perchè è Complementato.
Riarrangiando inoltre gli elementi del diagramma di Hasse, è molto più evidente che la struttura di questo reticolo è isomorfa alla "struttura a cubo" composta di 8 elementi dell'algebra booleana.
Cosa ne pensate? Grazie mille!
ho voluto riprendere l'esercizio, è interessante, e quì nel forum sono pochi i thread a riguardo, ho provato a svolgerlo, poichè era rimasto in sospeso.
Potreste per cortesia dirmi se ho fatto bene e potreste darmi qualche consiglio? Grazie mille!
punto 1)
"skipt":
(1) tracciare il diagramma di hasse di $D_{105}$
Il diagramma di Hasse del reticolo $D_105$ l'ho fatto così:
punto 2)
"skipt":
(2) determinare gli eventuali complementi di tutti gli elementi di $D_{105}$
In un reticolo, un elemento viene chiamato unità del reticolo se tutti gli altri elementi del reticolo sono $\le$ di esso;
un elemento viene chiamato zero del reticolo se l'elemento è $\le$ ti tutti gli altri. Dove per $\le$ s'intende una particolare relazione d'ordine. Come ad esempio in questo caso la relazione "divide". Perciò l'elemento "più in basso" nel diagramma di Hasse, cioè l'elemento 1 dell'insieme dei divisori, si comporterà come uno zero; mentre quello "più in alto" nel diagramma di Hasse, cioè l'elemento 105 dell'insieme dei divisori, come una unità.
Allora saranno soddisfatte contemporaneamente le seguenti condizioni:
[tex]a \lor 0 = 0 \lor a = a \quad \mbox{ and } \quad a \land 1 = 1 \land a = a, \quad \forall a \in D_{105}[/tex]
Perciò, 0 e 1 ci sono, per vedere se un elemento $a$ ha un complemento $a'$, bisogna verificare se valgano le seguenti:
[tex]a \land a' = 0 \quad \mbox{ and } \quad a \lor a' = 1[/tex]
se ogni elemento del reticolo ha un complemento allora il reticolo è detto: reticolo complementato.
A questo proposito ho fatto una tabella che riassume eventuali complementi,
se le condizioni vengono rispettate allora nella cella corrispondente si troverà un asterisco
[tex]\begin{array}{c|c}
\, & 1 & 3 & 5 & 7 & 15 & 21 & 35 & 105 \\
\hline
1 & - & - & - & - & - & - & - & * \\
\hline
3 & - & - & - & - & - & - & * & - \\
\hline
5 & - & - & - & - & - & * & - & - \\
\hline
7 & - & - & - & - & * & - & - & - \\
\hline
15 & - & - & - & * & - & - & - & - \\
\hline
21 & - & - & * & - & - & - & - & - \\
\hline
35 & - & * & - & - & - & - & - & - \\
\hline
105 & * & - & - & - & - & - & - & - \\
\end{array}[/tex]
perciò,
$1$ ha complemento $105$ e viceversa, infatti, come può essere visto nel diagramma di Hasse, vale la seguente:
[tex]1 \land 105 = 105 \land 1 =0 \quad \mbox{ and } \quad 1 \lor 105 = 105 \lor 1 = 1[/tex]
invece ad esempio $5$ NON ha complemento $15$ e viceversa, in quanto la seguente è:
[tex]5 \land 15 = 15 \land 5 = 5 \ne 0 \quad \mbox{ and } \quad 5 \lor 15 = 15 \lor 5 = 15 \ne 1[/tex]
analogamente si procede per gli altri elementi.
TUTTI gli elementi hanno un complemento, allora il reticolo è detto Complementato.
Punto 3)
"skipt":
(3) stabilire se il reticolo è distributivo
se è possibile ottenere dal nostro reticolo un sottoreticolo che abbia una delle seguenti strutture, allora il nostro reticolo NON è distributivo:
poichè NON è possibile ottenere un sottoreticolo che abbia una delle due configurazioni di cui sopra,
allora il nostro reticolo $D_{105}$ è distributivo.
Punto 4)
"skipt":
(4) stabilire se il reticolo è di bool
è un reticolo Booleano perchè è Complementato.
Riarrangiando inoltre gli elementi del diagramma di Hasse, è molto più evidente che la struttura di questo reticolo è isomorfa alla "struttura a cubo" composta di 8 elementi dell'algebra booleana.
Cosa ne pensate? Grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo