FACTOID # 24: Looking for table makers? Head to Mississippi, with an overwhlemingly large number of employees in furniture manufacturing.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Logic operation

Boolean logic is a complete system for logical operations. 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 base of digital electronics. 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. Logic, from Classical Greek λόγος logos (the word), is the study of the principles and criteria of valid inference and demonstration. ... In logic and mathematics, an operation ω is a function of the form ω : X1 × … × Xk → Y. The sets Xj are the called the domains of the operation, the set Y is called the codomain of the operation, and the fixed non-negative integer k is called the arity of the operation. ... George Boole [], (November 2, 1815 – December 8, 1864) was a British mathematician and philosopher. ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ... Alternative meaning: Nineteenth Century (periodical) (18th century — 19th century — 20th century — more centuries) As a means of recording the passage of time, the 19th century was that century which lasted from 1801-1900 in the sense of the Gregorian calendar. ... This Article does not cite its references or sources. ... Year 1938 (MCMXXXVIII) was a common year starting on Saturday (link will take you to calendar). ... Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001), an American electrical engineer and mathematician, has been called the father of information theory, and was the founder of practical digital circuit design theory. ... A BlueGene supercomputer cabinet. ...


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. The algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality (mathematics) and set inclusion. ... In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ... A Venn diagram of sets A, B, and C Venn diagrams are illustrations used in the branch of mathematics known as set theory. ... Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ... In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ... The binary or base-two numeral system is a system for representing numbers in which a radix of two is used; that is, each digit in a binary numeral may have either of two different values. ... The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ... A BlueGene supercomputer cabinet. ...

Contents

Terms

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

Let X be a set: Image File history File links Venn_A_intersect_B.svg‎ [edit] Summary [edit] Licensing File links The following pages on the English Wikipedia link to this file (pages on other projects are not listed): Mathematics ... Image File history File links Venn_A_intersect_B.svg‎ [edit] Summary [edit] Licensing File links The following pages on the English Wikipedia link to this file (pages on other projects are not listed): Mathematics ...

  • An element is one member of a set. This is denoted by . If it's not an element of the set, this is denoted by .
  • 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 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 union and intersection of sets. There are also other derived binary operators, such as XOR (exclusive OR). See the geometry of logic.
  • A subset is denoted by and means every element in set A is also in set B.
  • A proper subset is denoted by and means every element in set A is also in set B and the two sets are not equal.
  • A superset is denoted by and means every element in set B is also in set A.
  • A proper superset is denoted by and means every element in set B is also in set A and the two sets are not equal.

In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ... In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ...

Example

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". Image File history File links No higher resolution available. ...


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 (logical AND/intersection) and (logical OR/union), and for the single unary operation / ~ (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:

associativity
commutativity
absorption
distributivity
complements
idempotency
boundedness
0 and 1 are complements
de Morgan's laws
involution

The first three properties define a lattice; the first five define a Boolean algebra. In mathematics, associativity is a property that a binary operation can have. ... A map or binary operation from a set to a set is said to be commutative if, (A common example in school-math is the + function: , thus the + function is commutative) Otherwise, the operation is noncommutative. ... In algebra, the absorption law is an identity linking a pair of binary operations. ... In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalises the distributive law from elementary algebra. ... In the mathematical discipline of order theory, and in particular, in lattice theory, a complemented lattice is a bounded lattice in which each element x has a complement, defined as a unique element ~ x such that and A Boolean algebra may be defined as a complemented distributive lattice. ... In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ... In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S which is greater than or equal to any other element of S. The term least element is defined dually. ... A complementation test is used in genetics to decide if two recessive mutant phenotypes are determined by mutations in the same gene or two different genes. ... note that demorgans laws are also a big part in circut design. ... In mathematics, an involution is a function that is its own inverse, so that f(f(x)) = x for all x in the domain of f. ... The name lattice is suggested by the form of the Hasse diagram depicting it. ... In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ...


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: Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ...

0 1
0 0 0
1 0 1
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, as AND, as OR, and ¬ as NOT.

Logic, from Classical Greek λόγος logos (the word), is the study of the principles and criteria of valid inference and demonstration. ...

Other notations

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 (). Leonhard Euler is considered by many to be one of the greatest mathematicians of all time A mathematician is the person whose primary area of study and research is the field of mathematics. ... For the Technical Symposium of NITK Surathkal Engineer , see Engineer (Technical Fest). ... In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ... In a Boolean algebra, a Boolean function that is composed of standard logical operators can be expressed in a canonical form using the dual concepts of a minterms and maxterms. ...


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. A programmer or software developer is someone who programs computers, that is, one who writes computer software. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ...


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 () and less than or equals sign () may be assumed to contain a logical OR:
X < 2
OR
X = 2
  • The plus/minus sign (), 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, 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:

  • "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 either chicken or beef or both for dinner."

The use of the "and/or" virgule is generally disfavored in formal written English.[1] Such usage may introduce critical imprecision in legal instruments, research findings, and specifications for computer programs or electronic circuits. 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. A solidus, oblique or slash, /, is a punctuation mark. ... A specification is an explicit set of requirements to be satisfied by a material, product, or service. ...


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. Electrical Engineers design power systems… … and complex electronic circuits. ... This article is about the unit of information. ... Digital circuits are electric circuits based on a number of discrete voltage levels. ... International safety symbol Caution, risk of electric shock (ISO 3864), colloquially known as high voltage symbol. ...


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. A logic gate is an arrangement of electronically-controlled switches used to calculate operations in Boolean algebra. ... This article or section does not adequately cite its references or sources. ...


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: A relational database is a database based on the relational model. ... The related Category:SQL statements has been nominated for deletion, merging, or renaming. ... A SELECT statement in SQL returns a result set of records from one or more tables. ...

 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.


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. An electronic medical record (commonly abbreviated EMR) is a generic term used to describe computer-based patient medical records. ... Concept Processing is a type of technology used in some Electronic Medical Record (EMR) software applications, as an alternative to the more widespread template-based 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.[2] Google, Inc. ...

  • Doublequotes are used to combine whitespace-separated words into a single search term.[3]
  • 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 has a page on the topic of
Boolean Logic
Wikibooks Electronics has a page on the topic of
Boolean Algebra

Image File history File links Wikibooks-logo-en. ... Wikibooks logo Wikibooks, previously called Wikimedia Free Textbook Project and Wikimedia-Textbooks, is a wiki for the creation of books. ... Image File history File links Wikibooks-logo-en. ... Wikibooks logo Wikibooks, previously called Wikimedia Free Textbook Project and Wikimedia-Textbooks, is a wiki for the creation of books. ... In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ... Algebra of sets Ampheck Boole, George Boolean algebra Boolean domain Boolean function Boolean logic Boolean implicant Boolean prime ideal theorem Boolean-valued function Boolean-valued model Boolean satisfiability problem Booles syllogistic Canonical form (Boolean algebra) Characteristic function Compactness theorem Complete Boolean algebra De Morgan, Augustus De Morgans laws... A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true. ... In mathematics, a finitary boolean function is a function of the form f : Bk → B, where B = {0, 1} is a boolean domain and where k is a nonnegative integer. ... A boolean-valued function is a function of the type , where is an arbitrary set, where is a generic 2-element set, typically , and where the latter is frequently interpreted for logical applications as . ... The book Laws of Form (hereinafter abbreviated LoF), by G. Spencer-Brown, describes three distinct logical systems: The primary arithmetic (described in Chapter 4), which can be interpreted as Boolean arithmetic; The primary algebra (Chapter 6), which can be interpreted via two-element Boolean algebra (hereinafter abbreviated 2), Boolean logic... A logic gate performs a logical operation on one or more logic inputs and produces a single logic output. ... A logical graph is a special type of graph-theoretic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. ... A Venn diagram of sets A, B, and C Venn diagrams are illustrations used in the branch of mathematics known as set theory. ... A ternary, three-valued or trivalent logic is a term to describe any of several multi-valued logic systems in which there are three truth values indicating true, false and some third value. ... Zeroth-order logic is a term in popular use among practitioners for the subject matter otherwise known as boolean functions, monadic predicate logic, propositional calculus, or sentential calculus. ...

Notes and references

  1. ^ Usage Guide.
  2. ^ Not all search engines support the same query syntax. Additionally, some organizations (such as Google) provide "specialized" search engines that support alternate or extended syntax. (See e.g.,Syntax cheatsheet, Google codesearch supports regular expressions).
  3. ^ 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.
  • The Geometry of Logic
  • Logical Formula Evaluator (for Windows), a software which calculates all possible values of a logical formula
  • How Stuff Works - Boolean Logic
  • Maiki & Boaz BDD-PROJECT, a Web Application for BDD reduction and visualization.

  Results from FactBites:
 
Logical conjunction - Wikipedia, the free encyclopedia (567 words)
In mathematics, logical conjunction (usual symbol and) is a logical operator that results in true if both of the operands are true.
In logic and technical fields that use it, conjunction, or and, is a logical operator in logical calculi, and a rule of inference in deductive systems.
Logically, the sentence "it's raining, but the sun is shining" is equivalent to "it's raining, and the sun is shining", so logically, "but" is equivalent to "and".
Logical connective - Wikipedia, the free encyclopedia (574 words)
In formal logic, logical connectives, also known as logical connectors and sometimes logical constants, serve to connect statements into more complicated compound statements.
Logical operators are implemented as logic gates in digital circuits.
The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to Turing equivalence.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m