Combinational logic functions and Boolean algebra, logical tables, Karnaugh maps, minimization, solid execution logic and combinational logic functions
Karnaugh map

In the previous section was solved when it is known mathematical expression of logic functions. In fact, there may be, and very often it is necessary to deal with cases where the outcome of logical functions and it is necessary to find a mathematical expression. For this purpose so-called graphical expression maps. One of the best known and most widely used is Karnaugh map. It's a different way of expressing the logical table, which is used to simplify logical expressions. For a better illustration of the problem is the following example. The logical table is a logical expression of results for all combinations of independent variables.

Example logical table for the three independent variables is shown in the given example 4.1. In the first three columns are expressed in values of independent variables. The last column (far right) shows the values of the dependent variable.

If Karnaugh maps the resulting column is displayed as a rectangular array. On each side of the rectangle are expressed in values of the independent variables. It does not matter who, regardless of which side variable is assigned. The values of the independent variables, it is appropriate to fill out so that those values in adjacent column/row have been changed by one bit. On the thus filled can be seen as are the cells that make up the array of values dependent variable. The cells of this array are filled with the values of the dependent variables based on combinations of independent variables. For a better understanding is given the following worked example with explanations.

Example 4.3

This award is given to the fire alarm system. In the area there are three independent fire sensors. When at least two sensors record the fire, it is necessary to declare a fire alarm. Expressed mathematically: For logical function of three variables Y, the value of the function Y takes values true when at least two input variables come true values.

Problem resolution:

First, the embodiment shown in the logical table problem. This is a function of three independent variables "Y = f(X1, X2, X3)." The number of all combinations of independent variables is calculated according to the formula No. 3.1 A is equal to the eighth This means that the logical table will have outside headers 8 lines. In accordance with the procedure referred to in the given example No. 4.1 is done filling in the values of independent variables. Column for the dependent variable "Y" is filled in based on the formulation of the assignment. The award is very important to pay attention to expression, whether it is "at least two" (our example) or "only two." In both cases the result is a different solution. Created a logical table for the specified example is as follows:

X1

X2

X3

Y

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

Field values for the dependent variable "Y" can take various forms, such as "2 x 4" or "4 x 2". For arrays with eight cells are more options. In this case, the chosen shape Karnaugh maps "2 x 4". The horizontal side of the field were assigned to the independent variables "X1" (top row headers) and "X2" (bottom row headers). To the vertical side of the field was assigned to the remaining independent variable "X3". Assignment of the independent variables to the parties only depends on the tastes of solvers and do not affect the outcome of the solution. In the next step of the process are filled with values of independent variables so that, when moving to an adjacent column/row is changed by one bit (Gray code). The result is shown in the following table:

The cells are filled with values of field dependent variable to reflect the combined values of the independent variables:

The solution is carried out the following procedure. The map will combine field contains the value 1 in blocks (objects) according to the following rules:

Logical expression of one block is called term and consists of conjunctive input variables that do not alter its input value. Minimum logic function is created by these disjoint terms. The resulting mathematical expression logic function is:

(027)

Karnaugh map can also solve the coverage of fields with zeros. The resulting logic function is the negation of a disjunction of terms. The previous example would be the following:

(028)

Form solution map is chosen depending on which fields are less.