Method
of KARNAUGH |
||
|
Return
to the synopsis |
To
contact the author |
Low
of page |
Created it, 06/09/09
Update it, 06/09/13
N° Visitors
3. - VARIABLE FUNCTIONS WITH N
3. 1. - FUNCTIONS OF A VARIABLE
Knowing that a variable a can take only two values 1 or 0, one can imagine functions f0 (a), f1 (a), f2 (a) appearing all the possible combinations obtained with these two values.
We see in the table (figure 51) which it can exist for a variable 4 functions distinct.
There are two constant functions :
f0 = 0 whatever the a
f3 = 1 whatever the a
A function YES : f1 = a
A function NOT : f2 = 
3. 2. - FUNCTIONS OF 2 VARIABLES
The number of functions for two variables is 16 (figure 52).
One finds a certain number of remarkable functions :
f0 = 0 some are a and b “constant function”
f15 = 1 some are a and b “constant function”
f3 = a
f5 = b
f12 =
function NOT
f10 = 
function NOT
f1 = ab function AND
f7 = a + b function OR INCLUSIVE
One calls f14
or
NAND (of English NO
AND which means NOT AND).
One calls f8 
or
NOR (of English NO
OR which means NOT OR).
One calls f6 OR EXCLUSIVE that one also notes :
f6 = a Å b
F9 logical identity is called that one also notes :
a º
b
or f9 = a 
b
The functions are also noticed :
f2 = a
f4 = b
f11 = a +
f13 =
+ b
3. 3. - ALGEBRAIC SIMPLIFICATIONS
3. 3. 1. - STUDENTS'RAG PROCESSION
We saw for two variables a certain number of algebraical expressions.
Let us take the function f9 = ab
+ .
We will say that the algebraical expression ab +
is a polynomial made up of a students'rag procession ab and of a
students'rag procession .
In Boolean algebra, a students'rag
procession is an algebraical expression made up of the product of several
variables between them, such as abc, ab
…
etc It is it should be noted that in Boolean algebra x .
x = x, it does not have
there exhibitors such as x2,
x4, that does
not exist.
3. 3. 2. - POLYNOMIAL
A polynomial will be thus a sum of students'rag processions or nap of products.
3. 3. 3. - ADJACENT STUDENTS'RAG PROCESSION
One calls adjacent students'rag processions the students'rag processions which differ from/to each other only by only one variable. In a sum of two adjacent students'rag processions, the variable which differs eliminates.
Example :
3. 3. 4. - ALGEBRAIC REDUCTION
A simple method of algebraic reduction is to seek the adjacent students'rag processions after having put the algebraical expression which one seeks to simplify in the form of a sum of products or polynomials that one calls canonical form. Then, it will be enough to seek simplifications in the same way that we made for the property of absorption and by using the remarkable identities in order to reveal simplifications.
Example N° 1 :
One can write :
Since we know that we can add xyz as many already present once as we want without changing the value of f.
Example N° 2 :
Let us multiply member with member the expression :
Let us multiply member with member again the expression :
who becomes by removing the useless terms :
3. 4. -
METHOD
OF KARNAUGH (Return
to theory 3)
The algebraic simplification of the Booléennes equations is not always obvious and requires intuition. Contrary, the method of Karnaugh makes it possible to highlight the adjacent students'rag processions using a table without difficulty.
This method functions very well from 2 to 5 variables, it becomes complex beyond.
3. 4. 1. - TABLES OF KARNAUGH
a) - The table has
The table of Karnaugh is the particular shape of the truth table which we used up to now (truth table figure 53) :
A truth table includes/understands as many columns as variables of entry. It includes/understands one or more other columns, those of the variables of exit. All the combinations of values which the variables of entry can take are explored while counting in a binary order. The value of the variables of exit is indicated opposite the corresponding combination.
The table of Karnaugh includes/understands to him 2n boxes, N being the number of variables of entries of the function considered.
b) - Case of two variables
In this case, the number of boxes is 2n = 22 = 4 (figure 54).
The order of the variables in X-coordinate or ordinate does not have importance, only is very important the fact that when one passes from a box to the adjacent box, only one variable changes.
Example :
Let us represent the function f = a . b “function AND” (figure 55).
We see easily that one put the binary value which the exit inside the box can take for which the variables have the value carried in X-coordinate and ordinate.
f is worth 1 only for a = 1 and b = 1
c) - Case of three variables (figure 56).
Whereas for two variables, the table was square, it is now rectangular; indeed, we represented the variables bc on the same column.
One can notice that the order of the fourth and the third line appears reversed. Actually, it of it is nothing. One uses only the Gray code or binary considered in order to make change only one variable at the same time horizontally or vertically.
d) - Case of four variables (figure 57)
One finds a square which comprises 24 boxes is :
24 = 16 boxes
We again see, which is absolutely essential, that thanks to the Gray code, while passing from one box to another horizontally or vertically only one variable changes.
3. 4. 2. - GRAPHIC SIMPLIFICATION
has) - It is thus necessary now to use the table of Karnaugh to seek the adjacent students'rag processions instead of seeking them algebraically.
The table of Veitch (figure 58)
comprises in X-coordinate and ordinate the algebraical expressions represented
for each box. For example : put ac.
The table of Karnaugh (figure 59) gives, it, for each box the values which the variables in X-coordinate and ordinate take.
In the two systems, one indicates inside each box value 1 or 0 catch by the students'rag procession considered.
One can see easily that two adjacent students'rag processions will be in two close boxes since one said at the beginning which the tables of Karnaugh were made so that only one variable is changed when one changes box.
It will thus be enough for each combination to variables to note 1 or 0 in the corresponding box, according to the result found for the value of the function considered, then to gather the adjacent boxes whose contents are to 1 by group of 2, 4 or 8 or of 2n adjacent terms.
Example (figure 60)
The regroupings (here of 2 terms)
are illustrated in red, it will be noted that the boxes ab
and abc
are well the boxes representing of the adjacent students'rag processions.
One can compare the table represented with the surface of a torus if one tries
to bring closer all the boxes the adjacent students'rag processions one of the
other ; thus, if the boxes of the four corners of the table were to 1, one
could constitute a grouping of 4 boxes with them.
b) - Example for a table with 3 variables :
That is to say the expression: S
= ac
+ c
+ a
binding the variable S to the variables a, b, c.
Let us draw up the truth table (figure 61)
Simplification by the algebra
Simplification by the tables of Karnaugh
Let us defer the values of S in the table of Karnaugh (figure 62) :
Let us carry out the groupings a
and c.
We can write :
S = a
+ c
c) - Example for a table with four variables :
That is to say the expression: S = abcd + abd + bc binding the variable S to the variables a, b, c, d.
Let us draw up the truth table (figure 63) :
Algebraic simplification
S = abcd + abd + bc
Let us put abd in factor :
S = abd (c + 1) + bc
Let us use the remarkable identity (x + 1) = 1 from where (c + 1) = 1 from where one can write :
S = abd + bc
Simplification by the tables of Karnaugh
Let us defer the value of S in the table (figure 64).
Let us carry out the groupings abd and bc.
We can write :
S = abd + bc
d) - Case of 5 variables
From five variables, the problem becomes complicated a little. Indeed, it is not possible to obtain on a plane surface a table in which a box is adjacent with 5 other boxes. It is however possible to use the method of Karnaugh by making two tables (figure 65).
We see that by superimposing the two tables (figure 66), one can obtain a given box X, five adjacent boxes.
Figure 67 shows a case or one could carry out three groupings :
Red grouping : four corners in the same plan (table for e = 0)
Green grouping : two boxes in the same plan for e = 1
Blue grouping : two superimposed boxes.
NOTE :
We see in this example that the blue grouping seems to be superfluous. It is necessary when one uses an electric or electronic technology for reasons of correct operation that there is regrouping between the groupings.
This condition is not however obligatory in tire.
A grouping can include/understand only 2n boxes, i.e. 1, 2, 4, 8, 16, 32,… boxes.
e) - Case of 6 variables
One uses the same principle with four tables for six variables.
The example of figure 68 shows three groupings :
in green on four plans
in red on two plans
in blue in the same plan
Figure 69 shows in space an example of adjacent boxes.
Beyond 6 variables, the method of Karnaugh not being more valid, one uses the method known as of Mac Cluskey which we will describe later on in order not to bring of confusion with that of Karnaugh.
We will continue to look further into this lesson by practical applications of the tables of Karnaugh on another page in order not to encumber this one.
|
Click
here for the following lesson or in the synopsis envisaged to this end. |
High
of page |
 Preceding
page |
Following
page |
