Projekt: Symbolisches Differenzieren

Ableitungsregeln & Cuts

(Vorlage und Idee: Informatik mit Prolog, Gerhard Röhner, 3. Auflage, Kapitel 11 und 16.5.2)

Dieses Projekt ist die Umsetzung eines automatischen Ableitungsprädikat in Prolog.
Dies spaltet sich in folgende Abschnitte:

Ableitung

ableitung(+Term, +Ableitungsvariable, -AbgeleiteterTerm)

Als erstes muss man beim Ableiten überprüfen, ob der Term aus einer einzelnen Konstante besteht,
dazu schreibt man in Prolog folgende Vereinbarung:

% Konstantenregel
ableitung(K, X, 0) :- atomic(K), K \== X, !.

Danach kommen die allgemeinen Ableitungsregeln aus dem Mathematikunterricht:

% Ableitung von x
ableitung(X, X, 1) :- !.

% Vorzeichenregel
ableitung(-T, X, -Ta) :-  !, ableitung(T, X, Ta).

% Summenregel
ableitung(T1 + T2, X, T1a + T2a) :- !,
             ableitung(T1, X, T1a), ableitung(T2, X, T2a).

% Differenzenregel
ableitung(T1 - T2, X, T1a-T2a) :- !,
             ableitung(T1, X, T1a), ableitung(T2, X, T2a).

% Faktorregel
ableitung(Konst*T, X, Konst*Ta) :-
                   atomic(Konst), Konst \== X, !, ableitung(T, X, Ta).

% Produktregel
ableitung(T1*T2, X, T1*T2a + T2*T1a) :- !,
                 ableitung(T1, X, T1a), ableitung(T2, X, T2a).

% Quotientenregel
ableitung(T1/T2, X, (T1*T2a - T2* T1a)/(T2*T2)) :- !,
                 ableitung(T1, X, T1a), ableitung(T2, X, T2a).

% Ableitung der Grundfunktionen
ableitung(X^N, X, N*X^(N - 1)) :- atomic(N), N \== X, !.
ableitung(sin(X), X, cos(X)) :- !.
ableitung(cos(X), X, -sin(X)) :- !.
ableitung(ln(X), X, 1/X) :- !.
ableitung(e(X), X, e(X)) :- !.
ableitung(T, X, Ta*Ga) :- T =.. [_,G], G \== X, !, ableitung(T, G, Ta), ableitung(G, X, Ga).
ableitung(T, X, Ta) :- T =.. [F,X], atom_concat(F, 'S', G), Ta =.. [G,X].

% Kettenregel
ableitung(T, X, Ta*Ga) :- T =.. [_,G], G \== X, !, ableitung(T, G, Ta), ableitung(G, X, Ga).

% Allgemeine Ableitung
ableitung(T, X, Ta) :- T =.. [F,X], atom_concat(F, 'S', G), Ta =.. [G,X].

Prolog arbeitet wie gewohnt mit Resolution, Backtracking und Unifikation. Damit Prolog aber nicht alle möglichen Lösungswege abarbeitet, verwendet man Cuts. Diese verhindern erstens, dass Prolog unnötig weitersucht, aber auch, dass Prolog Regln nur anwendet, wenn sie auch nötig sind. Ein Beispiel:

ableitung(sin(X), X, cos(X)) :- !.

In diesem Beispiel wird einerseits deutlich, dass Prolog daran gehindert wird unnötige, weitere Schritte zu tun und zweitens in diesem Beispiel die Kettenregel nicht anwendet. Dieser rote Cut ist allerdings hier legitim, da wir ja nicht jedesmal durch die Kettenregel bestätigt haben wollen, dass die Ableitung vom Sinus gleich der Ableitung des einfachen Sinus ist.

Kettenregel

Die Kettenregel kann man mithilfe des univ Operators umsetzen, jedoch sollte man vorsichtig sein, da es zu schweren Fehlern führen kann, wenn man sie in der falschen Reihenfolge in die Wissensbasis schreibt. Wie bereits im Beispiel zuvor erwähnt, lässt sich die Kettenregel zumbeispiel unendlich oft auf einen Sinus anwenden. Daher sollte sie auch hinter den normalen Ableitungen stehen und ist in unserem Fall mit einer weiteren Sperre versehen: Sie wird nur angewendet, wenn das Innere der Funktion ungleich der Ableitungsvariable ist.


% Kettenregel
ableitung(T, X, Ta*Ga) :- T =.. [_,G], G \== X, !, ableitung(T, G, Ta), ableitung(G, X, Ga).

Allgemeine Funktionen

% Allgemeine Ableitung
ableitung(T, X, Ta) :- T =.. [F,X], atom_concat(F, 'S', G), Ta =.. [G,X].

Normalerweise benutzt man bei Ableitungen von f(X) --> f'(X) ein '. Damit man auch in Prolog ohne Probleme eine Ausgabe hat, wird mit dem Systemprädikat atom_concat der String "S" zum Funktionsnamen angehängt.
Ganz wichtig ist jedoch, dass die Reihenfolge im Programm wie oben beschrieben ist d.h. zuerst kommt die
Faktorregel --> Produktregel --> Grundfunktionen --> allgemeine Funktionen --> Kettenregel

Vereinfachung Arithmetischer Ausdrücke

Bei der Vereinfachung gehen wir davon aus ,dass der univ Operator nicht benutzt wird.
Zuerst deklarieren wir das Prädikat vereinfachen(+Term,-VereinfachterTerm).
Desweiteren müssen wir nun jede einzelne Regel mit dem Prädikat vereinfachen/2 erstellen.

%% Vereinfachen
%erst an Plus und Minus aufteilen
vereinfachen(T1 + T2, V) :- vereinfachen(T1, T1v), vereinfachen(T2, T2v), summe(T1v + T2v, V).
vereinfachen(T1 - T2, V) :- vereinfachen(T1, T1v), vereinfachen(T2, T2v), summe(T1v - T2v, V).
vereinfachen(T,V)        :- not(hatplus(T)), not(hatminus(T)), vereinfachen2(T,V).

%danach bei Mal und Durch, da ja Punkt vor Strich gilt.
vereinfachen2(T1 * T2,V) :- vereinfachen2(T1,T1v), vereinfachen2(T2,T2v), produkt(T1v * T2v, V).
vereinfachen2(T1 / T2,V) :- vereinfachen2(T1,T1v), vereinfachen2(T2,T2v), produkt(T1v / T2v, V).
vereinfachen2(T,T)       :- not(hatmal(T)), not(hatdurch(T)).

hatplus(_ + _).
hatminus(_ - _).
hatmal(_ * _).
hatdurch(_ / _).

Wie man sehen kann geht das Programm durch und sieht sich an, ob es sich um eine Summe oder ein Produkt handelt und ruft das entsprechende Prädikat auf. Sobald es eine Zeile abarbeitet, vereinfacht das Programm erstmal die einzelnen Variablen und setzt es dann wieder zusammen. Zum Schluss überprüft es, ob es nicht einen Operator vergessen hat und geht dann heraus.

Summe

Das Prädikat summe/2 geht verschiedene mathematische Regln durch und vereinfacht nach diesen den Term.

summe(0 + T, T) :- !.
summe(T + 0, T) :- !.
summe(T1 + T2, T) :- integer(T1), integer(T2), T is T1 + T2, !.
summe(0 - T1, T) :- integer(T1), T is -T1, !.
summe(T - 0, T) :- !.
summe(T1 - T2, T) :- integer(T1), integer(T2), T is T1 - T2, !.
summe(A + B, B + A) :- not(integer(A)), integer(B).
summe(T - T, 0) :- !.
summe(A*T - T, S) :- summe(A - 1, A1), produkt(A1 * T, S), !.
summe(T - A*T, S) :- summe(1 - A, A1), produkt(A1 * T, S), !.

summe(A*T - B*T, S) :- summe(A - B, A1), produkt(A1 * T, S), !.
summe(A*T + B*T, S) :- summe(A + B, A1), produkt(A1 * T, S), !.
summe(T1 + (T2 + T3), T4 + T3) :- vereinfachen(T1 + T2, T4), !.

summe(T, T).

Produkt

Das Prädikat produkt/2 überprüft wie summe/2 den Term nach mathematische Gesetzmäßigkeiten, die eine Vereinfachung zulassen.

produkt(T / T, 1).
produkt(A*T,A*T) :- not(number(T)),!.

produkt(0 * T, 0) :- !.
produkt(T * 0, 0) :- !.
produkt(T * 1, T) :- !.
produkt(1 * T, T) :- !.
produkt(T1 * T2, T) :- number(T1), number(T2), T is T1 * T2,!.

produkt(T / 0,_) :- !, fail.
produkt(T / 1, T) :- !.
produkt(T1 / T2, T) :- number(T1), number(T2), T is T1 / T2,!.
produkt(A * B, B * A).

Auswerten

Auswerten berechnet nach Möglichkeit die Teile, die zu berechnen sind. Hierzu nutzt es den univ-Operator, um den Inhalt der Terme zu "durchleuchten" und wenn möglich hier Teilergebnisse ausgibt.

% Term ist eine Konstante
auswerten(T,T) :- atomic(T), !.

% Term ist eine Variable
auswerten(T,T) :- var(T), !.

% allgemein
auswerten(T1,T2) :- T1 =.. [F|Arg], auswerten_liste(Arg,W), T3 =.. [F|W], einfacher(T3,T2),!.

% auswerten_liste
auswerten_liste([],[]) :- !.
auswerten_liste([Arg|Arge],[W|We]) :- auswerten(Arg,W), auswerten_liste(Arge, We).

% einfacher
einfacher(T1 + T2, W) :- number(T1), number(T2), W is T1 + T2.
einfacher(T1 - T2, W) :- number(T1), number(T2), W is T1 - T2.
einfacher(T1 * T2, W) :- number(T1), number(T2), W is T1 * T2.
einfacher(T1 / T2, W) :- number(T1), number(T2), W is T1 / T2.
einfacher(T1 mod T2, W) :- number(T1), number(T2), W is T1 mod T2.
einfacher(-T, W) :- number(T), W is -T.
einfacher(T,T).

Aufruf

Letztendlich benutzt man ein weiteres Prädikat ableiten/3 zum Aufruf. Seine Ein- und Ausgabe sind äquivalent zu ableitung/3, aber es fügt Ableitungs- und Vereinfachungsvorgänge zusammen.
Es treten allerdings noch diverse Schwierigkeiten beim Vereinfachen und auch beim Überprüfen negativer Ableitungen auf.

Alle dokumentierten Programme stehen hier zum Download bereit: