Digital Circuits/Logic Operations

In the previous chapter we learned what digital information is. Digital information is represented as bits, which can take on values of either 1 or 0. In this chapter we begin to explore how to perform calculations and do other work using digital information.

Much of what we will be discussing was formalized by George Boole (1815–1864) in his paper An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, published in 1854. It had few applications at the time, but eventually scientists and engineers realized that his system could be used to create efficient computer logic. The branch of mathematics involving digital logic is aptly named Boolean Algebra.

Basic Operators

edit

Digital logic has three basic operators, the AND, the OR and the NOT. These three operators form the basis for everything in digital logic. In fact, almost everything your computer does can be described in terms of these three operations. Fortunately, these operations are not difficult to understand, as their meanings resemble the meanings of the words as used in every day language.

The symbol for an AND operator is a single dot. A mathematical expression using AND looks like this.

 

Alternate notations for AND are   &&   and   The value of an AND expression is 1 only if both input values are 1. Otherwise, the value is 0. That is, the above expression equals 1 if and only if A and B are 1. The AND operator can be described with the following truth table.

     
0 0 0
0 1 0
1 0 0
1 1 1

The symbol for the OR operator is a plus sign. A mathematical expression using OR looks like this.

 

Alternate notations for OR are A B, A OR B and A || B. The value of an OR expression is 0 only if both the input values are 0. Otherwise the values is 1,that is the above expression equals only if A and B is 0. The truth table for the OR operator

     
0 0 0
0 1 1
1 0 1
1 1 1

NOT is a unary operator, which requires only single input, while as AND and OR are binary operators as they require two values as input. Symbol for NOT operator.   or A'

The value of a NOT expression is the opposite value of the input value.

   
0 1
1 0

NAND and NOR

edit

If the AND, OR and NOT operators are combined, then the NOR and NAND can be created:

  • A NAND B is  . This is the inverted output of the AND gate.
  • A NOR B is  . This is just the inverted output of an OR gate.
NAND NOR
   
X Y Q
0 0 1
0 1 1
1 0 1
1 1 0
X Y Q
0 0 1
0 1 0
1 0 0
1 1 0

XOR and XNOR

edit

Two other important gates are the exclusive-OR and exclusive -NOR operators, XOR and XNOR. This is sometimes denoted by a plus sign in a circle.

  • A XOR B is  . This is true only if exactly one of the inputs is one.
  • A XNOR B is  . This is the inverted output of an XOR gate: it is only true if both input are the same.
XOR XNOR
   
X Y Q
0 0 0
0 1 1
1 0 1
1 1 0
X Y Q
0 0 1
0 1 0
1 0 0
1 1 1

XOR represents a modulo-2 addition, which means that if you add 1 to 1, you wrap around back to 0. This is very useful function in digital electronics, but it is not an important concept in Boolean algebra.

Formal Mathematical Operators

edit

In the field of logic, which is part of discrete mathematics, there is an alternative notation to the addition/multiplication type we have seen:

  • AND is represented by   Therefore A AND B would be  .
  • OR is represented by   Therefore A OR B would be  .
  • NOT is represented by  . Therefore NOT A is  .

Unfortunately, computer science, engineering and mathematics seem unable to establish a consensus, so we are stuck with both forms of notation. Other books, and especially those that deal more with pure logic or discrete mathematics may have various notations, so if other books are consulted, then the other notation needs to be known. As this is an engineering book, we will not use this notation.

Boolean Algebra Laws

edit

Boolean Algebra, like regular algebra, has certain rules. These rules are Associativity, Distributivity, Commutativity and De Morgan's Laws. Associativity, Commutativity and Distributivity only apply to the AND and OR operators. Some of these laws may seem trivial because you are so used to them. However, when Boolean algebra was created with its different rules, every axiom we take for granted in "normal" algebra no longer was guaranteed to apply. These laws have been proved to hold under Boolean algebra.

Associativity

edit

Associativity is the property of algebra that the order of evaluation of the terms is immaterial.

 
 

Distributivity

edit

Distributivity is the property that an operator can be applied to each of the terms within the brackets.

 
 

Commutativity

edit

Commutativity is the property that order of application of an operator is immaterial.

 
 

De Morgan's Law

edit

De Morgan's Law is a consequence of the fact that the NOT or negation operator is not distributive.

 
 

De Morgan's laws (named after Augustus De Morgan, 1806–1871) tell us: a NAND gate gives the same output as an OR gate with inputs complemented; a NOR gate gives the same output as an AND gate with inputs complemented. These complemented-input gates are also known as bubbled gates because of the way that they are indicated on a symbol, i.e., by including a small 'bubble' on each input, in the same fashion that circles are drawn on the outputs of the NOT, NAND and NOR gates.

 

 

De Morgan's laws are the most useful while simplifying a boolean expression. An easy way to remember these laws is "Change the sign, break the line".

Exercise

By constructing the appropriate truth tables, verify the laws of:

  1. Associativity of the AND operator,
  2. Ditributivity of the OR operator,
  3. Commutativity of the OR operatar,
  4. De Morgan's Law for the NAND operator.
Solution
  1. We see that the truth tables for


Operator precedence

edit

It is important to note that

 

This can be seen as either AND having a higher precedence or the fact that associativity does not hold between AND and OR or that it is an invalid application of distributivity.

Another way of looking at this is the application of our understanding of normal algebra, where the analogy between OR being addition and AND being multiplication is made. We would never make this error if this were normal algebra with numbers rather than Boolean entities.

Other Rules

edit

All of these laws result in a number of rules that apply to all Boolean expressions. These laws have names, but it is only important that you are able to apply them where needed! Note that many rules have two forms - this called duality, and we will discuss it later.

Name Rule
1a Idempotency  
1b  
2a Identity  
2b  
3a Boundedness  
3b  
4a Complement Laws  
4b  
5a Absorption  
5b  
6 Involution or Double Negation  
7a Consensus Theorem  
7b  

Principle of Duality

edit

The principle of duality tells us: If, in a boolean equation, we interchange the AND and OR operators and interchange '0' with '1' then the resultant boolean equation is also true.

Example 1
If we are aware that A·(B+C)=(A·B)+(A·C) (law of distributivity of the AND operator) then by the principle of duality, we can say that A+(B·C)=(A+B)·(A+C) (law of distributivity of the OR operator).
Example 2
Consider the identity law for the OR operator: A+0=A . Applying duality, we get the identity law for the AND operator: A·1=A.

Boolean Simplification

edit

It is often the case that you want to simplify a given Boolean function. For example, you might want to reduce the number of logic gates required to implement that particular function. Simplification is done by repeated application of the rules and laws of Boolean algebra. Bear in mind that you sometimes have to apply them backwards to get the minimal form. NAND, NOR, XOR and XNOR all need to be expanded to just AND, OR and NOT in order for simplification to work.

Karnaugh Maps are a more formal way of doing this for the guaranteed smallest form, but we will do it by hand for now.

Examples

edit

Simplify the following expressions.

  1.  
  2.  

Example 1

edit
  by rule 4b.
  using rule 5 applied to the result from the previous line.

So  

Example 2

edit

Using distributivity, we can take A out of the brackets, giving

 

Using rule 4a, we see that:

 

We therefore see that  

See also

edit