Algèbre de De Morgan
From Wikipedia, the free encyclopedia
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].
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 K3 de Kleene[4]. K3 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].
