Boolean logic

Boolean logic is a complete system for logical operations, used in many systems^{[clarification needed]}. 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. The Boolean algebra (structure) article discusses a type of algebraic structure that satisfies the axioms of Boolean logic. The binary arithmetic article discusses the use of binary numbers in computer systems.

Terms

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 is the set X, sometimes denoted by 1. Note that this use of the word universe means "all elements being considered", which are 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 with respect to the universe, i.e. the set of all elements under consideration.

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").

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.

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 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.

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$ / ~ (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 (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
$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 (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

The first three properties define a lattice; the first five define a Boolean algebra. The remaining five are a consequence of the first five.

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.

Programmers will 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. "||", "&&", and "!" are used for variants of these operations.

Another notation uses "meet" for AND and "join" for OR.^{[clarification needed]} 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.^{[citation needed]}

Basic mathematics use of Boolean terms

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

x + y = 2

AND

x - y = 2

The same applies to simultaneous inequalities:

x + y < 2

AND

x - y < 2

The greater than or equals sign ( $\geq$ ) and less than or equals sign ( $\leq$ ) may be assumed to contain a logical OR:

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

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.

In certain cases, AND and OR can be used interchangeably in English: I always carry an umbrella for when it rains and snows has the same meaning as I always carry an umbrella for when it rains or snows. An alternate phrasing would be I always carry an umbrella for when precipitation is forecast.

Sometimes the English words "and" and "or" have a meaning that is apparently opposite of its meaning in boolean logic: "Give me all the red and blue berries" usually means, "Give me all the berries that are either red or blue". An alternative phrasing for this request would be, "Give me all berries that are red and all berries that are blue."

Depending on the context, the word "or" may correspond with either logical OR (which corresponds to the English equivalent "and/or") or logical XOR (which corresponds to the English equivalent "either/or"):
- The waitress asked, "Would you like cream or sugar with your coffee?" This is an example of a "Logical OR", whereby the choices are cream, sugar, or cream and sugar (in addition to none of the above).
- The waitress asked, "Would you like soup or salad with your meal?" This is an example of a "Logical XOR", whereby the choices are soup or salad (or neither), but soup and salad are not an option.)
- This can be a significant challenge when providing precise specifications for a computer program or electronic circuit in English. The description of such functionality may be ambiguous. Take for example the statement, "The program should verify that the applicant has checked the male or female box." This is usually interpreted as an XOR and so a verification is performed to ensure that one, and only one, box is selected. In other cases the intended interpretation of English may be less obvious; the author of the specification should be consulted to determine the original 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

Relational databases use SQL, or other database-specific languages, to perform queries, which may contain Boolean logic. For this application, each record in a table may be considered to be an "element" of a "set". For example, in SQL, these SELECT statements are used to retrieve data from tables in the database:

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

This 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' ;

This 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' ;

This 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.

Parentheses may be used to explicitly specify the order in which Boolean operations occur, when multiple operations are present:

SELECT * FROM employees WHERE (NOT last_name = 'Smith') AND (first_name = 'John' OR first_name = 'Mary') ;

This example will produce a list of employees named John OR named Mary, but specifically excluding those named John Smith or Mary Smith.

Multiple sets of nested parentheses may also be used, where needed.

Any Boolean operation (or operations) which combines two (or more) tables together is referred to as a join, in relational database terminology.

In the field of Electronic Medical Records, some software applications use Boolean logic to query their patient databases, in what has been named 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 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

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
Maiki & Boaz BDD-PROJECT, a Web Application for BDD reduction and visualization.

[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]

v t e Digital electronics
Components	Transistor Resistor Inductor Capacitor Printed electronics Printed circuit board Electronic circuit Flip-flop Memory cell Combinational logic Sequential logic Logic gate Boolean circuit Integrated circuit (IC) Hybrid integrated circuit (HIC) Mixed-signal integrated circuit Three-dimensional integrated circuit (3D IC) Emitter-coupled logic (ECL) Erasable programmable logic device (EPLD) Macrocell array Programmable logic array (PLA) Programmable logic device (PLD) Programmable Array Logic (PAL) Generic Array Logic (GAL) Complex programmable logic device (CPLD) Field-programmable gate array (FPGA) Field-programmable object array (FPOA) Application-specific integrated circuit (ASIC) Tensor Processing Unit (TPU)
Theory	Digital signal Boolean algebra Logic synthesis Logic in computer science Computer architecture Digital signal Digital signal processing Circuit minimization Switching circuit theory Gate equivalent
Design	Logic synthesis Place and route Placement Routing Transaction-level modeling Register-transfer level Hardware description language High-level synthesis Formal equivalence checking Synchronous logic Asynchronous logic Finite-state machine Hierarchical state machine
Applications	Computer hardware Hardware acceleration Digital audio radio Digital photography Digital telephone Digital video cinematography television Electronic literature
Design issues	Metastability Runt pulse