Математическая логика и теория алгоритмов. Стенюшкина В.А. - 26 стр.

       Доказательство Необходимость Пусть А ⇒ В. Тогда по определению ло-
гического следствия, если А = 1, то В = 1, то есть невозможен набор (А, В) = (1,
0). Это означает по определению импликации, что А → В - тавтология.
       Таблица 7.1

              Р                Р                   Q         Q        ( P → Q) ↔ (Q
                       →Q
              0                1                   1         1        1
              0                1                   0         1        1
                               0          0        1         0        1
                               1          0        0         1        1

Достаточность Пусть А → В – тавтология. Это означает, что (А, В) ≠ (1, 0), то
есть , если А = 1, то В = 1. Тогда по определению логического следствия А ⇒
В. Теорема доказана.
        Формула В называется логическим следствием формул А1, …Аn, если В
является логическим следствием формулы А1 ∧…∧ Аn, то есть А1 ∧…∧ Аn⇒ В.
Запись: А1, ..., Аn ⇒ В.
        Теорема Для того, чтобы А1 ∧…∧ Аn⇒ В, необходимо и достаточно,
чтобы формула А1 ∧…∧ Аn ∧ В была противоречием.

       7.3 Подстановка

         Если А - некоторая формула, в которую входит подформула В, то при-
меняется запись: А (...В...).
         Если С - некоторая формула, которую подставляют формулу А вместо
всех вхождений В, то применяется запись: А (...В...) {С//В}. В случае подстано-
вки необязательно всех вхождений символ «//» заменяется на «/».
         Теорема 7.1 Если А (...х...) – тавтология и С - любая формула, то А (...х...)
{С//х } – тавтология. Здесь В: =х).
         Теорема 7.2 Если А (...В...) и С = В («равносильно»), то А (...В...) = А
(...В...) {С/ В }.
         Доказательство проводится путем анализа интерпретаций формул.
         Две формулы логики высказываний называются логически эквивалент-
ными, если каждая из них является логическим следствием другой. Запись: А
⇔ В («А логически эквивалентно В»).
         Теорема Для того, чтобы А ⇒ В необходимо и достаточно, чтобы фор-
мула А ↔ В была тавтологией.
         Доказательство. Если А = 1, то из А ⇒ В следует, что В = 1. Если В = 1,
то из В ⇒ А следует, что А = 1 (по одной из двух предыдущих теорем). Это
означает, что А = 1, тогда и только тогда, когда В = 1, то есть А = В во всех ин-
терпретациях, и по определению эквиваленции А ↔ В = 1 во всех интерпрета-
циях. Теорема доказана.