<<
>>

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

Пример. Рассмотрим функцию . Приведем несколько различных формул, являющихся д. н. ф. и реализующих функцию .

Это ее СДНФ = и д. н. ф.: , , . Заметим, что .

Лемма. Число различных д. н. ф. от переменных равно .

Доказательство. Действительно, число различных элементарных конъюнкций равно (“пустой” конъюнкции сопоставлена константа 1), так как для каждой переменной имеется три возможности: присутствует в конъюнкции, присутствует с отрицанием и отсутствует. Выпишем все элементарные конъюнкции, поставив между ними дизъюнкции: . Удаляя различные , получим все возможные д. н. ф. Следовательно, число различных д. н. ф. равно и одной функции соответствует несколько различных д. н. ф.

Введем функционал , означающий сложность д. н. ф., обладающий свойствами:

1. .

2. Если , то .

3. Если и , то .

4. Если и получены одна из другой переименованием переменных, то .

Примеры: 1) – число букв в д. н. ф.; 2) – число элементарных конъюнкций; 3) – число знаков отрицаний.

Тогда для рассмотренного в начале параграфа примера:

, , ;

, ;

, , .

Д. н. ф. называется минимальной для данной функции , если имеет минимальное значение.

Проблема минимизации д. н. ф. состоит в том, чтобы для произвольной функции построить минимальную д. н. ф. Конечно, существует алгоритм, реализующий проблему минимизации, – это алгоритм полного перебора. Однако, этот алгоритм занимает слишком много времени, и для функций, зависящих от большого числа переменных, реализован быть не может. В связи с этим важное значение приобретают методы, позволяющие за реальное время получить д. н. ф., в той или иной степени приближенные к минимальной.

<< | >>
Источник: Дискретная математика. Лекции. 2016

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

  1. СПОСОБЫ ЗАДАНИЯ И ФОРМЫ ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ
  2. 1.4. ПОСТРОЕНИЕ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ* СВОБОДНОЙ ОТ СОСТЯЗАНИЙ
  3. 2.1. Рабочая программа (объем дисциплины 150 часов)
  4. 3.3. Элементы алгебры логики
  5. Глава II. Классификация суждений
  6. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  7. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
  8. §1.6. Дизъюнктивные нормальные формы
  9. Дизъюнктивные нормальные формы
  10. СОДЕРЖАНИЕ
  11. 2.1.4. Нормальные формы
  12. 2.1.5.Совершенные нормальные формы
  13. 2.2.2. Минимизация нормальных форм
  14. 2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм
  15. 2.2.2.4. Алгоритм минимизации функций в классе ДНФ
  16. 2.2 Дизъюнктивные нормальные формы.
  17. 1.7. Формы представления высказываний
  18. СЕМАНТИКА ИМПЕРАТИВОВ И ДЕОНТИЧЕСКАЯ ЛОГИКА1
  19. Возрастные тектонические подразделения
  20. ГЛАВА IV СИСТЕМА ЭКОЛОГИЧЕСКИХ ХАРАКТЕРИСТИК ВИДОВ КАК ОСНОВА ФИТОИНДИКАЦИИ