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 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.
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".
Let X be a set:
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.
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.
In this example we have used natural numbers, while in Boolean logic binary numbers are used. The universe, for example, could contain just two elements, "0" and "1" (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)
We define symbols for the two primary binary operations as (logical AND/set intersection) and (logical OR/set union), and for the single unary operation / ~ (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):
|0 and 1 are complements|
|de Morgan's laws|
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:
Mathematicians and engineers often use plus (+) for OR and a product sign () 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 ().
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. 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.
Care should be taken when converting an English sentence into a formal Boolean statement. Many English sentences have imprecise meanings, e.g. "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:
Sometimes the English words AND and OR have the opposite meaning in Boolean logic:
Also note that the word OR in English may correspond with either logical OR or logical XOR, depending on the context:
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:
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.
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.
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 = 'Smith' AND FIRST_NAME = 'John' ;
SELECT * FROM EMPLOYEES WHERE LAST_NAME = 'Smith' OR FIRST_NAME = 'John' ;
SELECT * FROM EMPLOYEES WHERE NOT LAST_NAME = 'Smith' ;
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') ;
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.
"Search term 1" "Search term 2"
"Search term 1" OR "Search term 2"
"Search term 1" -"Search term 2"
US Patent Issued to PDF Solutions on Dec. 20 for "Method and System for Mapping a Boolean Logic Network to a Limited Set of Application-Domain Specific Logic Cells" (California Inventor)
Dec 27, 2011; ALEXANDRIA, Va., Dec. 25 -- United States Patent no. 8,082,529, issued on Dec. 20, was assigned to PDF Solutions Inc. (San Jose,...