Задать вопрос юристу

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

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

Например, конъюнкции , , 1 являются элементарными.

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

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

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

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

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

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

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

Например, для функции , заданной булевым вектором w(F)=(00100111), существуют следующие эквивалентные ДНФ:

, (1)

, (2)

, (3)

, (4)

. (5)

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

Например, (1) - СДНФ функции F.

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

Любую булеву функцию 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

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

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

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

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

Решение: СДНФ: .

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

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

.

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

.

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

Элементарные конъюнкции СДНФ
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 1 1
1 0 1 0 0 1
1 1 0 1 1 1
1 1 1 0 0 1

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

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

  1. §1.6. Дизъюнктивные нормальные формы
  2. 2.2 Дизъюнктивные нормальные формы.
  3. 1.4. ПОСТРОЕНИЕ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ* СВОБОДНОЙ ОТ СОСТЯЗАНИЙ
  4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  5. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  6. 2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм
  7. 2.1.4. Нормальные формы
  8. 2.1.5.Совершенные нормальные формы
  9. Конъюнктивные нормальные формы
  10. Нормальный глаз – нормальное зрение
  11. Дизъюнктивные суждения
  12. с) Дизъюнктивное суждение (Das disjunktive Urteil)
  13. с) Дизъюнктивное умозаключение (Der disjunktive Schiup)
  14. Нормальный закон распределения
  15. Нормальный закон распределения
  16. Приведения ДУ n-го порядка к нормальной системе.
  17. Нормальный закон распределения.
  18. 2.2.2. Минимизация нормальных форм
  19. НОРМАЛЬНЫЙ (ГАУССОВСКИЙ) ЗАКОН РАСПРЕДЕЛЕНИЯ