Digital Circuits/Logic Operations

From Wikibooks, the open-content textbooks collection

Digital Circuits

In this page we are going to briefly discuss some of the background information necessary before studying Digital Circuits.

Boolean Algebra was created 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.

[edit] Boolean Algebra

Boolean algebra is a bit of an oddity in the mathematical world. Boolean algebra uses, as its fundamental values, the states of "true" and "false". To facilitate mathematics, we will turn "true" values into the number 1, and we will turn "false" values into the number 0. Then, we will go over some of the basic rules of boolean algebra:

Addition

1 + 1 = 1
1 + 0 = 1
0 + 0 = 0

There are only 2 values in boolean algebra, so there is no place to store the carry from an addition operation. The strangest part of boolean algebra is that 1 + 1 = 1. It's strange, but it's important.

Multiplication

1 × 1 = 1
1 × 0 = 0
0 × 0 = 0

These results seem pretty normal.

[edit] Inversion

Inversion, or a NOT operation changes a 1 to a 0, and changes 0 to 1. Mathematically, we will use the symbol "!" (exclamation point) to denote the logical inversion of a quantity or a variable. For instance:

!1 = 0
!0 = 1

Since you are using base 2 and since there are only two states then it stands to reason that if it's NOT "one" then it is "zero" and if it's NOT "zero" then it is "one"

If we want to talk about a variable that is always inverted, we will use the following notation:

$\overline{X} = !X$

Where the bar over top of the X denotes the fact that this value is always the opposite of the value.

[edit] Truth Tables

A truth table is a method to show how the output of a digital circuit reacts to the inputs. Along the top row of the truth table the state of each input for a given scenario is identified beginning at the left, with the last column on the right representing the corresponding output. All the possible combinations of inputs for the circuit are listed, and the resulting outputs are defined at the end of each row.

For example the truth table for the expression "Q is true only if A and B are the same" is given below:

A	B	Q
0	0	1
0	1	0
1	0	0
1	1	1

[edit] AND and OR

In terms of maths, AND gates are implemented by Boolean multiplication. OR gates are implemented by Boolean addition. Remember, in Boolean algebra, there are no carrys in addition.

To understand the difference between AND and OR, let's examine the truth tables below. As an aside, the result of a digital operation is usually named "Q". One explanation for this is that it used to be called "O", for "output", but was marked with a stroke to avoid confustion with zero, giving a symbol much like a "Q".

AND

OR

NOT

$Q=X \cdot Y$

Q = X + Y

$Q=\overline{X}$

X	Y	Q
0	0	0
0	1	0
1	0	0
1	1	1

X	Y	Q
0	0	0
0	1	1
1	0	1
1	1	1

X		Q
0		1
1		0

In the case of AND, both X and Y must be 1 for the result to be 1. In the case of OR, either X or Y or both must be a 1 for the result to be 1.

These simple operators are good because they allow us to create very simple logic circuits:

If user put in the correct money AND the Coke button is pressed, drop a can of Coke.

We can turn this into a Boolean expression:

COKE = MONEY and BUTTON

There are ways, however, to combine these expressions to make much more complex but useful digital circuits. By using multiple operators on the same inputs, it is possible to create much more complex outputs. Consider the following case:

To pass a test of three yes/no questions, Quentin needs to get 4 marks or more.
Question A is worth 2 marks, question B is worth 3 and question C is worth 5.

Quentin can pass his test by answering Question C correctly, or by answering Question A and Question B correctly. He can also answer all the questions and pass. We can formulate the following logical expression:

Q = (A and B) or C

Notice how parentheses have been used to group the variables. This is done if there is risk of confusing the order of operation. In fact, AND has a higher precedence than OR, and NOT is higher than both. Thus Q = A and B or C is also valid to write, even if it is less clear at forst glance. If you write the operators as Boolean alegebra, this becomes less of a problem: Q = AB + C is quite clearly grouped.

Quentin's passing of his test can be shown in a truth table:

A	B	C	Q
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

This truth table follows the rule: "If A and B are true, or C is true, then Q is true"

(Index of exercises)

Exercise

Instructions: Show this truth table has this value by constructing appropriate intermediate tables.

Remember, Q = A·B+C.

Solution

A	B	C	A·B	A·B+C
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1

This is the same truth table as we found above.

[edit] NAND and NOR

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

A NAND B is $\overline{A \cdot B}$ . This is the inverted output of the AND gate.
A NOR B is $\overline{A+B}$ . This is just the inverted output of an OR gate.

NAND

NOR

$Q=\overline{X \cdot Y}$

$Q=\overline{X + Y}$

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

[edit] XOR and XNOR

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

A XOR B is $\overline{A} \cdot B + A \overline{B} = A \oplus B$ . This is true only if exactly one of the inputs is one.
A XNOR B is $\overline{\overline{A} \cdot B + A \overline{B}} = \overline{A \oplus B}$ . This is the inverted output of an XOR gate: it is only true if both input are the same.

XOR

XNOR

$Q={X \oplus Y}$

$Q=\overline{X \oplus Y}$

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.

[edit] Formal Mathematical Operators

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 $\wedge$ Therefore A AND B would be $A \wedge B$ .
OR is represented by $\vee$ Therefore A OR B would be $A \vee B$ .
NOT is represented by $\lnot$ . Therefore NOT A is $\neg A$ .

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.

[edit] Boolean Algebra Laws

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 it's 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.

[edit] Associativity

Wikipedia has related information at
Associativity

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

$A+(B+C) \iff (A+B)+C \,$

$A \cdot(B \cdot C) \iff (A\cdot B) \cdot C \,$

[edit] Distributivity

Wikipedia has related information at
Distributivity

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

$A \cdot (B+C) \iff (A \cdot B)+(A \cdot C) \,$

$A+(B \cdot C ) \iff (A+B) \cdot (A + C) \,$

[edit] Commutativity

Wikipedia has related information at
Commutativity

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

$A \cdot B \iff B \cdot A \,$

$A+B \iff B+A \,$

[edit] De Morgan's Law

Wikipedia has related information at
De Morgan's Law

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

$\overline{P \cdot Q} \iff \overline {P}+ \overline {Q}$

$\overline{P+Q} \iff \overline {P} \cdot \overline {Q}$

De Morgan's laws (named after Augustus De Morgan, 1806–1871) tell us that a NAND gate gives the same output as an OR gate with inputs complemented and a NOR gate gives the same output as an AND gate with outputs 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".

(Index of exercises)

Exercise

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

Associativity of the AND operator,
Ditributivity of the OR operator,
Commutativity of the OR operatar,
De Morgan's Law for the NAND operator.

Solution

We see that the truth tables for

[edit] Operator precedence

It is important to note that

$A.B+C \ne A.(B+C)$

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.

[edit] Other Rules

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	$A \cdot A=A \,$
1b	Idempotency	$A+A=A \,$
2a	Identity	$A+0=A \,$
2b	Identity	$A \cdot 1 = A \,$
3a	Boundedness	$A+1=1 \,$
3b	Boundedness	$A \cdot 0 = 0 \,$
4a	Complement Laws	$A+\overline{A}=1 \,$
4b	Complement Laws	$A \cdot \overline{A} = 0 \,$
5a	Absorption	$A+A \cdot B = A \,$
5b	Absorption	$A \cdot A + B = A \,$
6	Involution or Double Negation	$\overline{\overline{\,A}}=A$

[edit] Principle of Duality

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 AND operator: A+0=A . Applying duality, we get the identity law for the OR operator: A·1=A.

[edit] Boolean Simplifcation

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.

[edit] Examples

Simplify the following expressions.

$B.A. \overline {A}$
$A. \overline {B} + A.B$

[edit] Example 1

Using rule 4b, we get:

$B \cdot 0 \,$

This is directly rule 5, so $B.A. \bar {A} = 0$

[edit] Example 2

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

$A \cdot (\overline{B} + B)$

Using rule 4a, we see that:

$A \cdot 1 = A$

We therefore see that $A. \overline {B} + A.B = A$

[edit] See also

Wikipedia: Boolean logic