Алгоритм минимизации функций в классе днф
Таблица 49
|
№ |
x1 |
x2 |
x3 |
x1x2 |
x1x3 |
x2x3 |
x1x2x3 |
f(x1, x2, x3) |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
2 |
0 |
1 |
0 |
1 |
0 |
2 |
2 |
0 |
|
3 |
0 |
1 |
1 |
1 |
1 |
3 |
3 |
1 |
|
4 |
1 |
0 |
0 |
2 |
2 |
0 |
4 |
1 |
|
5 |
1 |
0 |
1 |
2 |
3 |
1 |
5 |
0 |
|
6 |
1 |
1 |
0 |
3 |
2 |
2 |
6 |
1 |
|
7 |
1 |
1 |
1 |
3 |
3 |
3 |
7 |
1 |
Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 50):
Таблица 50
|
№ |
x1 |
x2 |
x3 |
x1x2 |
x1x3 |
x2x3 |
x1x2x3 |
f(x1, x2, x3) |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
2 |
0 |
1 |
0 |
1 |
0 |
2 |
2 |
0 |
|
3 |
0 |
1 |
1 |
1 |
1 |
3 |
3 |
1 |
|
4 |
1 |
0 |
0 |
2 |
2 |
0 |
4 |
1 |
|
5 |
1 |
0 |
1 |
2 |
3 |
1 |
5 |
0 |
|
6 |
1 |
1 |
0 |
3 |
2 |
2 |
6 |
1 |
|
7 |
1 |
1 |
1 |
3 |
3 |
3 |
7 |
1 |
Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 51):
Таблица 51
|
№ |
x1 |
x2 |
x3 |
x1x2 |
x1x3 |
x2x3 |
x1x2x3 |
f(x1, x2, x3) |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
2 |
0 |
1 |
0 |
1 |
0 |
2 |
2 |
0 |
|
3 |
0 |
1 |
1 |
1 |
1 |
3 |
3 |
1 |
|
4 |
1 |
0 |
0 |
2 |
2 |
0 |
4 |
1 |
|
5 |
1 |
0 |
1 |
2 |
3 |
1 |
5 |
0 |
|
6 |
1 |
1 |
0 |
3 |
2 |
2 |
6 |
1 |
|
7 |
1 |
1 |
1 |
3 |
3 |
3 |
7 |
1 |
Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 52):
предыдущаяследующая