Click here to load reader

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

  • View
    107

  • Download
    1

Embed Size (px)

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

  • Folie 1
  • Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 1 Kapitel 6 Kongruenzen Definition "Kongruenzrelation" Eine -Kongruenz R ber einer -Algebra A = [A, F ] ist eine Familie R = (R s ) s S von quivalenzrelationen R s in A s mit der Eigenschaft der Kompatibilitt, d.h. fr alle mit ( ) = (s 1,s 2,...,s n,s) gilt: wenn (a i,b i ) R s i fr 1 i n, so ist auch ( f (a 1,a 2,...,a n ), f (b 1,b 2,...,b n ) ) R s.
  • Folie 2
  • Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 2 quivalenzklasse von a A s bzgl. R s : [a] R s oder [a] R oder [a] s oder [a] Familie der Mengen der quivalenzklassen: A R = (A s R s ) s S mit A s R s = { [a] R s | a A s }. Durch f induzierte Operationen f * ber den quivalenzklassen: f * ([a 1 ] R s 1, [a 2 ] R s 2,..., [a n ] R s n ) = df [ f (a 1,a 2,...,a n )] R s Wenn die R s bzgl. den f kompatibel sind, so ist diese Definition reprsentantenunabhngig, d.h. die f * sind tatschlich Operationen ber A R.
  • Folie 3
  • Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 3 Definition "Faktoralgebra" R sei eine -Kongruenz ber der -Algebra A = [A, F ]. Die -Algebra [A R, (f * ) ] mit den durch f induzierten Operationen f * heit die Faktoralgebra A R der -Algebra A nach der -Kongruenz R. Homomorphiesatz: Es sei A = [(A s ) s S, (f ) ] eine -Algebra und eine -Kongruenz ber A. Dann ist die Abbildung : A A mit (a) = [a] ein -Homomorphismus von A nach A. Ist h: A B ein weiterer -Homomorphismus, und ist h die Bildgleichheit bzgl. h, so ist h eine -Kongru- enz ber A ; und wenn h zustzlich surjektiv ist, dann sind A h und B isomorph.
  • Folie 4
  • Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 4 A B A h Homomorphiesatz: h Die Abbildung heit auch natrliche Abbildung von. = nat( ).
  • Folie 5
  • 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 vllig 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 fr eine eindeutig bestimmte Kongruenz R. Semantik entspricht also einer Kongruenzrelation ber der Syntax!
  • Folie 6
  • Syntax, Semantik, Spezifikation - Grundlagen der Informatik R. Hartwig Kapitel 6 / 6 Faktorisierung des Erzeugendensystems: Es sei A eine -Algebra und R eine -Kongruenz ber A. Wenn X ein Erzeugendensystem von A ist, dann ist X R ein Erzeugendensystem der Faktoralgebra A R. Beweis: Wir haben A = [X] A. = nat(R) ist Homomorphismus von A auf A R. Also gilt A R = (A) = ( [X] A ) = [ ( X ) ] A R entsprechend dem Satz vom homomorphen Bild der Hlle. Weiter ist (X) = ( s (X s )) s S mit s (X s ) = { s (x) | x X s } = { [x] R s | x X s } = X s R s, womit A R = [ X R] A R bewiesen ist.