<<
>>

2.1.4. Нормальные формы

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

Иногда будем допускать в элементарной конъюнкции наличие повторов элементов.

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

Иногда будем допускать в ДНФ наличие повторов элементов.

Пример 25.

Следующие формулы находятся в ДНФ:.

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

Иногда будем допускать в элементарной дизъюнкции наличие повторов элементов.

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

Иногда будем допускать в КНФ наличие повторов элементов.

Пример 26.

Следующие формулы находятся в КНФ:

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

Еще по теме 2.1.4. Нормальные формы:

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