Algèbre de De Morgan

En mathématiques, une algèbre de De Morgan (nommé d'après Auguste De Morgan, un mathématicien et logicien britannique) est une structure A = (A, ∨, ∧, 0, 1, ¬) tel que:

(A, ∨, ∧, 0, 1) est un trellis distributif borné, et
¬ est une involution de De Morgan: ¬(x ∧ y) = ¬x ∨ ¬y et ¬¬x = x.

Dans une algèbre de De Morgan, les lois

¬x ∨ x = 1 (Principe du tiers exclu), et
¬x ∧ x = 0 (Principe de non-contradiction)

ne tiennent pas toujours. En présence des lois de De Morgan, une algèbre qui les satisfait devient une algèbre booléenne.

Remarque: Il en découle que ¬(x∨y) = ¬x∧¬y, ¬1 = 0 et ¬0 = 1 (par exemple: ¬1 = ¬1∨0 = ¬1∨¬¬0 = ¬(1∧¬0) = ¬¬0 = 0). Ainsi ¬ est un double automorphisme.

Les algèbres de De Morgan ont été introduites par Grigore Moisil^[1]^,^[2] autour de 1935^[2]. Bien que sans la restriction d'avoir un 0 et un 1^[3].

Les algèbres de De Morgan sont importantes pour l'étude des aspects mathématiques de la logique floue. L'algèbre floue F = ([0, 1], max (x, y), min (x, y), 0, 1, 1 - x) est un exemple d'algèbre de De Morgan où les lois du tiers exclu et de non-contradiction ne tiennent pas.

Un autre exemple est la logique à quatre valeurs de Dunn, dans laquelle faux < ni-vrai-ni-faux < vrai et faux < vrai-et-faux < vrai, alors que ni-vrai-ni-faux et vrai-et-faux ne sont pas comparable^[2].

Algèbre de Kleene[modifier | modifier le code]

Si une algèbre de De Morgan satisfait en outre x ∧ ¬x ≤ y ∨ ¬y, elle est appelée algèbre de Kleene^[3]^,^[1]. (Cette notion ne doit pas être confondue avec l'autre algèbre de Kleene généralisant les expressions régulières.)

Des exemples d'algèbres de Kleene dans le sens défini ci-dessus comprennent: les groupes ordonnés, Post-algèbres et algèbres de Łukasiewicz^[3]. Les algèbres booléennes répondent également à cette définition d'algèbre de Kleene. L'algèbre de Kleene la plus simple qui ne soit pas booléenne est la logique ternaire K₃ de Kleene^[4]. K₃ a fait sa première apparition dans On notation for ordinal numbers (1938) de Kleene^[5]. L'algèbre a été nommée d'après Kleene par Brignole et Monteiro^[6].

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « De Morgan algebra » (voir la liste des auteurs).

↑ ^{a et b} (en) T. S. Blyth et J. C. Varlet, Ockham algebras, Oxford University Press, 1994, 4-5 p. (ISBN 978-0-19-859938-8)
↑ ^{a b et c} (en) Jean-Yves Béziau, « A History of Truth-Values », dans Dov M. Gabbay, Francis Jeffry Pelletier et John Woods, Logic: A History of its Central Concepts, North Holland (an imprint of Elsevier), 2012, 280-281 p. (ISBN 978-0-08-093170-8)
↑ ^{a b et c} (en) Roberto Cignoli, « Injective de Morgan and Kleene Algebras », Proceedings of the American Mathematical Society, vol. 47, n^o 2,‎ 1975, p. 269–278 (DOI 10.1090/S0002-9939-1975-0357259-4, lire en ligne)
↑ Kalle Kaarli et Alden F. Pixley, Polynomial Completeness in Algebraic Systems, CRC Press, 21 juillet 2000, 297– (ISBN 978-1-58488-203-9, lire en ligne)
↑ https://www.jstor.org/stable/2267778
↑ Brignole, D. and Monteiro, A. Caractérisation des algèbres de Nelson par des égalites, Notas de Logica Matematica, Instituto de Matematica Universidad del sur Bahia Blanca 20 (1964) A (possibly abbreviated) version of this paper appeared later in Proc.

Lectures supplémentaires[modifier | modifier le code]

Raymond Balbes et Philip Dwinger, Distributive lattices, University of Missouri Press, 1975 (ISBN 978-0-8262-0163-8)
Birkhoff, G. review of Moisil Gr. C.. Recherches sur l’algèbre de la logique. Annales scientifiques de l’Université de Jassy, vol. 22 (1936), p. 1–118. in J. symb. log. 1, p. 63 (1936) DOI 10.2307/2268551
J. A. Kalman Lattices with involution, Trans. Amer. Math. Soc. 87 (1958), 485-491, DOI 10.1090/S0002-9947-1958-0095135-X
Piero Pagliani et Mihir Chakraborty, A Geometry of Approximation: Rough Set Theory: Logic, Algebra and Topology of Conceptual Patterns, Springer Science & Business Media, 2008 (ISBN 978-1-4020-8622-9)
Cattaneo, G. & Ciucci, D. Lattices with Interior and Closure Operators and Abstract Approximation Spaces. Lecture Notes in Computer Science 67–116 (2009). DOI 10.1007/978-3-642-03281-3_3
M. Gehrke, C. Walker, E. Walker (dir.), Topological and Algebraic Structures in Fuzzy Sets: A Handbook of Recent Developments in the Mathematics of Fuzzy Sets, Springer, 2003 (ISBN 978-1-4020-1515-1), « Fuzzy Logics Arising From Strict De Morgan Systems »
Maria Luisa Dalla Chiara, Roberto Giuntini et Richard Greechie, Reasoning in Quantum Theory: Sharp and Unsharp Quantum Logics, Springer, 2004 (ISBN 978-1-4020-1978-4)

[BV-1] {a et b} (en) T. S. Blyth et J. C. Varlet, Ockham algebras, Oxford University Press, 1994, 4-5 p. (ISBN 978-0-19-859938-8)

[Bez-2] {a b et c} (en) Jean-Yves Béziau, « A History of Truth-Values », dans Dov M. Gabbay, Francis Jeffry Pelletier et John Woods, Logic: A History of its Central Concepts, North Holland (an imprint of Elsevier), 2012, 280-281 p. (ISBN 978-0-08-093170-8)

[Cignoli75-3] {a b et c} (en) Roberto Cignoli, « Injective de Morgan and Kleene Algebras », Proceedings of the American Mathematical Society, vol. 47, n^o 2,‎ 1975, p. 269–278 (DOI 10.1090/S0002-9939-1975-0357259-4, lire en ligne)

[KaarliPixley2000-4] Kalle Kaarli et Alden F. Pixley, Polynomial Completeness in Algebraic Systems, CRC Press, 21 juillet 2000, 297– (ISBN 978-1-58488-203-9, lire en ligne)

[5] ttps://www.jstor.org/stable/2267778

[6] Brignole, D. and Monteiro, A. Caractérisation des algèbres de Nelson par des égalites, Notas de Logica Matematica, Instituto de Matematica Universidad del sur Bahia Blanca 20 (1964) A (possibly abbreviated) version of this paper appeared later in Proc.

[1]

[2]

[3]

[4]

[5]

[6]