Математическая логика и теория алгоритмов. Сергиевская И.М. - 5 стр.

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

      Другими словами, тавтология – это тождественно истинная формула.
      Установить, является ли формула тавтологией, можно:
– по таблице истинности,
– используя свойства логических операций.
      Из курса дискретной математики известны основные логические
эквивалентности (свойства логических операций), которые являются примерами
тавтологий.
1. Коммутативность: A ∨ B = B ∨ A , A ∧ B = B ∧ A .
2. Ассоциативность:
   A ∨ (B ∨ C ) = ( A ∨ B ) ∨ C , A ∧ (B ∧ C ) = ( A ∧ B ) ∧ C .
3. Дистрибутивность:
   A ∨ ( B ∧ C ) = ( A ∨ B ) ∧ ( A ∨ C ) , A ∧ (B ∨ C ) = ( A ∧ B ) ∨ ( A ∧ C ) .
4. Идемпотентность: A ∨ A = A , A ∧ A = A .
5. Закон двойного отрицания: ¬¬A = A .
6. Закон исключения третьего: A ∨ ¬A = 1 .
7. Закон противоречия: A ∧ ¬A = 0 .
8. Законы де Моргана:
    ¬( A ∨ B ) = ¬A ∧ ¬B , ¬( A ∧ B ) = ¬A ∨ ¬B .
9. Свойства операций с логическими константами:
    A ∨ 1 = 1, A ∨ 0 = A , A ∧ 1 = A , A ∧ 0 = 0 .
      Здесь A , B и C – любые буквы.

     Примеры. 1. Доказать, что формула A ∧ B → A является тавтологией.
     Доказательство. Допустим, что при некоторых значениях букв (то есть в
некоторой интерпретации)
                 ⎧ A ∧ B = 1,   ⎧ A = 1,
                 ⎪              ⎪
 A∧ B → A = 0 ⇔ ⎨             ⇔ ⎨ B = 1,
                 ⎪A =0          ⎪
                 ⎩              ⎩ A = 0.
      Приходим к противоречию, которое доказывает, что исходная формула –
тавтология.

      2. Доказать, что формула ( A ∧ B ) ∧ C ↔ A ∧ (B ∧ C ) является тавтологией.
      Доказательство. Эквиваленция истинна, если левая и правая части
принимают одинаковые значения на некотором наборе значений букв.
      Допустим, что при некоторых значениях букв
                   ⎧ A ∧ B = 1,   ⎧ A = 1,   ⎧ A = 1,
                   ⎪              ⎪          ⎪
(A ∧ B) ∧ C = 1 ⇔ ⎨             ⇔ ⎨ B = 1, ⇔ ⎨            ⇔ A ∧ ( B ∧ C ) = 1.
                   ⎪ C = 1,       ⎪          ⎪ B ∧ C = 1,
                   ⎩              ⎩ C = 1,   ⎩


                                       10