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

Под равносильными преобразованиями понимается замена формулы или ее части (подформулы) на равносильную ей формулу, исходя из равносильностей 1-10 пункта 3.3 и равносильностей 1-4 пункта 3.4.

В силу свойства транзитивности отношения равносильности, если А = А‘2-) Л2 = Лз, Ak- = Ak, то A = Ak. В таком случае будем для простоты записывать цепочку: А = Ао = Лз — ••• — i = 7Ц.

Приведем формулировки двух правил, с помощью которых можно переходить от одних формул к другим, равносильным данным, что позволит расширить запас равносильностей.

Теорема 3.1. (правило замены подформулы). Пусть Fa - логическая формула, содержащая А в качестве подформулы. Пусть FB получается из Fa заменой А в этом вхождении на В. Тогда, если А = В, то Fa = Fb.

Теорема 3.2. (правило подстановки формулы вместо переменной). Пусть две равносильные формулы содержат переменную X: Fx = Нх и формулы Fa и Па получены заменой всех вхождений переменной X на произвольную формулу А. Тогда /Д = //д, т. е. равносильность сохраняется.

Равносильность Fx — Нх означает, что формула Fx = Нх является тавтологией, поэтому 3.2 следует из более общего результата для тавтологий (пункт 3.3, утверждение 2). Доказательства теорем 3.1 и 3.2 можно найти в [7] §1.1.2.

Заметим, что алгебраический аналог этих правил достаточно очевиден. Например, известное тождество а2 — Ь2 — {а — 6)(а + 6) можно использовать следующим образом: (ca+cb)(a—b) = c(a—b)(a+b) = c(a2—b2) (подформулу заменили на равную ей формулу). С другой стороны, из этого же тождества получаем: sin2 хb2 = (sin хb) (sin хЬ) (все вхождения а заменили функцией sin ж).

Укажем важное отличие в использовании этих правил. В правиле подстановки формулы вместо переменной можно подставить произвольную формулу, но обязательно вместо всех вхождений переменной. Тогда как в правиле замены подформулы можно заменить только одно из вхождений подформулы, но не на любую формулу, а обязательно на равносильную формулу.

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

П р и м е р 3.5. Упростить формулу (-<(Л У В) —> Л V В)&В.

Запишем цепочку равносильных формул:

Поясним наши преобразования. На первом шаге исключили импликацию, воспользовавшись равносильностью 1 (пункт 3.4). Затем, применили закон двойного отрицания. При этом в равносильности 8 все вхождения переменной А заменили на формулу (Л V В). На следующем шаге использовали закон идемпотентности, заменив в равносильности 4 все вхождения Л на формулу (Л V /i). Pi, наконец, воспользовались законом поглощения.

Этот же прием можно использовать и для доказательства тождественной истинности (ложности) формулы.

П р и м е р 3.6. Доказать тождественную истинность формулы

Запишем цепочку равносильных формул:

Сначала мы применили известную равносильность Л—?В = -Д V В, затем законы двойного отрицания и ассоциативности. Далее использовали закон коммутативности. Следующим действием с помощью законов дистрибутивности вынесли за скобки и раскрыли скобки в подформуле Вк-^СМС. Наконец, воспользовавшись законом исключенного третьего и правилами действий с константами, получили окончательный ответ.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >