Построение сокращенной днф в классе дизъюнктивных нормальных форм
Решение.
1.Строим минимизационную карту (табл. 24):
Таблица 24
|
№ |
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 |
1 |
|
3 |
0 |
1 |
1 |
1 |
1 |
3 |
3 |
0 |
|
4 |
1 |
0 |
0 |
2 |
2 |
0 |
4 |
0 |
|
5 |
1 |
0 |
1 |
2 |
3 |
1 |
5 |
1 |
|
6 |
1 |
1 |
0 |
3 |
2 |
2 |
6 |
0 |
|
7 |
1 |
1 |
1 |
3 |
3 |
3 |
7 |
1 |
2. Вычеркиваем строки, в которых функция обращается в нуль (табл. 25):
Таблица 25
|
№ |
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 |
1 |
|
3 |
0 |
1 |
1 |
1 |
1 |
3 |
3 |
0 |
|
4 |
1 |
0 |
0 |
2 |
2 |
0 |
4 |
0 |
|
5 |
1 |
0 |
1 |
2 |
3 |
1 |
5 |
1 |
|
6 |
1 |
1 |
0 |
3 |
2 |
2 |
6 |
0 |
|
7 |
1 |
1 |
1 |
3 |
3 |
3 |
7 |
1 |
3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 26):
Таблица 26
|
№ |
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 |
1 |
|
3 |
0 |
1 |
1 |
1 |
1 |
3 |
3 |
0 |
|
4 |
1 |
0 |
0 |
2 |
2 |
0 |
4 |
0 |
|
5 |
1 |
0 |
1 |
2 |
3 |
1 |
5 |
1 |
|
6 |
1 |
1 |
0 |
3 |
2 |
2 |
6 |
0 |
|
7 |
1 |
1 |
1 |
3 |
3 |
3 |
7 |
1 |
4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 27):
предыдущаяследующая