BBC Home

Explore the BBC

Front Page

Life | The Universe | Everything | Advanced Search
 
Front PageReadTalkContributeHelp!FeedbackWho is Online

Click here to complete your registration.

 
3. Everything / Maths, Science & Technology / Computers / Computer Languages and Programming
3. Everything / Maths, Science & Technology / Mathematics

Boolean Algebra

Boolean Algebra | Truth Tables | Expressions from Truth Tables | Universal Functions | Function Reduction | Functions Classified


Invented by George Boole, Boolean Algebra deals with situations where there are only two possibilities. These possibilities can be named anything as long as they are opposites. For instance, true and false, yes and no, or 0 and 11. These situations arrive frequently in digital systems such as computers, and thus Boolean Algebra has become vital to the day-to-day operations of the entire civilized world, whether those living there realise it or not. Boolean Algebra is also used by people as a decision making process, though you probably don't think of it as that.

Overview of Boolean Operations

There are several Boolean operations:

AND

The Boolean AND operator returns true if all operands are true, and false if any are false. AND is equivalent to binary multiplication.

  • 0 AND 0 = 0
  • 1 AND 0 = 0
  • 1 AND 1 = 1

OR

Boolean OR is true if any operands are true, and false only if all operands are false. OR is equivalent to binary addition, with the both true case resulting in true, instead of in false with a true carried over.

  • 0 OR 0 = 0
  • 1 OR 0 = 1
  • 1 OR 1 = 1

NOT

NOT is a unary operator, meaning it acts on a single Boolean value instead of on two. Operators which act on two values are Binary operators, which may seem confusing.

NOT changes a Boolean value to its opposite.

  • NOT 1 = 0
  • NOT 0 = 1

NOR

NOR is defined as NOT OR, and its action is just what it suggests: it returns true if the operands are both false, that is, if neither operand 1 NOR operand 2 are true, and returns false if either are true.

  • 0 NOR 0 = 1
  • 1 NOR 0 = 0
  • 1 NOR 1 = 0

Equivalent to A NOR B are NOT (A OR B) and (NOT A) AND (NOT B). These are useful in systems where an explicit NOR is not available.

NAND

NAND means NOT AND, and returns false if both operands are true, and true if any are false.

  • 0 NAND 0 = 1
  • 1 NAND 0 = 1
  • 1 NAND 1 = 0

A NAND B is the same as NOT (A AND B) and (NOT A) OR (NOT B). As with NOR, these are useful when a specific NAND is not available, but as will be discussed later, this is rarely the case.

XOR

XOR is short for Exclusive-OR, and is like a merger of AND and NOR. XOR returns true, essentially, if the two operands are different. That is, if one or the other is true, it returns true, but not if both are true. It is OR with an Exclusion; thus, Exclusive OR.

  • 0 XOR 0 = 0
  • 1 XOR 0 = 1
  • 1 XOR 1 = 0

XOR is like binary addition, with the carried bit ignored.

XNOR

XNOR means NOT XOR, and it returns true if both operands are the same, and false otherwise. (You may have guessed this from the name by now.)

  • 0 XNOR 0 = 1
  • 1 XNOR 0 = 0
  • 1 XNOR 1 = 1

Notation

Using the words for the operations is excessively verbose, so shorter notation is available. OR is +, AND is a dot, NOT is a bar over a value, NOR is the OR expression with a bar over the whole thing, NAND is the AND expression with a similar bar, and XOR and XNOR are like OR and NOR, but with the + in a small circle.

Since computer programming languages also use Boolean logic for many operations, they have their own notation. The symbols used by C and C++ are &(AND), |(OR), ~(NOT)2, and ^(XOR). Since these characters are easiest to type, they will be used here.

Boolean Tricks

NAND is the most useful operator, because any other operation can be done with some number of NANDs. While not always useful, in small circuitry, a single NAND IC can perform the functions of a number of other ICs, thus saving in cost and size. For this section only, lower case 'n' will be the operator for NAND, so it is perfectly clear where its use is.

  • NOT A = AnA
  • A AND B = ~(AnB) = (AnB)n(AnB)3
  • A OR B = (~A)n(~B) = (AnA)n(BnB)
  • A NOR B = (AnB)n(AnB)
  • A XOR B = (An(AnB))n(Bn(AnB))
  • A XNOR B = (An(AnB))n(Bn(AnB))

XOR is a useful operator because (A^B)^B = A. This can be used on long strings of bits to obscure them to anyone without the correct key. This is decidedly weak encryption, but it is a clever trick which has other applications in computer programming.


1 Technically the opposite of zero is non-zero. In single digit systems, 1 is the only non-zero value, but when multiple binary digits are taken as a single value, the whole is considered non-zero if any value is one, true, or whatever.
2 These are the symbols for bitwise operations, which act on each bit respectively, instead of on the sum of the bits. Logical operators acting on all the bits are: &&(AND), ||(OR), !(NOT), and ^^(XOR). These use 0 and non-0 as their logical values, instead of 0 and 1.
3 You only need two leads in the IC for this, since you can connect the output for the AnB operation to both inputs of another NAND gate on the chip. A similar trick can be used in any case where two identical Boolean operations are performed at about the same time.

Discuss this Entry  People have been talking about this Guide Entry. Here are the most recent Conversations:

Discrete Math
(Last Posting: Feb 3, 2004)

Neo-Boolean Mathematics
(Last Posting: Jan 23, 2002)

<No subject>
(Last Posting: Nov 27, 2000)

Nand gates
(Last Posting: Nov 16, 2000)

XOR for encryption?
(Last Posting: Nov 14, 2000)

Dirty Tricks
(Last Posting: Oct 7, 2003)

Boolean Graphics
(Last Posting: Aug 9, 2001)

note to edito: circled + for xnor
(Last Posting: Nov 27, 2000)

Web searches using Boolean Logic
(Last Posting: Nov 15, 2000)




Add your Opinion!

There are tens of thousands of h2g2 Guide Entries, written by our Researchers. If you want to be able to add your own opinions to the Guide, simply become a member as an h2g2 Researcher. Tell me More!

 
Entry Data
Entry ID: A412642 (Edited)

Written and Researched by:
Torgen

Edited by:
Menza


Date: 14   November   2000


Text only
Like this page?
Send it to a friend


Referenced Guide Entries
Boolean Truth Tables
Boolean Functions Classified
Boolean Function Reduction
Universal Functions of Boolean Algebra
Boolean Expressions from Truth Tables


Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below.
 


Front PageReadTalkContributeHelp!FeedbackWho is Online

Most of the content on h2g2 is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here. For any other comments, please start a Conversation above.


About the BBC | Help | Terms of Use | Privacy & Cookies Policy