Юридическая
консультация:
+7 499 9384202 - МСК
+7 812 4674402 - СПб
+8 800 3508413 - доб.560
 <<
>>

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

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

Например, дизъюнкции , , 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

<< | >>
Источник: БУЛЕВЫ ФУНКЦИИ. Лекция. 2016

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

  1. §12. Отсутствие смысла (Unsinn) и бессмыслица (Widersinn)
  2. Примеры
  3. 1.3.1. Выбор и спецификация выбора числа
  4. 2.1. Рабочая программа (объем дисциплины 150 часов)
  5. 3.3. Элементы алгебры логики
  6. Глава II. Классификация суждений
  7. Свойства операций над высказываниями
  8. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  9. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  10. Конъюнктивные нормальные формы
  11. СОДЕРЖАНИЕ
  12. 2.1.4. Нормальные формы
  13. 2.1.5.Совершенные нормальные формы
  14. 2.2.2. Минимизация нормальных форм