De Morgan-Algebra - De Morgan algebra

In der Mathematik ist eine De Morgan-Algebra (benannt nach Augustus De Morgan , einem britischen Mathematiker und Logiker) eine Struktur A = (A, ∨, ∧, 0, 1, ¬) derart, dass:

In einer De Morgan-Algebra sind die Gesetze

nicht immer halten. Bei Vorhandensein der De Morgan-Gesetze impliziert jedes Gesetz das andere, und eine Algebra, die sie erfüllt, wird zu einer Booleschen Algebra .

Bemerkung: Es folgt ¬(x y) = ¬x ∧ ¬y, ¬1 = 0 und ¬0 = 1 (zB ¬1 = ¬1 ∨ 0 = ¬1 ∨ ¬¬0 = ¬(1 ∧ ¬0 ) = ¬¬0 = 0). Somit ist ¬ ein dualer Automorphismus von ( A , ∨, ∧, 0, 1).

Wenn das Gitter stattdessen durch die Ordnung definiert wird, dh (A, ≤) ist eine beschränkte Teilordnung mit einer kleinsten oberen Schranke und einer größten unteren Schranke für jedes Elementpaar, und die so definierten Meet- und Join-Operationen erfüllen das Distributivgesetz , dann kann die Komplementation auch als involutiver Anti-Automorphismus definiert werden, also als Struktur A = (A, ≤, ¬) mit:

De Morgan-Algebren wurden um 1935 von Grigore Moisil eingeführt , allerdings ohne die Einschränkung, eine 0 und eine 1 zu haben. Sie wurden dann in der polnischen Schule verschiedentlich als quasi-boolesche Algebren bezeichnet , zB von Rasiowa und auch distributive i- Gitter von JA Kalman . ( i- lattice ist eine Abkürzung für Gitter mit Involution.) Sie wurden in der argentinischen algebraischen Logikschule von Antonio Monteiro weiter untersucht .

De Morgan-Algebren sind wichtig für das Studium der mathematischen Aspekte der Fuzzy-Logik . Die Standard-Fuzzy-Algebra F = ([0, 1], max( x ,  y ), min( x ,  y ), 0, 1, 1 −  x ) ist ein Beispiel für eine De Morgan-Algebra, bei der die Gesetze der ausgeschlossenen Mitte und Widerspruchsfreiheit nicht halten.

Ein weiteres Beispiel ist Dunns 4-wertige Logik, in der falsch < weder-wahr-noch-falsch < wahr und falsch < beides-wahr-und-falsch < wahr ist , während weder-wahr-noch-falsch und beides-wahr- and-false sind nicht vergleichbar.

Kleene-Algebra

Erfüllt eine De Morgan-Algebra zusätzlich x ¬ x ≤ y ∨ ¬ y , so heißt sie Kleene-Algebra . (Dieser Begriff sollte mit dem anderen nicht zu verwechseln Kleene Algebra verallgemeinern reguläre Ausdrücke ) . Dieser Begriff ist auch ein genannt normalen i -Gerüst von Kalman.

Beispiele für Kleene-Algebren im oben definierten Sinne sind: gittergeordnete Gruppen , Post-Algebren und ukasiewicz-Algebren . Boolesche Algebren erfüllen diese Definition der Kleene-Algebra ebenso wie jede De Morgan-Algebra, die ¬ x  ∧  x = 0 erfüllt . Die einfachste Kleene-Algebra, die nicht boolesch ist, ist Kleenes dreiwertige Logik K 3 . K 3 hatte seinen ersten Auftritt in Kleene ‚s On - Notation für Ordnungszahlen (1938). Die Algebra wurde von Brignole und Monteiro nach Kleene benannt.

Verwandte Begriffe

De Morgan-Algebren sind nicht die einzige plausible Möglichkeit, Boolesche Algebren zu verallgemeinern. Eine andere Möglichkeit besteht darin, ¬ x  ∧  x = 0 (dh das Gesetz des Widerspruchs) beizubehalten, aber das Gesetz der ausgeschlossenen Mitte und das Gesetz der doppelten Negation wegzulassen. Dieser Ansatz (als Semikomplementation bezeichnet ) ist selbst für ein ( Treffer- ) Semigitter wohldefiniert ; Wenn die Menge der Semikomplemente ein größtes Element hat, wird sie normalerweise als Pseudokomplement bezeichnet . Erfüllt das Pseudokomplement das Gesetz der ausgeschlossenen Mitte, ist die resultierende Algebra ebenfalls Boolesch. Wird jedoch nur das schwächere Gesetz ¬ x  ∨ ¬¬ x = 1 benötigt, so erhält man Stone-Algebren . Allgemeiner gesagt sind sowohl De Morgan- als auch Stone-Algebren echte Unterklassen von Ockham-Algebren .

Siehe auch

Verweise

Weiterlesen

  • Balbes, Raymond; Dwinger, Philipp (1975). „Kapitel IX. De Morgan Algebras und Lukasiewicz Algebras“. Verteilungsgitter . University of Missouri Press. ISBN 978-0-8262-0163-8.
  • Birkhoff, G. (1936). „Rezensionen: Moisil Gr. C.. Recherches sur l'algèbre de la logique. Annales scientifiques de l'Université de Jassy, ​​Bd. 22 (1936), S. 1-118 “. Die Zeitschrift für symbolische Logik . 1 (2): 63. doi : 10.2307/2268551 . JSTOR  2268551 .
  • Batyrshin, IZ (1990). „Über unscharfe Entropiemaße auf Kleene-Algebren“. Fuzzy-Sets und -Systeme . 34 (1): 47–60. doi : 10.1016/0165-0114(90)90126-Q .
  • Kalman, JA (1958). "Gitter mit Involution" (PDF) . Transaktionen der American Mathematical Society . 87 (2): 485–491. doi : 10.1090/S0002-9947-1958-0095135-X . JSTOR  1993112 .
  • Pagliani, Piero; Chakraborty, Mihir (2008). Eine Näherungsgeometrie: Grobe Mengenlehre: Logik, Algebra und Topologie konzeptueller Muster . Springer Wissenschaft & Wirtschaftsmedien. Teil II. Kapitel 6. Grundlegende logisch-algebraische Strukturen, S. 193-210. ISBN 978-1-4020-8622-9.
  • Cattaneo, G.; Ciucci, D. (2009). „Gitter mit Innen- und Abschlussoperatoren und abstrakten Approximationsräumen“. Transaktionen auf groben Sets X . Skript zur Vorlesung Informatik 67–116. 5656 . S. 67–116. doi : 10.1007/978-3-642-03281-3_3 . ISBN 978-3-642-03280-6.
  • Gehrke, M. ; Walker, C.; Walker, E. (2003). „Fuzzy Logics, die aus strengen De Morgan-Systemen entstehen“. In Rodabaugh, SE; Klement, EP (Hrsg.). Topologische und algebraische Strukturen in Fuzzy-Mengen: Ein Handbuch der jüngsten Entwicklungen in der Mathematik von Fuzzy-Mengen . Springer. ISBN 978-1-4020-1515-1.
  • Dalla Chiara, Maria Luisa ; Giuntini, Roberto; Greechie, Richard (2004). Argumentation in der Quantentheorie: Scharfe und unscharfe Quantenlogiken . Springer. ISBN 978-1-4020-1978-4.