Before constructing the scheme realizing logical functions, it is necessary to minimize it accordingly, i.e. to find such equivalent form of concept at which expression for function will consist of the least number of variables (letters in most of cases). Minimization of logical functions may lead to analytical calculations, using postulates and laws of Boolean algebra.
The basic concepts of every digital device which are entered at a stage of minimization of logical functions are the concepts of adjacent minterms and implicant, and the basic operation of simplification is the operation of pasting adjacent minterms. The conjunction being as a result of pasting two adjacent minterms in the “digits” is refers to as implicant. Implicants with identical number of variables (rank), in turn, can appear to be adjacent, which allows conducting successfully their pasting among themselves.
Multistage pasting oriented process leads to reception of implicants, which have no adjacencies. Such implicants are called simple implicants. Process of minimization of logical functions is simplified significantly with the Karnaugh map. This map represent the rectangular table (matrix) broken by horizontal and vertical lines on cells. The general number of cells coincides with number of minterms and is equal to 2n, where n is the number of variables of simplified function. Thus, each cell of the map is conformed to a certain minterm which accommodation is carried out so that adjacent minterms are in adjacent cells. Adjacent cells are the cells which have adjacent sides and are located on edges of the same lines or columns of the map.
Such order of minterm accommodation provides an accepted way of formation of variables set appropriating various cells of the Karnaugh map. All variables are broken on two groups. The sets of variables of one group are put in conformity columns to sets of the other group – lines of the map. For definiteness an extreme left column and the top line of the map are designated with zero values sets of all variables but this condition is optional.
|