Primary mathematics:Boolean logic

< Wikiversity < Wikiversity:School of Mathematics < School of Mathematics:Primary School Mathematics

Boolean logic (also called Boolean algebra) is a complete system for logical operations, used often since popularization of mathematical logic and discussions concerning the foundations of mathematics. It was named after George Boole, who first defined an algebraic system of logic in the mid 19th century. Boolean logic has many applications in electronics, computer hardware and software, and is the basis of all modern digital electronics. In 1938, Claude Shannon showed how electric circuits with relays could be modeled with Boolean logic. This fact soon proved enormously consequential with the emergence of the electronic computer.

Using the algebra of sets, this article contains a basic introduction to sets, Boolean operations, Venn diagrams, truth tables, and Boolean applications.

Set logic vs. Boolean logic

Sets can contain any elements. We will first start out by discussing general set logic, then restrict ourselves to Boolean logic, where elements (or "bits") each contain only two possible values, called various names, such as "true" and "false", "yes" and "no", "on" and "off", or "1" and "0".

Terms

Venn diagram showing the intersection of sets "A AND B" (in violet/dark shading), the union of sets "A OR B" (all the colored regions), and the exclusive OR case "set A XOR B" (all the colored regions except the violet). The "universe" is represented by all the area within the rectangular frame.

Let X be a set:

An element is one member of a set and is denoted by $\in$ . If the element is not a member of a set it is denoted by $\notin$ .
The universe, sometimes denoted by 1, is "all elements being considered", which is not necessarily the same as "all elements there are".
The empty set or null set is the set of no elements, denoted by $\varnothing$ and sometimes 0.
A unary operator applies to a single set. There is only one unary operator, called logical NOT. It works by taking the complement (opposite) of a set.
A binary operator applies to two sets. The basic binary operators are logical OR and logical AND. They perform the union and intersection of sets.

There are also other derived binary operators, such as XOR (exclusive OR, i.e., "one or the other, but not both"), and set difference, A−B.

The identity or equivalence of two sets is denoted by $A\equiv B$ and means that every element in set A is also in set B and every element in set B is also in set A.
A subset is denoted by $A\subseteq B$ and means every element in set A is also in set B.
A superset is denoted by $A\supseteq B$ and means every element in set B is also in set A.
A proper subset is denoted by $A\subset B$ and means every element in set A is also in set B and the two sets are not identical.
A proper superset is denoted by $A\supset B$ and means every element in set B is also in set A and the two sets are not identical.

a = a and ~a = ~a and a =/= ~a

a + 0 = a and a - 0 = a and ~a + 0 = ~a and ~a - 0 = ~a

a.1 = a and a/1 = a and ~a.1 = ~a and ~a/1 = ~a

a.0 = 0 and a/0 = 0 and ~a.0 = 0 and ~a/0 = 0

a + 1 = 1 + a and a - 1 = -1 + a and ~a + 1 = 1 + ~a and ~a - 1 = -1 + ~a

0 + a = a and 0 - a = -a and 0 + ~a = ~a and 0 - ~a = - ~a

a + a = a + a and a . a = a and a - a = 0 and a / a = 1

a + ~a = 0 and a . ~a = 0 and a - ~a = 1 and a / ~a = -1

a . b = b . a and a + b = b + a

(a + b) + c = a + (b + c) and (a . b) . c = a . (b . c)

a + (b . c) = (a + b) . (a + c) and a . (b + c) = (a . b) + (a . c)

~(a + b) = ~a + ~b and ~(a . b) = ~a . ~b

a / b = a / b and a - b = -b + a

(a - b) - c = a - (b - c) and (a / b) / c = a / (b / c)

a - (b / c) = (a - b) / (a - c) and a / (b - c) = (a / b) - (a / c)

~(a - b) = ~a - ~b and ~(a / b) = ~a / ~b

Example

Imagine that set A contains all even numbers (multiples of two) in "the universe" (defined in the example below as all integers between 0 and 30 inclusive) and set B contains all multiples of three in "the universe". Then the intersection of the two sets (all elements in sets A AND B) would be all multiples of six in "the universe". The complement of set A (all elements NOT in set A) would be all odd numbers in "the universe".

Chaining operations together

While at most two sets are joined in any Boolean operation, the new set formed by that operation can then be joined with other sets utilizing additional Boolean operations. Using the previous example, we can define a new set C as the set of all multiples of five in "the universe". Thus "sets A AND B AND C" would be all multiples of 30 in "the universe". If more convenient, we may consider set AB to be the intersection of sets A and B, or the set of all multiples of six in "the universe". Then we can say "sets AB AND C" are the set of all multiples of 30 in "the universe". We could then take it a step further, and call this result set ABC.

Use of parentheses

While any number of logical ANDs (or any number of logical ORs) may be chained together without ambiguity, the combination of ANDs and ORs and NOTs can lead to ambiguous cases. In such cases, parentheses may be used to clarify the order of operations. As always, the operations within the innermost pair is performed first, followed by the next pair out, etc., until all operations within parentheses have been completed. Then any operations outside the parentheses are performed.

Application to binary values

In this example we have used natural numbers, while in Boolean logic binary numbers are often used. The universe, for example, could contain just two elements, "1" and "0" (or "true" and "false", "yes" and "no", "on" or "off", etc.). We could also combine binary values together to get binary words, such as, in the case of two digits, "00", "01", "10", and "11". Applying set logic to those values, we could have a set of all values where the first digit is "0" ("00" and "01") and the set of all values where the first and second digits are different ("01" and "10"). The intersection of the two sets would then be the single element, "01". This could be shown by the following Boolean expression, where "1st" is the first digit and "2nd" is the second digit:

(NOT 1st) AND (1st XOR 2nd)

Properties

We define symbols for the two primary binary operations as $\land /\cap$ (logical AND/set intersection) and $\lor /\cup$ (logical OR/set union), and for the single unary operation $\lnot /\sim$ (logical NOT/set complement). We will also use the values 0 (logical FALSE/the empty set) and 1 (logical TRUE/the universe). The following properties apply to both Boolean logic and set logic (although only the notation for Boolean logic is displayed here):

$a\lor \lnot a=1$	$a\land \lnot a=0$	complements
$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$	boundedness
$\lnot 0=1$	$\lnot 1=0$	0 and 1 are complements
$\lnot (\lnot a)=a$		involution
$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
$\lnot (a\lor b)=\lnot a\land \lnot b$	$\lnot (a\land b)=\lnot a\lor \lnot b$	de Morgan's laws

Truth tables

For Boolean logic using only two values, 0 and 1, the INTERSECTION and UNION of those values may be defined using truth tables such as these:

$\cap$	0	1
0	0	0
1	0	1

$\cup$	0	1
0	0	1
1	1	1

More complex truth tables involving multiple inputs, and other Boolean operations, may also be created.

Truth tables have applications in logic, interpreting 0 as FALSE, 1 as TRUE, $\cap$ as AND, $\cup$ as OR, and ¬ as NOT.

Other notations

Mathematicians and engineers often use plus (+) for OR and a product sign ( $\cdot$ ) for AND. OR and AND are somewhat analogous to addition and multiplication in other algebraic structures, and this notation makes it very easy to get sum of products form for normal algebra. NOT may be represented by a line drawn above the expression being negated ( ${\overline {x}}$ ). It also commonly leads to giving $\cdot$ a higher precedence than +, removing the need for parenthesis in some cases.

Programming languages often use a pipe symbol (|) for OR, an ampersand (&) for AND, and a tilde (~) for NOT. In many programming languages, these symbols stand for bitwise operations, however, and "||", "&&", and "!" may be used for the logical OR, AND, and NOT operations.

Another notation uses "meet" for AND and "join" for OR. However, this can lead to confusion, as the term "join" is also commonly used for any Boolean operation which combines sets together, which includes both AND and OR.

Basic mathematics use of Boolean terms

Underlying the "language of mathematics" are boolean assumptions that are seldom explicitly stated. The following examples show the unstated boolean relationship.

In the case of simultaneous equations, they are connected with an implied logical AND:

(4x + y = 2) and (2x − y = 2)

Similarly, for simultaneous inequalities:

(x + y < 2) and (x − y < 7)

Both the greater-than-or-equals and less-than-or-equals inequalities most often implicitly have an OR boolean joining them:

(x ≤ 2) means

(x < 2) or (x = 2)

The plus/minus sign ( $\pm$ ), as in the case of the solution to a square root problem, may be taken as logical OR:

(Width ± 3) means

(Width = 3) or (Width = −3)

English language use of Boolean terms

Care should be taken when converting an English sentence into a formal Boolean statement. Many English sentences have imprecise meanings, for example "all that glitters is not gold", which could mean that "nothing that glitters is gold" or "some things which glitter are not gold".

AND and OR can also be used interchangeably in English, in certain cases:

"I always carry an umbrella for when it rains and snows."

"I always carry an umbrella for when it rains or snows."

Sometimes the English words AND and OR have the opposite meaning in Boolean logic:

"Give me all the red and blue berries" usually means "Give me all berries that are red or blue". An alternative phrasing for standard written English: "Give me all berries that are red as well as all berries that are blue".

Also note that the word OR in English may correspond with either logical OR or logical XOR, depending on the context:

"I start to sweat when the humidity or temperature is high." (logical OR)

"You want ice cream and candy? You may have ice cream or candy." (logical XOR)

The combination AND/OR is sometimes used in English to specify a logical OR, when just using the word OR alone might have been mistaken as meaning logical XOR:

"I'm having chicken and/or beef for dinner." (logical OR). An alternative phrasing for standard written English: "I'm having chicken, or beef, or both, for dinner."

A case where this is an issue is when specifications for a computer program or electronic circuit are supplied as an English paragraph describing their function. For example, the statement: "the program should verify that the applicant has checked the male or female box", should be taken as an XOR, and a check added to ensure that one, and only one, box is selected. In other cases, the interpretation of English may be less certain, and the author of the specification may need to be consulted to determine their true intent.

Applications

Digital electronic circuit design

Boolean logic is also used for circuit design in electrical engineering; here 0 and 1 may 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.

Basic logic gates such as AND, OR, and NOT gates may be used alone, or in conjunction with NAND, NOR, and XOR gates, to control digital electronics and circuitry. Whether these gates are wired in series or parallel controls the precedence of the operations.

Database applications

For this application, each record in a table may be considered to be a row "element" of a data "set". There are Boolean data types, and then there is Boolean logic used for the selection of elements from any set of data types. Examples of both are shown.

Some Relational databases (DB Management Systems, DBMS) can query a set of data having Boolean values. The standardized query language, SQL, supports a three-valued logic: true, false, or unknown. This Boolean data type was introduced in the ISO SQL:1999 standard.

CREATE TABLE test1 
(
  a int, 
  b boolean
);

INSERT INTO test1 
VALUES (1, true);

INSERT INTO test1 
VALUES (2, false);

INSERT INTO test1
VALUES (3, null);

INSERT INTO test1
VALUES (4, unknown);

SELECT * 
FROM test1;

a              b
------------- ----------------
1             TRUE
2             FALSE
3             NULL
4             UNKNOWN

The SQL Boolean data type did not gain widespread adoption, owing to the following inconsistency: SQL data types can have the special null value as well. The standard says that the NULL BOOLEAN and UNKNOWN "may be used interchangeably to mean exactly the same thing". This identification creates the possibility that UNKNOWN = UNKNOWN is not TRUE but UNKNOWN/NULL. Most SQL DBMSs use other data types like bit, byte, and char to simulate the behavior of Boolean data types. PostgreSQL does support the standard SQL Boolean data type.

Here are some examples using Boolean logic "NOT", "AND", and "OR":

SELECT * FROM employees WHERE last_name = 'Dean' AND first_name = 'James' ;

That example will produce a list of all employees, and only those employees, named James Dean.

SELECT * FROM employees WHERE last_name = 'Dean' OR  first_name = 'James' ;

That example will produce a list of all employees whose first name is James OR whose last name is Dean. Any and all employees named James Dean (from the first example) would also appear in this list.

SELECT * FROM employees WHERE NOT last_name = 'Dean' ;

That example will produce a list of all employees whose last name is not Dean. All employees named James from the second example would appear on this list, except for those employees named James Dean.

In the field of Electronic Medical Records, the Boolean logic is called a Concept Processing technology.

Search engine queries

Search engine queries also employ Boolean logic. For this application, each web page on the Internet may be considered to be an "element" of a "set". The following examples use a syntax supported by Google.^[1]

Doublequotes are used to combine whitespace-separated words into a single search term.^[2]
Whitespace is used to specify logical AND, as it is the default operator for joining search terms:

   "Search term 1" "Search term 2"

The OR keyword is used for logical OR:

   "Search term 1" OR "Search term 2"

The minus sign (approximated as a hyphen) is used for logical NOT (AND NOT):

   "Search term 1" -"Search term 2"

Notes and references

↑ Not all search engines support the same query syntax. Additionally, some organizations provide "specialized" search engines that support alternate or extended syntax. (See e.g.,Syntax cheatsheet, Google codesearch supports regular expressions).
↑ Doublequote-delimited search terms are called "exact phrase" searches in the Google documentation.

External links

Wikibooks Electronics has a page on the topic of Boolean Algebra.

Wikibooks How to search has a page on the topic of Boolean Logic.

The Calculus of Logic, by George Boole, Cambridge and Dublin Mathematical Journal Vol. III (1848), pp. 183–98.
Logical Formula Evaluator (for Windows), a software which calculates all possible values of a logical formula
How Stuff Works - Boolean Logic
Wikipedia:Boolean algebra

[1] Not all search engines support the same query syntax. Additionally, some organizations provide "specialized" search engines that support alternate or extended syntax. (See e.g.,Syntax cheatsheet, Google codesearch supports regular expressions).

[2] Doublequote-delimited search terms are called "exact phrase" searches in the Google documentation.

[1]

[2]