Residuated Boolean algebra

Residuated Boolean algebra

In mathematics, a residuated Boolean algebra is a residuated lattice whose lattice structure is that of a Boolean algebra. Examples include Boolean algebras with the monoid taken to be conjunction, the set of all formal languages over a given alphabet Σ under concatenation, the set of all binary relations on a given set "X" under relational composition, and more generally the power set of any equivalence relation, again under relational composition. The original application was to relation algebras as a finitely axiomatized generalization of the binary relation example, but there exist interesting examples of residuated Boolean algebras that are not relation algebras, such as the language example.

Definition

A residuated Boolean algebra is an algebraic structure ("L", ∧, ∨, ¬, 0, 1, •, I, , /) such that: (i) ("L", ∧, ∨, •, I, , /) is a residuated lattice, and:(ii) ("L", ∧, ∨, ¬, 0, 1) is a Boolean algebra.

An equivalent signature better suited to the relation algebra application is ("L", ∧, ∨, ¬, 0, 1, •, I, , ) where the unary operations "x" and "x" are intertranslatable in the manner of De Morgan's laws via:"x""y" = ¬("x"¬"y"), "x""y" = ¬("x"¬"y"), and dually /"y" and "y" as: "x"/"y" = ¬(¬"x""y"), "x""y" = ¬(¬"x"/"y"),

with the residuation axioms in the residuated lattice article reorganized accordingly (replacing "z" by ¬"z") to read:("x""z")∧"y" = 0 ⇔ ("x"•"y")∧"z" = 0 ⇔ ("z""y")∧"x" = 0

This De Morgan dual reformulation is motivated and discussed in more detail in the section below on conjugacy.

Since residuated lattices and Boolean algebras are each definable with finitely many equations, so are residuated Boolean algebras, whence they form a finitely axiomatizable variety.

Examples

1. Any Boolean algebra, with the monoid multiplication • taken to be conjunction and both residuals taken to be material implication "x"→"y". Of the remaining 15 binary Boolean operations that might be considered in place of conjunction for the monoid multiplication, only five meet the monotonicity requirement, namely 0, 1, "x", "y", and "x"∨"y". Setting "y" = "z" = 0 in the residuation axiom "y" ≤ "x""z" ⇔ "x"•"y" ≤ "z", we have 0 ≤ "x"


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Residuated lattice — In abstract algebra, a residuated lattice is an algebraic structure that is simultaneously a lattice x le; y and a monoid x • y which admits operations x z and z / y loosely analogous to division or implication when x • y is viewed as… …   Wikipedia

  • Relation algebra — is different from relational algebra, a framework developed by Edgar Codd in 1970 for relational databases. In mathematics, a relation algebra is a residuated Boolean algebra supporting an involutary unary operation called converse. The… …   Wikipedia

  • Action algebra — In algebraic logic, an action algebra is an algebraic structure which is both a residuated semilattice and a Kleene algebra. It adds the star or reflexive transitive closure operation of the latter to the former, while adding the left and right… …   Wikipedia

  • Heyting algebra — In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras, named after Arend Heyting. Heyting algebras arise as models of intuitionistic logic, a logic in which the law of excluded… …   Wikipedia

  • MV-algebra — In abstract algebra, a branch of pure mathematics, an MV algebra is an algebraic structure with a binary operation oplus, a unary operation eg, and the constant 0, satisfying certain axioms. MV algebras are models of Łukasiewicz logic; the… …   Wikipedia

  • Outline of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • List of algebraic structures — In universal algebra, a branch of pure mathematics, an algebraic structure is a variety or quasivariety. Abstract algebra is primarily the study of algebraic structures and their properties. Some axiomatic formal systems that are neither… …   Wikipedia

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Glossary of order theory — This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”