Получение СКНФ и СДНФ с помощью таблиц истинности
Известно, что для каждой формулы алгебры высказываний можно составить таблицу истинности. А можно ли по заданной таблице истинности найти соответствующую ей формулу? Оказывается, эта задача также всегда разрешима с помощью СДНФ или СКНФ.
Пусть, например, дана таблица истинности некоторой, неизвестной пока формулы F, содержащей переменные x, y, z:
Выделим строки, в которых значение формулы равно 1. Это строки 1, 4 и 8. Для каждой из выделенных строк составим конъюнкцию переменных или их отрицаний так, чтобы наборам значений переменных в выделенных строках соответствовали истинные конъюнкции. Для этого переменные, под которыми в соответствующей строке стоит 0, взять со знаком отрицания, а переменные над 1 – без отрицания.
В результате получим конъюнкции:
Для 1 строки: ; для 4 строки: ; и для 8 строки: .
Дизъюнкция этих конъюнкций и есть искомая формула:
.
Тот факт, что полученная формула действительно соответствует данной таблице истинности, легко проверить. Действительно: если формула F истинна, то и дизъюнкция истинна, так как истинна одна из составляющих ее конъюнкций. Если формула F ложна, то ложна и дизъюнкция, так как ложна каждая из составляющих ее конъюнкций.
Подобным образом можно составить формулу для всякой таблицы истинности, в последнем столбце которой есть хотя бы одна единица. Очевидно, что одну и ту же таблицу истинности имеет множество равносильных формул.
Формула, которая получается в результате применения описанного способа, является совершенной дизъюнктивной формой данной формулы и всех формул с теми же переменными, ей равносильных.
Так как для любой формулы можно составить таблицу истинности, и притом, единственную, то всякая формула, не являющаяся тождественно ложной, имеет СДНФ и притом единственную.
Формулу, соответствующую данной таблице истинности, можно составить и другим способом, а именно:
1) выделить те строки в таблице истинности, в которых искомая формула принимает значение 0;
2) для каждой из выделенных строк составить дизъюнкцию переменных или их отрицаний так, чтобы каждая переменная вошла в дизъюнкцию только один раз (со знаком отрицания или без него) и чтобы наборам значений переменных, записанным в этих строках, соответствовали ложные дизъюнкции;
3) составить из полученных дизъюнкций конъюнкцию.
В результате для данной таблицы получится формула:
, которая является совершенной конъюнктивной нормальной формой данной формулы и всех равносильных ей формул.
Каждая формула, не являющаяся тавтологией, имеет СКНФ и притом единственную.
Таким образом, все множества равносильных формул с одними и теми же переменными, не являющимися тавтологиями или противоречиями, имеют по два «представителя» стандартного вида: СКНФ и СДНФ.
Множества тавтологий и противоречий имеют по одному «представителю» стандартного вида – соответственно СДНФ и СКНФ.
Вопросы для контроля:
1. Конъюнктивная и дизъюнктивная нормальная форма.
2. Совершенная дизъюнктивная нормальная форма, ее характерные признаки.
3. Совершенная конъюнктивная нормальная форма, ее характерные признаки.
4. Приведение к СДНФ или СКНФ с помощью равносильных преобразований.
5. Получение СДНФ и СКНФ по таблице истинности произвольной формулы.
6. Единственность СДНФ и СКНФ для формул алгебры высказываний.
Раздел 4. Логическое следование
Логическое следование
Определение 1. Формула B называется логическим следствием формул A1, A2, …, An, если при любых значениях, входящих в них, элементарных высказываний формула B принимает значение истинно всякий раз, когда формулы A1, A2, …, An принимают значение истинно. Обозначается A1, A2, …, An ╞ B
Из определения логического следования вытекает:
1. Тавтология логически следует из любой формулы.
2. Из противоречия логически следует любая формула.
Теорема 1. Из A логически следует B тогда и только тогда, когда тавтологией является A B.
Теорема 2. A1, A2,…, An╞ B тогда и только тогда, когда является тавтологией A1&A2& …& An B.
Теорема 3. Из формул A1, A2,…, An , B логически следует C тогда и только тогда, когда из формул A1, A2, …, An логически следует B C.
Следствие 1. Из A и B логически следует C тогда и только тогда, когда тавтологией является A (B C).
Следствие 2. Из формул A1, A2, …, An логически следует B тогда и только тогда, когда тавтологией является A1 (A2 … (An B)…).
Отношение логического следования играет в математике большую роль.
Если из A B, то A называется достаточным условием для B, а B – необходимым условием для A.
Если вместе с A B из B A, то A называется необходимым и достаточным условием для B, а B – необходимым и достаточным условием для A.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|