Boolean logic: Difference between revisions

Revision as of 01:33, 13 August 2010

Latest revision as of 09:50, 6 May 2020

(92 intermediate revisions by 50 users not shown)

Line 1:

{{Mergeto|Introduction to#REDIRECT [[Boolean algebra|date=February 2010}}]]

'''Boolean logic''' is a complete [[formal system|system]] for [[logic]]al [[operation (mathematics)|operation]]s, used in many systems. It was named after [[George Boole]], who first defined an [[algebraic structure|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 Elwood Shannon|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 introduction to [[Set (mathematics)|sets]], Boolean operations, [[Venn diagram]]s, [[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 numeral system|binary]] numbers in computer systems.''

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

[[Image:Venn A intersect B.svg|thumb|300px|right|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 <math>\in</math>. If the element is not a member of a set it is denoted by <math>\notin</math>.

* 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 <math>\varnothing</math> 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 (set theory)|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 (set theory)|union]] and [[intersection (set theory)|intersection]] of sets. There are also other derived binary operators, such as '''XOR''' (exclusive OR).

* A '''subset''' is denoted by <math>A \subseteq B</math> and means every element in set A is also in set B.

* A '''superset''' is denoted by <math>A \supseteq B</math> and means every element in set B is also in set A.

* The '''identity''' or '''equivalence''' of two sets is denoted by <math>A \equiv B</math> 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 <math>A \subset B</math> 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 <math>A \supset B</math> and means every element in set B is also in set A and the two sets are not identical.

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

[[Image:Boolean multiples of 2 3 5.svg|480px|right]]

===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 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)'''

==Properties==

We define symbols for the two primary binary operations as <math>\land / \cap</math> (logical AND/set intersection) and <math>\lor / \cup</math> (logical OR/set union), and for the single unary operation <math>\lnot</math> / ~ (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):

:{| cellpadding=5

|<math>a \lor (b \lor c) = (a \lor b) \lor c </math>

|<math>a \land (b \land c) = (a \land b) \land c </math>

| [[associativity]]

|-

|<math>a \lor b = b \lor a </math>

|<math>a \land b = b \land a </math>

| [[commutativity]]

|-

|<math>a \lor (a \land b) = a </math>

|<math>a \land (a \lor b) = a </math>

| [[absorption laws|absorption]]

|-

|<math>a \lor (b \land c) = (a \lor b) \land (a \lor c) </math>

|<math>a \land (b \lor c) = (a \land b) \lor (a \land c) </math>

| [[distributivity]]

|-

|<math>a \lor \lnot a = 1 </math>

|<math>a \land \lnot a = 0 </math>

| [[complemented lattice|complements]]

|-

|<math>a \lor a = a</math>

|<math>a \land a = a </math>

| [[Idempotent|idempotency]]

|-

|<math>a \lor 0 = a </math>

|<math>a \land 1 = a </math>

| rowspan=2 | [[bounded poset|boundedness]]

|-

|<math>a \lor 1 = 1 </math>

|<math>a \land 0 = 0 </math>

|-

|<math>\lnot 0 = 1 </math>

|<math>\lnot 1 = 0 </math>

| 0 and 1 are complements

|-

|<math>\lnot (a \lor b) = \lnot a \land \lnot b</math>

|<math>\lnot (a \land b) = \lnot a \lor \lnot b</math>

| [[de Morgan's laws]]

|-

|<math> \lnot \lnot a = a </math>

|

| [[Involution (mathematics)|involution]]

|}

The first three properties define a [[Lattice (order)|lattice]]; the first five define a [[Boolean algebra]].

The remaining five are a consequence of the first five.

==Other notations==

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

[[Programmer]]s will often use a pipe symbol (|) for OR, an ampersand (&) for AND, and a tilde (~) for NOT. In many [[programming language]]s, these symbols stand for [[bitwise operation]]s. "||", "&&", 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.

==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 (<math>\ge</math>) and less than or equals sign (<math>\le</math>) may be assumed to contain a logical OR:

::X < 2

::OR

::X = 2

* The plus/minus sign (<math>\pm</math>), 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.''

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

* ''I never walk in the rain '''or''' snow.''

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 berries that are red '''or''' blue". (The former might have been interpreted as a request for berries that are each both red and 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''' or logical '''XOR''':

* ''The waitress asked, "Would you like cream '''or''' sugar with your coffee?"'' (Logical '''OR'''.)

* ''The waitress asked, "Would you like soup '''or''' salad with your meal?"'' (Logical '''XOR'''.)

Logical '''XOR''' can be translated as "one, or the other, but not both". In most cases, this concept is most effectively communicated in English using "[[Either|either/or]]".

The word 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 would be, "For dinner, I'm having chicken or beef (or both)."

* The use of "and/or" is generally disfavored in [[Standard written English|formal writing]].<ref>[http://www.ntsc.navy.mil/Resources/Library/Acqguide/SpecWord.htm#and_or Usage Guide].</ref> Its usage may introduce critical imprecision in [[Legal English|legal agreements]], research findings, and [[specification]]s for [[computer program]]s or [[electronic circuit]]s.

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 should be interpreted as an '''XOR''' and a verification performed to ensure that one, and only one, box is selected. In other cases the proper 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 and parallel circuits|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:

<source lang="sql">

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

</source>

<source lang="sql">

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

</source>

<source lang="sql">

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

</source>

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

<source lang="sql">

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

</source>

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 Search|Google]].<ref>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.,[http://www.google.com/help/cheatsheet.html Syntax cheatsheet], [http://www.google.com/intl/en/help/faq_codesearch.html#regexp Google codesearch supports regular expressions]).</ref>

* Doublequotes are used to combine whitespace-separated words into a single search term.<ref>Doublequote-delimited search terms are called "exact phrase" searches in the Google documentation.</ref>

* 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"

==See also==

{{wikibooks|How to search|Boolean Logic}}

{{wikibooks|Electronics|Boolean Algebra}}

* [[Boolean algebra topics]]

* [[Boolean ___domain]]

* [[Boolean function]]

* [[Boolean-valued function]]

* ''[[Laws of Form]]''

* [[Logic minimization]]

* [[Logic gate]]

* [[Logical graph]]

* [[Venn diagram]]

* [[Ternary logic]]

==Notes and references==

{{reflist}}

==External links==

*[http://www.maths.tcd.ie/pub/HistMath/People/Boole/CalcLogic/CalcLogic.html The Calculus of Logic], by George Boole, Cambridge and Dublin Mathematical Journal Vol. III (1848), pp.&nbsp;183–98.

*[http://sourceforge.net/projects/logicaleval/ Logical Formula Evaluator] (for Windows), a software which calculates all possible values of a logical formula

* Maiki & Boaz [http://www.bdd-project.com BDD-PROJECT], a Web Application for BDD reduction and visualization.

{{Digital systems}}

[[Category:Boolean algebra]]

[[Category:Logic]]

[[Category:Articles with example code]]

[[ar:منطق بولياني]]

[[ca:Lògica binària]]

[[cs:Booleova logika]]

[[es:Lógica binaria]]

[[fr:Algèbre de Boole (logique)]]

[[hi:बूलीय बीजगणित (तर्कशास्त्र)]]

[[he:לוגיקה בוליאנית]]

[[ja:ブール論理]]

[[ru:Алгебра логики]]

[[simple:Boolean algebra]]

[[uk:Булева логіка]]

[[zh:逻辑代数]]