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

         6 Интерпретация исчисления высказываний

         6.1 Интерпретация       исчисления     высказываний   в   алгебру
         высказываний

       Интерпретация ИВ в алгебру высказываний задается приписыванием в
качестве значений:
       -каждой пропозициональной переменной конкретного высказывания (с
его истинным значением);
       -каждой связке - соответствующей логической операции (с сохранением
приоритета).
       В результате интерпретации формула ИВ становится высказыванием,
истинностное значение которого вычисляется в соответствии со структурой
формулы и определением логических операций. «Лишние» скобки можно опу-
скать.
       Формула называется истинной в данной интерпретации, если соответст-
вующее ей высказывание истинно; ложное - в противном случае.

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

       Две формулы ИВ называются равносильными, если они имеют одинако-
вые истинностные значения во всех интерпретациях.
       Запись: А=В («А равносильно В»).
       Имеют место следующие равносильности:
       1 Коммутативность конъюнкции, дизъюнкции:
       А ∧ В = В ∧ А, А ∨ В= В ∨ А.
       2 Ассоциативность конъюнкции, дизъюнкции:
       А ∧ (В ∧ С)= (А ∧ B) ∧ C, А ∨ (В ∨ С) = (А ∨ В) ∨ С.
       3 Дистрибутивность конъюнкции относительно дизъюнкции, дизъюнк-
ции относительно конъюнкции:
       А∧(В∨С) = (А∧В)∨(А∧C)=(A∨(В∧С)=(А∨D)∧(А∨С).
       4 Законы де Моргана:

A ∧ B = A ∨ B,   A ∨ B= A ∧ B,
      5 Закон двойного отрицания.
A = A.
         6 Закон исключенного третьего, закон противоречия:
         А ∨ A =1, А ∧ A =0.
         7 Закон идемпотентности:
         А ∧ А = А, А ∨ А = А.
         8 Законы поглощения:
         А ∧ (А ∨ В) = А, А ∨ (А ∧ В)=А.
         9 Элиминация импликации и эквивалентности: