Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: BOOLEAN ALGEBRA notes
Description: Providing complete details about the Boolean algebra with good vocabulary and solutions,examples.
Description: Providing complete details about the Boolean algebra with good vocabulary and solutions,examples.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
COE 202: Digital Logic Design
Combinational Logic
Part 1
Dr
...
• What is inside the gate is not of concern to the
system/computer designer (Only its function)
• Binary logic (Boolean Algebra ) is a mathematical system
to analyze and design digital circuits
– George Boole (introduced mathematical theory
of logic in1854)
Ahmad Almulhem, KFUPM 2009
Boolean Algebra
Regular Algebra
Boolean Algebra
Values
Numbers
Integers
Real numbers
Complex Numbers
1 (True, High)
0 (False, Low)
Operators
+, -, x, /, … etc
AND (
...
Ahmad Almulhem, KFUPM 2009
Logical Operations
Three basic logical operations can be applied to binary
variables:
AND: Z = X
...
Y
0
0
0
0
1
0
1
0
0
1
1
1
Ahmad Almulhem, KFUPM 2009
Similar to
multiplication
AND Gate
The electronic device that performs the AND operation is
called the AND gate
X
Z
Y
An AND gate with two input variables X, Y and one output Z
Note: The output of the AND gate Z is a 1 if and only if all
the inputs are 1 else it is 0
Ahmad Almulhem, KFUPM 2009
3-input AND gate
Truth Table for a 3 input AND gate
W
X
Z
Y
Note: For an n-input logic gate,
the size of the truth table is 2n
W
X
Y
Z
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
Ahmad Almulhem, KFUPM 2009
OR Operation
The truth table for the OR logical operation
OR
X
Y
Z = X +Y
0
0
0
0
1
1
1
0
1
1
1
1
Ahmad Almulhem, KFUPM 2009
Similar to
addition
OR Gate
The electronic device that performs the AND operation is
called the AND gate
X
Y
Z
An OR gate with two input variables X, Y and one output Z
Note: The output of the OR gate Z is a 1 if either of the two
inputs X, Y are 1
Ahmad Almulhem, KFUPM 2009
OR Gate – 3 Input
Truth Table for a 3 input OR gate
W
X
Z
Y
Note: For an n-input logic gate,
the size of the truth table is 2n
W
X
Y
Z=W+X+Y
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
Ahmad Almulhem, KFUPM 2009
NOT Operation
•NOT is a unary operator, meaning there can only be 1 input
•The NOT operation can be represented as follows: Z= X’ or
Z=X
•X is also referred to as the complement of Z
...
Boolean expressions are fully defined by their truth tables
A Boolean expression can be represented using interconnected logic
gates
– Literals correspond to the input signals to the gates
– Constants (1 or 0) can also be input signals
– Operators of the expression are converted to logic gates
Example: a’bd + bcd + ac’ + a’d’ (4 variables, 10 literals, ?? gates)
Ahmad Almulhem, KFUPM 2009
Operator Precedence
•
•
Given a Boolean expression, the order of operations
depends on the precedence rules given by:
1
...
NOT
3
...
OR
Lowest Priority
Example: XY + WZ will be evaluated as:
1
...
WZ
3
...
( Y’ + Z)
This function has three inputs X, Y, Z and the output is
given by F
As can be seen, the gates needed to construct this circuit
are: 2 input AND, 2 input OR and NOT
Y’
Y
X
Z
Ahmad Almulhem, KFUPM 2009
F
Example (Cont
...
( Y’ + Z)
X
Y
Z
Y’
Y’ + Z
F=X
...
1 = X
1 with 0
X+0=X
X
...
X = X
+ with
...
X = 0
...
+X n = X1
...
Xn
X1 X2 …
...
+Xn
Ahmad Almulhem, KFUPM 2009
Why Boolean Algebra?
• Boolean algebra identities and properties help reduce the
size of expressions
• In effect, smaller sized expressions will required fewer
logic gates for building the circuit
• As a result, less cost will be incurred for building simpler
circuits
• The speed of simpler circuits is also high
Ahmad Almulhem, KFUPM 2009
Algebraic Manipulation
Ability to use the Boolean identities and properties to reduce
complex equations
Example 1: Prove that X + XY = X
X + XY = X
...
1 = X
(using the distributive property, and the identities (X +
1=X, X
...
(X+Y) = 1
...
1 + XZ
(id 7)
= X’Y + XZ
(id 2)
Ahmad Almulhem, KFUPM 2009
Examples
Show that XY + X’Z + YZ = XY + X’Z
XY+X’Z+YZ = XY+X’Z+YZ
...
1 + X’Z
...
B
...
(A’+B’)
...
(B’+C’)
= (A’
...
A’ + A’
...
B’)
...
(B’+C’)
= (A’B + 0)
...
(B’+C’)
= (A’BA’ + A’BB’) (A+C’)
...
(B’+C’)
= (A’BA+A’BC’)(B’+C’)
= (0+A’BC’)(B’+C’)
= (A’BC’B’ + A’BC’C’)
= (0 + A’BC’) = A’BC’
Ahmad Almulhem, KFUPM 2009
Examples
Simplify G = ((A+B+C)
...
(C+D)))
...
ACD + (AB
...
ACD
= (ACD+ABCD) + (ABCD+ABCD)
= (ACD +ACD(B+B) + ABCD)
= (ACD + ACD + ABCD)
= (ACD + ABCD)
= (ACD(1+B))
= ACD
Ahmad Almulhem, KFUPM 2009
Complement of a Function
Truth table
The complement of a function F,
F is obtained in two ways:
A B
F F’
1
...
Boolean Expression:
Apply DeMorgan’s
Theorem (Be Careful,
before begin, surround
all AND terms with
parentheses (easy to
make a mistake!))
...
(A’+B)
= AB + A’B’
Short cut: Take the dual and
complement the literals
Title: BOOLEAN ALGEBRA notes
Description: Providing complete details about the Boolean algebra with good vocabulary and solutions,examples.
Description: Providing complete details about the Boolean algebra with good vocabulary and solutions,examples.