109
edits
Changes
Jump to navigation
Jump to search
no edit summary
== Grades ==
Nesta seção, vamos olhar para o problema de determinar se uma ordem parcial é reticulada. A abordagem que devemos tomar é um bom exemplo de ''top down programming'' (programação de cima para baixo).
Para que possamos construir alguma exemplo interessante, vamos introduzir uma nova função para produzir exemplos de uma boa classe de reticulados.
<pre>
DivisorLattice := proc(n::posint)
DividesRelation(numtheory[divisors](n));
end:
</pre>
O procedimento '''divisors''', do pacote '''numtheory''', retorna o conjunto de divisores positivos de seu argumento inteiro. Usamos o procedimento '''DividesRelation''', construído no início deste capítulo, para criar a relação de divisão neste conjunto.
<pre>
type(DivRel(6), po);
</pre>
Queremos escrever um programa em ''Maple'' que irá determinar se uma ordem parcial (finita) é um reticulado. Agora, uma ordem de ''R'' parcial é um reticulado, se, e somente se, é tanto um ''meet semilattice'' quanto um ''join semilattice''. A primeira é uma ordem parcial em que cada par de elementos tem um encontro - um limite mínimo superior ou supremo; Segundo, é aquele em que a dupla condição for satisfeita: cada par de elementos tem um supremo, ou um ínfimo. Então, o nosso teste para uma ordem parcial deve ser um reticulado, apenas precisa de verificar se estas duas condições são satisfeitas.
<pre>
IsLattice := proc(R::po)
IsMeetSemiLattice(R) and IsJoinSemiLattice(R);
end:
</pre>
Em seguida, usamos o fato de que uma ordem parcial é um ''meet semilattice'', se, e somente se, a sua relação dual é um ''join semilattice''.
<pre>
IsJoinSemiLattice := IsMeetSemiLattice @ DualRelation;
</pre>
Agora o verdadeiro trabalho começa; devemos codificar a função '''IsMeetSemiLattice'''. Para isso, é preciso testar se, dada a relação ''R'', cada par ''a'', ''b'' no domínio da ''R'' tem um supremo com relação a ''R''. Uma observação que simplifica a nossa tarefa consideravelmente é que, uma vez que estamos a lidar apenas com relações finitas, basta verificar que cada par tem um limite superior comum.
<pre>
IsMeetSemiLattice := proc(R::po)
local DomR, # the domain of R
r,s; # indices into R
DomR := DomainRelation(R);
for r in DomR do
for s in DomR do
if lub(R, r, s) = NULL then
RETURN(false);
fi;
od;
od;
RETURN(true);
end:
</pre>
Finalmente, todas as sub-rotinas que estão fazendo o nosso programa '''IsLattice''' estão completas, e podemos testá-lo em alguns exemplos. O seguinte resultado não deve vir com qualquer surpresa.
<pre>
IsLattice(DivisorLattice(24));
</pre>
Mas, observe o que acontece quando nós construímos a relação ''divides'' em todos os inteiros no conjunto {1,2,3, ..., 24}.
<pre>
IsLattice(DividesRelation(seq(i, i=1..24)));
</pre>
== Relações de abrangência ==
É muito ineficiente, em geral, armazenar todos os pares em uma relação de ordem parcial. Há uma representação mínima de uma ordem parcial, a partir do qual toda a relação pode ser reconstruída, denominado sua relação de abrangência. (Isto não é abordado no texto, mas será útil para nós na seção seguinte, além de ser um tema importante por si só). A relação de abrangência de uma ordem parcial não é em si uma ordem parcial. É um subconjunto mínimo da ordem parcial a partir do qual todos os outros pares de relação podem ser deduzidos. Seja ''R'' uma ordem parcial em um conjunto ''S''. Dizemos que um elemento ''b'' em ''S'' abrange um elemento ''a'' em ''S'' se (''a'', ''b'') pertence a ''R'', e ''a''≠''b'', mas não há elemento ''s'' em ''S'' para o qual ambos (''a'', ''s'') e (''s'', ''b'') pertencem a ''R''. Em outras palavras, ''b'' abrange ''a'' se ''b'' é maior do que ''a'', e se não há nada entre eles. A relação de abrangência de uma ordem ''R'' parcial é a relação ''C'' de ''S'' que consiste naqueles pares (''a'', ''b'') em ''R'' para o qual ''b'' abrange ''a''. Como um exemplo simples, considere o conjunto {1,2,3,4} ordenado pela magnitude. Sua relação de abrangência é o conjunto {(1,2), (2,3), (3,4)}. Todos os outros pares, tais como (1,3), pode ser deduzida a partir da relação de abrangência, usando transitividade: 1 ≤ 2 ≤ 3, e, portanto, uma 1 ≤ 3 (isto é, o par (1,3) está na relação). Relações de abrangência também são importantes porque é a relação de abrangência de uma ordem parcial que é desenhada num diagrama de Hasse, em vez de toda a relação.
Nesta seção, nós fornecemos um procedimento em Maple para calcular a relação cobrindo de uma ordem parcial. Em primeiro lugar, precisamos de um teste para saber se um determinado elemento cobre outro.
<pre>
Covers := proc(R::po, a, b)
local u; # index into Dom(R)
if a = b then
RETURN(false);
fi;
if not member([a,b], R) then
RETURN(false);
fi;
for u in DomainRelation(R) minus a, b do
if member([a,u], R) and member([u,b], R) then
RETURN(false);
fi;
od;
RETURN(true);
end:
</pre>
Agora podemos construir a relação cobrindo de uma ordem parcial usando o seguinte procedimento em Maple:
<pre>
CoveringRelation := proc(R::po)
local C, # covering relation; returned
DomR, # the domain of R
r,s; # indices into DomR
DomR := DomainRelation(R);
C := {};
for r in DomR do
for s in DomR do
if Covers(R, r, s) then
C := C union [r,s];
fi;
od;
od;
RETURN(C);
end:
</pre>
Vejamos alguns pequenos exemplos.
<pre>
CoveringRelation(DivisorLattice(6));
CoveringRelation(DividesRelation(1,3,5,7,11,13,17));
</pre>
