Файл: Булевы функции.doc

Утверждение. Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.

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

Получить СДНФ функции.
Провести все операции неполного склеивания.
Провести все операции поглощения.

Пример.

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

Решение.

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

Таблица

№	x₁	x₂	x₃	x₄	f(x₁, x₂, x₃, х₄)
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	0
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	0
10	1	0	1	0	1
11	1	0	1	1	0
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	1

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

Таблица

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

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

Первый этап склеивания (табл.):

Таблица

Слагаемые	Склеивание по	Результат	Новые слагаемые
1, 2	x₄		1
1, 3	x₃		2
1, 6	x₁		3
2, 4	x₃		4
2, 5	x₂		5
3, 4	x₄		6
3, 7	x₁		7
5, 9	x₁		8
6, 7	x₃		9
6, 8	x₂		10
7, 10	x₂		11
8, 9	x₄		12
8, 10	x₃		13
9, 11	x₃		14
10, 11	x₄		15

В первом этапе склеивания участвовали все слагаемые СДНФ, значит, ни одно из исходных слагаемых не войдут в сокращенную ДНФ. После первого этапа склеивания (и возможных поглощений) получаем, что

Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15 (табл.).

Второй этап склеивания:

Таблица 23

Слагаемые	Склеивание по	Результат
1, 6	x₃
2, 4	x₄
2, 9	x₁
3, 7	x₃
9, 13	x₂
10, 11	x₃
12, 15	x₃
13, 14	x₄

В процедуре склеивания на втором этапе не принимали участие слагаемые № 5, 8 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что

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

Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм

Этот метод не отличается большой эффективностью, но он прост для изложения и не требует введения дополнительных понятий.

Пусть булева функция задана таблицей истинности или СДНФ.

Минимизирующая карта булевой функции представляет собой квадратную матрицу 2ⁿ2ⁿ, где n – число переменных. Первые столбцы отводят для аргументов, дальнейшие – для их всевозможных конъюнкций по 2, по 3 и т. д. сомножителей, предпоследний - для конъюнкции всех аргументов, последний – для значений функции.

Шаг 1. Столбцы для аргументов, как обычно в таблицах истинности, заполняются всевозможными наборами 0 и 1. В столбцах для конъюнкций проставляются десятичные значения двоичных чисел, соответствующих наборам значений аргументов. Последний столбец заполняется соответственно значению функции.

Далее работа чередуется по строкам, по столбцам.

Шаг 2. Вычеркиваются строки, в которых функция обращается в нуль.

Шаг 3. В каждом столбце из сохранившихся чисел вычеркивают те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге.

Шаг 4. В сохранившихся строках выбирают «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводят их кружочками.

Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркивают все, кроме одного.

Шаг 6. С помощью оставшихся обведенных чисел образуют конъюнкции. Для этого переводят каждое число в двоичную систему. Переменную, которой соответствует 1, берут сомножителем без отрицания, которой соответствует 0 – с отрицанием.

Шаг 8. Составляют дизъюнкцию полученных конъюнкций. В результате получаем сокращенную ДНФ функции.

Пример 36.

Построить сокращенную ДНФ для функции f=11100101.

Решение.