Boolean algebra
Boolean algebra
Boolean algebra is often referred to as the algebra of logic. The English mathematician George Boole (1815–1864), who is largely responsible for its beginnings, was the first to apply algebraic techniques to logical methodology. He showed that logical propositions and their connectives could be expressed in the language of set theory. Thus, Boolean algebra is also the algebra of sets. Algebra is that branch of mathematics which is concerned with the relations of quantities.
Beginning with the members of a specific set (called the universal set), together with one or more binary operations defined on that set, procedures are derived for manipulating the members of the set using the defined operations, and combinations of those operations. Both the language and the rules of manipulation vary, depending on the properties of elements in the universal set. For instance, the algebra of real numbers differs from the algebra of complex numbers, because real numbers and complex numbers are defined differently, leading to differing definitions for the binary operations of addition and multiplication, and resulting in different rules for manipulating the two types of numbers. Boolean algebra consists of the rules for manipulating the subsets of any universal set, independent of the particular properties associated with individual members of that set. It depends, instead, on the properties of sets. The universal set may be any set, including the set of real numbers or the set of complex numbers, because the elements of interest, in Boolean algebra, are not the individual members of the universal set, but all possible subsets of the universal set.
Properties of sets
A set is a collection of objects, called members or elements. The members of a set can be physical objects, such as people, stars, or roses, or they can be abstractions such as numbers or even other sets. A set is referred to as the universal set (usually called I) if it contains all the elements under consideration. A set S not equal to I is called a proper subset of I if every element of S is contained in I. This is written and read “S is contained in I.” (see Figure 1)
If S equals I, then S is called an improper subset of I, that is, I is an improper subset of itself (note that two sets are equal if and only if they both contain exactly the same elements). The special symbol is given to the set with no elements, called the empty set or null set. The null set is a subset of every set.
When dealing with sets there are three important operations. Two of these operations are binary (that is, they involve combining sets two at a time), and the third involves only one set at a time. The two binary operations are union and intersection. The third operation is complementation. The union of two sets S and T is the collection of those members that belong to either S or T or both. (see Figure 2)
The intersection of the sets S and T is the collection of those members that belong to both S and T. (see Figure 3)
The complement of a subset, S, is that part of I not contained in S, and is written S’. (see Figure 4)
Properties of Boolean algebra
The properties of Boolean algebra can be summarized in four basic rules.
(1) Both binary operations have the property of commutativity, that is, order doesn’t matter.
S∩T= T∩S, and S∪T = T∪S.
(2) Each binary operation has an identity element associated with it. The universal set is the identity element for the operation of intersection, and the null set is the identity element for the operation of union.
S∩I = S, and S ∪Ø = S.
(3) each operation is distributive over the other.
S ∪(T∩ V) = (S ∪ T) ∩ (S ∪ V), and S ∩ (T∪V) = (S ∩ T) U (S ∩ V).
This differs from the algebra of real numbers, for which multiplication is distributive over addition, a(b + c) = ab + ac, but addition is not distributive over multiplication, a + (bc) not equal (a + b)(a + c).
(4) each element has associated with it a second element, such that the union or intersection of the two results in the identity element of the other operation.
A ∪′ = I, and A ∩ ′ = Ø.
This also differs from the algebra of real numbers. Each real number has two others associated with it, such that its sum with one of them is the identity element for addition, and its product with the other is the identity element for multiplication. That is, a + (-a) = 0, and a(1/a) = 1.
Applications
The usefulness of Boolean algebra comes from the fact that its rules can be shown to apply to logical statements. A logical statement, or proposition, can either be true or false, just as an equation with real
numbers can be true or false depending on the value of the variable. In Boolean algebra, however, variables do not represent the values that make a statement true, instead they represent the truth or falsity of the statement. That is, a Boolean variable can only have one of two values. In the context of symbolic logic these values are true and false.
Boolean algebra has proved essential in the field of computer engineering. By taking the two-valued variables of Boolean algebra to represent electronic states of on and off (or the binary digits 0 and 1), Boolean algebra can be used to design digital computational circuitry. It is thus the fundamental design language of all modern computers and other digital devices.
See also Computer, digital.
KEY TERMS
Binary operation— A binary operation is a method of combining the elements of a set, two at a time, in such a way that their combination is also a member of the set.
Complement— The complement of a set, S, written S’, is the set containing those members of the universal set that are not contained in S.
Element— Any member of a set. An object in a set.
Intersection— The intersection of two sets is itself a set comprised of all the elements common to both sets.
Set— A set is a collection of things called members or elements of the set. In mathematics, the members of a set will often be numbers.
Set theory— Set theory is the study of the properties of sets and subsets, especially those properties that are independent of the particular elements in a set.
Subset— A set, S, is called a subset of another set, I, if every member of S is contained in I.
Union— The union of two sets is the set that contains all the elements found in one or the other of the two sets.
Universal set— The universal set is the set containing all the elements being considered.
Resources
BOOKS
Marcovitz, Alan B. Introduction to Logic Design. New York: McGraw-Hill, 2006.
J.R. Maddocks
Boolean Algebra
Boolean Algebra
In 1847 George Boole (1815–1864), an English mathematician, published one of the works that founded symbolic logic. His combination of ideas from classical logic and algebra resulted in what is called Boolean algebra.
Using variables and symbols, Boole designed a language for describing and manipulating logical statements and determining if they are true or not. The variables stand for statements that are either true or false. The symbols +, * and − represent and, or, and not and are equivalent to the symbols [.logicaland], [.logicalor], and − used in the truth tables in logic. Although truth tables use T and F (for true and false respectively) to indicate the state of the sentence, Boolean algebra uses 1 and 0.
The relationship between Boolean algebra, set algebra, logic, and binary arithmetic has given Boolean algebra a central role in the development of electronic digital computers. Besides its many applications in the design of computers, it forms the foundation of information theory.
Truth Tables
Boolean algebra is based on propositions, which are non-ambiguous sentences that can be either true or false. One can combine these propositions in a variety of ways by using the connectives and and or, or one can negate them by preceding them with not. The results of these operations on propositions are dictated by the rules of Boolean algebra. For example, if one says: "I will buy green mittens," then she is actually saying that she will buy mittens and those mittens will be green. Therefore the properties of "mittens" and "green" will have to be present in all her "hand-covering" purchases. This will exclude gloves and all non-green mittens. How does this work out using truth tables? Let A represent "mittens," B represent "green." Figure 1(a) shows how the statement "mittens and green" is represented using truth tables, while Figure 1(b) shows the same statement using Boolean algebra.
What the tables indicate is that if an item does not possess both the quality of being a mitten and the quality of being green, then it will be discarded. Only those that satisfy both qualities will be selected.
On the other hand, if one says: "I will buy gloves or mittens," then he is actually saying that he will buy mittens, or gloves, or some combination. This means that he will have a great assortment of "hand-covering" garments. Let A represent "mittens" and B represent "gloves." Figure 2(a) shows how the statement "mittens or gloves" is represented using truth tables, while Figure 2(b) shows the same statement using Boolean algebra.
What the tables indicate is that an item will be selected if it possesses both qualities of mitten and glove, or possesses only one quality, either glove or mitten. Only those that satisfy neither quality will be discarded—for example, all red socks.
One can also say: "I will buy something to cover my hands, but not mittens." Let A represent "mittens." Figure 3(a) shows how the statement "not mittens" is represented using truth tables, while Figure 3(b) shows the same statement using Boolean algebra.
The tables indicate that if an item is a mitten then its negation, –A, represents a non-mitten—for example, a glove or a sock.
Computer Design
Boolean algebra can be applied to the design and simplification of complex circuits present in computers because computer circuits are two-state devices: they can be either off or on. This corresponds to the general representation of Boolean algebra with two elements, 0 and 1. To show how this works, take a look at two simple circuits, "and," and "or," which correspond to the first two sets of tables presented earlier. These simple circuits consist of a power source—a battery connected by a wire to a destination—and a lamp with two switches that control the flow of electricity. The position of a switch either allows electricity to flow from the power source to the destination, or stops it. For example, if the switch is up, or open, then electricity does not flow, and this condition is represented by a 0. However, if the switch is down, or closed, the electricity will flow, and this is represented by 1.
Figure 4 shows the diagram of a two-switch series circuit, where electricity will flow from the source to the destination only if both switches are closed. This diagram represents the and condition of Boolean algebra.
A circuit where electricity flows whenever at least one of the switches is closed is known as a parallel circuit. This corresponds to the or condition of Boolean algebra. Figure 5 shows the diagram of a two-switch parallel circuit.
To represent the not condition, one must remember that in this system a switch has only two possible positions, open or closed. Its complement is a switch that will have the opposite position. For example, if switch A is open, its complement will be closed and vice versa. Logic designers can use these diagrams to plan complex computer circuits that will perform the needed functions for a specific machine.
Information Theory
Boolean algebra is used in information theory because almost all search engines allow someone to enter queries in the form of logical expressions. The operator and is used to narrow a query whereas or is used to broaden it. The operator not is used to exclude specific words from a query. For example, if one is looking for information about "privacy in computer environments," she could phrase her query as "computer and privacy," or "computer or privacy," or even "computer and privacy not mainframes." The amount of information received from each query will be different.
The first query will retrieve fewer documents because it will only select those that contain both terms. The second will retrieve many documents because it will select those that contain "computer," those that contain "privacy," and also those that contain both terms. The last query will retrieve documents that contain both "privacy" and "computer," while anything containing the term "mainframe" will be discarded.
When using search engines, one must realize that each one will access its database differently. Typically the same search performed in more than one database will not return the same result. To do a thorough search, one must become familiar with a few of the different search engines and understand their major features, such as Boolean logic and truncation. In addition, one must check the search engine's documentation often because it can change frequently.
see also Algorithms; Binary Number System; Boole, George; Decision Support Systems; Digital Logic Design.
Ida M. Flynn
Bibliography
McCullough, Robert N. Mathematics for Data Processing, 2nd ed. Englewood, CO: Morton Publishing Co., 2001.
Warring, Ronald H. Logic Made Easy. Summit, PA: TAB Books, Inc., 1985.
Whitesitt, J. Eldon. Boolean Algebra and Its Applications. New York: Dover Publications, Inc., 1995.
Boolean Algebra
Boolean algebra
Boolean algebra is often referred to as the algebra of logic, because the English mathematician George Boole, who is largely responsible for its beginnings, was the first to apply algebraic techniques to logical methodology. Boole showed that logical propositions and their connectives could be expressed in the language of set theory . Thus, Boolean algebra is also the algebra of sets. Algebra, in general, is the language of mathematics , together with the rules for manipulating that language. Beginning with the members of a specific set (called the universal set), together with one or more binary operations defined on that set, procedures are derived for manipulating the members of the set using the defined operations, and combinations of those operations. Both the language and the rules of manipulation vary, depending on the properties of elements in the universal set. For instance, the algebra of real numbers differs from the algebra of complex numbers , because real numbers and complex numbers are defined differently, leading to differing definitions for the binary operations of addition and multiplication , and resulting in different rules for manipulating the two types of numbers. Boolean algebra consists of the rules for manipulating the subsets of any universal set, independent of the particular properties associated with individual members of that set. It depends, instead, on the properties of sets. The universal set may be any set, including the set of real numbers or the set of complex numbers, because the elements of interest, in Boolean algebra, are not the individual members of the universal set, but all possible subsets of the universal set.
Properties of sets
A set is a collection of objects, called members or elements. The members of a set can be physical objects, such as people, stars, or red roses, or they can be abstract objects, such as ideas, numbers, or even other sets. A set is referred to as the universal set (usually called I) if it contains all the elements under consideration. A set, S, not equal to I, is called a proper subset of I, if every element of S is contained in I. This is written and read "S is contained in I." (see Figure 1)
If S equals I, then S is called an improper subset of I, that is, I is an improper subset of itself (note that two sets are equal if and only if they both contain exactly the same elements). The special symbol is given to the set with no elements, called the empty set or null set. The null set is a subset of every set.
When dealing with sets there are three important operations. Two of these operations are binary (that is, they involve combining sets two at a time), and the third involves only one set at a time. The two binary operations are union and intersection. The third operation is complementation. The union of two sets S and T is the collection of those members that belong to either S or T or both. (see Figure 2)
The intersection of the sets S and T is the collection of those members that belong to both S and T. (see Figure 3)
The complement of a subset, S, is that part of I not contained in S, and is written S'. (see Figure 4)
Properties of Boolean algebra
The properties of Boolean algebra can be summarized in four basic rules.
- Both binary operations have the property of commutativity, that is, order doesn't matter.
- Each binary operation has an identity element associated with it. The universal set is the identity element for the operation of intersection, and the null set is the identity element for the operation of union.
- each operation is distributive over the other.
This differs from the algebra of real numbers, for which multiplication is distributive over addition, a(b+c) = ab + ac, but addition is not distributive over multiplication, a+(bc) not equal (a+b)(a+c).
each element has associated with it a second element, such that the union or intersection of the two results in the identity element of the other operation.
This also differs from the algebra of real numbers. Each real number has two others associated with it, such that its sum with one of them is the identity element for addition, and its product with the other is the identity element for multiplication. That is, a + (-a) = 0, and a(1/a) = 1.
Applications
The usefulness of Boolean algebra comes from the fact that its rules can be shown to apply to logical statements. A logical statement, or proposition, can either be true or false, just as an equation with real numbers can be true or false depending on the value of the variable . In Boolean algebra, however, variables do not represent the values that make a statement true, instead they represent the truth or falsity of the statement. That is, a Boolean variable can only have one of two values. In the context of symbolic logic these values are true and false. Boolean algebra is also extremely useful in the field of electrical engineering . In particular, by taking the variables to represent values of on and off (or 0 and 1), Boolean algebra is used to design and analyze digital switching circuitry, such as that found in personal computers, pocket calculators, cd players, cellular telephones, and a host of other electronic products.
See also Computer, digital.
Resources
books
Christian, Robert R. Introduction to Logic and Sets. Waltham, MA: Blaisdell Publishing Co., 1965.
Garfunkel, Soloman A., ed. For All Practical Purposes: Introduction to Contemporary Mathematics. New York: W. H. Freeman, 1988.
Hoernes, Gerhard E., and Melvin F. Heilweil. Boolean Algebra and Logic Design. New York: McGraw Hill, 1964.
Ryan, Ray, and Lisa A. Doyle. Basic Digital Electronics, 2nd ed. Blue Ridge Summit, PA: Tab Books, 1990.
J.R. Maddocks
KEY TERMS
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .- Binary operation
—A binary operation is a method of combining the elements of a set, two at a time, in such a way that their combination is also a member of the set.
- Complement
—The complement of a set, S, written S', is the set containing those members of the universal set that are not contained in S.
- Element
—Any member of a set. An object in a set.
- Intersection
—The intersection of two sets is itself a set comprised of all the elements common to both sets.
- Set
—A set is a collection of things called members or elements of the set. In mathematics, the members of a set will often be numbers.
- Set theory
—Set theory is the study of the properties of sets and subsets, especially those properties that are independent of the particular elements in a set.
- Subset
—A set, S, is called a subset of another set, I, if every member of S is contained in I.
- Union
—The union of two sets is the set that contains all the elements found in one or the other of the two sets.
- Universal set
—The universal set is the set containing all the elements being considered.
Boolean Algebra
Boolean algebra
Boolean algebra is a form of mathematics developed by English mathematician George Boole (1815–1864). Boole created a system by which certain logical statements can be expressed in mathematical terms. The consequences of those statements can then be discovered by performing mathematical operations on the symbols.
As a simple example, consider the following two statements: "I will be home today" and "I will be home tomorrow." Then let the first statement be represented by the symbol P and the second statement be represented by the symbol Q. The rules of Boolean algebra can be used to find out the consequences of various combinations of these two propositions, P and Q.
In general, the two statements can be combined in one of two ways:
P or Q: I will be home today OR I will be home tomorrow.
P and Q: I will be home today AND I will be home tomorrow.
Now the question that can be asked is what conclusions can one draw if P and Q are either true (T) or false (F). For example, what conclusion can be drawn if P and Q are both true? In that case, the combination P or Q is also true. That is, if the statement "I will be home today" (P) is true, and the statement "I will be home tomorrow" (Q) is also true, then the combined statement, "I will be home today OR I will be home tomorrow" (P or Q) must also be true.
By comparison, suppose that P is true and Q is false. That is, the statement "I will be home today" (P) is true, but the statement "I will be home tomorrow" (Q) is false. Then the combined statement "I will be home today OR I will be home tomorrow" (P or Q) must be false.
Most problems in Boolean algebra are far more complicated than this simple example. Over time, mathematicians have developed sophisticated mathematical techniques for analyzing very complex logical statements.
Applications
Two things about Boolean algebra make it a very important form of mathematics for practical applications. First, statements expressed in everyday language (such as "I will be home today") can be converted into mathematical expressions, such as letters and numbers. Second, those symbols generally have only one of two values. The statements above (P and Q), for example, are either true or false. That means they can be expressed in a binary system: true or false; yes or no; 0 or 1.
Binary mathematics is the number system most often used with computers. Computer systems consist of magnetic cores that can be switched on or switched off. The numbers 0 and 1 are used to represent the two possible states of a magnetic core. Boolean statements can be represented, then, by the numbers 0 and 1 and also by electrical systems that are either on or off. As a result, when engineers design circuitry for personal computers, pocket calculators, compact disc players, cellular telephones, and a host of other electronic products, they apply the principles of Boolean algebra.
[See also Algebra; Computer, digital ]
Boolean algebra
There are two very common examples of Boolean algebras. The first consists of the set B = {FALSE, TRUE}
with the dyadic AND and OR operations replacing ∧ and ∨ respectively, and the NOT operation producing complements. Thus 1 and 0 are just TRUE and FALSE respectively. This idea can be readily extended to the set of all n-tuples (x1,x2,…,xn)
where each xi is in B. The AND and OR operations are then extended to operate between corresponding pairs of elements in each n-tuple to produce another n-tuple; the NOT operation negates each item of an n-tuple.
The second common example of a Boolean algebra is the set of subsets of a given set S, with the operations of intersection and union replacing ∧ and ∨ respectively; set complement fills the role of Boolean algebra complement.
Boolean algebras, named for George Boole, the 19th-century English mathematician, are fundamental to many aspects of computing – logic design, logic itself, and aspects of algorithm design.
Boolean operation
In constructive solid geometry, Boolean operations are the three set operations union, set difference, and intersection.
Boolean Operator
BOOLEAN OPERATOR
When individuals use search engines to find information on the Internet, the Boolean Operators "AND," "OR," and "NOT" are often used to maximize the relevancy and effectiveness of their search. By entering them in the form of a search query, these operators specify the parameters of a search. For example, someone searching for information about surfing in California might enter the following query to target their search: "Surfing AND California". By using the "AND" operator, the search will only include results that contain the words California and surfing, not results that include only one of the two terms. If the individual were interested in results about California, surfing, or California and surfing, the following query could be used: Surfing OR California. Finally, if someone wanted information about surfing, but specifically not about surfing in California, the NOT operator could be used as follows: Surfing NOT California.
Boolean operators are a fundamental component of a kind of algebra called Boolean Logic. Named after 19th century English mathematician George Boole, Boolean Logic boils down all values to one of two states: true or false. This closely mirrors the binary approach digital computers use to interpret and process information, whereby commands are converted to sequences of either zeroes or ones. The millions of transistors found on a computer's microprocessor are always in one of two states (on or off). These two states, which are represented by ones and zeroes, respectively, correspond to Boolean Logic.
FURTHER READING:
"Boolean." CNET.com, . May 29, 2001. Available from www.cnet.com/Resources/Info/Glossary.
"Boolean Expression." Ecomm Webopedia, May 25, 2001. Available from www.e-comm.webopedia.com.
"Boolean Logic." Ecomm Webopedia, May 25, 2001. Available from www.e-comm.webopedia.com.
"Boolean Logic." Tech Encyclopedia, . May 25, 2001. Available from www.techweb.com.
Morton, Douglas. "Refresher Course: Boolean AND (searching OR retrieval)." Online, January, 1993.
Boolean function
For any particular values of its constituent variables, the value of the function is either 0 or 1, depending on the combinations of values assigned to the variables. A Boolean function can be represented in a truth table. It can also be transformed into a logic diagram of logic gates. See also product of sums expression, sum of products expression.
Boolean expression
Any combinational circuit can be modeled directly and completely by means of a Boolean expression, but this is not so of sequential circuits.
Boolean Operators
BOOLEAN OPERATORS
Boolean operators help expand or narrow the scope of a search. A search for rivers OR lakes returns documents with either word in them. A search for rivers AND lakes returns documents with both words in them. A search for rivers AND lakes NOT swamps returns documents that mention both rivers and lakes but omits those that also mention swamps. Implied Boolean Operators are characters such as and , which can be used to require or prohibit a word or phrase as part of a search expression. The acts somewhat like AND, and the acts as NOT would in a Boolean expression. For example, the Boolean expression rivers AND lakes NOT swamps may be expressed as rivers lakes swamps.