logo
Лекции ДМ

Проблема разрешимости.

Как было сказано выше, все формулы алгебры логики делятся на три класса:

1) тождественно истинные,

2) тождественно ложные и

3) выполнимые.

В связи с этим возникает задача: к какому классу относится данная формула?

Эта задача носит название проблемы разрешимости.

Очевидно, проблема разрешимости алгебры логики разрешима.

Действительно, для каждой формулы алгебры логи­ки может быть записана таблица истинности, которая и даст ответ на поставленный вопрос.

Однако практическое использование таблицы истин­ности для формулы А(х1, х2, …, хк)при больших п зат­руднительно.

Существует другой способ, позволяющий, не исполь­зуя таблицы истинности, определить, к какому классу относится формула А. Этот способ основан на приведе­нии формулы к нормальной форме (КНФ или ДНФ) и использовании алгоритма, который позволяет определить, является ли данная формула тождественно истинной или

не является. Одновременно с этим решается вопрос о том, будет ли формула А выполнимой.

Предположим, что мы имеем критерий тождествен­ной истинности для формул алгебры логики. Рассмот­рим механизм его применения.

Применим критерий тождественной истинности к формуле А. Если окажется, что формула-А - тождественно истинная, то задача решена. Если же окажется, что фор­мула А не тождественно истинная, то применим крите­рий тождественной истинности к формуле . Если ока­жется, что формула — тождественно истинная, то ясно, что формула А - тождественно ложная, и задача решена.

Если же формула - не тождественно истинная, то оста­ется единственно возможный результат: формула А вы­полнима.

Установим теперь критерий тождественной истин­ности произвольной формулы алгебры логики. С этой целью предварительно сформулируем кри­терий тождественной истинности элементарной дизъ­юнкции.

Теорема 1. Для того, чтобы элементарная дизъюнк­ция была тождественно истинной, необходимо и доста­точно, чтобы в ней содержалась переменная и ее отри­цание.

Критерий тождественной истинности элементарной дизъюнкции позволяет сформулировать и доказать критерии тождественной истинности произвольной фор­мулы алгебры логики.

Теорема 2. Для того, чтобы формула алгебры логи­ки А была тождественно истинна, необходимо и дос­таточно, чтобы любая элементарная дизъюнкция, вхо­дящая в КНФ А, содержала переменную и ее отрица­ние.

Аналогично можно установить критерий тождественной ложности формулы алгебры логики, используя ее ДНФ. Приводим соответствующие теоремы.

Теорема 3. Для того, чтобы элементарная конъюн­кция была тождественно ложной, необходимо и доста­точно, чтобы в ней содержалась переменная и ее отри­цание.

Теорема 4. Для того, чтобы формула алгебры логики А была тождественно ложной, необходимо и достаточ­но, чтобы, любая конъюнкция, входящая в ДНФ А, содер­жала переменную и ее отрицание.

На основании теорем 3 и 4 получим алгоритм проверки формулы:

  1. привести формулу к какой либо ДНФ;

  2. если ДНФА  0, то задача решена, если нет, то переходим к следующему шагу;

  3. составляем , если , то задача решена и А  1, если же не является тождественно ложной, то А выполнима.

На основании критериев тождественной ложности и истинности можно составить комбинированные критерии.

Например:

  1. привести формулу А к КНФА;

  2. если КНФА  1, то задача решена, если нет, то переходим к следующему шагу;

  3. составляем ДНФА, если ДНФА  0, то А  0; если ДНФА не тождественно ложная, то А выполнимая.

(Самостоятельно составьте комбинированный алгоритм, начав его с приведения формулы к ДНФА.)

Пример 1. Применим критерий истинности.

1.

2.Составим КНФ : , значит, А выполнима.

Пример 2. Применим критерий ложности.

1.

2.Составим ДНФ : , значит, А  1.

Пример 3.

Приведем формулу к какой-либо нормаль­ной форме:

Полученная ДНФ не является тождественно ложной, так как каждая элементарная конъюнкция не содержит переменную и ее отрицание. Следовательно, исходная формула тождественно истинна или выполнима. Преоб­разуем данную формулу к КНФ.

Полученная КНФА не является тавтологией, значит, А выполнима.

Задачи для самостоятельного решения.

1. С помощью таблицы истинности и какого-либо критерия определить класс формулы.

2.С помощью критерия тождественной истинности или тождественной ложности установить класс формулы.

3. Для каждой из формул задания 2 составить ее ДНФ и КНФ.

Контрольные вопросы

  1. Определение двойственных формул.

  2. Формулировка леммы 1.

  3. Формулировка леммы 2.

  4. Формулировка принципа двойственности.

  5. Какая формула называется элементарной конъюнкцией?

  6. Какая формула называется элементарной дизъюнкцией?

  7. Что такое дизъюнктивная нормальная форма формулы А?

  8. Что такое конъюнктивная нормальная форма формулы А?

  9. Критерий истинности для элементарной дизъюнкции.

  10. Критерий ложности для элементарной конъюнкции.

  11. Критерий истинности для произвольной формулы.

  12. Критерий ложности для произвольной формулы.