![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Дизьюнктивной нормальной формулой (ДНФ) называется дизьюнкция элементарных коньюнктов, при этом коньюнкты не должны повторяться.
Совершенной дизьюнктивной нормальной формулой (СДНФ) называется такая ДНФ в любой коньюнкт которой входят все переменные формулы.
Коньюктивной нормальной формулой (КНФ) называется коньюнкция элементарных дизьюнктов, при этом дизьюнкты не должны повторяться.
Совершенной коньюнктивной нормальной формулой (СКНФ) называется такая КНФ в любой дизьюнкт которой входят все переменные формулы.
Теорема 1: всякая формула отличная от тождественно ложной имеет СДНФ и эта форма единственная с точностью до пеестановки элементарных коньюнктов и порядка переменных в этих коньюнктах.
Теорема 2: всякая формула отличная от тафтологии имеет СКНФ и эта форма единственная с точностью до пеестановки элементарных дизьюнктов и порядка переменных в этих дизьюнктах.
Доказательство 1:
1)Пусть есть функция f (A1 … Аn) не тождественно ложная
Рассмотрим ее таблицу истинности: каждой строке поставим в соответствии элементарный коньюнкт, где Хi = Аi , если Аi = И
Хi = Аi , если Аi = Л
Дизьюнкция берется по все строчкам, в которых f=И.
F - СДНФ
Возьмем любую строку таблицы
1. Если f=И, тогда все коньюнкты в этой строке истинны, следовательно, F=И
2. Если f=Л, тогда все коньюнкты в этой строке ложны, следовательно, F=Л
2)Всякому элементарному коньюнкту, который входит в СДНФ соответствует одна строка таблицы истинности, всякий элементарный коньюнкт истинен только в той строке, которой он соответствует, следовательно, каждый из СДНФ задает именно единственную функцию.
Доказательство 2:
Аналогично доказательству 1.
Дата публикования: 2015-03-26; Прочитано: 236 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!