Boolean Algebra

Definition: Boolean Algebra

Boolean Algebra

Noun

1. A system of symbolic logic devised by George Boole; used in computers.

Specialty Definitions: Boolean Algebra

Domain	Definitions
Computing	Boolean algebra (After the logician George Boole) 1. Commonly, and especially in computer science and digital electronics, this term is used to mean two-valued logic. 2. This is in stark contrast with the definition used by pure mathematicians who in the 1960s introduced "Boolean-valued models" into logic precisely because a "Boolean-valued model" is an interpretation of a theory that allows more than two possible truth values! Strangely, a Boolean algebra (in the mathematical sense) is not strictly an algebra, but is in fact a lattice. A Boolean algebra is sometimes defined as a "complemented distributive lattice". Boole's work which inspired the mathematical definition concerned algebras of sets, involving the operations of intersection, union and complement on sets. Such algebras obey the following identities where the operators ^, V, - and constants 1 and 0 can be thought of either as set intersection, union, complement, universal, empty; or as two-valued logic AND, OR, NOT, TRUE, FALSE; or any other conforming system. a ^ b = b ^ a a V b = b V a (commutative laws) (a ^ b) ^ c = a ^ (b ^ c) (a V b) V c = a V (b V c) (associative laws) a ^ (b V c) = (a ^ b) V (a ^ c) a V (b ^ c) = (a V b) ^ (a V c) (distributive laws) a ^ a = a a V a = a (idempotence laws) --a = a -(a ^ b) = (-a) V (-b) -(a V b) = (-a) ^ (-b) (de Morgan's laws) a ^ -a = 0 a V -a = 1 a ^ 1 = a a V 0 = a a ^ 0 = 0 a V 1 = 1 -1 = 0 -0 = 1 There are several common alternative notations for the "-" or logical complement operator. If a and b are elements of a Boolean algebra, we define a <= b to mean that a ^ b = a, or equivalently a V b = b. Thus, for example, if ^, V and - denote set intersection, union and complement then <= is the inclusive subset relation. The relation <= is a partial ordering, though it is not necessarily a linear ordering since some Boolean algebras contain incomparable values. Note that these laws only refer explicitly to the two distinguished constants 1 and 0 (sometimes written as LaTeX \top and \bot), and in two-valued logic there are no others, but according to the more general mathematical definition, in some systems variables a, b and c may take on other values as well. (1997-02-27). Source: The Free On-line Dictionary of Computing.
Aerospace	The study of the manipulation of Symbols representing operations according to the rules of logic.Boolean algebra corresponds to an algebra using only the numbers 0 and 1, therefore can be used in programming digital computers which operate on the binary principle. (references)
Source: compiled by the editor from various references; see credits.

Top

Specialty Definition: Boolean algebra

(From Wikipedia, the free Encyclopedia)

In mathematics and computer science, Boolean algebras, or Boolean lattices, are algebraic structures which "capture the essence" of the logical operations AND, OR and NOT as well as the set theoretic operations union, intersection and complement.

They are named after George Boole, an Englishman, who invented them as part of a system of logic in the mid 19th century. Specifically, Boolean algebra was an attempt to use algebraic techniques to deal with expressions in the propositional calculus.

Today, Boolean algebras find many applications in electronic design. They were first defined by George Boole in the middle of the 19th century and first applied to switching by Claude Shannon in the 20th century.

The operators of Boolean algebra may be represented in various ways. Often they are simply written as AND, OR and NOT. In describing circuits, NAND (NOT AND), NOR (NOT OR) and XOR (exclusive OR) may also be used. Mathematicians often use + for OR and . for AND (since in some ways those operations are analogous to addition and multiplication in other algebraic structures) and represent NOT by a line drawn above the expression being negated.

Here we use another common notation with ∧ (or ^ for browsers that don't support the character) for AND, ∨ (or v) for OR, and ¬ (or ~) for NOT.

Definition and first consequences

A Boolean algebra is a lattice (A, ∧ , ∨) with the following four additional properties:

bounded below: There exists an element 0, such that a ∨ 0 = a for all a in A.
bounded above: There exists an element 1, such that a ∧ 1 = a for all a in A.
distributive law: For all a, b, c in A, (a ∨ b) ∧ c = (a ∧ c) ∨ (b ∧ c).
existence of complements: For every a in A there exists an element ¬a in A such that a ∨ ¬a = 1 and a ∧ ¬a = 0.

From these axioms, one can directly show that the smallest element 0 and the largest element 1 are unique, that every element has only one complement, that

a ∧ 0 = 0 and a ∨ 1 = 1,

¬1 = 0 and ¬0 = 1,

and that deMorgan's laws

¬(a ∨ b) = (¬a) ∧ (¬b) and ¬(a ∧ b) = (¬a) ∨ (¬b)

are valid. The dual version of the distributive law,

(a ∧ b) ∨ c = (a ∨ c) ∧ (b ∨ c)

also holds true. In general, any law valid about Boolean algebras can be transformed into another valid, "dual" law by replacing 0 by 1 and ∧ by ∨, and vice versa.

Like any lattice, a Boolean algebra can be seen as a partially ordered set by defining

a ≤ b iff a = a ∧ b

(which is also equivalent to b = a ∨ b).

Examples

The most important Boolean algebra has only two elements, 0 and 1, and is defined by the rules

  ∨  0  1     ∧   0  1
      ----         ----
  0 | 0  1     0 | 0  0
  1 | 1  1     1 | 0  1

It has applications in logic, where 0 is interpreted as "false", 1 is "true", ∧ is "and", ∨ is "or", and ¬ is "not". Expressions involving variables and the Boolean operations represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are logically equivalent.

The two-element Boolean algebra is also used for circuit design in electrical engineering; here 0 and 1 represent the two different states of digital circuits, typically high and low voltage. Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input-output behavior. Furthermore, every possible input-output behavior can be modeled by a suitable Boolean expression.

The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can always be checked by a trivial brute force algorithm). This can for example be used to show that the following laws (Consensus theorems) are generally valid in all Boolean algebras:

(a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) = (a ∨ b) ∧ (¬a ∨ c)

(a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) = (a ∧ b) ∨ (¬a ∧ c)

The power set of any given set S forms a Boolean algebra with the two operations ∨ = union and ∧ = intersection. The smallest element 0 is the empty set and the largest element 1 is the set S itself.

For any natural number n, the set of all positive divisors of n forms a lattice if we write a ← b for a divides b. This lattice is a Boolean algebra if and only if n is square-free. The smallest element 0 of this Boolean algebra is the natural number 1; the largest element 1 of this Boolean algebra is the natural number n.

Other examples of Boolean algebras arise from topological spaces: if X is a topological space, then the collection of all subsets of X which are both open and closed forms a Boolean algebra with the operations ∨ = union and ∧ = intersection.

If R is an arbitrary ring and we define the set of central idempotents by

A = { e in R : e² = e and ex = xe for all x in R }

then the set A becomes a Boolean algebra with the operations e ∨ f = e + f + ef and e ∧ f = ef.

Homomorphisms and isomorphisms

A homomorphism between the Boolean algebras A and B is a function f : A → B such that for all a, b in A:

f(a ∨ b) = f(a) ∨ f(b)

f(a ∧ b) = f(a) ∧ f(b)

f(0) = 0

f(1) = 1

It then follows that f(¬a) = ¬f(a) for all a in A as well. The class of all Boolean algebras, together with this notion of morphism, forms a category. An isomorphism from A to B is a homomorphism from A to B which is bijective. The inverse of an isomorphism is also an isomorphism, and we call the two Boolean algebras A and B isomorphic. From the standpoint of Boolean algebra theory, they cannot be distinguished; they only differ in the notation of their elements.

Boolean rings, ideals and filters

Every Boolean algebra (A, ∧, ∨) gives rise to a ring (A, +, *) by defining a + b = (a ∧ ¬b) ∨ (b ∧ ¬a) (this operation is called "symmetric difference" in the case of sets and XOR in the case of logic) and a * b = a ∧ b. The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the 1 of the Boolean algebra. This ring has the property that a * a = a for all a in A; rings with this property are called Boolean rings.

Conversely, if a Boolean ring A is given, we can turn it into a Boolean algebra by defining x ∨ y = x + y + xy and x ∧ y = xy. Since these two operations are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map f : A → B is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The categories of Boolean rings and Boolean algebras are equivalent.

An ideal of the Boolean algebra A is a subset I such that for all x, y in I we have x ∨ y in I and for all a in A we have a ∧ x in I. This notion of ideal coincides with the notion of ring ideal in the Boolean ring A. An ideal I of A is called prime if I ≠ A and if a ∧ b in I always implies a in I or b in I. An ideal I of A is called maximal if I ≠ A and if the only ideal properly containing I is A itself. These notions coincide with ring theoretic ones of prime ideal and maximal ideal in the Boolean ring A.

The dual of an ideal is a filter. A filter of the Boolean algebra A is a subset p such that for all x, y in p we have x ∧ y in p and for all a in A if a ∨ x = a then a in p.

Representing Boolean algebras

It can be shown that every finite Boolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set; in particular, the number of elements of every finite Boolean algebra is a power of two.

The celebrated Stone representation theorem states that every Boolean algebra A is isomorphic to the Boolean algebra of all closed-open sets in some (compact totally disconnected T1) topological space. This space can be defined as the space of all maximal ideals in A, with the sets {M : M is a maximal ideal that doesn't contain a} for a in A as base of the topology.

The Stone representation theorem cannot be proven within the Zermelo-Fraenkel axioms. It is equivalent to the Boolean Prime Ideal Theorem which states every Boolean algebra has a prime ideal. Both can be proven using the Axiom of Choice. But the Stone representation theorem is strictly weaker than the axiom of choice.

Source: adapted by the editor from Wikipedia, the free encyclopedia under a copyleft GNU Free Documentation License (GFDL) from the article "Boolean algebra."

Top

Synonym: Boolean Algebra

Synonym: Boolean logic (n). (additional references)

Top

Crosswords: Boolean Algebra

English words defined with "Boolean algebra": binary arithmetic operation, binary operation, Boole, boolean operation ♦ George Boole. (references)

Specialty definitions using "Boolean algebra": algebraic structure ♦ Finite State Machine ♦ logical complement ♦ OR-gate ♦ two-valued logic. (references)

Top

Commercial Usage: Boolean Algebra

Domain	Title
Books	Boolean Algebra and Its Applications (Dover Books on Mathematics) (reference) The Essentials of Boolean Algebra (Essentials) (reference) Ones and Zeros: Understanding Boolean Algebra, Digital Circuits, and the Logic of Sets (IEEE Press Understanding Science & Technology Series) (reference) (more book examples)
Source: compiled by the editor from various references; see credits.

Top

Frequency of Internet Keywords: Boolean Algebra

The following statistics estimate the number of searches per day across the major English-language search engines as identified by various trade publications. Hyperlinks lead to commercial use of the expression at Amazon.com.

Expression	Frequency per Day
boolean algebra	115
Source: compiled by the editor from various references; see credits.

Top

Modern Translations: Boolean Algebra

Language		Translations for "Boolean algebra"; alternative meanings/domain in parentheses.
Russian		алгебра логики, булева алгебра. (various references)
Source: compiled by the editor from various translation references.

Top

Misspellings: Boolean Algebra

Misspellings
	"Boolean Algebra" is suggested in spellcheckers for the following: boolean algerbra. (additional references)
Source: compiled by the editor, based on several corpora (additional references).

Top

Anagrams: Boolean Algebra

Scrabble® Enable2K-Verified Anagrams
	Words within the letters "a-a-a-b-b-e-e-g-l-l-n-o-o-r"
	-5 letters: gleanable, learnable, organelle.
Source: compiled by the editor from various references; see credits. SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the U.S.A and Canada by Hasbro Inc., and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc. Mattel and Spear are not affiliated with Hasbro.

Top

Alternative Orthography: Boolean Algebra

Hexadecimal (or equivalents, 770AD-1900s) (references)

42 6F 6F 6C 65 61 6E 41 6C 67 65 62 72 61

Leonardo da Vinci (1452-1519; backwards) (references)

Binary Code (1918-1938, probably earlier) (references)

01000010 01101111 01101111 01101100 01100101 01100001 01101110 00100000 01000001 01101100 01100111 01100101 01100010 01110010 01100001

HTML Code (1990) (references)

&#66 &#111 &#111 &#108 &#101 &#97 &#110 &#32 &#65 &#108 &#103 &#101 &#98 &#114 &#97

ISO 10646 (1991-1993) (references)

0042 006F 006F 006C 0065 0061 006E 0041 006C 0067 0065 0062 0072 0061

Encryption (beginner's substitution cypher): (references)

36818178716780235787371688467

Top

INDEX

1. Definition
2. Synonyms
3. Crosswords
4. Usage: Commercial

5. Expressions: Internet
6. Translations: Modern
7. Derivations
8. Anagrams

9. Orthography
10. Bibliography

Note to the press & webmasters - this dictionary can be linked, indexed, or referred to using the following non-English expressions:
woordeboek, fjalor, ‏معجم, ‏قاموس, diccionariu, речник, diccionari, diksyonario, diksinario, 字典, gérlyver, slovník, ordbog, woordenboek, shimiyuc p'anca, orðabók, orðbók, dictionnaire, wurdboek, wörterbuch, λεξικό, אוצר מילים, szótár, uqausiit tukingit, dizionario, 字引 , じい, じびき, じて�", ディクショナリー , じり�", じしょ, �'�"かい, ディクショナリ , 사� �, dizionari, recnik, fockleyr, dikshonario, słownik, dicionário, dicţionar, dicziunari, словарь, lolomi fefiloi, foclair, abardair, faclair, briathrachan, pukuntau, leksikon, rečnik, vocabbulariu, diccionario, sí-chazamagâma, ordbok, lexikon, พจนานุกรม, sözlük, ansiklopedik sözlük, словник, довідник, có tính chất sách vở, geirlyfr, geiriadur, for dictionary;
definisie, qartësi, përcaktim, saktësi, ‏الوضوحية في الشيء, ‏حد, ‏تحديد, ‏تعريف, ‏التحديد, ‏الإيضاحية, яснота, сила, очертания, дефиниция, 定義 , 定义, definice, deskriptordefinition, definitie, määritelmä, définition, ορισμός, �"�'�"ר�", �"�'בל�", meghatározás, definíció, definizione, 確定 , ディーゼル電気車 , デ�'ドロ酢酸 , デフィニション , ディフィニション , ていぎ, かくてい, � �의, geyrid, meenaghey, keeayllaght, baght, definishon, definição, definiţie, determinare, definire, определение, definicija, definición, definition, açıklama, belirleme, belirtme, kesinleştirme, tanım, tarif, seçiklik, tanımlama, чіткість, тлумачення, виразність, визначення, дефініція, ясність, чітка чутність, sự định rõ, sự định nghĩa, lời định nghĩa sự định, diffiniad, darnodiad, for definition;
vertaling, transferim, transmetim, ‏ترجمة من لغة أجنبية للغة الأم, ‏ترجمة, ‏إفتتان, транслация, огъване, превод, предаване, поддаване, тълкуване, превеждане, 翻译, překlad, oversættelse, translatie, taajuusmuutos, translaatio, traduction, oersetting, Übersetzung, μετάφραση, תור�'מ� ות, תר�'ום, �"עתק�", �"עתק, fordítás, traduzione, 翻訳 , へい�"ういどう, やくしょ, やくしゅつ, �"うどく, ほ�"やく, トランスレーション , やくじゅつ, ほ�"やくしょ, 번역, tradukshon, tradução, translaţie, tãlmãcire, traducere, сдвиг, трансляция, перемещение, перевод, tumačenje, traducción, översättning, tercüme, процес перекладу, переклад, пояснення, переміщення, sự dịch, sự biến th� nh sự giải thích, trosiad, for translation;
Russies, Rus, ‏الروسية, ‏روسي, ‏اللغة الروسية, Rusu, руски, руски език, руснак, Rusyan, 俄語 , 俄语, 俄文 , ruština, ruský, russer, russur, russiskt, venäläinen, Russysk, Russe, russisch, Ρώσος, רוסי, orosz, rússneskur, Rússi, Rúisis, russo, ロシア語 , ロシア�", 러시아, Rooshish, Rooshagh, russisk, Rosjanin, русский, Lusia, ruski jezik, ruski, ruso, sí-Rashîya, ryss, ชาวรัสเซีย, rusça, росіянка, росіянин, російська мова, російський, người Nga tiếng Nga, for Russian;

Boolean Algebra

Definition: Boolean Algebra

Boolean Algebra

Noun

Specialty Definitions: Boolean Algebra

Specialty Definition: Boolean algebra

Synonym: Boolean Algebra

Crosswords: Boolean Algebra

Commercial Usage: Boolean Algebra

Books

Frequency of Internet Keywords: Boolean Algebra

Modern Translations: Boolean Algebra

Russian

Misspellings: Boolean Algebra

Misspellings

Anagrams: Boolean Algebra

Scrabble® Enable2K-Verified Anagrams

Alternative Orthography: Boolean Algebra

42 6F 6F 6C 65 61 6E 41 6C 67 65 62 72 61

01000010 01101111 01101111 01101100 01100101 01100001 01101110 00100000 01000001 01101100 01100111 01100101 01100010 01110010 01100001

&#66 &#111 &#111 &#108 &#101 &#97 &#110 &#32 &#65 &#108 &#103 &#101 &#98 &#114 &#97

0042 006F 006F 006C 0065 0061 006E 0041 006C 0067 0065 0062 0072 0061

36818178716780235787371688467

INDEX