Tugas 7 Bravo 2103015233 Boolean dan Karnaugh Map
Nama: Bravo Marvel
Kelas: 2B
NIM: 2103015233
Rangkuman Boolean dan Karnaugh Map
Standard Forms
of Boolean Expressions
Sum of Product
(SOP) Form
The sum-of-products
(SOP) form is a method (or form) of simplifying the Boolean expressions of
logic gates. In this SOP form of Boolean function representation, the variables
are operated by AND (product) to form a product term and all these product terms
are ORed (summed or added) together to get the final function.
A sum-of-products form
can be formed by adding (or summing) two or more product terms using a Boolean
addition operation. Here the product terms are defined by using the AND
operation and the sum term is defined by using OR operation.
The sum-of-products
form is also called as Disjunctive Normal Form as the product terms are ORed
together and Disjunction operation is logical OR. Sum-of-products form is also
called as Standard SOP.
SOP form representation
is most suitable to use them in FPGA (Field Programmable Gate Arrays).
Examples
AB + ABC + CDE
(AB) ̅ + ABC + CD E ̅
SOP form can be
obtained by
- Writing an AND term for each input combination, which
produces HIGH output.
- Writing the input variables if the value is 1, and
write the complement of the variable if its value is 0.
- OR the AND terms to obtain the output function.
Ex: Boolean expression
for majority function F = A’BC + AB’C + ABC ‘ + ABC
Product of Sums (POS)
Form
The product of sums
form is a method (or form) of simplifying the Boolean expressions of logic
gates. In this POS form, all the variables are ORed, i.e. written as sums to
form sum terms.
All these sum terms
are ANDed (multiplied) together to get the product-of-sum form. This form is
exactly opposite to the SOP form. So this can also be said as “Dual of SOP
form”.
Here the sum terms are
defined by using the OR operation and the product term is defined by using AND
operation. When two or more sum terms are multiplied by a Boolean OR operation,
the resultant output expression will be in the form of product-of-sums form or
POS form.
The product-of-sums
form is also called as Conjunctive Normal Form as the sum terms are ANDed
together and Conjunction operation is logical AND. Product-of-sums form is also
called as Standard POS.
Examples
(A+B) * (A + B + C) *
(C +D)
(A+B) ̅ * (C + D + E ̅)
POS form can be
obtained by
- Writing an OR term for each input combination, which
produces LOW output.
- Writing the input variables if the value is 0, and
write the complement of the variable if its value is 1.
- AND the OR terms to obtain the output function.
Ex: Boolean expression
for majority function F = (A + B + C) (A + B + C ‘) (A + B’ + C) (A’ + B + C)
The Karnaugh Map
l Provides a systematic method for simplifying Boolean expressions
l Produces the simplest SOP or POS expression
l Similar to a truth table because it presents
all of the possible values of input variables
The Karnaugh map (KM
or K-map) is a method of simplifying Boolean algebra expressions. Maurice
Karnaugh introduced it in 1953, as a refinement of Edward W. Veitch's 1952
Veitch chart, which was a rediscovery of Allan Marquand's 1881 logical diagram aka
Marquand diagram, but with a focus now set on its utility for switching
circuits.Veitch charts are therefore also known as Marquand–Veitch diagrams,and
Karnaugh maps as Karnaugh–Veitch maps (KV maps).
The Karnaugh map
reduces the need for extensive calculations by taking advantage of humans'
pattern-recognition capability.It also permits the rapid identification and
elimination of potential race conditions.
The required Boolean
results are transferred from a truth table onto a two-dimensional grid where,
in Karnaugh maps, the cells are ordered in Gray code, and each cell position
represents one combination of input conditions. Cells are also known as minterms,
while each cell value represents the corresponding output value of the boolean
function. Optimal groups of 1s or 0s are identified, which represent the terms
of a canonical form of the logic in the original truth table. These terms can
be used to write a minimal Boolean expression representing the required logic.
Karnaugh maps are used
to simplify real-world logic requirements so that they can be implemented using
a minimum number of logic gates. A sum-of-products expression (SOP) can always
be implemented using AND gates feeding into an OR gate, and a product-of-sums
expression (POS) leads to OR gates feeding an AND gate. The POS expression
gives a complement of the function (if F is the function so its complement will
be F'). Karnaugh maps can also be used to simplify logic expressions in
software design. Boolean conditions, as used for example in conditional
statements, can get very complicated, which makes the code difficult to read
and to maintain. Once minimised, canonical sum-of-products and product-of-sums
expressions can be implemented directly using AND and OR logic operators.
Questions & Answers
1. What is the primary motivation for using Boolean algebra
to simplify logic expressions?
A. It may make
it easier to understand the overall function of the circuit.
B. It may
reduce the number of gates.
C. It may
reduce the number of inputs required.
D. all of the
above
Answer: D
2. How many gates would be required to implement the
following Boolean expression after simplification? XY + X(X + Z) + Y(X + Z)
A. 1
B. 2
C. 4
D. 5
Answer: B
3. AC + ABC = AC
A. True
B. False
C. I Don’t know
D. Maybe
Answer: A
4. When are the
inputs to a NAND gate, according to De Morgan's theorem, the output expression
could be:
A. X = A + B
B. X = AB
C. X = (A)(B)
D. X = ABC
Answer: A
5. Which Boolean algebra property allows us to group
operands in an expression in any order without affecting the results of the
operation [for example, A + B = B + A]?
A. associative
B. commutative
C. Boolean
D. distributive
Answer: B
6. When grouping cells within a K-map, the cells must be
combined in groups of ________.
A. 2s
B. 1, 2, 4, 8,
etc.
C. 4s
D. 3s
Answer: B
7. Use Boolean algebra to find the most simplified SOP
expression for F = ABD + CD + ACD + ABC + ABCD.
A. F = ABD +
ABC + CD
B. F = CD + AD
C. F = BC + AB
D. F = AC + AD
Answer: A
8. The NAND or NOR gates are referred to as
"universal" gates because either:
A. can be found
in almost all digital circuits
B. can be used
to build all the other types of gates
C. are used in
all countries of the world
D. were the
first gates to be integrated
Answer: B
9. The truth table for the SOP
expression has how many input
combinations?
A. 1
B. 2
C. 4
D. 8
Answer: D
10. Converting the Boolean expression LM + M(NO + PQ) to
SOP form, we get ________.
A. LM + MNOPQ
B. L + MNO +
MPQ
C. LM + M + NO
+ MPQ
D. LM + MNO +
MPQ
Answer: D
11. A Karnaugh map is a systematic way of reducing which
type of expression?
A. product-of-sums
B. exclusive
NOR
C. sum-of-products
D. those with
overbars
Answer: C
12. Which of the following combinations cannot be combined
into K-map groups?
A. corners in
the same row
B. corners in
the same column
C. diagonal
D. overlapping
combinations
Answer: C
13. An OR gate with schematic
"bubbles" on its inputs performs the same functions as a(n)________
gate.
A. NOR
B. OR
C. NOT
D. NAND
Answer: D
14. Which of the examples below expresses the commutative
law of multiplication?
A. A + B = B +
A
B. AB = B + A
C. AB = BA
D. AB = A × B
Answer: C
15. The expression W(X + YZ) can
be converted to SOP form by applying which law?
A. associative law
B. commutative law
C. distributive law
D. none of the above
Answer: C
16. The commutative law of addition and multiplication
indicates that:
A. we can group
variables in an AND or in an OR any way we want
B. an
expression can be expanded by multiplying term by term just the same as in
ordinary algebra
C. the way we
OR or AND two variables is unimportant because the result is the same
D. the
factoring of Boolean expressions requires the multiplication of product terms
that contain like variables
Answer: C
17. Which of the following is an
important feature of the sum-of-products (SOP) form of expression?
A. All logic circuits are reduced to nothing more than simple
AND and OR gates.
B. The delay times are greatly reduced over other forms.
C. No signal must pass through more than two gates, not
including inverters.
D. The maximum number of gates that any signal must pass through
is reduced by a factor of two.
Answer: C
18. Which of the following
expressions is in the sum-of-products (SOP) form?
A. (A + B)(C + D)
B. (A)B(CD)
C. AB(CD)
D. AB + CD
Answer: D
|
19. One of De Morgan's theorems states that X+Y =
X.Y. Simply stated, this means that logically there is no difference between: |
||||||||
|
Answer: A
|
20. Determine the binary values of the variables for
which the following standard POS expression is equal to 0. (A+B+C) (A+B+C) |
||||||||
Answer:
A |
Source:
Comments
Post a Comment