EnggPedia - The Engineering Encyclopedia

Wed03292017

Last update06:04:15 AM

Font Size

Profile

Menu Style

Cpanel
Back Computer Computer Engineering Dictionary Dgital Logic Design Karnaugh Mapping Procedure - Simplify Boolean Functions

Karnaugh Mapping Procedure - Simplify Boolean Functions

Before proceeding to the topic of Karnaugh Mapping, there are some basic terms which should be understood.

  • The two forms in which a binary variable exists is either its normal form (x) or the complement form (x').

Boolean Function:

It is a function which contains binary variables, one or more

Binary operators i.e OR or AND, a Unitary Operator i.e NOT, parenthesis and an equal sign. Examples are:

  1. F=xyz' (F=1 only when x=1,y=1 and z=0 because z'=1)
  2. F=x+y+z
  3. F=xyz+x'yz

The Following Truth Table shows some Boolean functions with their results. Boolean functions Boolean Function can also be derived by looking at the truth table carefully.

Minterms:

When n variables, suppose 2 i.e x and y, are combined through an AND operation, there are four combination in which they can appear i.e x'y, xy', xy, x'y'. Each of these four terms are different from each other and these four terms AND terms are called minterms or standard product. In minterms, if a variable is primed i.e complemented, then that corresponding bit is taken as a "o" and if it is unprimed,it is taken as a "1".

Maxterms:

When n variables, suppose 2 i.e x and y,are combined through an OR operation, there are four combination in which they can appear i.e x'+y, x+y', x+y, x'+y'. Each of these four terms are different from each other and these four OR terms are called maxterms or standard sums. In maxterms, if a variable is primed i.e complemented, then that corresponding bit is taken as a "1" and if it is unprimed,it is taken as a "0". Note that n variables can combine to form 2^n minterms or maxterms depending on the operation used.

Karnaugh Mapping:

To simplify Boolean function, Boolean algebra provides a difficult method. The Karnaugh map (K-map) is a simple and straightforward method to minimize or simplify Boolean functions. This method may be regarded as an extension to the Venn diagram or as a pictorial representation of truth table. The values inside a K-map are the output values of the function computed from the truth table. If the number of variables are two and we consider a general case then, the relation between a truth table f and a K-map can be seen in the diagram given below. General KP As stated above,the values inside the squares of the K-map are the output values of the function computed with the help of truth table. The values outside the K-map are the values of the input variables. e.g in the truth table we get the value of F= a when input A=0 and input B=0.Similarly F=b, when A=0 and B=1 and so on. Following are the general diagrams for two,three and four variable map. two variable map three variable map four variable map

Rules for Minimizing the Boolean Function:

Examples given below will help in understanding the concept.

Example 1: Consider the following map. The function plotted is: Z = f(A,B) = A + AB Karnap map examaple

Using algebraic simplification,


Z = A + AB
Z = A( + B)
Z = A

Three Variable K-map Examples:

three var example three var example three var example

FOUR Variable Examples:

4var example
four var KP

Related Articles to this Article
Anomalies: Anomalies are problems that can occur in poorly planned, un-normalized databases where al
Read more similar Articles