Алгоритм куайна построения сокращенной днф
Первый этап склеивания (табл. 22):
Таблица 22
|
Слагаемые |
Склеивание по |
Результат |
Новые слагаемые |
|
1, 2 |
x4 |
|
1 |
|
1, 3 |
x3 |
|
2 |
|
1, 6 |
x1 |
|
3 |
|
2, 4 |
x3 |
|
4 |
|
2, 5 |
x2 |
|
5 |
|
3, 4 |
x4 |
|
6 |
|
3, 7 |
x1 |
|
7 |
|
5, 9 |
x1 |
|
8 |
|
6, 7 |
x3 |
|
9 |
|
6, 8 |
x2 |
|
10 |
|
7, 10 |
x2 |
|
11 |
|
8, 9 |
x4 |
|
12 |
|
8, 10 |
x3 |
|
13 |
|
9, 11 |
x3 |
|
14 |
|
10, 11 |
x4 |
|
15 |
В первом этапе склеивания участвовали все слагаемые СДНФ, значит, ни одно из исходных слагаемых не войдут в сокращенную ДНФ. После первого этапа склеивания (и возможных поглощений) получаем, что
Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15 (табл. 23).
Второй этап склеивания:
Таблица 23
|
Слагаемые |
Склеивание по |
Результат |
|
1, 6 |
x3 |
|
|
2, 4 |
x4 |
|
|
2, 9 |
x1 |
|
|
3, 7 |
x3 |
|
|
9, 13 |
x2 |
|
|
10, 11 |
x3 |
|
|
12, 15 |
x3 |
|
|
13, 14 |
x4 |
|
В процедуре склеивания на втором этапе не принимали участие слагаемые № 5, 8 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что
предыдущаяследующая