Transcript Prepositional Logic

Fundamentals of Computer Science
Propositional Logic
(Boolean Algebra)
1
What is Propositional logic?
• Propositional logic is a mathematical model that
allows us to reason about the truth or falsehood of
logical expressions.
• Propositional logic is used in the design of
computer circuits.
• Propositional logic is made up of propositions.
• A proposition is any statement that evaluates to
one of the truth values TRUE or FALSE.
2
Propositional Variables
• A proposition variable is a variable that stands for
some proposition. For example,
p c<d
NOT p  NOT (c < d)
•  means “is equivalent to” or “has the same
Boolean value as”.
• In this class I will use the terms propositional and
Boolean interchangeably.
3
Logical Expressions
• Logical expressions are made up of
– Boolean variables
– Boolean constants
– Boolean operators
• There is no strict naming convention for Boolean
variables.
• There are only two Boolean constants, TRUE and
FALSE.
• There are many Boolean operators, the most
frequently used being NOT, AND, and OR.
4
Truth Tables
• Boolean functions are commonly displayed using
truth tables.
• The truth tables for the NOT, AND, and OR
operators are as follows.
A
0
1
NOT A
1
0
A B A AND B
0 0
0
0 1
0
1 0
0
1 1
1
A B A OR B
0 0
0
0 1
1
1 0
1
1 1
1
5
Truth Tables
• Other Boolean operators include XOR (exclusive
or), NAND (not-and), and NOR (not-or).
• NAND and NOR transistors are well represented
in circuit design due to their simplicity.
A B A XOR B
0 0
0
0 1
1
1 0
1
1 1
0
A B A NAND B
0 0
1
0 1
1
1 0
1
1 1
0
A B A NOR B
0 0
1
0 1
0
1 0
0
1 1
0
6
Transistor
Implementation
of Elementary
Logic Gates
7
Precedence of Logical Operators
• The order of precedence is..
1.
2.
3.
4.
5.
NOT (highest)
NAND
NOR
AND
OR
6.  (lowest)
8
Shorthand Notations for Boolean
Operators
•
•
•
•
•
NOT A
A NAND B
A NOR B
A AND B
A OR B
A
 AB
 A+B
 AB
 A+B
Common misconceptions:
AB  AB
A+B  A+B
9
Evaluating Complex Boolean
Expressions with Truth Tables
• Truth tables can be used to verify the equality of
inequality of two or more Boolean expressions.
• The size of a truth table grows exponentially
relative to the number of variables in the Boolean
expression.
– The number of entries (rows) in a truth table is 2n where
n represents the number of variables in the expression.
• Truth tables are one of the principle tools used in
digital circuit design.
10
Evaluating Complex Boolean
Expressions with Truth Tables
AB + CA  A(B + C)
ABC
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
AB
0
0
0
0
0
0
1
1
C
1
0
1
0
1
0
1
0
CA AB+CA
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
1
B+C A(B+C)
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
11
Boolean Identities
Boolean identities are rules used to simplify
Boolean expressions.
12
Proof of DeMorgan’s Law
X + Y = XY
13
More Useful Boolean Identities
14
Circuit Design Problem
• Design a combinational circuit that determines if
a binary value in the range of 0 to 7 (000b to
111b) is prime.
• P(A,B,C)  1 if the value ABC is prime and 0 if
ABC is not prime.
A
B
P
Circuit
C
High-level block diagram
15
Circuit Design Problem
• Steps to developing the “Prime” circuit:
1. Construct the truth table.
2. Express the value of the truth table as a Boolean
expression in sum of the min terms format.
3. Using Boolean identities, simplify the Boolean
expression.
4. Draw the circuit from the simplified Boolean
expression.
16
Circuit Design Problem
1. Draw the truth table
A, B, and C are the inputs to the
circuit; P is the output. A, B, and C
collectively represent a single three
digit unsigned binary number. A is
the most significant digit and C is
the least significant digit. If the
digit is prime the output, P, is high
(1); if the digit is not prime the
output, P, is low (0).
17
Circuit Design Problem
2. Express the value of the truth
table in sum of the min terms
format.
Notice that each term in the
expression corresponds to the
values for A, B, and C when P
is high
18
Circuit Design Problem
3. Using Boolean
identities, simplify
the Boolean
expression.
Simplest form
19
Circuit Design Problem
4. Draw the circuit from the simplified
Boolean expression.
A
B
Circuit
P
C
20
Digital Logic Gates
21
Digital Logic Gates
22
Implementation of Boolean
Functions with Gates
Both of these circuits
are logically
equivalent.
However, version (b)
saves on
performance, space,
and cost.
23
Karnaugh Maps
• Karnaugh maps (a.k.a. k-maps) provide an
alternative technique for simplifying Boolean
expressions.
• K-maps are most commonly used for Boolean
expressions containing 2, 3, or 4 variables.
• Steps to using a k-map in a digital design
1. Construct the truth table.
2. Transfer the value (output) of the truth table to an
appropriate size k-map.
3. Group the appropriate elements of the k-map.
4. Convert the groupings to the resulting simplified
Boolean expression.
24
Karnaugh Map Grouping Rules
• Each grouping must be a power of 2: 1, 2, 4, 8,
16, etc.
• Each grouping must be in the shape of a square or
a rectangle - no diagonals are allowed.
• Groupings may overlap.
• Each grouping should be as large as possible so as
to minimize the total number of groupings.
• Each grouping should have at least one element
that is not a part of another grouping.
25
Karnaugh Map Example
Using a Karnaugh map to generate a
simplified Boolean expression for the
prime number problem.
26
Three-Variable K-Map Interpretation
• Each box in the k-map corresponds to a row in the
truth table. Row 1 is m0, row 2 is m1, etc.
• The boxes do not follow a strict sequential numbering.
• The labeled brackets in illustration (b) show where the
corresponding variable has a value of 1.
27
Karnaugh Map Interpretation
• The grouping of 4 is completely inside the area of the k-map
where C  1. This gives us the term C.
• The grouping of 2 is completely inside the area of the k-map
where B  1, and completely outside the area where A  1.
This gives us the term AB.
28
Two-Variable Karnaugh Maps
• mi represents a min-term
–
–
–
–
m0 = 00
m1 = 01
m2 = 10
m3 = 11
29
Four-Variable Karnaugh Maps
30
“Don’t Care” Conditions
Occasionally there will be
combinations of inputs
that will never occur for
one reason or another. For
those combinations we
can label the outputs as
don’t-cares by putting an
‘X’ in the corresponding
output field. An ‘X’ may
be treated either as a 0 or a
1 in k-map simplification.
31
Propagation Delay for an Inverter
Gate
32