29.      Проблема разрешимости (разрешения) для класса однотипных задач. Проблема разрешимости в алгебре высказываний и способы их разрешения.

Проблема разрешимости для класса однотипных задач. Проблема разрешимости в алгебре высказываний и способы их разрешения.

Все формулы алгебры логики делятся на три класса: тавтологии (тождественно истинные),тождественно ложные, выполнимые.

Формулу А называют тождественно истинной, если она при всех значениях входящих в неё переменных высказываний принимает значение 1(истина). Формулу А называют тождественно ложной, если она при всех значениях входящих в неё переменных принимает значение 0(ложь).Формулу A называют выполнимой, если она принимает значение 1(истина), хотя бы на одном наборе входящих в нее переменных и не является тождественно истинной.

Вопрос к какому классу формул относится текущая формула A и называется проблемой разрешимости.  Эта проблема решается элементарно с помощью таблицы истинности, однако для больших формул таблицы очень громоздки и их использование затруднительно.

Другой способ основан на приведение формулы A к КНФ (конъюнктивная нормальная формула) или ДНФ (дизъюнктивная) и использовании специального алгоритма, который позволяет определить является ли данная формула тождественно истинной или не является. Одновременно с этим решается проблема разрешимости.

Механизм применения вышеназванного алгоритма таков. Сначала он применяется к формуле A. Если A1 то задача решена. Если это не так, то алгоритм применяется к формуле ¬A Если ¬A 1  то A0 и задача решена. Если это не так, то A - выполнимая формула.

Механизм установления тождественной истинности формулы A основан на следующих теоремах.

     Теорема 3. Для того, чтобы элементарная дизъюнкция (сумма переменных и их отрицаний) была тождественно истинной, необходимо и достаточно, чтобы в ней содержалась переменная и ее отрицание ( xi v ¬xi1)

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

( xi ^ ¬xi0) 

     Теорема 5. Для того, чтобы формула алгебры логики A была тождественно истинна, необходимо и достаточно, чтобы каждая элементарная дизъюнкция, входящая в КНФ (конъюктивная нормальная форма – произведение элементарных сумм (дизъюнкций)) A, содержала переменную и ее отрицание. Доказательство:

Необходимо. Пусть  A1  Тогда КНФ A1  и КНФAA1 ^A2 ^A3 ^...^An ^1 -> 

V1=¬(1,n), Ai1

Так как  Ai - элементарная дизъюнкция, то по теореме 3  Ai  содержит переменную и ее отрицание.

Достаточно. Пусть  Ai - содержит переменную и ее отрицание. Тогда по теореме 3  Ai1, i=¬(1,n)  Но  Следовательно A- тождественно истинная формула.

Теорема 6. Для того, чтобы формула алгебры логики A была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция, входящая в ДНФ (дизъюнктивная нормальная форма сумма элементарных произведений (конъюнкций)) A, содержала переменную и ее отрицание.

Примеры. A=(¬(xy) -> ¬x) ^ ¬(xy -> ¬y) Получить  СДНФ  и СКНФ с помощью таблицы истинности и путем элементарных преобразований.

а).   с помощью таблицы истинности