Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 4 / 1 Termalgebren Definition "Freie Algebra" Die -Algebra A = [A, F ] heißt

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 4 / 1

Termalgebren

Definition "Freie Algebra"

Die -Algebra = [A , F ] heißt frei mit dem freien Erzeugendensystem X (über der Klasse aller -Algebren) gdw. X Erzeugendensystem von ist, so daß für jede -Algebra = [B , G ] und jede eindeutige Abbildungsfamilie 0 von X in B genau einen -Homomorphismus von in existiert, der 0 fortsetzt.

Kapitel 4


0

X

frei über X:


Isomorphie freier Algebren: = [A , F ] und = [B , G ] seien zwei freie -Algebren mit den freien Erzeugendensystemen X bzw. Y Dann gilt: und sind isomorph, wenn ihre freien Erzeugendensysteme X bzw. Y sortenweise gleichmächtig sind.

Beweisidee: Wegen der Gleichmächtigkeit von X und Y gibt es eine 1-1-Abbildung von X auf Y, die man wegen der Freiheit von zu einem Homomorphismus '' von in fortsetzen kann. Die inverse Abbildung -1 kann analog wegen der Freiheit von zu einem Homomorphismus (-1)'' von in fortgesetzt

werden. Um zu sehen, überzeuge man sich davon, daß beides Epimorphismen sind und zueinander invers.


Syntaxanalyse

(p (r q))

keine Variable, zu im(neg):

keine Variable, zu im(con):(p (r q))

(p (r q))

p (r q)

Variable keine Variable, zu im(alt)

(r q)

r q

Variable keine Variable, zu im(neg)

q Variable


Definition "PEANO-Algebra"

Eine -Algebra = [(Es)sS , (f) ] heißt -Ausdrucksalgebra (-Termalgebra) über dem Alphabet X oder auch -PEANO-Algebra über der PEANO-Basis X genau dann, wenn

X = (Xs)sS

und für alle sS ist Xs Es ,und die sogenannten verallgemeinerten PEANO-Axiome gelten.Die Elemente von Es heißen dann Terme oder Ausdrücke der Sorte s, die von Xs heißen Variablen der Sorte s.


Definition "PEANO-Algebra"

Die verallgemeinerten PEANO-Axiome sind die folgenden Bedingungen:

(P1) s( o() = s Ei () f() X )

(P2) 12s(1,2 o(1)=o(2)= s Ei (1) Ei (2) f1

() = f2()

1 = 2 = )

(P3) [X] = E


Fallunterscheidungssatz für Termalgebren:Ist eine -Termalgebra über X, so gilt für alle e E:

Es gibt ein sS und es ist entweder e Xs oder es existiert genau ein mit o() = s und genau ein Ausdruckstupel (e1,e2 ,...,en) Ei () mit e = f (e1,e2 ,...,en) .

Beweis: Wegen (P3) und dem Darstellungssatz für die algebraische Hülle ergibt sich die Behauptung trivialerweise aus den Bedingungen (P1) und (P2).


Folgerung:Ist -Termalgebra über X, so gilt für alle sS :

Xs = Es \ im ( f ) .

Mit der Angabe einer -Termalgebra = [E , F ] ist damit zugleich ihr Alphabet X festgelegt.

o() = s


Definition "homomorphe Fortsetzung einer Belegung"

Es sei = [A , F] eine -Algebra und = [E , G] eine -Ausdrucksalgebra über dem Alphabet X. Jede eindeutige Abbildung : X A heißt -Belegung von X. Eine eindeutige Abbildung *: E A, die für alle sS

folgenden Gleichungen 1. s*(x) = s(x) für alle xXs und2. s*(g (e1,e2 ,...,en)) = f (*w(e1,e2 ,...,en)) alle mit () = (w,s) und alle (e1,e2 ,...,en)Ew

genügt, heißt homomorphe (oder natürliche) Fortsetzung der -Belegung von X. Die Voraussetzung = [E , F ] -Termalgebra ist wesentlich.


Fortsetzungssatz für Termalgebren:Es sei = [A , F] eine -Algebra und = [E , G] eine -Ausdrucksalgebra über dem Alphabet X. Dann existiert zu jeder -Belegung von X genau ein Homomorphismus * von in , der über X mit übereinstimmt. Dieser ist die homomorphe Fortsetzung von .

Beweis: Die Existenz einer homomorphen Fortsetzung * ergibt sich aus

dem Fallunterscheidungssatz sofort. Außerdem ist * wegen 2. Gleichung Homomorphismus von in Die Eindeutigkeit folgt aus dem Satz von der Eindeutigkeit der homomorphen Fortsetzung.


Folgerung:Jede -PEANO-Algebra über X ist also freie Algebra mit dem freien Erzeugendensystem X über der Klasse aller -Algebren.

*

X


Isomorphie von PEANO-Algebren:Zwei -PEANO-Algebren = [A , F] und = [B , G] sind isomorph genau dann, wenn ihre PEANO-Basen X bzw. Y sortenweise gleichmächtig sind.

Beweis: Einfach wegen dem vorigen Satz und dem Satz über die Isomorphie freier Algebren, die umgekehrte Richtung ergibt sich leicht aus der Folgerung zum Fallunterscheidungssatz für Termalgebren.


Konstruktion von Ausdrucksalgebren Definition "Standardtermalgebra"

Sei = (S, , ) Signatur und sei X = (Xs)sS eine disjunkte Mengenfamilie, die auch zu disjunkt ist.Die Mengen Ti,s , iNz, sS seien folgende Mengen endlicher Folgen:T0,s = Xs { | () = (s) },Ti+1,s = Ti,s { t1t2 ,...tn | w(() = (w,s) (t1,t2 ,...,tn)Ti

w }.

Weiter bezeichne Ts = Ti,s i Nz

und T(X) = ( T(X)s )sS = ( Ts )sS .


Konstruktion von Ausdrucksalgebren noch zur Definition "Standardtermalgebra"

Bezeichnet nun f für jedes mit () = (w,s) die Funktion

f : T(X)w T(X)s vermöge

f (t1,t2 ,...,tn) = t1t2 ,...tn für alle (t1,t2 ,...,tn)T(X)w

mit w und f () = ,dann ist

T(X) = [ T(X) , ( f ) ] eine -Algebra und heißt Standardtermalgebra T(X)

der Signatur über dem Variablensystem (dem Alphabet) X.


Rechtfertigung der Bezeichnung:Die Standardtermalgebra T(X) über X ist eine PEANO-Algebra über X.

Beweis: durch Nachweis der verallgemeinerten PEANO-Axiome

Folgerung:Jede -PEANO-Algebra über X ist isomorph zur Standardtermalgebra T(X).


Initialität:Für jede -Algebra gibt es genau einen Homomorphismus

h: T .

In der Definition von T(X) kann X auch als S-sortige Familie

leerer Mengen X = = ()s S gewählt werden. Definition "Grundterme"

Es wird gesetzt:T = T() und T = T() .

Die Elemente von T heißen (Standard-)Grundterme.


"frei ist PEANOsch":Ist die -Algebra = [A , F] frei über der Klasse aller -Algebren mit dem freien Erzeugendensystem X, welches zu disjunkt ist, so ist eine -PEANO-Algebra über der PEANO-Basis X.

Beweis: durch Nachweis der verallgemeinerten PEANO-Axiome Folgerungen:1. Ist eine freie Algebra mit einem freien Erzeugendensystem X, so ist dieses eindeutig bestimmt. 2. Freie Algebren und sind isomorph genau dann, wenn ihre freien Erzeugendensysteme sortenweise gleichmächtig sind.


Jede freie -Algebra , frei über X, ist isomorph zur Standardtermalgebra T(X) vermöge eines X festlassenden Isomorphismus.

T(X) injektiv!

X X


Zusammenfassung Begriff Charakterisierungen

PEANO-Algebra innere analytisch

freie Algebra äußere algebraisch

Standard-termalgebra konstruktiv synthetisch


Äquivalenz der drei Charakterisierungen für Termalgebren:Für jede -Algebra = [A , F] und beliebige Teilfamilien X A sind folgende Aussagen äquivalent:1. ist -PEANO-Algebra über der PEANO-Basis X. 2. ist frei in der Klasse aller -Algebren mit dem freien Erzeugendensystem X. 3. ist isomorph zu T(X) vermöge eines X festlassenden Isomorphismus.

Beweis: (1) (2) : Folgerung zum Fortsetzungssatz (Folie 11)

(2) (1) : "frei ist PEANOsch" (Folie 17)

(1) (3) : Folgerung zu T(X) ist PEANO-Algebra (Folie 15)

(3) (2) : wird im folgenden noch gezeigt !


* T(X)

X

(3) (2) :

= * Homomorphismus von in mit

|X = (* )|X = * |X = * X = *|X = ,

also ist homomorphe Fortsetzung von .

Documents

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 4 / 1 Termalgebren Definition "Freie Algebra" Die -Algebra A = [A, F ] heißt