# EnggPedia - The Engineering Encyclopedia

Wed03292017

Last update06:04:15 AM

Cpanel
Back

# 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 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. 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.

## 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

Using algebraic simplification,

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