Конъюнктивные нормальные формы

Определение. Элементарной дизъюнкцией называется дизъюнкция литералов (переменных или их отрицаний), взятых не более чем по одному разу.

Например, дизъюнкции , , 1 являются элементарными. Причем первая элементарная дизъюнкция имеет ранг (число литералов) 2, вторая - 3, а третья - 0.

Следующие дизъюнкции: , , , , 0 не являются элементарными.

Определение.Элементарная дизъюнкция булевой функции , содержащая n литералов, называется полной.

Определение. Конъюнкция любого конечного множества элементарных дизъюнкций булевой функции F называется конъюнктивной нормальной формой (КНФ) функции F. Число элементарных дизъюнкций, составляющих КНФ, называется длиной КНФ.

Например, КНФ  имеет длину, равную 3.

Для произвольной булевой функции F существует, вообще говоря, много различных реализующих ее КНФ, отличающихся друг от друга длиной, числом вхождений литералов и т.д.

Определение. Две (или несколько) КНФ, реализующих одну и ту же булеву функцию F , называются эквивалентными (или равносильными).

Определение. КНФ булевой функции F, состоящая только из полных элементарных дизъюнкций, называется совершеннойКНФ(СКНФ).

Например, - СКНФ функции F, заданной вектором значений таблицы истинности w(F)=(01100111).

Отметим, что КДНФ является единственной (с точностью перестановки множителей) для конкретной булевой функции F .

Любую булеву функцию F, заданную формулой, можно с помощью основных равносильностей преобразовать к КНФ, а затем к СКНФ.

Пример.Привести к виду СКНФ булеву функцию F= .

Решение.С помощью основных равносильностей преобразуем к КНФ:

= = = =

=

 ― КНФ.

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

Применяя закон склеивания (в обратном порядке: ), дополняем дизъюнкции ,  до полных элементарных дизъюнкций:

.

Так как , то после сокращения одинаковых конъюнкций получаем СКНФ: F .

Составим таблицу истинности для булевой функции F= (функция из предыдущего примера). Отметим связь между СКНФ и таблицей истинности.

Таблица истинности                                     СКНФ

						Элементарные дизъюнкции СКНФ
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	1
0	1	1	1	0	1
1	0	0	0	1	1
1	0	1	0	0	0
1	1	0	0	1	0
1	1	1	0	0	1

В общем случае также можно вывести закономерности построения СКНФ по таблице истинности булевой функции, что является очень удобным.

СКНФ состоит из конъюнкций полных элементарных дизъюнкций наборов переменных , на которых функция принимает значение 0. Переменные берутся без отрицания, если им соответствует в таблице истинности 0, с отрицанием, если 1.

Пример. По таблице истинности составить СКНФ.

			F
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

Решение: F .

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

Решение: Применяя формулу , из ДНФ получаем КНФ:

.

Применяя закон склеивания (в обратном порядке: ), дополняем дизъюнкции ,  до полных элементарных дизъюнкций:

.

Так как , то после сокращения одинаковых дизъюнкций получаем СКНФ:

.

Таблица истинности                                  СКНФ

						Элементарные дизъюнкции СКНФ
0	0	0	1	0	0
0	0	1	0	0	0
0	1	0	1	1	1
0	1	1	0	0	0
1	0	0	1	0	1
1	0	1	0	0	1
1	1	0	1	1	1
1	1	1	0	0	1

Минимизация КНФ

Определение. Элементарная дизъюнкция u называется имплицентой булевой функции F , если . 

Например, элементарная дизъюнкция  является имплицентой функции .

Определение. Если никакая собственная часть  имплиценты u ( т.е. ) булевой функции F не является имплицентой F, то u называется простойимплицентой (т. е. если удаление из u хотя бы одного литерала нарушает условие , то u – простаяимплицента).

Например,  – простая имплицента булевой функции ,  имплицента  не является простой для этой функции, так как  (собственная часть имплиценты ) является имплицентой функции F.

Определение. Конъюнкция всех простых имплицент булевой функции F называется сокращенной КНФ (СкКНФ)функции F.

Например,   – СкКНФ булевой функции . Отметим, что СкКНФ является единственной для конкретной булевой функции F.

Определение.КНФ булевой функции F, содер­жащая наименьшее число множителей среди всех КНФ, реализующих функцию F, называется кратчайшей КНФ (КрКНФ).

Например, является также и КрКНФ этой же булевой функции F.

Вообще говоря, для заданной булевой функции F может существовать несколько различных по числу вхождений литералов КрКНФ.

Определение.КНФ булевой функции F, содер­жавшая наименьшее число вхождений литералов среди всех КНФ, ре­ализующих функцию F, называется минимальной КНФ (МКНФ).

Отметим, что для заданной булевой функции F существует, вообще говоря, несколько МКНФ, отличающихся друг от друга чис­лом слагаемых.

Более того, МКНФ не всегда совпадает с КрКНФ булевой функции n переменных F. Хотя для начальных значе­ний n ( n = 2 или n = 3 ) МКНФ всегда совпадает с КрКНФ. Например,  является КрКНФ и МКНФ рассматриваемой функции F.

Задача минимизации булевой функции  в классе КНФ формулируется следующим образом: тре­буется для булевой функции n переменных F построить КНФ с минимально возможным числом множителей (КрКНФ) или с мини­мально возможным числом вхождений литералов (МКНФ).

Также отметим, что задача минимизации булевых функций n переменных F в классе КНФ также, как и задача минимизации булевых функций n переменных F в классе ДНФ, является чрезвычайно громоз­дкой и ее трудоемкость с ростом n возрастает по экспонен­циальному закону.

К настоящему времени разработано около 200 различных ме­тодов минимизации булевых функций в классе КНФ.

Пример. Составить по таблице истинности СКНФ булевой функции   и минимизировать ее, применяя законы склеивания.

Решение.

0	0	0	1	1	1
0	0	1	0	1	1
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	1	0	0
1	0	1	0	0	1
1	1	0	1	0	0
1	1	1	1	0	0

СКНФ будет иметь вид: .

Минимизируем ее, применяя законы склеивания. Подчеркнем дизъюнкции, которые можно склеить. Очевидно, что это можно сделать различными способами, например:

,

.

Выберем один из возможных вариантов склеивания, например  и минимизируем КНФ:

.

Замечание.При минимизации КНФ достаточно часто (но не всегда!) удается получить лучшие результаты, если «нарастить» данную КНФ используя свойство идемпотентности дизъюнкции: .

Например, в рассматриваемом примере третью, последнюю дизъюнкцию  можно было бы склеить со второй дизъюнкцией . Добавив вторую дизъюнкцию еще раз, мы не изменим саму булеву функцию, но получим в результате минимизации КНФ более короткое ее представление:

.

Ответ: F

Пример. Составить СКНФ булевой функции, заданной вектором значений таблицы истинности w(F)=(10010110) и минимизировать ее, применяя законы склеивания.

Решение.Так как вектор значений заданной булевой функции имеет 8=2³ разрядов, следовательно, булевой функции соответствует следующая таблица истинности:

			F
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

СКНФ будет иметь вид:

.

К сожалению, минимизировать ее, применяя законы склеивания, невозможно.

Ответ: .