Примеры равносильных формул - Равносильные преобразования формул и логическое следование формул логики предикатов

В теореме 4.4 перечисляются некоторые основные равносильности. Они получаются из тавтологий, приведенных в теоремах 3.1-3.4, на основании признака равносильности формул.

Теорема 4.4. Справедливы следующие равносильности:

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

Лемма 4.5 (о замене). Если, то для любой формулы алгебры высказываний имеет место равносильность

Другими словами, если в формуле некоторую ее подформулу заменить на равносильную ей формулу, то полученная формула будет равносильна исходной.

Доказательство. Поскольку формулы и принимают всегда одинаковые значения при одинаковых значениях пропозициональных переменных, то формулы

И

Принимают одинаковые значения при любых одинаковых наборах значений переменных и Следовательно,

То есть, что и требовалось доказать.

Например, на основании этой леммы и равносильности из теоремы 4.4 (пункт п), формула

Равносильна формуле.

Общая формулировка леммы о замене может быть конкретизирована в соответствии с индуктивным определением формулы следующим образом. Пусть имеется формула. Если, то. Далее, пусть исходная формула имеет следующее строение: . Если, то. Если, кроме того, , то

, то есть.

Об этом свойстве говорят, что отношение равносильности формул стабильно относительно операции конъюнкции. (Предыдущее свойство означает стабильность относительно отрицания.) Аналогично, отношение равносильности стабильно и относительно остальных логических операций -- дизъюнкции, импликации и эквивалентности. Это означает, что если и, то

Похожие статьи




Примеры равносильных формул - Равносильные преобразования формул и логическое следование формул логики предикатов

Предыдущая | Следующая