Kleene algebra (with involution)

TheInfoList

OR:

__NOTOC__ 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 In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set ...
, and * ¬ is a De Morgan involution: ¬(''x'' ∧ ''y'') = ¬''x'' ∨ ¬''y'' and ¬¬''x'' = ''x''. (i.e. an
involution Involution may refer to: * Involute, a construction in the differential geometry of curves * '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
De Morgan's laws In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...
) In a De Morgan algebra, the laws * ¬''x'' ∨ ''x'' = 1 (
law of the excluded middle In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontradi ...
), and * ¬''x'' ∧ ''x'' = 0 (
law of noncontradiction In logic, the law of non-contradiction (LNC) (also known as the law of contradiction, principle of non-contradiction (PNC), or the principle of contradiction) states that contradictory propositions cannot both be true in the same sense at the sa ...
) do not always hold. In the presence of the De Morgan laws, either law implies the other, and an algebra which satisfies them becomes a
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
. 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 In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphism ...
of (''A'', ∨, ∧, 0, 1). If the lattice is defined in terms of the order instead, i.e. (A, ≤) is a bounded partial order with a least upper bound and greatest lower bound for every pair of elements, and the meet and join operations so defined satisfy the distributive law, then the complementation can also be defined as an involutive anti-automorphism, that is, a structure ''A'' = (A, ≤, ¬) such that: * (A, ≤) is a bounded
distributive lattice In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set ...
, and * ¬¬''x'' = ''x'', and * ''x'' ≤ ''y'' → ¬''y'' ≤ ¬''x''. De Morgan algebras were introduced by Grigore Moisil around 1935, although without the restriction of having a 0 and a 1. 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. (''i''-lattice being an abbreviation for lattice with involution.) They have been further studied in the Argentinian algebraic logic school of Antonio Monteiro. De Morgan algebras are important for the study of the mathematical aspects of
fuzzy logic Fuzzy logic is a form of many-valued logic in which the truth value of variables may be any real number between 0 and 1. It is employed to handle the concept of partial truth, where the truth value may range between completely true and complete ...
. The standard fuzzy algebra ''F'' = (
, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
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. Another example is Dunn's 4-valued logic, in which ''false'' < ''neither-true-nor-false'' < ''true'' and ''false'' < ''both-true-and-false'' < ''true'', while ''neither-true-nor-false'' and ''both-true-and-false'' are not comparable.

# Kleene algebra

If a De Morgan algebra additionally satisfies ''x'' ∧ ¬''x'' ≤ ''y'' ∨ ¬''y'', it is called a Kleene algebra. (This notion should not to be confused with the other
Kleene algebra In mathematics, a Kleene algebra ( ; named after Stephen Cole Kleene) is an idempotent (and thus partially ordered) semiring endowed with a closure operator. It generalizes the operations known from regular expressions. Definition Various ineq ...
generalizing
regular expression A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
s.) This notion has also been called a normal ''i''-lattice by Kalman. Examples of Kleene algebras in the sense defined above include:
lattice-ordered group In abstract algebra, a partially ordered group is a group (''G'', +) equipped with a partial order "≤" that is ''translation-invariant''; in other words, "≤" has the property that, for all ''a'', ''b'', and ''g'' in ''G'', if ''a'' ≤ ''b'' ...
s, Post algebras and Łukasiewicz algebras.
Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
s also meet this definition of Kleene algebra. The simplest Kleene algebra that is not Boolean is Kleene's
three-valued logic In logic, a three-valued logic (also trinary logic, trivalent, ternary, or trilean, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating ''true'', ''false'' and some indeterminate ...
K3. K3 made its first appearance in
Kleene Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
's ''On notation for
ordinal numbers In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the least ...
'' (1938). The algebra was named after Kleene by Brignole and Monteiro. A (possibly abbreviated) version of this paper appeared later in ''Proceedings of the Japan Academy'':

# Related notions

De Morgan algebras are not the only plausible way to generalize Boolean algebras. Another way is to keep ¬''x'' ∧ ''x'' = 0 (i.e. the law of noncontradiction) but to drop the law of the excluded middle and the law of double negation. This approach (called ''semicomplementation'') is well-defined even for a (meet)
semilattice In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
; if the set of semicomplements has a
greatest element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an elem ...
it is usually called pseudocomplement. If the pseudocomplement 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. More generally, both De Morgan and Stone algebras are proper subclasses of Ockham algebras.