a. Introduction
In 1854, George
Boole
performed an investigation into the "laws of thought" which
were based on a simplified version of the "group" or "set"
theory, and from this Boolean
or "Switching" algebra was developed. Boolean
Algebra
deals mainly with the theory that both logic and set operations are
either "TRUE" or "FALSE" but not both at the same
time. For example, A + A = A and not 2A as it would be in normal
algebra. Boolean algebra is a simple and effective way of
representing the switching action of standard Logic Gates and the
basic logic statements which concern us here are given by the logic
gate operations of the AND, the OR and the NOT gate functions.
b. The logic AND Function
The Logic
AND Function
states that two or more events must occur together and at the same
time for an output action to occur. But the order at which they occur
is unimportant as it does not affect the final result. For example, A
& B = B & A. In Boolean algebra the Logic AND Function
follows the Commutative
Law
which allows a change in position of either variable.
The AND function is
represented in electronics by the dot or full stop symbol ( . ) Thus
a 2-input (A B) AND Gate has an output term represented by the
Boolean expression A.B
or just AB.
Switch Representation of the AND Function
|
|
Here the two
switches A and B are connected in series and both Switch A AND
Switch B must be closed (Logic "1") in order to put the
light on. Then this type of logic gate only produces and output when
"ALL" of its inputs are present and in Boolean Algebra
terms the output will be TRUE only when all of its inputs are TRUE.
In electrical terms, the logic AND function is equal to a series
circuit.
As there are only two Switches, each
with two possible states "open" or "closed",
there are then 4 different ways or combinations of arranging the two
switches as shown.
Truth
Table
|
Switch
A
|
||||||||||||||||||||||||
 |
||||||||||||||||||||||||
|
|
||||||||||||||||||||||||
AND Gates are available as standard
i.c. packages such as the common TTL 74LS08 Quadruple 2-input
Positive AND Gates, (or the 4081 CMOS equivalent) the TTL 74LS11
Triple 3-input Positive AND Gates or the 74LS21 Dual 4-input Positive
AND Gates. AND Gates can also be "cascaded" together to
produce circuits with more than just 4 inputs.
c. The Logic NOT Function
The Logic
NOT Function
is simply a single input inverter that changes the input of a logic
level "1" to an output of logic level "0" and
vice versa. The logic NOT function is so called because its output
state is NOT
the same as its input state. It is generally denoted by a bar or
overline ( ¯ ) over its input symbol which denotes the inversion
operation. As NOT gates perform the logic INVERT
or COMPLEMENTATION
function they are more commonly known as Inverters because they
invert the signal. In logic circuits this negation can be represented
by a normally closed switch.
Switch Representation of the NOT Function
 |
If A means that the
switch is closed, then NOT A or simply A says that the switch is NOT
closed or in other words, it is open. The logic NOT function has a
single input and a single output as shown.
Truth Table
 |
||||||||
|
|
||||||||
|
|
The inversion
indicator for a logic NOT function is a "bubble", ( O )
symbol on the output (or input) of the logic elements symbol. In
Boolean algebra the Logic NOT Function follows the Complementation
Law
producing inversion.
NOT gates or Inverters can be used
with standard AND and OR gates to produce NAND and NOR gates.
Inverters can also be used to produce "Complementary"
signals in more complex decoder/logic circuits for example, the
complement of logic A is A and a double inversion will give the
original value of A.
When designing logic circuits and you need only one or two inverters,
but do not have the space or the money for a dedicated Inverter chip
such as the 74LS04, you can easily make inverter functions using any
spare NAND or NOR gates by simply connecting their inputs together as
shown below.
|
|
 |
d. The Logic OR Function
The Logic
OR Function
states that an output action will occur or become TRUE if either one
"OR" more events are TRUE, but the order at which they
occur is unimportant as it does not affect the final result. For
example, A + B = B + A. In Boolean algebra the Logic OR Function
follows the Commutative
Law
the same as for the logic AND function, allowing a change in position
of either variable.
The OR function is
sometimes called by its full name of "Inclusive OR" in
contrast to the Exclusive-OR
function we will look at later in tutorial six.
The logic or
Boolean expression given for a logic OR gate is that for Logical
Addition
which is denoted by a plus sign, (+). Thus a 2-input (A B) Logic
OR Gate
has an output term represented by the Boolean expression
of: A+B = Q.
Switch Representation of the OR Function
 |
Here the two
switches A and B are connected in parallel and either Switch A OR
Switch B can be closed in order to put the light on. Then this type
of logic gate only produces and output when "ANY" of its
inputs are present and in Boolean Algebra terms the output will be
TRUE when any of its inputs are TRUE. In electrical terms, the logic
OR function is equal to a parallel circuit.
Again as with the AND function there
are two switches, each with two possible positions open or closed so
therefore there will be 4 different ways of arranging the switches.
Truth
Table
|
Switch
A
|
||||||||||||||||||||||||
 |
||||||||||||||||||||||||
|
|
||||||||||||||||||||||||
OR Gates are available as standard
i.c. packages such as the common TTL 74LS32 Quadruple 2-input
Positive OR Gates. As with the previous AND Gate, OR can also be
"cascaded" together to produce circuits with more inputs
such as in security alarm systems (Zone A or Zone B or Zone C,etc).
e. The NAND Function
The NAND or Not AND function is a
combination of the two separate logical functions, the AND function
and the NOT function connected together in series. The logic NAND
function can be expressed by the Boolean expression of, A.B
The Logic
NAND Function
only produces and output when "ANY" of its inputs are not
present and in Boolean Algebra terms the output will be TRUE only
when any of its inputs are FALSE.
Switch
Representation of the NAND Function
|
|
The truth table for the NAND function
is the opposite of that for the previous AND function because the
NAND function performs the reverse function of the AND gate. Then the
NAND gate is the complement of the AND gate.
Truth Table
|
Switch
A
|
Switch
B
|
Output
|
Description
|
|
0
|
0
|
1
|
A
and B are both open, lamp ON
|
|
0
|
1
|
1
|
A
is open and B is closed, lamp ON
|
|
1
|
0
|
1
|
A
is closed and B is open, lamp ON
|
|
1
|
1
|
0
|
A
is closed and B is closed, lamp OFF
|
|
Boolean
Expression (A NAND B)
|
_____
A
. B
|
||
The NAND Function is sometimes known as the Sheffer Stroke Function and is denoted by a vertical bar or upwards arrow operator, for example, A NAND B = A|B or A↑B.
NAND Gates are used as the basic
"building blocks" to construct other logic gate functions
and are available in standard i.c. packages such as the very common
TTL 74LS00 Quadruple 2-input NAND Gates, the TTL 74LS10 Triple
3-input NAND Gates or the 74LS20 Dual 4-input NAND Gates. There is
even a single chip 74LS30 8-input NAND Gate.
f. The NOR Function
Like the NAND Gate above, the NOR or
Not OR Gate is also a combination of two separate functions, the OR
function and the NOT function connected together in series and is
expressed by the Boolean expression as, A + B
The Logic
NOR Function
only produces and output when "ALL" of its inputs are not
present and in Boolean Algebra terms the output will be TRUE only
when all of its inputs are FALSE.
Switch Representation of the NOR Function
|
|
The truth table for the NOR function
is the opposite of that for the previous OR function because the NOR
function performs the reverse function of the OR gate. Then the NOR
gate is the complement of the OR gate.
Truth Table
|
Switch
A
|
Switch
B
|
Output
|
Description
|
|
0
|
0
|
1
|
Both
A and B are open, lamp ON
|
|
0
|
1
|
0
|
A
is open and B is closed, lamp OFF
|
|
1
|
0
|
0
|
A
is closed and B is open, lamp OFF
|
|
1
|
1
|
0
|
A
is closed and B is closed, lamp OFF
|
|
Boolean
Expression (A NOR B)
|
______
A
+ B
|
||
The NOR Function is sometimes known as the Pierce Function and is denoted by a downwards arrow operator as shown, A NOR B = A↓B.
NOR Gates are available as standard
i.c. packages such as the TTL 74LS02 Quadruple 2-input NOR Gate, the
TTL 74LS27 Triple 3-input NOR Gate or the 74LS260 Dual 5-input NOR
Gate.
g. The Laws of Boolean
As well as the
logic symbols "0" and "1" being used to represent
a digital input or output, we can also use them as constants for a
permanently "Open" or "Closed" circuit or contact
respectively. Laws or rules for Boolean Algebra expressions have been
invented to help reduce the number of logic gates needed to perform a
particular logic operation resulting in a list of functions or
theorems known commonly as the Laws
of Boolean.
Boolean Algebra
uses these "Laws of Boolean" to both reduce and simplify a
Boolean expression in an attempt to reduce the number of logic gates
required. Boolean Algebra is therefore a system of mathematics based
on logic that has its own set of rules which are used to define and
reduce Boolean expressions. The variables used in Boolean Algebra
only have one of two possible values, a "0" and a "1"
but an expression can have an infinite number of variables all
labeled individually to represent inputs to the expression, For
example, variables A, B, C etc, giving us a logical expression of A +
B = C, but each variable can ONLY be a 0 or a 1.
Examples of these individual Boolean
laws, rules and theorems for Boolean Algebra are given in the
following table.
Truth Tables for the Laws of Boolean
|
Boolean
Expression |
Description
|
Equivalent
Switching Circuit |
Boolean
Algebra
Law or Rule |
|
A
+ 1 = 1
|
A
in parallel with closed = CLOSED
|
 |
Annulment
|
|
A
+ 0 = A
|
A
in parallel with open = A
|
 |
Identity
|
|
A
. 1 = A
|
A
in series with closed = A
|
 |
Identity
|
|
A
. 0 = 0
|
A
in series with open = OPEN
|
 |
Annulment
|
|
A
+ A = A
|
A
in parallel with A = A
|
 |
Indempotent
|
|
A
. A = A
|
A
in series with A = A
|
 |
Indempotent
|
|
NOT Ā
= A
|
NOT
NOT A (double negative) = A
|
|
Double
Negation
|
|
A
+ Ā = 1
|
A
in parallel with not A = CLOSED
|
 |
Complement
|
|
A
. Ā = 0
|
A
in series with not A = OPEN
|
 |
Complement
|
|
A+B
= B+A
|
A
in parallel with B = B in parallel with A
|
 |
Commutative
|
|
A.B
= B.A
|
A
in series with B = B in series with A
|
 |
Commutative
|
|
____ _
A+B = Ā.B
|
invert
and replace OR with AND
|
|
de
Morgan's Theorem
|
|
___ _
A.B = Ā
+B
|
invert
and replace AND with OR
|
|
de
Morgan's Theorem
|
The basic Laws of Boolean Algebra that relate to the Commutative Law allowing a change in position for addition and multiplication, the Associative Law allowing the removal of brackets for addition and multiplication, as well as the distributive Law allowing the factoring of an expression, are the same as in ordinary algebra. Each of the laws above are given with just a single or two variables, but the number of variables defined by a single law is not limited to this as there can be an infinite number of variables as inputs to the expression. The above laws can be used to prove any given Boolean expression and for simplifying complicated digital circuits. A brief description of the Laws of Boolean is given below.
h. Description of the Laws and Theorems
-
Annulment Law - A term AND´ed with a "0" equals 0 or OR´ed with a "1" will equal 1.
- A . 0 = 0, A variable AND'ed with 0 is always equal to 0.
- A + 1 = 1, A variable OR'ed with 1 is always equal to 1.
-
Identity Law - A term OR´ed with a "0" or AND´ed with a "1" will always equal that term.
- A + 0 = A, A variable OR'ed with 0 is always equal to the variable.
- A . 1 = A, A variable AND'ed with 1 is always equal to the variable.
- Indempotent Law - An input AND´ed with itself or OR´ed with itself is equal to that input.
- A + A = A, A variable OR'ed with itself is always equal to the variable.
- A . A = A, A variable AND'ed with itself is always equal to the variable.
- Complement Law - A term AND´ed with its complement equals "0" and a term OR´ed with its complement equals "1".
- A . Ā = 0, A variable AND'ed with its complement is always equal to 0.
- A + Ā = 1, A variable OR'ed with its complement is always equal to 1.
-
Commutative Law - The order of application of two separate terms is not important.
- A . B = B . A, The order in which two variables are AND'ed makes no difference.
- A + B = B + A, The order in which two variables are OR'ed makes no difference.
- Double Negation Law - A term that is inverted twice is equal to the original term
- _
- Ā = A, A double complement of a variable is always equal to the variable.
- de Morgan´s Theorem - There are two "de Morgan´s" rules or theorems,
- (1) Two separate terms NOR´ed together is the same as the two terms inverted
- (Complement) and AND´ed for example, A+B = Ā. B.
- (2) Two separate terms NAND´ed together is the same as the two terms inverted
- (Complement) and OR´ed for example, A.B = Ā +B.
Other algebraic laws not detailed
above include:
-
Distributive Law - This law permits the multiplying or factoring out of an expression.
- Absorptive Law - This law enables a reduction in a complicated expression to a simpler one by absorbing like terms.
-
Associative Law - This law allows the removal of brackets from an expression and regrouping of the variables.
Boolean Algebra Functions
Using the information above, simple
2-input AND, OR and NOT Gates can be represented by 16 possible
functions as shown in the following table.
|
Function
|
Description
|
Expression
|
|
1.
|
NULL
|
0
|
|
2.
|
IDENTITY
|
1
|
|
3.
|
Input
A
|
A
|
|
4.
|
Input
B
|
B
|
|
5.
|
NOT
A
|
_
A
|
|
6.
|
NOT
B
|
_
B
|
|
7.
|
A
AND B (AND)
|
A
. B
|
|
8.
|
A
AND NOT B
|
_
A
. B
|
|
9.
|
NOT
A AND B
|
Ā
. B
|
|
10.
|
NOT
A AND NOT B (NAND)
|
_____
A
. B
|
|
11.
|
A
OR B (OR)
|
A
+ B
|
|
12.
|
A
OR NOT B
|
_
A
+ B
|
|
13.
|
NOT
A OR B
|
Ā
+ B
|
|
14.
|
NOT
OR (NOR)
|
_____
A
+ B
|
|
15.
|
Exclusive-OR
|
A.B ⊕ A.B
|
|
16.
|
Exclusive-NOR
|
________
A.B ⊕ A.B
|
Example
No1
Using the above laws, simplify the
following expression: (A + B)(A + C)
|
Q =
|
(A + B)(A + C)
|
|
|
|
AA + AC + AB +
BC
|
- Distributive
law
|
|
|
A + AC + AB +
BC
|
- Identity AND
law (A.A = A)
|
|
|
A(1 + C) + AB +
BC
|
- Distributive
law
|
|
|
A.1 + AB + BC
|
- Identity OR
law (1 + C = 1)
|
|
|
A(1 + B) + BC
|
- Distributive
law
|
|
|
A.1 + BC
|
- Identity OR
law (1 + B = 1)
|
|
Q =
|
A + BC
|
- Identity AND
law (A.1 = A)
|
Then the expression: (A +
B)(A + C) can be simplified to A + BC
Next Topic will be introduction to signals
No comments:
Post a Comment