Lecture 05
Boolean Algebra
Chapter 02
Logical Statements
° A proposition that may or may not be true:
• Today is Monday
• Today is Sunday
• It is raining
° Compound Statements
° More complicated expressions can be built from
simpler ones:
• Today is Monday AND it is raining.
• Today is Sunday OR it is NOT raining
• Today is Monday AND today is NOT Monday
- (This is a contradiction)
° The expression as a whole is either true or false.
Things can get a little tricky…
° Are these two statements equivalent?
• It is not nighttime and it is Monday OR it is raining and it is
Monday.
• It is not nighttime or it is raining and Monday AND it is Monday.
Boolean Algebra
° Formal logic: In formal logic, a statement
(proposition) is a declarative sentence that is either
true(1) or false (0).
° It is easier to communicate with computers using
formal logic.
° Boolean variable: Takes only two values – either
true (1) or false (0).
They are used as basic units of formal logic.
Venn Diagrams
A B A B
A B A B
A B A B
A B A B
A
A A AB
A A B 5
Boolean Algebra
° Boolean Algebra is a mathematical technique that
provides the ability to algebraically simplify logic
expressions. These simplified expressions will
result in a logic circuit that is equivalent to the
original circuit, yet requires fewer gates.
B
C AB+A(B+C)+B(B+C)
B B+A
C
A
C
Boolean Algebra, Logic and Gates
° Logical operators operate on binary values and binary
variables.
° Basic logical operators are the logic functions AND, OR and
NOT.
° Logic gates implement logic functions.
° Boolean Algebra: a useful mathematical system for
specifying and transforming logic functions.
° We study Boolean algebra as a foundation for designing
and analyzing digital systems!
° A literal is a Boolean variable or its complement. A minterm
of the Boolean variables x1, x2, …, xn is a Boolean product
y1y2…yn, where yi = xi or yi = -xi.
° Hence, a minterm is a product of n literals, with one literal
for each variable.
Boolean Switching
° Boolean (switching) variable x ∈ {0,1}
• 0, 1 are abstract symbols
They may correspond to {false, true} in logic, {off, on} of a switch, {low
voltage, high voltage} of a CMOS circuit, or other meanings
° Boolean space {0,1}n
° The configuration space of all possible {0,1 assignments to
n Boolean variables
E.g.,
the Boolean space spanned by (x1,x2) is {0,1}2 =
{0,1}×{0,1} = {00, 01, 10, 11}
Overview
° Logic functions with 1’s and 0’s
• Building digital circuitry
° Truth tables
° Logic symbols and waveforms
° Boolean algebra
° Properties of Boolean Algebra
• Reducing functions
• Transforming functions
Binary Variables
° Recall that the two binary values have different
names:
• True/False
• On/Off
• Yes/No
• 1/0
° We use 1 and 0 to denote the two values.
° Variable identifier examples:
• A, B, y, z, or X1 for now
• RESET, START_IT, or ADD1 later
Logical Operations
° The three basic logical operations are:
• AND
• OR
• NOT
° AND is denoted by a dot (·).
° OR is denoted by a plus (+).
° NOT is denoted by an overbar ( ¯ ), a single quote
mark (') after, or (~) before the variable.
Notation Examples
° Examples:
Y • A B is read “Y is equal to A AND B.”
z •x y is read “z is equal to x OR y.”
X • A is read “X is equal to NOT A.”
Note: The statement:
1 + 1 = 2 (read “one plus one equals two”)
is not the same as
1 + 1 = 1 (read “1 or 1 equals 1”).
Operator Definitions
Operations are defined on the
values "0" and "1" for each
operator:
OR NOT
AND
0·0=0 0+0=0 01
0·1=0 0+1=1 10
1·0=0 1+0=1
1·1=1 1+1=1
Truth Tables
° Truth table a tabular listing of the values of a function
for all possible combinations of values on its arguments
° Example: Truth tables for the basic logic operations:
AND OR NOT
X Y Z = X·Y X Y Z = X+Y X ZX
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
Log
ic
Fun
° Using
ctioSwitches Switches in parallel => OR
n
• Inputs:
Imp
- logic 1 is switch closed
lem
- logic 0 is switch open
ent
• Outputs:
atio
- logic 1 is light on
n- logic 0 is light off. Switches in series => AND
• NOT input:
- logic 1 is switch open
- logic 0 is switch closed
Normally-closed switch => NOT
C
Logic Function Implementation – cont’d
° Example: Logic Using Switches
B C
A
° Light is on (L = 1) for
L(A, B, C, D) = A (B C + D) = A B C + A D
and off (L = 0), otherwise.
° Useful model for relay and CMOS gate
circuits, the foundation of current digital
logic circuits
Digital
Systems
° Analysis problem:
. Logic .
Inputs Outputs
Circuit
. .
• Determine binary outputs for each combination of inputs
° Design problem: given a task, develop a circuit
that accomplishes the task
• Many possible implementation
• Try to develop “best” circuit based on some criterion
(size, power, performance, etc.)
Toll Booth
Controller
° Consider the design of a toll booth controller
° Inputs: quarter, car sensor
° Outputs: gate lift signal, gate close signal
$.25 Logic Raise gate
Car? Circuit Close gate
° If driver pitches in quarter, raise gate.
° When car has cleared gate, close gate.
Describing Circuit Functionality:
Inverter
Truth Table
A Y
A Y 0 1
1 0
Symbol
Input Output
° Basic logic functions have symbols.
° The same functionality can be represented with truth
tables.
• Truth table completely specifies outputs for all input combinations.
° The above circuit is an inverter.
• An input of 0 is inverted to a 1.
• An input of 1 is inverted to a 0.
The
AN
D
Gat A
e Y
B
° This is an AND gate.
° So, if the two inputs signals Truth Table
are asserted (high) the A B Y
output will also be asserted. 0 0 0
Otherwise, the output will 0 1 0
be deasserted (low). 1 0 0
1 1 1
The
OR
Gat
e A
Y
B
° This is an OR gate. A B Y
° So, if either of the two 0 0 0
input signals are 0 1 1
asserted, or both of 1 0 1
them are, the output 1 1 1
will be asserted.
Describing Circuit Functionality:
Waveforms
AND Gate
A B Y
0 0 0
0 1 0
1 0 0
1 1 1
° Waveforms provide another approach for representing
functionality.
° Values are either high (logic 1) or low (logic 0).
° Can you create a truth table from the waveforms?
Consider three-input
gates
3 Input OR Gate
Distributivity of the Operators and
Complements
° The Distributive Property:
For every a, b, and c in K,
• a+(b.c)=(a+b).(a+c)
• a.(b+c)=(a.b)+(a.c)
° The Existence of the Complement:
For every a in K there exists a unique element
called a’ (complement of a) such that,
• a + a’ = 1
• a . a’ = 0
° To simplify notation, the . operator is frequently
omitted. When two elements are written next to
each other, the AND (.) operator is implied…
• a+b.c=(a+b).(a+c)
• a + bc = ( a + b )( a + c )
Dua
lity
° The principle of duality is an important concept.
This says that if an expression is valid in Boolean
algebra, the dual of that expression is also valid.
° To form the dual of an expression, replace all +
operators with . operators, all . operators with +
operators, all ones with zeros, and all zeros with
ones.
° Form the dual of the expression
a + (bc) = (a + b)(a + c)
° Following the replacement rules…
a(b + c) = ab + ac
° Take care not to alter the location of the
parentheses if they are present.
Involutio
n
° This theorem states:
a’’ = a
° Remember that aa’ = 0 and a+a’=1.
• Therefore, a’ is the complement of a and a is also the
complement of a’.
• As the complement of a’ is unique, it follows that a’’=a.
° Taking the double inverse of a value will give the
initial value.
Absorptio
n
° This theorem states:
a + ab = a a(a+b) = a
° To prove the first half of this theorem:
a + ab = a . 1 + ab
= a (1 + b)
= a (b + 1)
= a (1)
a + ab = a
DeMorgan’s Theorem
° A key theorem in simplifying Boolean algebra
expression is DeMorgan’s Theorem. It states:
(a + b)’ = a’b’ (ab)’ = a’ + b’
° Complement the expression
a(b + z(x + a’)) and simplify.
(a(b+z(x + a’)))’ = a’ + (b + z(x + a’))’
= a’ + b’(z(x + a’))’
= a’ + b’(z’ + (x + a’)’)
= a’ + b’(z’ + x’a’’)
= a’ + b’(z’ + x’a)
Boolean & DeMorgan’s Theorems
1) X 0 0 10A) XY Y X
Commutative
2) X 1 X 10B) XY Y X Law
3) XX X 11A) X YZ XY Z
Associative
4) X X 0 11B) X Y Z X Y Z Law
5) X0 X 12A) X Y Z XY XZ
Distributive
6) X 1 1 12B) X Y W Z XW XZ YW YZ Law
7) XXX 13A) X XY X Y
8) X X 1 13B) X XY X Y
Consensus
9) XX 13C) X XY X Y Theorem
13D) X XY X Y
14A) XY XY
DeMorgan’s
14B) XYX Y
DeMorgan Shortcut
BREAK THE LINE, CHANGE THE SIGN
Break the LINE over the two variables,
and change the SIGN directly under the line.
A B A B For Theorem #14A, break the line, and
change the AND function to an OR function.
Be sure to keep the lines over the variables.
A B A B For Theorem #14B, break the line, and
change the OR function to an AND function.
Be sure to keep the lines over the variables.
Summary
° Basic logic functions can be made from AND, OR,
and NOT (invert) functions
° The behavior of digital circuits can be represented
with waveforms, truth tables, or symbols
° Primitive gates can be combined to form larger
circuits
° Boolean algebra defines how binary variables can
be combined
° Rules for associativity, commutativity, and
distribution are similar to algebra
° DeMorgan’s rules are important.
• Will allow us to reduce circuit sizes.