Transcript Boolean Logic 1

Boolean Logic 1
©Paul Godin
Created September 2007
Last Edit September 2009
prgodin @Boolean
gmail.com1.1
Boolean Simplification
◊ Boolean equations are used to describe a logic
circuit’s function.
◊ Equations can become complex and require
simplification.
◊ There are laws and theorems to help simplify
complex Boolean problems.
◊ Manipulating Boolean equations follows many
of the rules of standard algebra.
Boolean 1.2
The 3 Boolean Laws
◊
◊
◊
Commutative:
◊ Addition:
◊ Multiplication:
Associative:
◊ Addition:
◊ Multiplication:
A+B=B+A
AB = BA
A + (B + C) = (A + B) + C
A(BC) = (AB)C
Distributive:
◊ A(B + C) = AB + AC
◊ (A + B)(C + D) = AC + AD + BC + BD
Boolean 1.3
The 10 Basic Rules (part 1)
1.
Anything ANDed with a 0 is equal to 0:
A●0=0
2.
Anything ANDed with a 1 is equal to itself:
A●1=A
3.
Anything ORed with a 0 is equal to itself:
A+0=A
4.
Anything ORed with a 1 is equal to 1:
A+1=1
5.
Anything ANDed with itself is equal to itself:
A●A=A
Boolean 1.4
The 10 Basic Rules
(part 2)
6.
Anything ORed with itself is equal to itself:
A+A=A
7.
Anything ANDed with its own complement equals 0:
A●A=0
8.
Anything ORed with its own complement equals 1:
A+A=1
9.
Anything complemented twice is equal to the original:
10. The two variable rules:
A=A
a) A + AB = A + B
b) A + AB = A + B
c) A + AB = A
Boolean 1.5
De Morgan’s Theorem Review
◊
De Morgan’s Theorem allows the inversion of an expression
to be broken up into inversions of individual variables.
◊
Inversion of an expression: A + B
◊
Inversion of individual variables: A ● B
“Break the bar and change the sign”
Boolean 1.6
Basic Boolean Rules Exercise 1
Determine the outcome of the following:
1.
A + 0 = ____
7.
A ● 0 = ___
2.
A + AB = ____
8.
A + A = ____
3.
A + 1 = ____
9.
A + A = ____
4.
5.
A + AB = ____
A ● A = ____
10. A + AB = ____
11. A ● 1 = ____
12. A = ____
6.
A ● A = ____
Boolean 1.7
Basic Boolean Rules Exercise 2
Determine the output of the following gates
A
0
?
1
?
A
A’
1
?
A
A
0
?
A
A’
Boolean 1.8
Boolean Simplification
◊ Boolean equations can be simplified using
algebraic methods, using the Boolean rules and
laws to reduce the equation.
Boolean 1.9
Examples of Boolean Reduction 1
◊ Consider CD(D+DF)
◊ CD(D) Rule 10a where D+DF=D
◊ CDD Associative Law
◊ CD
Rule 5 where DD=D
◊ Consider C’D’(C+D)’
◊ C’D’(C’D’)
◊ C’C’D’D’
◊ C’D’
DeMorgan where (C+D)=(CD)
Associative where brackets removed
Rule 5 where C’C’=C’ and D’D’=D’
Boolean 1.10
Examples of Boolean Reduction 2
◊
Consider (C+D)(C+D’)
◊
◊
◊
◊
◊
◊
◊
◊
CC+CD’+DC+DD’
C+CD’+CD+0
C+CD’+CD
(C+CD’)+CD
C+CD
C+C
C
Distributive
Rule 5: CC=C; Rule 7:DD’=0,
Rule 3: (A+0=A)
Associative
Rule 10c: C+CD’=C
Rule 10c: C+CD=C
Rule 6: C+C=C
Consider C’+CDE+E
◊
◊
◊
◊
(C’+CDE)+E
C’+DE+E
C’+(E+DE)
C’+E
Associative
Rule 10b: C’+CDE=C’+DE
Associative, Commutative
Rule 10c: E+DE=E
Boolean 1.11
Exercise 3
◊ Simplify the following:
◊
A’+AB’+B
◊ A+A’B+B’C+AC
◊ AB’+A’CD+B+C’+D’
Other examples may be given in class
Boolean 1.12
END
©Paul R. Godin
prgodin°@ gmail.com
Boolean 1.13