<<
>>

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

2.2.1 Основные определения.

- конечный алфавит из переменных.

Рассмотрим слово:

Экспоненциальные обозначения:

- элемент конъюнкции.

S – длина элемента конъюнкции.

ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.

Любая булева функция может быть представлена как ДНФ

2.2.2 Теорема о совершенной ДНФ.

Любая булева функция тождественно не равная 0 может быть разложена в ДНФ следующего вида:

Опр: Носитель булевой функции

.

Лемма:

1) это элементарно

2) возьмем набор

а)

б)

Доказательство: , будем доказывать, что.

1) Докажем, что . Возьмем он попадает в число суммируемых наборов и по нему будет проводиться сумирование.

2) Докажем, что . Возьмем другой набор из

Следовательно

2.2.3 Некоторые другие виды ДНФ.

Опр: - называется минимальной ДНФ, если она имеет - наименьшую возможную длину из всех ДНФ данной функции.

Опр: - называется тупиковой ДНФ, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции.

(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)

Опр: К-мерной гранью называется такое подмножество , которая является носителем некоторой элементарной конъюнкции длины: n-k.

Опр: Предположим дана функция и есть . Грань называется отмеченной, если она целиком содержится в носителе Т.

Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.

Предложение: Любую отмеченную грань можно вложить в максимальную грань.

Предложение:

(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)

Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.

Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.

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

Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.

<< | >>
Источник: Конспекты лекций по математической логике. 2017

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

  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 Дизъюнктивные нормальные формы.