Algebra de Boole y Simplificacion
Algebra de Boole y Simplificacion
Algebra de Boole y Simplificacion
Funciones bsicas
Boolean functions : NOT, AND, OR,
exclusive OR(XOR) : odd function exclusive NOR(XNOR) : even function(equivalence)
Funciones bsicas
AND
Z=X Y or Z=XY Z=1 if and only if X=1 and Y=1, otherwise Z=0
OR
Z=X + Y Z=1 if X=1 or if Y=1, or both X=1and Y=1. Z=0 if and only if X=0 and Y=0
NOT
Z=X or Z=1 if X=0, Z=0 if X=1
Funciones bsicas
Operaciones booleanas
Boolean Addition
Logical OR operation
Ex 4-1) Determine the values of A, B, C, and D that make the sum term A+B+C+D Sol) all literals must be 0 for the sum term to be 0 A+B+C+D=0+1+0+1=0 A=0, B=1, C=0, and D=1
Boolean Multiplication
Logical AND operation
Ex 4-2) Determine the values of A, B, C, and D for ABCD=1 Sol) all literals must be 1 for the product term to be 1
Identidades bsicas
AB=BA
Teorema de DeMorgan
Teorema de
(A B) = A + B and (A + B) = A B
Teorema de DeMorgan
2-input Karnaugh Map This has 4 entries on the Truth Table and so the Karnaugh Map has 4 squares A 0 0 1 1 B 0 1 0 1 Y 0 B A 0 1 Y
The top left square is where A = 0 and where B = 0 and so the value of Y for A = 0 and B = 0 would be placed in here. Each entry in the Truth Table has one square in the Karnaugh Map.
(*) Fuente: Logic Equation Simplification. University of Wales, Newport
STEP ONE of the simplification process would be to fill in the Karnaugh Map (Note: we normally only transfer 1s onto the map.)
STEP TWO is to group the 1s. Groups are formed using the following rules: 1. Group sizes must be powers of 2 1, 2, 4, 8, 16, etc no other size groups are allowed. 2. Groups must be square of rectangles (1 x 4 or 2 x 2 etc) 3. Groups must be as large as possible (never group 2 groups of 2 if a group of 4 can be made.) 4. All 1s must be grouped. 5. A 1 may be grouped more than once. 6. Do not include redundant groups a redundant group is a group that contains 1s which have all been previously grouped.
(*) Fuente: Logic Equation Simplification. University of Wales, Newport
STEP THREE identifies the expression for each group. The groups are examined one at a time. For a group the following question is asked for each input one at a time: For the group: Is the input logic state for every square in the group: Always 1 if it is then the input appears in the expression Always 0 - if it is then the not input appears in the expression Both 1 and 0 - if it is then the input does not appears in the expression After each input has been checked, the expression is the AND of the inputs states identified.
(*) Fuente: Logic Equation Simplification. University of Wales, Newport
STEP FOUR identifies the complete expression for the function. The individual group expressions are OR-ed together to give the simplified expression.
Y A B A B A B
The Truth Table and Karnaugh Map are shown below: A B Y B A 0 1 Y
Example
0 0 1 1
0 1 0 1
0
1
A 0
0 1
B 0
1 0
Y 1
0 1
B A 0 0
1
A 0
0 1
B 0
1 0
Y 1
0 1
B A 0 0
1 1
1
1 1
STEP 1
A 0
0 1 1
B 0
1 0 1
Y 1
0 1 1
B A 0
1
0
1
1
1 1
STEP 2
A 0
0 1 1
B 0
1 0 1
Y 1
0 1 1
B A 0
1
0
1
1
1 1
STEP 3
A 0
0 1 1
B 0
1 0 1
Y 1
0 1 1
B A 0
1
0
1
1
1 1
Y A B
3-input Karnaugh Map This has 8 entries on the Truth Table and so the Karnaugh Map has 8 squares A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Y 0 1 A 0 C B 0 0 1 1 1 1 0
Note there is one additional rule for grouping 1s on this map and larger maps:
Rule: 1s may be grouped between the left hand column and the right hand column.
Example A function F has the truth table shown below. Determine the simplest Boolean Expression for the function.
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 0 0 1 1 1 1 1
C B 0
1
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
F 1 0 0 1 1 1 1 1
A 0 C B 0
0 1
1 1 1 1 1
1 0
F 1
1
0
1
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
F 1 0 0 1 1 1 1 1
A 0 C B 0
0 1
1 1 1 1 1
1 0
F 1
1
0
1
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
0 1
1 1 1 1 1
1 0
F 1
1
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
F 1 0 0 1 1 1 1 1
A 0 C B 0
0 1
1 1 1 1 1
1 0
F 1
1
0
1
Complete expression
F A BC BC
Example Three judges A, B and C vote: 1 guilty and 0 not guilty. Design a logic circuit using NAND only which will allow a majority decision (F) to be found. e.g. A = 1, B = 0, C = 0 gives an output of 0 (not guilty)
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
C 0 1 0 1 0 1 0 1
A C B 0
1
0 0
0 1
1 1
1 0
B 0 0
C 0 0
D 0 1
A CD B
0 0
0 1
1 1
1 0 Y
4-input Karnaugh Map This has 16 entries on the Truth Table and so the Karnaugh Map has 16 squares
0 0
0
0 0 0
0
0 1 1
1
1 0 0
0
1 0 1
00
01 11 10
0
0 1 1 1 1 1 1 1 1
1
1 0 0 0 0 1 1 1 1
1
1 0 0 1 1 0 0 1 1
0
1 0 1 0 1 0 1 0 1
(*) Fuente: Logic Equation Simplification. University of Wales, Newport
Note there is one additional rule for grouping 1s on this map and larger maps: Rule: 1s may be grouped between the top row and the bottom row.
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
A CD B
0 0
0 1
1 1
1 0
00 01 11
10
Example Four judges A, B, C and D vote: 1 guilty and 0 not guilty. Obtain a Boolean Expression that will allow a majority decision to be found. In the case of a split decision the vote of A determines the outcome Y.
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Y 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1
A CD B
0 0
0 1
1 1 1 1
1 0
00
01 11
1 1 1
1 1
10
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Y 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1
A CD B
0 0
0 1
1 1 1 1
1 0
00
01 11
1 1 1
1 1
10
AC
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
A CD B
0 0
0 1
1 1 1 1
1 0
00
01 11
Identify groups
1 1 1
1 1
10
A D
A B
AC
AC
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Y 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1
A CD B
0 0
0 1
1 1 1 1
1 0
00
01 11
1 1 1
1 1
10
Boolean Expression
Y A B A C A D B C D
(*) Fuente: Logic Equation Simplification. University of Wales, Newport
Example Two 2-bit numbers (A,B) and (C,D) are to be compared. If (A,B) > (C,D) then the G (greater than) output is to equal 1 If (A,B) < (C,D) then the L (less than) output is to equal 1 If (A,B) = (C,D) then the E (Equal to) output is to equal 1 e.g. A = 1, B = 0, C = 1, D = 1 10 (2) is less than 11 (3) so L = 1
(*) Fuente: Logic Equation Simplification. University of Wales, Newport
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
B 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
A 0 CD B 0 00
0 1
1 1
1 0
01
11 10
A CD B 00 01 11 10
0 0
0 1
1 1
1 0 L
A CD B 00 01 11 10
0 0
0 1
1 1
1 0 E
Expression G Expression L
Expression E
(*) Fuente: Logic Equation Simplification. University of Wales, Newport