Beispielmakro: Dicomplement.omf
Makro zur Berechnung von Dikomplementen in Verbänden
Allgemeine Bemerkungen:
Ein Dikomplement auf einem Verband (L,≤) ist ein Paar ( ∆, ∇) von einstelligen Operationen auf L, so dass folgende Bedingungen erfüllt sind:
| x∆∆ ≤ x | x∇∇ ≥ x |
| x ≤ y ⇒ x∆ ≥ y∆ | x ≤ y ⇒ x∇ ≥ y∇ |
| (x ∧ y) ∨ (x ∧ y∆) = x | (x ∨ z) ∧ (x ∨ y∇) = x |
Für weitere Angaben zum Thema Dikomplementer Verbände vergleiche:
Leonard Kwuida. Dicomplemented Lattices - A Contextual Generalization of Boolean Algebras. Aachen: Shaker Verlag, 2004.
Das Makro in Dicomplement.omf berechnet auf einem Verband, den der Anwender frei wählen kann, die Menge aller möglichen Definitionen für ein Dikomplement, genauer aller möglichen Operationen, die gemäss obiger Definition als erste Komponente eines Dikomplements zulässig sind. Zu diesem Zweck werden alle möglichen einstelligen Operationen als Liste ihrer Werte erzeugt, d.h. eine einstellige Operation f auf (L,≤) ist gegeben durch die Liste (f(x1), ..., f(xn)) ihrer Werte auf L = {x1, ..., xn}. Um den Algorithmus zu beschleunigen, werden nicht die vollständigen Listen auf Erfüllung der Bedingungen getestet, sondern vielmehr bereits partielle Listen auf das potentielle Erfüllen der Bedingungen, da im Falle des Nicht-Erfüllens sämtliche Erweiterungen der Liste gar nicht mehr untersucht werden müssen.
Die Implementation (Download: unformatierter Quelltext in Dicomplement.omf):
% isdicomplement prüft, ob die Liste argumentlist bis zum Index i die Bedingungen eines Dikomplements erfüllen. %
isdicomplement:=lambda(i)
% Die drei Bedingungen werden mit "AND" logisch verknüpft. %
and(
% Für alle x, y muss gelten (x ∧ y) ∨ (x ∧ y∆) = x : %
forall(x in L, forall(y in L,
% argumentlist wird nur bis Index i getestet, also darf der Index von y in L höchstens i sein: %
if <=(indexof(L, y), i) then
% Die folgenden Zwischenschritte könnten auch ausgelassen werden und durch "if equal(sup(inf(x,y),inf(x,item(argumentlist,indexof(L,y)))),x) then true else false endif" ersetzt werden: %
% yc: = y∆ : %
yc:=item(argumentlist,indexof(L,y));
% infxy := (x ∧ y) : %
infxy:=inf(x,y);
% infxyc := (x ∧ y∆) : %
infxyc:=inf(x,yc);
% s:= (x ∧ y) ∨ (x ∧ y∆) : %
s:=sup(infxy,infxyc);
if equal(s,x) then true else false endif
else true endif)),
% Für alle x muss gelten x∆∆ ≤ x : %
forall(x in L,
% argumentlist wird nur bis Index i getestet, also darf der Index von x in L höchstens i sein: %
if <=(indexof(L, x), i) then
xc:=item(argumentlist,indexof(L,x));
% argumentlist wird nur bis Index i getestet, also darf der Index von xc in L auch höchstens i sein: %
if <=(indexof(L, xc), i) then
xcc:=item(argumentlist,indexof(L,xc));
if <=(xcc,x) then true else false endif
else true endif
else true endif),
% Für alle x muss gelten x ≤ y ⇒ x∆ ≥ y∆ %
forall(x in L, forall(y in L,
% argumentlist wird nur bis Index i getestet, also dürfen die Indices von x und y in L höchstens i sein: %
if and(<=(indexof(L, x), i),<=(indexof(L, y), i),<=(x,y)) then
xc:=item(argumentlist,indexof(L,x));
yc:=item(argumentlist,indexof(L,y));
if >=(xc,yc) then true else false endif
else true endif)))
endlambda;
% findnextlist erhöht argumentlist, d.h. die nächste Liste von Werten für die einstellige Operation wird bestimmt und gegebenfalls ausgegeben. %
% Der Parameter i ist die Stelle in argumentlist, die aktuell erhöht werden muss. Wenn i=maxindex, dann ist die letzte Stelle in argumentlist dran, d.h. die Operation ist vollständig und kann deshalb ausgegeben werden. Ist i<maxindex, dann ist die Operation nur bis zur Stelle i geprüft, und für jede gültige partielle Definition (d.h. falls isdicomplement(i) true ergibt) muss findnextlist(i+1) durchgeführt werden. %
findnextlist:=lambda(i)
for k in L do
% Die i-te Stelle von argumentlist durchläuft ganz L: %
setitem(argumentlist, i, k);
% Prüfen, ob argumentlist für eine gültige (partielle) Operation steht: %
if isdicomplement(i) then
if equal(i,maxindex) then
% Die gefundene gültige Operation ist vollständig, also Ausgabe : %
numfound:=+(numfound,1);
writeln("");
write("No. "); writeln(numfound);
for k1 in L do write(k1); write(" -> "); writeln(item(argumentlist,indexof(L,k1))) endfor;
true
else % Die gefundene gültige Operation ist noch nicht vollständig: % findnextlist(+(i,1)) endif
else false endif
endfor
endlambda;
% "Hauptprogramm": %
% L auswählen: %
L:=listprompt("Select a structure", structures);
% Operations- und Relationstabellen für Ordnung vorbereiten: %
prepare(L);
% Der höchste Index von argumentlist ist "Anzahl Elemente in L"-1, da Nummerierung bei 0 beginnt: %
maxindex:=difference(card(L),1);
argumentlist:=emptyset;
numfound:=0;
% argumentlist mit dem Element von L mit kleinstem Index füllen: %
for e in L do additem(argumentlist, item(L,0)) endfor;
% ... und los geht's: %
findnextlist(0);