'''Boolean logic''' is a complete system for Logical Operations. It was named after George_Boole, an English mathematician at University College Cork who first defined an algebraic system of logic in the mid 19th_century. Boolean logic has many applications in electronics, computer hardware and software. In 1938, Claude Shannon showed how electric circuits with relays were a model for 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 intro to Sets, Boolean operations, Venn_diagrams, Truth_tables, and Boolean applications. The Boolean_algebra article discusses the Algebraic_structure of applied Boolean logic. The Binary_arithmetic article discusses the use of binary numbers in Computer systems. ==Terms== Image:Venn_A_intersect_B.png Let ''X'' be a set: * An '''element''' is one member of a set. This is denoted by $\backslash in$. If it's not an element of the set, this is denoted by $\backslash 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 $\backslash varnothing$ and sometimes 0. * A '''unary operator''' applies to a single set. There is one unary operator, called logical '''NOT'''. It works by taking the complement. * A '''binary operator''' applies to two sets. The basic binary operators are logical '''OR''' and logical '''AND'''. They perform the intersection and union of sets. There are also other derived binary operators, such as '''XOR''' (exclusive OR). * A '''subset''' is denoted by $A\; \backslash subseteq\; B$ and means every element in set A is also in set B. * A '''proper subset''' is denoted by $A\; \backslash subset\; B$ and means every element in set A is also in set B and the two sets are not equal. * A '''superset''' is denoted by $A\; \backslash supseteq\; B$ and means every element in set B is also in set A. * A '''proper superset''' is denoted by $A\; \backslash supset\; B$ and means every element in set B is also in set A and the two sets are not equal. ==Example== Image:Boolean_Multiples_of_2_3_5.jpg Let's imagine that set A contains all even numbers (multiples of two) in "the universe" 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. ==Properties== Let's define symbols for the two primary binary operations as $\backslash land\; /\; \backslash cap$ (logical AND/intersection) and $\backslash lor\; /\; \backslash cup$ (logical OR/union), and for the single unary operation $\backslash lnot$ / ~ (logical NOT/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 algebra and Boolean logic: :{| cellpadding=5 |$a\; \backslash lor\; (b\; \backslash lor\; c)\; =\; (a\; \backslash lor\; b)\; \backslash lor\; c$ |$a\; \backslash land\; (b\; \backslash land\; c)\; =\; (a\; \backslash land\; b)\; \backslash land\; c$ | Associativity |- |$a\; \backslash lor\; b\; =\; b\; \backslash lor\; a$ |$a\; \backslash land\; b\; =\; b\; \backslash land\; a$ | Commutativity |- |$a\; \backslash lor\; (a\; \backslash land\; b)\; =\; a$ |$a\; \backslash land\; (a\; \backslash lor\; b)\; =\; a$ | absorption |- |$a\; \backslash lor\; (b\; \backslash land\; c)\; =\; (a\; \backslash lor\; b)\; \backslash land\; (a\; \backslash lor\; c)$ |$a\; \backslash land\; (b\; \backslash lor\; c)\; =\; (a\; \backslash land\; b)\; \backslash lor\; (a\; \backslash land\; c)$ | Distributivity |- |$a\; \backslash lor\; \backslash lnot\; a\; =\; 1$ |$a\; \backslash land\; \backslash lnot\; a\; =\; 0$ | complements |- |$a\; \backslash lor\; a\; =\; a$ |$a\; \backslash land\; a\; =\; a$ | idempotency |- |$a\; \backslash lor\; 0\; =\; a$ |$a\; \backslash land\; 1\; =\; a$ | rowspan=2 | boundedness |- |$a\; \backslash lor\; 1\; =\; 1$ |$a\; \backslash land\; 0\; =\; 0$ |- |$\backslash lnot\; 0\; =\; 1$ |$\backslash lnot\; 1\; =\; 0$ | 0 and 1 are complements |- |$\backslash lnot\; (a\; \backslash lor\; b)\; =\; \backslash lnot\; a\; \backslash land\; \backslash lnot\; b$ |$\backslash lnot\; (a\; \backslash land\; b)\; =\; \backslash lnot\; a\; \backslash lor\; \backslash lnot\; b$ | De_Morgan's_laws |- |$\backslash lnot\; \backslash lnot\; a\; =\; a$ | | Involution |} ==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: {| |- | width="80" | | {| border="1" cellpadding="4" cellspacing="0" |- ! $\backslash cap$ || 0 || 1 |- ! 0 | 0 || 0 |- ! 1 | 0 || 1 |} | width="40" | | {| border="1" cellpadding="4" cellspacing="0" |- ! $\backslash 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, $\backslash cap$as AND, $\backslash cup$as OR, and ¬ as NOT. ==Other notation== Various sets of basic operators may be used to express Boolean logic. AND, OR and NOT are the most intuitive. Mathematicians, Engineers, and Programmers often use + for OR and $\backslash cdot$ for AND (since in some ways those operations are analogous to addition and multiplication in other Algebraic_structures and this notation makes it very easy to get Sum_of_products_form for people who are familiar with normal algebra). NOT may also be represented by a line drawn above the expression being negated. 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== * 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 ($\backslash ge$) and less than or equals sign ($\backslash le$) may be assumed to contain a logical OR: ::X < 2 ::OR ::X = 2 * The plus/minus sign ($\backslash 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 words have imprecise meanings which may correspond with multiple formal meanings, for example, the word NOT: * "All that glitters is '''not''' gold." That 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." 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 candy and ice cream? You may have candy, '''or''' ice cream." (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) 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=== 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 engine queries=== {{wikibookschapter|book=How to search|chapter=Boolean Logic|name=Boolean Logic}} For this application, each web page on the Internet may be considered to be an "element" of a "set". The various online search engines may each use a different syntax. The syntax used by Google will be described here. * No symbol is used for logical AND. Therefore, it's the default way to link two 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: ::-"Search term 1" * Parentheses do not appear to be supported for explicitly specifying the order of operations. ==See also== {{col-begin}} {{col-break}} * Boolean_algebra * Boolean_algebra_topics * Boolean_domain * Boolean_function * Boolean-valued_function {{col-break}} * Laws_of_Form * Logic_gate * Logical_graph * Two-element_boolean_algebra * Venn_diagram {{col-end}} ==External links== {{wikibookspar||Boolean Algebra}} *The Calculus of Logic, by George Boole, Cambridge and Dublin Mathematical Journal Vol. III (1848), pp. 183-98. Category:Boolean_algebra Category:Logic Ru:Алгебра_логики Simple:Boolean_algebra Zh:布尔逻辑