Wiederholung: Relationen

• (zweistellige) Relation R⊆U², gerichteter Graph
• Operationen:
  • Mengen-Operationen (Vereinigung, Durchschnitt)
  • Produkt RoS, Potenz R^k, inverse Relation R^-1
  • symmetrische Hülle R¹∪R^-1
  • R⁺ transitive Hülle = $\bigcup_{{k>0}}^{}$R^k
  • R⁼ reflexive Hülle = R⁰∪R¹
  • R^* transitive und reflexive Hülle = $\bigcup_{{k\ge 0}}^{}$R^k
• Eigenschaften:
  • symmetrisch, reflexix, transitiv; linear (total),
  • terminierend (wohlfundiert)
• alle zweist. Relationen auf U bilden Halbring (mit ∪,o)