Digital Circuits/Logic Operations

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

Boolean Algebra

Boolean algebra is a bit of an oddity in the math 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.

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.

AND and OR

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

To understand the difference between AND and OR, let's examine the following truth tables:

 AND                  OR 

 X   Y  RESULT        X   Y  RESULT
 0   0    0           0   0    0
 0   1    0           0   1    1
 1   0    0           1   0    1
 1   1    1           1   1    1

In the case of AND, both must be 1 for the result to be 1.

In the case of OR, at least one must be a 1 for the result to be 1.

Boolean Algebra

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. The Boolean system has two states: True (T) or False (F). This can be represented in several different ways as on or off, one or zero, yes or no, etc. These states are manipulated by three fundamental operations called logical operators: AND, OR and NOT. These operators take certain inputs and produce an output based on a predetermined table of results. For example, the AND operator takes two (or more) inputs and returns an 'on' result only when both (or all) inputs are 'on'.

• In these tables T means "True", or "Yes", or 1 (in electronics), and
• F means "False", or "No" or 0 (in electronics).
• For example, the 1st line of the AND table says that if A is F and B is F then the result also is F. This is also said often as If A is 0 and B is also 0, then A AND B = 0 times 0 = 0
• Also at the bottom of the AND table 1 times 1 is 1.
• Looking at the OR table, use plus instead of times: 0 plus 0 is 0, where again 0 is F and 1 is T. Only 0 and 1 exist, therefore if the result of the addition is more than 1, then change it to 1.
• The 3rd table shows NEGATION: whatever it is, change it to the other; 0 is changed into 1, and 1 is changed into 0.

Truth Tables

AND A B $A\wedge B$ F F F F T F T F F T T T

OR A B $A\vee B$ F F F F T T T F T T T T

NOT A $\overline{A}$ F T T F

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

if user put in a quarter AND the Coke button is pressed, drop a Coke

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. An expression like:

A and B or C

would have a truth table of the following:

A and B or C

A	B	C	X
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 rules If A and B are true, or C is true, then X is true

Exercise: Go through each case in the table and check it using the above statement.

Formal Mathematical Operators

AND is represented by $\wedge$ or $.$ that is A AND B would be $A\wedge B$ or $A.B$.

OR is represented by $\vee$ or $+$ that is A OR B would be $A\vee B$ and $A+B$.

NOT is represented by $\mathrm{\neg }$ or $\stackrel{}{¯}$ that is NOT A is $\mathrm{\neg }A$ or $\overline{A}$.

If these three operators are combined, then the NOR and NAND can be created. So A NOR B is $\mathrm{\neg }(A\vee B)$ or $\overline{A+B}$. (This last one has been rendered wrong, the bar should extend all the way over both A and B). NAND is $\mathrm{\neg }(A\wedge B)$ or $\overline{A.B}$. (The last one has once again been rendered wrong.) The reason for the double notation is because, unfortunately, computer science, engineering and mathematics seem unable to establish a consensus. The point is that this book is not the only source of information. Other books have various notations, so if other books are consulted, then the other notation needs to be known.

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 in normal Algebra but in other algebras they are not.

Associativity

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

$A\vee (B\vee C)=(A\vee B)\vee C$

$A\wedge (B\wedge C)=(A\wedge B)\wedge C$

Or

$A+(B+C)=(A+B)+C$

$A.(B.C)=(A.B).C$

Wikipedia:Associativity

Distributivity

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

$A\wedge (B\vee C)=(A\wedge B)\vee (A\wedge C)$

Or

$A.(B+C)=(A.B)+(A.C)$

Wikipedia:Distributivity

Commutativity

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

$A\wedge B=B\wedge A$

$A\vee B=B\vee A$

Or

$A.B=B.A$

$A+B=B+A$

Wikipedia:Commutativity

De Morgan's Law

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

$\mathrm{\neg }(P\wedge Q)=(\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$

$\mathrm{\neg }(P\vee Q)=(\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)$

Or

$\overline{P.Q}=\bar{P}+\bar{Q}$

$\overline{P+Q}=\bar{P}.\bar{Q}$

De Morgan's laws 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, similar to the circle drawn on the output of the Not, Nand and Nor gates.

De Morgan's laws are the most useful while simplifying a boolean expression. These laws can be verified by constructing the corresponding truth table.

Notes

It is important to note that

$A\wedge B\vee C\ne A\wedge (B\vee C)$

Or

$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 possible application of our understanding of normal algebra rules using the second notation. Where clearly the analogy between OR being addition and AND being multiplication is made. We would never make this error if this were high school algebra.

Rules

All of these Laws Result in a number of rules used for the reduction of Boolean Algebra.

1. $A\wedge A=A$
2. $A\vee A=A$
3. $A\wedge 1=A$
4. $A\vee 1=1$
5. $A\wedge 0=0$
6. $A\vee 0=A$
7. $A\wedge \mathrm{\neg }A=0$
8. $A\vee \mathrm{\neg }A=1$
9. $\mathrm{\neg }(\mathrm{\neg }A)=A$
10. $A\vee \mathrm{\neg }A\wedge B=A+B$
11. $\mathrm{\neg }A\vee A\wedge B=\mathrm{\neg }A\vee B$

Or

1. $A.A=A$
2. $A+A=A$
3. $A.1=A$
4. $A+1=1$
5. $A.0=0$
6. $A+0=A$
7. $A.\overline{A}=0$
8. $A+\overline{A}=1$
9. $\overline{\overline{A}}=A$
10. $A+\overline{A}.B=A+B$
11. $\overline{A}+A.B=\overline{A}+B$

Double Negation:

$\overline{\stackrel{‾}{A}}=A$

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.

Eg: If we are aware that A.(B+C)=A.B+A.C then:
Dual of the left side is A+B.C
Dual of the right side is (A+B).(A+C)

By the principle of duality, we can say that A+B.C=(A+B).(A+C)

Examples

Simplify the following Expressions.

1. $B\wedge A\wedge \mathrm{\neg }A$
2. $A\wedge \mathrm{\neg }B\vee A\wedge B$

Or

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

For number 1 using rule 7. We get.

$B\wedge 0=0$

Or

$B.0=0$

Which happens to be rule 5 so the answer is zero. In number 2 we can take out A. Giving

$A\wedge (\mathrm{\neg }B\vee B)$

Or

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

The Expression brackets is rule 8. So the answer is A.

What is a Truth Table?

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. Inputs can only be one of two states; either "1" (a/k/a hi, on, true) or "0" (a/k/a low, off, false). All the possible combinations of inputs for the circuit are listed, and the resulting outputs are defined at the end of each row. Outputs, just as the inputs, are only represented as either "1" or "0" (hi or lo, on or off, true or false).

Common Truth Tables

We will use the following diagram for writing out our truth tables in this section:

X ---+------+
     | Gate |-----Z
Y ---+------+

Where Y and X are the inputs to the given gate, and Z is the output of the gate. The most common logical gates are the AND, OR, XOR, NAND, and XNOR.

AND

The AND gate has the following truth table:

• Both X AND Y must be TRUE for Z to be True

OR

The OR gate has the following truth table:

• Either X OR Y must be TRUE for Z to be TRUE

XOR

The XOR Gate has the following truth table:

• Either X OR Y (Not Both) for Z to be True

NAND

The NAND gate has the following truth table:

• It is simply "NOT of AND".

NOR

The NOR gate has the followint truth table:

• It is simply "NOT of OR".

XNOR

The XNOR gate has the following truth table: