![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Замечание: Каждая элементарная конъюнкция (дизъюнкция), входящая в СНДФ (в СНКФ), должна содержать все пропозиционные буквы, входящие в исходную формулу. Только в этом случае можно говорить о том, что полученная форма является совершенной. Иначе имеем ДНФ (КНФ).
СНДФ и СНКФ можно составлять для данной формулы, пользуясь её таблицей истинности.
Рассмотрим таблицу истинности для произвольной формулы алгебры высказываний :
![]() | ![]() | ... | ![]() | ![]() |
... | ... | ... | ... | ... |
и | л | ... | и | и |
... | ... | ... | ... | ... |
Для каждой строки таблицы истинности строим элементарную конъюнкцию , которая истинна только для этой строки, а для всех остальных строк эта элементарная конъюнкция ложна. Пропозиционная переменная
входит в элементарную конъюнкцию без черты, если
в данной строке принимает значение «истина». Если же переменная
принимает в данной строке значение «ложь», то в элементарную конъюнкцию эта буква входит с чертой.
Тогда дизъюнкция всех элементарных конъюнкций, построенная для всех строк, в которых формула принимает значение «истина», будет иметь ту же таблицу истинности, что и рассмотренная формула . Такое представление данной формулы и будет являться совершенной нормальной дизъюнктивной формой (СНДФ).
Таким образом, всякая формула, не являющаяся тождественно ложной, может быть представлена в виде СНДФ. Если формула тождественно ложна, то она представима в виде .
Например, составим СНДФ для формулы .
![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
и | и | и | л | и | и |
и | и | л | л | и | л |
и | л | и | л | л | и |
л | и | и | и | и | и |
и | л | л | л | л | и |
л | и | л | и | и | л |
л | л | и | и | и | и |
л | л | л | и | и | л |
СНДФ для данной формулы имеет вид: =
.
В правой части равносильности просто «перечислены» все строки таблицы истинности, в которых наша формула принимает значение «истина».
Из рассмотренного примера видно, что СНДФ существует для всякой выполнимой формулы.
Аналогичные рассуждения можно привести и для СНКФ.
Если произвольная формула не является тождественно истинной, то по таблице истинности для каждой строки, где наша формула ложна, строим элементарную дизъюнкцию, которая принимает значение «ложь» только в данной строке, а в остальных строках принимает значение «истина». Если пропозиционная буква в данной строке принимает значение «ложь», то она входит в элементарную дизъюнкцию без черты. Если же переменная
в данной строке принимает значение «истина», то в элементарную дизъюнкцию она входит с чертой. Если построить такие дизъюнкции для всех строк таблицы, в которых формула принимает значение «ложь», и соединить их знаками конъюнкции, то полученная конъюнкция таких элементарных дизъюнкций имеет такую же таблицу истинности, что и исходная формула. Полученное представление формулы называется совершенной нормальной конъюнктивной формой (СНКФ).
Таким образом, всякая формула, не являющаяся тождественно истинной, может быть представлена в виде СНКФ.
Если же формула является тавтологией, то её можно представить в виде дизъюнкции .
Для рассмотренного примера СНКФ имеет вид:
↔
.
Искать СНДФ или СНКФ по таблице не всегда удобно. Особенно для тех формул, которые зависят от 4-х и более переменных. Поэтому рассмотрим алгоритм, позволяющий преобразовать произвольную формулу в СНДФ или СНКФ.
Дата публикования: 2014-11-03; Прочитано: 879 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!