6
Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz R über einer - Algebra = [A , F ] ist eine Familie R = (R s ) sS von Äquivalenzrelationen R s in A s mit der Eigenschaft der Kompatibilität, d.h. für alle mit () = (s 1 ,s 2 ,...,s n ,s) gilt: wenn (a i ,b i ) R s i für 1 i n, so ist auch

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz

Embed Size (px)

Citation preview

Page 1: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz

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

Kapitel 6

Kongruenzen

Definition "Kongruenzrelation"

Eine -Kongruenz R über einer -Algebra = [A , F ] ist eine Familie R = (Rs)sS von Äquivalenzrelationen Rs in As mit der Eigenschaft der Kompatibilität, d.h. für alle mit () = (s1,s2 ,...,sn,s) gilt:wenn (ai ,bi) Rsi

für 1 i n,

so ist auch ( f (a1,a2 ,...,an), f (b1,b2 ,...,bn) ) Rs .

Page 2: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 2

Äquivalenzklasse von a As bzgl. Rs :[a]Rs

oder [a]R oder [a]s

oder [a]

Familie der Mengen der Äquivalenzklassen:A R = (As Rs)sS

mit As Rs = { [a]Rs | a As }.

Durch f induzierte Operationen f* über den Äquivalenzklassen:

f*([a1]Rs1, [a2]Rs2

,..., [an]Rsn) =df [ f (a1,a2 ,...,an)]Rs

Wenn die Rs bzgl. den f kompatibel sind, so ist diese Definition repräsentantenunabhängig, d.h. die f* sind tatsächlich Operationen über A R.

Page 3: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 3

Definition "Faktoralgebra"

R sei eine -Kongruenz über der -Algebra = [A , F ].Die -Algebra [A R , (f*) ] mit den durch finduzierten Operationen f* heißt die Faktoralgebra R der -Algebra nach der -Kongruenz R. Homomorphiesatz:Es sei = [(As)sS , (f) ] eine -Algebra undeine -Kongruenz über . Dann ist die Abbildung : A A mit (a) = [a] ein -Homomorphismus von nach . Ist h: ein weiterer -Homomorphismus, und ist h die Bildgleichheit bzgl. h, so ist h eine -Kongru-enz über ; und wenn h zusätzlich surjektiv ist, dann sind hund isomorph.

Page 4: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz

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

h

Homomorphiesatz:h

Die Abbildung heißt auch natürliche Abbildung von = nat(

Page 5: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz

Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 5

1. Jede Faktoralgebra ist homomorphes Bild der Ausgangs- algebra, und umgekehrt ist jedes homomorphe Bild einer Algebra isomorph zu einer Faktoralgebra dieser Algebra.2. Damit kann jedes homomorphe Bild einer Algebra völlig „innerhalb“ der Algebra gefunden werden.3. Eine Faktoralgebra ist festgelegt durch die Algebra und eine Kongruenz. Nach dem Homomorphiesatz kann das Studium der Homomorphismen gleichwertig ersetzt werden durch das Studium der Kongruenzen!4. Semantik ist ein homomorphes Bild SEM der syntaktischen Algebra SYN. Damit gilt

SEM SYN R für eine eindeutig bestimmte Kongruenz R.• Semantik entspricht also einer Kongruenzrelation über der Syntax!

Page 6: Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz

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

Faktorisierung des Erzeugendensystems:Es sei eine -Algebra und R eine -Kongruenz über . Wenn X ein Erzeugendensystem von ist, dann ist X R ein Erzeugendensystem der Faktoralgebra R.

Beweis: Wir haben A = [X] . = nat(R) ist Homomorphismus von auf

R. Also gilt A R = (A) = ([X]) = [(X)] R

entsprechend dem Satz vom homomorphen Bild der Hülle. Weiter ist (X) = (s(Xs))sS mit

s(Xs) = {s(x) | x Xs } = { [x]Rs | x Xs } = Xs Rs ,

womit A R = [X R] R bewiesen ist.