www.wikidata.de-de.nina.az

Relationsalgebra Dieser Artikel behandelt den Begriff aus der Theorie der Booleschen Algebren Zum ähnlich lautenden Begr

Relationsalgebra

In der Mathematik und abstrakten Algebra ist eine Relationsalgebra (englisch: relation algebra) eine residuierte Boolesche Algebra, die um eine Involution (als einstellige Operation), genannt Konverse, erweitert wurde. Das für diese Begriffsbildung maßgebliche Beispiel einer Relationsalgebra ist die Algebra aller zweistelligen Relationen auf einer Menge (d. h. auf den Teilmengen des kartesischen Produkts ), zusammen mit der Verkettung von Relationen und der Umkehrrelation (konversen Relation).

Definition Bearbeiten

Die folgenden Axiome sind angelehnt an Givant (2006, Seite 283), und wurden zuerst 1948 von Alfred Tarski aufgestellt.

Eine Relationsalgebra ist ein 9-Tupel , für das gilt:

  • ist eine Boolesche Algebra mit Konjunktion , Disjunktion und Negation sowie Nullelement und Einselement :
  • ist ein Monoid mit einem eigenen Einselement ,
  • ist eine Involution, genannt Konverse,
  • , d. h. die Konverse ist gegenüber der Verknüpfung treu,
  • ,
  • (Distributivität) und
  • , was nichts anderes bedeutet als (Peircesches Gesetz).
    Veranschaulichung zum Peirceschen Gesetz, hier mit u, v, w statt a, b, c

Beispiel Bearbeiten

Die homogenen zweistelligen Relationen bilden die Relationsalgebra

unter Verwendung der Notationen .

Peirce-Algebra Bearbeiten

  • Eine Weiterentwicklung davon ist die (heterogene) Peirce-Algebra, benannt nach Charles Sanders Peirce – eine abstrakte Beschreibung der Relationsalgebra der homogenen zweistelligen Relationen zusammen mit Vor-/Nachbeschränkungen auf Mengen.

Siehe auch Bearbeiten

Einzelnachweise und Bemerkungen Bearbeiten

  1. eine Boolesche Algebra, deren Verbandsstruktur ein residuierter Verband ist (englisch: residuated Algebra), siehe: Marcel Erné: Algebraische Verbandstheorie, Institut für Algebra, Zahlentheorie und Diskrete Mathematik, Leibniz Universität Hannover
  2. Alfred Tarski (1948) "Abstract: Representation Problems for Relation Algebras," Bulletin of the AMS 54: 80.
  3. Chris Brink et al. Seite 12
  4. Nach Robin Hirsch, Ian Hodkinson: Relation algebras Seite 7, auf: Third Indian Conference on Logic and its Applications (ICLA), 7.–11. Januar 2009, Chennai, India. Das Tupel wurde an die obige Definition angeglichen.
  5. Von den Verknüpfungen (einstellig), sowie (zweistellig) sind - genau genommen - die Einschränkungen auf bzw. gemeint.

Literatur Bearbeiten

  • Rudolf Carnap: Introduction to Symbolic Logic and its Applications. Dover Publications, 1958.
  • Steven Givant: The calculus of relations as a foundation for mathematics. In: Journal of Automated Reasoning. Band 37, 2006, S. 277–322, doi:10.1007/s10817-006-9062-x.
  • P. R. Halmos: Naive Set Theory. Van Nostrand, 1960.
  • Leon Henkin, Alfred Tarski, J. D. Monk: Cylindric Algebras. Part 1, 1971, und Part 2, 1985, North Holland.
  • R. Hirsch, I. Hodkinson: Relation Algebra by Games. (= Studies in Logic and the Foundations of Mathematics. vol. 147). Elsevier Science, 2002, ISBN 0-444-50932-1.
  • Bjarni Jónsson, Constantine Tsinakis: Relation algebras as residuated Boolean algebras. In: Algebra Universalis. Band 30, 1993, S. 469–478, doi:10.1007/BF01195378.
  • Roger Maddux: The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations. In: Studia Logica. Band 50, Nr. 3–4, 1991, S. 421–455, doi:10.1007/BF00370681 (iastate.edu [PDF]).
  • Roger D Maddux: Relation Algebras. (= Studies in Logic and the Foundations of Mathematics. Vol. 150). Elsevier Science, 2006, ISBN 1-280-64163-0.
  • Patrick Suppes: Axiomatic Set Theory. Van Nostrand. Dover 1972, Chapter 3.
  • Gunther Schmidt: Relational Mathematics. Cambridge University Press, 2010.
  • Alfred Tarski: On the calculus of relations. In: Journal of Symbolic Logic. Band 6, 1941, S. 73–89, doi:10.2307/2268577.
  • Steven Givant: A Formalization of Set Theory without Variables. American Mathematical Society, Providence RI 1987, ISBN 0-8218-1041-3.

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Dieser Artikel behandelt den Begriff aus der Theorie der Booleschen Algebren Zum ahnlich lautenden Begriff aus der Theorie der Datenbanken siehe Relationale Algebra In der Mathematik und abstrakten Algebra ist eine Relationsalgebra englisch relation algebra eine residuierte Boolesche Algebra 1 die um eine Involution als einstellige Operation genannt Konverse erweitert wurde Das fur diese Begriffsbildung massgebliche Beispiel einer Relationsalgebra ist die Algebra 2 A 2 P A A displaystyle 2 A 2 mathcal P A times A aller zweistelligen Relationen auf einer Menge A displaystyle A d h auf den Teilmengen des kartesischen Produkts A A A 2 displaystyle A times A A 2 zusammen mit der Verkettung von Relationen und der Umkehrrelation konversen Relation Inhaltsverzeichnis 1 Definition 2 Beispiel 3 Peirce Algebra 4 Siehe auch 5 Einzelnachweise und Bemerkungen 6 Literatur 7 WeblinksDefinition BearbeitenDie folgenden Axiome sind angelehnt an Givant 2006 Seite 283 und wurden zuerst 1948 von Alfred Tarski aufgestellt 2 Eine Relationsalgebra ist ein 9 Tupel L 0 1 I displaystyle L land lor neg 0 1 circ mathrm I smile nbsp fur das gilt L 0 1 displaystyle L land lor neg 0 1 nbsp ist eine Boolesche Algebra mit Konjunktion displaystyle land nbsp Disjunktion displaystyle lor nbsp und Negation displaystyle neg nbsp sowie Nullelement 0 displaystyle 0 nbsp und Einselement 1 displaystyle 1 nbsp L I displaystyle L circ mathrm I nbsp ist ein Monoid mit einem eigenen Einselement I displaystyle mathrm I nbsp displaystyle smile nbsp ist eine Involution genannt Konverse a b L a b b a displaystyle forall a b in L a circ b smile b smile circ a smile nbsp d h die Konverse ist gegenuber der Verknupfung displaystyle circ nbsp treu a b L a b a b displaystyle forall a b in L a lor b smile a smile lor b smile nbsp a b c L a b c a c b c displaystyle forall a b c in L a lor b circ c a circ c lor b circ c nbsp Distributivitat und a b L a a b b b displaystyle forall a b in L a smile circ neg a circ b lor neg b neg b nbsp was nichts anderes bedeutet als a b c a c b c b a displaystyle a circ b leq neg c Leftrightarrow a smile circ c leq neg b Leftrightarrow c circ b smile leq neg a nbsp Peircesches Gesetz 3 nbsp Veranschaulichung zum Peirceschen Gesetz hier mit u v w statt a b cBeispiel BearbeitenDie homogenen zweistelligen Relationen R A A displaystyle R subseteq A times A nbsp bilden die Relationsalgebra R e A 2 A 2 A 2 I A displaystyle mathfrak Re A 2 A 2 cap cup emptyset A 2 circ mathrm I A smile nbsp 4 unter Verwendung der Notationen A 2 A A 2 A 2 P A A displaystyle A 2 A times A 2 A 2 mathcal P A times A nbsp 5 Peirce Algebra BearbeitenEine Weiterentwicklung davon ist die heterogene Peirce Algebra benannt nach Charles Sanders Peirce eine abstrakte Beschreibung der Relationsalgebra R e A displaystyle mathfrak Re A nbsp der homogenen zweistelligen Relationen zusammen mit Vor Nachbeschrankungen auf Mengen Siehe auch BearbeitenBoolesche Algebra Heyting AlgebraEinzelnachweise und Bemerkungen Bearbeiten eine Boolesche Algebra deren Verbandsstruktur ein residuierter Verband ist englisch residuated Algebra siehe Marcel Erne Algebraische Verbandstheorie Institut fur Algebra Zahlentheorie und Diskrete Mathematik Leibniz Universitat Hannover Alfred Tarski 1948 Abstract Representation Problems for Relation Algebras Bulletin of the AMS 54 80 Chris Brink et al Seite 12 Nach Robin Hirsch Ian Hodkinson Relation algebras Seite 7 auf Third Indian Conference on Logic and its Applications ICLA 7 11 Januar 2009 Chennai India Das Tupel wurde an die obige Definition angeglichen Von den Verknupfungen displaystyle smile nbsp einstellig sowie displaystyle cap cup circ nbsp zweistellig sind genau genommen die Einschrankungen auf A displaystyle A nbsp bzw A 2 displaystyle A 2 nbsp gemeint Literatur BearbeitenRudolf Carnap Introduction to Symbolic Logic and its Applications Dover Publications 1958 Steven Givant The calculus of relations as a foundation for mathematics In Journal of Automated Reasoning Band 37 2006 S 277 322 doi 10 1007 s10817 006 9062 x P R Halmos Naive Set Theory Van Nostrand 1960 Leon Henkin Alfred Tarski J D Monk Cylindric Algebras Part 1 1971 und Part 2 1985 North Holland R Hirsch I Hodkinson Relation Algebra by Games Studies in Logic and the Foundations of Mathematics vol 147 Elsevier Science 2002 ISBN 0 444 50932 1 Bjarni Jonsson Constantine Tsinakis Relation algebras as residuated Boolean algebras In Algebra Universalis Band 30 1993 S 469 478 doi 10 1007 BF01195378 Roger Maddux The Origin of Relation Algebras in the Development and Axiomatization of the Calculus of Relations In Studia Logica Band 50 Nr 3 4 1991 S 421 455 doi 10 1007 BF00370681 iastate edu PDF Roger D Maddux Relation Algebras Studies in Logic and the Foundations of Mathematics Vol 150 Elsevier Science 2006 ISBN 1 280 64163 0 Patrick Suppes Axiomatic Set Theory Van Nostrand Dover 1972 Chapter 3 Gunther Schmidt Relational Mathematics Cambridge University Press 2010 Alfred Tarski On the calculus of relations In Journal of Symbolic Logic Band 6 1941 S 73 89 doi 10 2307 2268577 Steven Givant A Formalization of Set Theory without Variables American Mathematical Society Providence RI 1987 ISBN 0 8218 1041 3 Weblinks BearbeitenRelationsalgebra Mathepedia deutsch Yohji Akama Yasuo Kawahara Hitoshi Furusawa Constructing Allegory from Relation Algebra and Representation Theorems WayBack Richard Bird Oege de Moor Paul Hoogendijk Generic Programming with Relations and Functors R P de Freitas J P Viana A Completeness Result for Relation Algebra with Binders Chris Brink Katarina Britz Renate A Schmidt Peirce AlgebrasPeter Jipsen Relation algebras WayBack Foundations of Relations and Kleene Algebra Computer Aided Investigations of Relation Algebras A Gentzen System And Decidability For Residuated LatticesVaughan Pratt Origins of the Calculus of Binary Relations The Second Calculus of Binary Relations Uta Priss An FCA interpretation of Relation Algebra Relation Algebra and FCAWolfram Kahl Gunther Schmidt Exploring Finite Relation Algebras Using Tools Written in Haskell RATH Relation Algebra Tools in Haskell Abgerufen von https de wikipedia org w index php title Relationsalgebra amp oldid 212704280