Boolean algebra: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>John R. Brews
(→‎Axioms: Correct De Morgan's laws)
imported>John R. Brews
(→‎Venn diagrams: correction)
Line 52: Line 52:
[[Venn diagram]]s provide a graphical visualization of the Boolean operations.<ref name=Whitesitt/> The ''intersection'' of two sets ''A&cap;B'' plays the role of the ''AND'' operation and the ''union'' of two sets ''A&cup;B'' represents the ''OR'' function, as shown by gray shaded areas in the figure. To introduce the ''NOT'' operation, the universal set is represented by the rectangle, so ''~A'' is the set of everything not included in ''A'', corresponding to the gray portion of the rectangle in the lower left panel.
[[Venn diagram]]s provide a graphical visualization of the Boolean operations.<ref name=Whitesitt/> The ''intersection'' of two sets ''A&cap;B'' plays the role of the ''AND'' operation and the ''union'' of two sets ''A&cup;B'' represents the ''OR'' function, as shown by gray shaded areas in the figure. To introduce the ''NOT'' operation, the universal set is represented by the rectangle, so ''~A'' is the set of everything not included in ''A'', corresponding to the gray portion of the rectangle in the lower left panel.


These diagrams provide a visualization of the Boolean axioms as well. For example, the depiction of ''~(A&cup;B)'' is readily seen to be the same as ''(~A)&cup;(~B)'', as required by the De Morgan axiom.
These diagrams provide a visualization of the Boolean axioms as well. For example, the depiction of ''~(A&cap;B)'' is readily seen to be the same as ''(~A)&cup;(~B)'', as required by the De Morgan axiom.


==References==
==References==

Revision as of 12:31, 19 July 2011

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

A Boolean algebra is a form of logical calculus with two binary operations AND (multiplication, •) and OR (addition, +) and one unary operation NOT (negation, ~) that reverses the truth value of any statement. Boolean algebra can be used to analyze computer chips and switching circuits, as well as logical propositions.

Boolean algebra is not a portion of elementary algebra as taught in secondary schools, and is only a facet of algebra, the general mathematical discipline treating variables, symbols and sets.

Boolean algebra has strong connections to the propositional calculus, which relates the truth value of a conclusion to the truth value of the propositions upon which it is based. However, this is only a small, and unusually simple branch of modern mathematical logic.[1]

History

Boolean algebra was introduced in 1854 by George Boole in his book An Investigation of the Laws of Thought.[2] This algebra was shown in 1938 by Claude Elwood Shannon to be useful in the design of logic circuits.[3]

Axioms

The operations of a Boolean algebra, namely, two binary operations on a set A, named AND (multiplication, •) and OR (addition, +), and one unary operation NOT (negation, ~), are supplemented by two distinguished elements, namely 0 (called zero) and 1 (called one) that satisfy the following axioms for any subsets p, q, r of the set A:

The above axioms are redundant, and all can be proven using only the identity, complement, commutative and distributive laws. The distributive law:

may seem at variance with the laws for elementary algebra, which would state:

However, this expression is equivalent within the Boolean axioms above. From the other axioms, p·p = p. Also, p·r + q·p = p·(q + r). This set lies within p, so intuitively p + p·(q + r) = p. Using the Boolean axioms instead of intuition, p + p·(q + r) = p·(1 + q + r) and according to the properties of ‘1’, (1 + q + r) = 1. Thus, the elementary algebraic result, when interpreted in terms of the Boolean axioms, reduces to the Boolean distributive law.

Alternative notations

Some alternative notations for the operations of Boolean algebra include the following:

&&&

Venn diagrams

(PD) Image: John R. Brews
Interpretation of Boolean operations using Venn diagrams.
For more information, see: Venn diagram.

Venn diagrams provide a graphical visualization of the Boolean operations.[4] The intersection of two sets A∩B plays the role of the AND operation and the union of two sets A∪B represents the OR function, as shown by gray shaded areas in the figure. To introduce the NOT operation, the universal set is represented by the rectangle, so ~A is the set of everything not included in A, corresponding to the gray portion of the rectangle in the lower left panel.

These diagrams provide a visualization of the Boolean axioms as well. For example, the depiction of ~(A∩B) is readily seen to be the same as (~A)∪(~B), as required by the De Morgan axiom.

References

  1. Elliott Mendelson (1970). “Chapter 1: The algebra of logic”, Schaum's Outline of Boolean Algebra and Switching Circuits. McGraw-Hill. ISBN 0070414602. 
  2. George Boole (1854). An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities. Macmillan and Co.. 
  3. For example, see Jonathan Sterne (2003). “Shannon, Claude (1916-2001)”, Steve Jones, ed: Encyclopedia of new media: an essential reference to communication and technology. SAGE Publications, p. 406. ISBN 0761923829. 
  4. For a discussion, see J. Eldon Whitesitt (1995). “§1-4: Venn diagrams”, Boolean algebra and its applications, Republication of Addison-Wesley 1961 ed. Courier Dover Publications, pp. 5 ff. ISBN 0486684830.