FACTOID # 17: Though Rhode Island is the smallest state in total area, it has the longest official name: The State of Rhode Island and Providence Plantations.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Boolean algebra

In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. Specifically, it deals with the set operations of intersection, union, complement; and the logic operations of AND, OR, NOT. Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ... This article does not cite its references or sources. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is the study of criteria for the evaluation of arguments, although the exact definition of logic is a matter of controversy among philosophers. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ... In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ... Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is the study of criteria for the evaluation of arguments, although the exact definition of logic is a matter of controversy among philosophers. ... AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ... OR logic gate. ... Negation, in its most basic sense, changes the truth value of a statement to its opposite. ...


For example, the logical assertion that a statement a and its negation ¬a cannot both be true, Proposition is a term used in logic to describe the content of assertions. ...

Boolean lattice of subsets
Boolean lattice of subsets
aland(lnot a) = mbox{FALSE},

parallels the set-theory assertion that a subset A and its complement AC have empty intersection, Image File history File links Download high resolution version (1050x799, 67 KB) Summary PNG file created as SVG, rendered by Batik, and uploaded by author. ... Image File history File links Download high resolution version (1050x799, 67 KB) Summary PNG file created as SVG, rendered by Batik, and uploaded by author. ...

Acap(A^C) = varnothing.

Because truth values can be represented as binary numbers or as voltage levels in logic circuits, the parallel extends to these as well. Thus the theory of Boolean algebras has many practical applications in electrical engineering and computer science, as well as in mathematical logic. The binary numeral system (base 2 numerals) represents numeric values using two symbols, typically 0 and 1. ... A logic gate is an arrangement of electronically-controlled switches used to calculate operations in Boolean algebra. ... Electrical Engineers design power systems… … and complex electronic circuits. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ...


A Boolean algebra is also called a Boolean lattice. The connection to lattices (special partially ordered sets) is suggested by the parallel between set inclusion, A ⊆ B, and ordering, a ≤ b. Consider the lattice of all subsets of {x,y,z}, ordered by set inclusion. This Boolean lattice is a partially ordered set in which, say, {x}  ≤ {x,y}. Any two lattice elements, say p = {x,y} and q = {y,z}, have a least upper bound, here {x,y,z}, and a greatest lower bound, here {y}. Suggestively, the least upper bound (or join or supremum) is denoted by the same symbol as logical OR, pq; and the greatest lower bound (or meet or infimum) is denoted by same symbol as logical AND, pq. The name lattice is suggested by the form of the Hasse diagram depicting it. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ...


The lattice interpretation helps in generalizing to Heyting algebras, which are Boolean algebras freed from the restriction that either a statement or its negation must be true. Heyting algebras correspond to intuitionist (constructivist) logic just as Boolean algebras correspond to classical logic. In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. ... Intuitionistic logic, or constructivist logic, is the logic used in mathematical intuitionism and other forms of mathematical constructivism. ... Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. ...

Contents

Formal definition

A Boolean algebra is a set A, supplied with two binary operations land (called AND), lor (called OR), a unary operation lnot (called NOT) and two distinct elements 0 (called zero) and 1 (called one), such that, for all elements a, b and c of set A, the following axioms hold: In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ... In mathematics, a unary operation is an operation with only one operand. ... For the algebra software named Axiom, see Axiom computer algebra system. ...

a lor (b lor c) = (a lor b) lor c a land (b land c) = (a land b) land c associativity
a lor b = b lor a a land b = b land a commutativity
a lor (a land b) = a a land (a lor b) = a absorption
a lor (b land c) = (a lor b) land (a lor c) a land (b lor c) = (a land b) lor (a land c) distributivity
a lor lnot a = 1 a land lnot a = 0 complements

The first three pairs of axioms above: associativity, commutativity and absorption, mean that (A, land, lor) is a lattice. If A is a lattice and one of the above distributivity laws holds, then the second distributivity law can be proven. Thus, a Boolean algebra can also be equivalently defined as a distributive complemented lattice. In mathematics, associativity is a property that a binary operation can have. ... In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ... In algebra, the absorption law is an identity linking a pair of binary operations. ... In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalises the distributive law from elementary algebra. ... In the mathematical discipline of order theory, and in particular, in lattice theory, a complemented lattice is a bounded lattice in which each element x has a complement, defined as a unique element ~ x such that and A Boolean algebra may be defined as a complemented distributive lattice. ... The name lattice is suggested by the form of the Hasse diagram depicting it. ... In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. ... In the mathematical discipline of order theory, and in particular, in lattice theory, a complemented lattice is a bounded lattice in which each element x has a complement, defined as a unique element ~ x such that and A Boolean algebra may be defined as a complemented distributive lattice. ...


From these axioms, one can show that the smallest element 0, the largest element 1, and the complement ¬a of any element a are uniquely determined. For all a and b in A, the following identities also follow: For the algebra software named Axiom, see Axiom computer algebra system. ... In mathematics, an identity is an equality that remains true regardless of the values of any variables that appear within it. ...

a lor a = a a land a = a idempotency
a lor 0 = a a land 1 = a boundedness
a lor 1 = 1 a land 0 = 0
lnot 0 = 1 lnot 1 = 0 0 and 1 are complements
lnot (a lor b) = lnot a land lnot b lnot (a land b) = lnot a lor lnot b De Morgan's laws
lnot lnot a = a involution

In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ... In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S which is greater than or equal to any other element of S. The term least element is defined dually. ... note that demorgans laws are also a big part in circut design. ... In mathematics, an involution is a function that is its own inverse, so that f(f(x)) = x for all x in the domain of f. ...

Examples

  • The simplest Boolean algebra has only two elements, 0 and 1, and is defined by the rules:
0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
a 0 1
¬a 1 0
  • It has applications in logic, interpreting 0 as false, 1 as true, ∧ as and, ∨ as or, and ¬ as 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 one bit in a digital circuit, 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:
    • (ab) ∧ (¬ac) ∧ (bc) ≡ (ab) ∧ (¬ac)
    • (ab) ∨ (¬ac) ∨ (bc) ≡ (ab) ∨ (¬ac)
  • Starting with the propositional calculus with κ sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo tautology). This construction yields a Boolean algebra. It is in fact the free Boolean algebra on κ generators. A truth assignment in propositional calculus is then a Boolean algebra homomorphism from this algebra to {0,1}.
  • The power set (set of all subsets) of any given nonempty 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.
  • The set of all subsets of S that are either finite or cofinite is a Boolean algebra.
  • For any natural number n, the set of all positive divisors of n forms a distributive lattice if we write ab for a | 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 = { eR : e2 = e, ex = xe, ∀xR }
    then the set A becomes a Boolean algebra with the operations ef := e + fef and ef := ef.
  • Certain Lindenbaum–Tarski algebras.

Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason) is the study of criteria for the evaluation of arguments, although the exact definition of logic is a matter of controversy among philosophers. ... In logic, statements p and q are logically equivalent if they have the same logical content. ... Electrical Engineers design power systems… … and complex electronic circuits. ... A bit (binary digit) refers to a digit in the binary numeral system, which consists of base 2 digits (ie. ... Digital circuits are electric circuits based on a number of discrete voltage levels. ... now. ... -1... In computer science, a brute-force search consists of systematically enumerating every possible solution of a problem until a solution is found, or all possible solutions have been exhausted. ... In mathematical logic the propositional calculus or sentential calculus is a formal deduction system whose atomic formulas are propositional variables. ... In mathematical logic, the Lindenbaum-Tarski algebra A of a logical theory T consists of the equivalence classes of sentences p of the theory, under the equivalence relation ~ defined by p ~ q when p and q are logically equivalent in T. That is, in T q can be deduced from... In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called generators, such that: Each element of the Boolean algebra can be expressed as a finite combination of generators, using the Boolean operations, and The generators are as independent as possible, in the sense... In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... In mathematics and more specifically set theory, the empty set is the unique set which contains no elements. ... In mathematics, a cofinite subset of a set X is a subset Y whose complement in X is a finite set. ... In mathematics, a natural number is either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). The former definition is generally used in number theory, while the latter is preferred in set theory and computer science. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. ... In mathematics, a square-free, or quadratfrei, integer is one divisible by no perfect square, except 1. ... A Möbius strip, a surface with only one side and one edge; such shapes are an object of study in topology. ... In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... In mathematical logic, the Lindenbaum-Tarski algebra A of a logical theory T consists of the equivalence classes of sentences p of the theory, under the equivalence relation ~ defined by p ~ q when p and q are logically equivalent in T. That is, in T the sentence q can be...

Order theoretic properties

Boolean lattice of subsets
Boolean lattice of subsets

Like any lattice, a Boolean algebra (A, land, lor) gives rise to a partially ordered set (A, ≤) by defining Image File history File links Download high resolution version (1050x799, 67 KB) Summary PNG file created as SVG, rendered by Batik, and uploaded by author. ... Image File history File links Download high resolution version (1050x799, 67 KB) Summary PNG file created as SVG, rendered by Batik, and uploaded by author. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ...

ab precisely when a = a land b

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


In fact one can also define a Boolean algebra to be a distributive lattice (A, ≤) (considered as a partially ordered set) with least element 0 and greatest element 1, within which every element x has a complement ¬x such that

x land ¬x = 0 and x lor ¬x = 1

Here land and lor are used to denote the infimum (meet) and supremum (join) of two elements. Again, if complements in the above sense exist, then they are uniquely determined. In mathematics the infimum of a subset of some set is the greatest element, not necessarily in the subset, that is smaller than all other elements of the subset. ... In mathematics, the supremum of an ordered set S is the least element that is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound (also lub and LUB). ...


The algebraic and the order theoretic perspective can usually be used interchangeably and both are of great use to import results and concepts from both universal algebra and order theory. In many practical examples an ordering relation, conjunction, disjunction, and negation are all naturally available, so that it is straightforward to exploit this relationship. Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ...


Principle of duality

One can also apply general insights from duality in order theory to Boolean algebras. Especially, the order dual of every Boolean algebra, or, equivalently, the algebra obtained by exchanging land and lor, is also a Boolean algebra. In general, any law valid for Boolean algebras can be transformed into another valid, dual law by exchanging 0 with 1, land with lor, and ≤ with ≥. In the mathematical area of order theory, every partially ordered set P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop. ...


Other notation

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, engineers, and programmers often use + for OR and · for AND (since in some ways those operations are analogous to addition and multiplication in other algebraic structures and this notation makes it very easy to get sum of products form for people who are familiar with normal algebra) and represent NOT by a line drawn above the expression being negated. Sometimes, the symbol ~ or ! is used for NOT. To meet Wikipedias quality standards, this article or section may require cleanup. ... Look up engineer in Wiktionary, the free dictionary. ... A programmer or software developer is someone who programs computers, that is, one who writes computer software. ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ... In a Boolean algebra, a Boolean function that is composed of standard logical operators can be expressed in a canonical form using the dual concepts of a minterms and maxterms. ...


Here we use another common notation with "meet" land for AND, "join" lor for OR, and ¬ for NOT.


Homomorphisms and isomorphisms

A homomorphism between the Boolean algebras A and B is a function f : AB such that for all a, b in A: In abstract algebra, a homomorphism is a structure-preserving map. ... Partial plot of a function f. ...

f(a lor b) = f(a) lor f(b)
f(a land b) = f(a) land f(b)
f(0) = 0
f(1) = 1

It then follows that fa) = ¬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 differ only in the notation of their elements. In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share. ... In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ...


Boolean rings, ideals and filters

Every Boolean algebra (A, land, lor) gives rise to a ring (A, +, *) by defining a + b = (a land ¬b) lor (b land ¬a) (this operation is called "symmetric difference" in the case of sets and XOR in the case of logic) and a * b = a land 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. In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ... In mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists of idempotent elements. ...


Conversely, if a Boolean ring A is given, we can turn it into a Boolean algebra by defining x lor y = x + y + xy and x land 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 : AB 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. In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ...


An ideal of the Boolean algebra A is a subset I such that for all x, y in I we have x lor y in I and for all a in A we have a land 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 IA and if a land b in I always implies a in I or b in I. An ideal I of A is called maximal if IA 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. In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ... In mathematics, a prime ideal is a subset of a ring which shares many important properties of a prime number in the ring of integers. ... In mathematics, more specifically in ring theory a maximal ideal is a special kind of ideal which is in some sense maximal, that is not contained in any other non-trivial ideal of the ring. ...


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 land y in p and for all a in A if a lor 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. Therefore, the number of elements of every finite Boolean algebra is a power of two. In mathematics, a power of two is any of the nonnegative integer powers of the number two; in other words, two times itself a certain number of times. ...


Stone's celebrated representation theorem for Boolean algebras states that every Boolean algebra A is isomorphic to the Boolean algebra of all closed-open sets in some (compact totally disconnected Hausdorff) topological space. Marshall Harvey Stone (April 8, 1903–January 9, 1989) was a American mathematician who made several important contributions in various areas of mathematical analysis, including in particular functional analysis. ... In mathematics, Stones representation theorem for Boolean algebras, named in honor of Marshall H. Stone, is the duality between the category of Boolean algebras and the category of Stone spaces, i. ... In topology, a clopen set (or closed-open set) in a topological space is a set which is both open and closed. ... In mathematics, a subset of Euclidean space Rn is called compact if it is closed and bounded. ... In topology and related branches of mathematics, a topological space X is said to be disconnected if it is the union of two disjoint nonempty open sets. ... In topology and related branches of mathematics, a Hausdorff space is a topological space in which points can be separated by neighbourhoods. ...


Axiomatics for Boolean algebras

Let the unary functional symbol n be read as 'complement'. In 1933, the American mathematician Edward Vermilye Huntington (1874–1952) set out the following elegant axiomatization for Boolean algebra: In mathematics, a unary operation is an operation with only one operand. ... Edward Vermilye Huntington (born 1874 April 26 in Clinton, New York, USA, died 1952 November 25 in Cambridge, Massachusetts, USA), was a Harvard professor interested in the foundations of mathematics. ...

  1. Commutativity: x + y = y + x.
  2. Associativity: (x + y) + z = x + (y + z).
  3. Huntington equation: n(n(x) + y) + n(n(x) + n(y)) = x.

Herbert Robbins immediately asked: If the Huntington equation is replaced with its dual, to wit: Herbert Ellis Robbins (1922 - 2001) was a mathematician and statistician who did research in topology, measure theory, statistics, and a variety of other fields. ...

4. Robbins Equation: n(n(x + y) + n(x + n(y))) = x,

do (1), (2), and (4) form a basis for Boolean algebra? Calling (1), (2), and (4) a Robbins algebra, the question then becomes: Is every Robbins algebra a Boolean algebra? This question remained open for decades, and became a favorite question of Alfred Tarski and his students. Alfred Tarski (January 14, 1901, Warsaw Poland – October 26, 1983, Berkeley California) was a logician and mathematician of considerable philosophical importance. ...


In 1996, William McCune at Argonne National Laboratory, building on earlier work by Larry Wos, Steve Winker, and Bob Veroff, answered Robbins's question in the affirmative: Every Robbins algebra is a Boolean algebra. Crucial to McCune's proof was the automated reasoning program EQP he designed. For a simplification of McCune's proof, see Dahn (1998). Argonne National Laboratory is one of the United States governments oldest and largest science and engineering research national laboratories and is the largest in the Midwest. ... Automated reasoning is an area of computer science dedicated to creating software which allows to perform reasoning on computers completely or nearly completely automatically. ... EQP, an abbreviation for Equational Prover is an automated theorem-proving program for first-order equational logic, developed by the Mathematics and Computer Science Division of the Argonne National Laboratory and among other used for solving the problem proposed by Herbert Robbins whether all Robbins algebras are Boolean, the problem...


History

The term "Boolean algebra" honors George Boole (1815–1864), a self-educated English mathematician. The algebraic system of logic he formulated in his 1854 monograph The Laws of Thought differs from that described above in some important respects. For example, conjunction and disjunction in Boole were not a dual pair of operations. Boolean algebra emerged in the 1860s, in papers written by William Jevons and Charles Peirce. To the 1890 Vorlesungen of Ernst Schröder we owe the first systematic presentation of Boolean algebra and distributive lattices. The first extensive treatment of Boolean algebra in English is A. N. Whitehead's 1898 Universal Algebra. Boolean algebra as an axiomatic algebraic structure in the modern axiomatic sense begins with a 1904 paper by Edward Vermilye Huntington. Boolean algebra came of age as serious mathematics with the work of Marshall Stone in the 1930s, and with Garrett Birkhoff's 1940 Lattice Theory. In the 1960s, Paul Cohen, Dana Scott, and others found deep new results in mathematical logic and axiomatic set theory using offshoots of Boolean algebra, namely forcing and Boolean-valued models. George Boole [], (November 2, 1815 – December 8, 1864) was a British mathematician and philosopher. ... William Stanley Jevons (September 1, 1835 - August 13, 1882), English economist and logician, was born in Liverpool. ... Charles Sanders Peirce (pronounced purse), (September 10, 1839 – April 19, 1914) was an American polymath, physicist, and philosopher, born in Cambridge, Massachusetts. ... Ernst Schröder Ernst Schröder (25 November 1841 Mannheim, Germany - 16 June 1902 Karlsruhe Germany) was a German mathematician mainly known for his work on algebraic logic. ... In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. ... Alfred North Whitehead Alfred North Whitehead (February 15, 1861 _ December 30, 1947) was a British philosopher and mathematician who worked in logic, mathematics, philosophy of science and metaphysics. ... Edward Vermilye Huntington (born 1874 April 26 in Clinton, New York, USA, died 1952 November 25 in Cambridge, Massachusetts, USA), was a Harvard professor interested in the foundations of mathematics. ... Marshall Harvey Stone (April 8, 1903–January 9, 1989) was a American mathematician who made several important contributions in various areas of mathematical analysis, including in particular functional analysis. ... Garrett Birkhoff (January 19, 1911, Princeton, New Jersey, USA - November 22, 1996, Water Mill, New York, USA) was an American mathematician. ... Paul Joseph Cohen (born April 2, 1934) is an American mathematician. ... Dana Stewart Scott (born 1932) is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California. ... Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... This article or section is in need of attention from an expert on the subject. ... In axiomatic set theory, forcing is a technique, invented by Paul Cohen, for proving consistency and independence results with respect to the Zermelo-Fraenkel axioms. ...


See also

Algebra of sets George Boole Boolean algebra Boolean function Boolean logic Boolean homomorphism Boolean Implicant Boolean prime ideal theorem Boolean-valued model Boolean satisfiability problem Booles syllogistic canonical form (Boolean algebra) compactness theorem Complete Boolean algebra connective -- see logical operator de Morgans laws Augustus De Morgan duality (order... A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true. ... In mathematics, a boolean function is usually a function F(b1, b2, ..., bn) of a number n of boolean variables bi from the two-element boolean algebra B = {0, 1}, such that F also takes values in B. A function on an arbitrary set X taking values in B is... Boolean logic is a complete system for logical operations. ... In mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists of idempotent elements. ... A boolean-valued function is a function of the type , where is an arbitrary set, where is a generic 2-element set, typically , and where the latter is frequently interpreted for logical applications as . ... In a Boolean algebra, a Boolean function that is composed of standard logical operators can be expressed in a canonical form using the dual concepts of a minterms and maxterms. ... In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum. ... A finitary boolean function is a function of the type , where is a generic 2-element set, typically , frequently interpreted for logical applications as , and where k is a positive integer. ... In axiomatic set theory, forcing is a technique, invented by Paul Cohen, for proving consistency and independence results with respect to the Zermelo-Fraenkel axioms. ... In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called generators, such that: Each element of the Boolean algebra can be expressed as a finite combination of generators, using the Boolean operations, and The generators are as independent as possible, in the sense... In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. ... The Karnaugh map, also known as a Veitch diagram (K-map or KV-map for short), is a tool to facilitate management of Boolean algebraic expressions. ... The book Laws of Form (hereinafter abbreviated LoF), by G. Spencer-Brown, describes three distinct logical systems: The primary arithmetic (described in Chapter 4), which can be interpreted as Boolean arithmetic; The primary algebra (chapter 6), an algebraic structure that is a provocative and economical notation for the two-element... A logic gate performs a logical operation on one or more logic inputs and produces a single logic output. ... A logical graph is a special type of graph-theoretic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. ... A logical matrix, in the finite dimensional case, is a k-dimensional array with entries from the boolean domain B = {0, 1}. Such a matrix affords a matrix representation of a k-adic relation. ... -1... Venn diagrams are illustrations used in the branch of mathematics known as set theory. ... Zeroth-order logic is a term in popular use among practitioners for the subject matter otherwise known as boolean functions, monadic predicate logic, propositional calculus, or sentential calculus. ...

References

  • Cori, Rene, and Lascar, Daniel, 2000. Mathematical Logic: A Course with Exercises. Oxford Univ. Press. See Chapter 2.
  • Dahn, B.I. (1998), "Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem," Journal of Algebra 208: 526–532.
  • Halmos, Paul, 1963. Lectures on Boolean Algebras, Van Nostrand.
  • Halmos, Paul and Steven Givant, 1998. Logic as Algebra, Dolciani Mathematical Expositions No. 21, Mathematical Association of America.
  • Mendelson, Elliott, 1970. Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics. McGraw–Hill.
  • Monk, J. Donald, and R. Bonnet, eds., 1989. Handbook of Boolean Algebras, 3 vols. North-Holland.
  • Stoll, R.R., 1979 (1963). Set Theory and Logic. Dover Publications.
  • Huntington, E. V., 1933, "New sets of independent postulates for the algebra of logic," Trans. AMS 35: 274--304.
  • Huntington, E. V., 1933, "Boolean algebra: A correction," Trans. AMS 35: 557--558.

Paul Halmos Paul Richard Halmos (born March 3, 1916) is a Hungarian-born American mathematician who has written on probability theory, statistics, operator theory, ergodic theory, functional analysis (in particular, Hilbert spaces), and mathematical logic. ... Paul Halmos Paul Richard Halmos (born March 3, 1916) is a Hungarian-born American mathematician who has written on probability theory, statistics, operator theory, ergodic theory, functional analysis (in particular, Hilbert spaces), and mathematical logic. ... The Mathematical Association of America (MAA) is a professional society that focuses on undergraduate mathematics education. ... Edward Vermilye Huntington (born 1874 April 26 in Clinton, New York, USA, died 1952 November 25 in Cambridge, Massachusetts, USA), was a Harvard professor interested in the foundations of mathematics. ... Edward Vermilye Huntington (born 1874 April 26 in Clinton, New York, USA, died 1952 November 25 in Cambridge, Massachusetts, USA), was a Harvard professor interested in the foundations of mathematics. ...

External links

A monograph available free online: The Stanford Encyclopedia of Philosophy (hereafter SEP) is a free online encyclopedia of philosophy run and maintained by Stanford University. ...


  Results from FactBites:
 
The Mathematics of Boolean Algebra (Stanford Encyclopedia of Philosophy) (2063 words)
Boolean algebra is the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.
Another general algebraic notion which applies to Boolean algebras is the notion of a free algebra.
Much of the deeper theory of Boolean algebras, telling about their structure and classification, can be formulated in terms of certain functions defined for all Boolean algebras, with infinite cardinals as values.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m