De Morgan algebra: Difference between revisions
| Line 39: | Line 39: | ||
* J. A. Kalman [http://www.ams.org/journals/tran/1958-087-02/S0002-9947-1958-0095135-X/S0002-9947-1958-0095135-X.pdf Lattices with involution], Trans. Amer. Math. Soc. 87 (1958), 485-491, {{doi|10.1090/S0002-9947-1958-0095135-X}} |
* J. A. Kalman [http://www.ams.org/journals/tran/1958-087-02/S0002-9947-1958-0095135-X/S0002-9947-1958-0095135-X.pdf Lattices with involution], Trans. Amer. Math. Soc. 87 (1958), 485-491, {{doi|10.1090/S0002-9947-1958-0095135-X}} |
||
* {{cite book|author1=Piero Pagliani|author2=Mihir Chakraborty|title=A Geometry of Approximation: Rough Set Theory: Logic, Algebra and Topology of Conceptual Patterns|year=2008|publisher=Springer Science & Business Media|isbn=978-1-4020-8622-9|at=Part II. Chapter 6. Basic Logico-Algebraic Structures, pp. 193-210}} |
* {{cite book|author1=Piero Pagliani|author2=Mihir Chakraborty|title=A Geometry of Approximation: Rough Set Theory: Logic, Algebra and Topology of Conceptual Patterns|year=2008|publisher=Springer Science & Business Media|isbn=978-1-4020-8622-9|at=Part II. Chapter 6. Basic Logico-Algebraic Structures, pp. 193-210}} |
||
* 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}} |
|||
[[Category:Algebra]] |
[[Category:Algebra]] |
||
Revision as of 07:03, 21 August 2014
In mathematics, a De Morgan algebra (named after Augustus De Morgan, a British mathematician and logician) is a structure A = (A, ∨, ∧, 0, 1, ¬) such that:
- (A, ∨, ∧, 0, 1) is a bounded distributive lattice, and
- ¬ is a De Morgan involution: ¬(x ∧ y) = ¬x ∨ ¬y and ¬¬x = x. (i.e. an involution that additionally satisfies De Morgan's laws)
In a De Morgan algebra:
- ¬x ∨ x = 1 (law of the excluded middle), and
- ¬x ∧ x = 0 (law of noncontradiction)
do not always hold (when they do, the algebra becomes a Boolean algebra).
Remark: It follows that ¬( x∨y) = ¬x∧¬y, ¬1 = 0 and ¬0 = 1 (e.g. ¬1 = ¬1∨0 = ¬1∨¬¬0 = ¬(1∧¬0) = ¬¬0 = 0). Thus ¬ is a dual automorphism.
De Morgan algebras were introduced by Grigore Moisil[1][2] around 1935.[2] although without the restriction of having a 0 and an 1.[3] They were then variously called quasi-boolean algebras in the Polish school, e.g. by Rasiowa and also distributive i-lattices by J. A. Kalman.[2] (i-lattice being an abbreviation for lattice with involution.) The have been further studied in the Argentian algebraic logic school of Antonio Monteiro.[1][2]
De Morgan algebras are important for the study of the mathematical aspects of fuzzy logic. The standard fuzzy algebra F = ([0, 1], max(x, y), min(x, y), 0, 1, 1 − x) is an example of a De Morgan algebra where the laws of excluded middle and noncontradiction do not hold.
Kleene algebra
If a De Morgan algebra additionally satisfies x ∧ ¬x ≤ y ∨ ¬y, it is called a Kleene algebra.[3][1] (This notion should not to be confused with the other Kleene algebra generalizing regular expressions.) This notion has also been called a normal i-lattice by J. A. Kalman.
Examples of Kleene algebras in the sense defined above include: lattice-ordered groups, Post algebras and Łukasiewicz algebras.[3] Boolean algebras also meet this definition of Kleene algebra. The simplest Kleene algebra that is not Boolean is Kleene's three-valued logic K3.[4] K3 made its first appearance in Kleene's On notation for ordinal numbers (1938).[5] The algebra was named after Kleene by Brignole and Monteiro.[6]
Related notions
De Morgan algebra is not the only plausible way to generalize the Boolean algebra. Another way is to keep ¬x ∧ x = 0 (i.e. the law of noncontradiction) but to drop the law of the excluded middle. This approach (called semicomplementation) is well-defined even for a [meet] semilattice; if the set of semicomplements has a greatest element it is usually called pseudocomplement. If the pseudocomplement thus defined satisfies the law of the excluded middle, the resulting algebra is also Boolean. However, if only the weaker law ¬x ∨ ¬¬x = 1 is required, this results in Stone algebras.[1] More generally, both De Morgan and Stone algebras are proper subclasses of Ockham algebras.
Notes
- ^ a b c d Blyth & Varlet 1994, p. 5.
- ^ a b c d Béziau 2012, p. 280.
- ^ a b c Cignoli 1975.
- ^ Kalle Kaarli; Alden F. Pixley (21 July 2000). Polynomial Completeness in Algebraic Systems. CRC Press. pp. 297–. ISBN 978-1-58488-203-9.
- ^ http://www.jstor.org/stable/2267778
- ^ Brignole, D. and Monteiro, A. Caracterisation des algebres de Nelson par des egalites, 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. Acad. Japan doi:10.3792/pja/1195521624 doi:10.3792/pja/1195521625
References
- Cignoli, Roberto (1975). "Injective de Morgan and Kleene Algebras" (PDF). Proceedings of the American Mathematical Society. 47 (2): 269–278. doi:10.1090/S0002-9939-1975-0357259-4.
{{cite journal}}: Invalid|ref=harv(help) - Blyth, T. S.; Varlet, J. C. (1994). Ockham algebras. Oxford University Press. ISBN 978-0-19-859938-8.
{{cite book}}: Invalid|ref=harv(help) - Béziau, Jean-Yves (2012). "A History of Truth-Values". Logic: A History of its Central Concepts. North Holland (an imprint of Elsevier). ISBN 978-0-08-093170-8.
{{cite book}}: Invalid|ref=harv(help); Unknown parameter|editors=ignored (|editor=suggested) (help)
Further reading
- Raymond Balbes; Philip Dwinger (1975). Distributive lattices. University of Missouri Press. Chapter IX. De Morgan Algebras and Lukasiewicz Algebras. 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), pp. 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; Mihir Chakraborty (2008). A Geometry of Approximation: Rough Set Theory: Logic, Algebra and Topology of Conceptual Patterns. Springer Science & Business Media. Part II. Chapter 6. Basic Logico-Algebraic Structures, pp. 193-210. 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