2.2.2.1. Алгоритм Куайна построения сокращенной ДНФ

1. Получить СДНФ функции.

2. Провести все операции неполного склеивания.

3. Провести все операции поглощения.

Пример 35.

Минимизировать функцию f=1111010010101111.

Решение.

1. Строим таблицу значения для данной функции (табл. 20). Строим СДНФ функции. При этом слагаемые нумеруем и записываем в столбец (табл. 21).

Таблица 20

СДНФ (1): № 0, 1, 2, 3, 5, 8, 10, 12, 13, 14, 15.

Таблица 21

№ слагаемого	слагаемое
1
2
3
4
5
6
7
8
9
10
11

2.

Первый этап склеивания (табл. 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

Слагаемые	Склеивание по	Результат
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 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что

Поскольку дальнейшее склеивания невозможны, то это и будет сокращенная ДНФ исходной функции.