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

      7 Классификация формул логики высказываний

      7.1 Типы формул

       Формула в ЛВ называется тождественно-истинной, или тавтологией, ес-
ли она истинна в любой интерпретации
       Формула ЛВ называется тождественно-ложной, или противоречием, ес-
ли она ложна в любой интерпретации.
       Очевидно, формула тождественно истинна тогда и только тогда, когда 
А тождественно ложна.
       Формула ЛВ называется выполнимой если она истинна хотя бы в одной
интерпретации.
       Пример – Формула Р → P выполнима, так как, например 0 → 1 = 1.
       Основные примеры тавтологий:
       Р → Р (закон тождества);
       P ∨ P (закон исключенного третьего);
       P ∧ P (закон противоречия);
       P ↔ P (закон двойного отрицания);
      P → (Q → Р) (истина из чего угодно);
       P → (P →Q) (из лжи что угодно);
      (Р →Q) ∧ Р → Q (Modus Ponens);
      (Р → Q) ∧ Q → P (Modus Tollens);
      (Р → Q) ∧ (Q →R) → (Р →R) (закон силлогизма);
      (Р → Q) → (Q → P ) (закон контрапозиции).
      Эти тавтологии называются законами АВ, поскольку они тождественно
истинны (для любых высказываний Р, Q, R,..) в силу своей структуры, и их мо-
жно рассматривать как схемы правильных умозаключений.
      Пример - Составить таблицу истинности для следующего высказывания:
(P → Q) ↔ (Q → P) . Решение даётся таблицей 7.1.

      7.2 Логическое следствие. Логическая эквивалентность
       Формула ЛВ называется логическим следствием формулы А, если В ис-
тинна во всех интерпретациях, в которых А истинна. Запись: А ⇒ В («из А ло-
гически следует В»).
       Пример - Имеет место логическое следование Р ⇒ (Q → Р) (Таблица
7.1).
       Доказательство. Если Р=1, то как известно, Q→Р=1 при любом Q
(0→1=1,1→1=1).Тогда имеем очевидное следование 1 ⇒ 1.
       Теорема Для того, чтобы А ⇒ В необходимо и достаточно, чтобы фор-
мула А → В были тавтологией.