Основные равносильности алгебры высказываний.

1. закон двойного отрицания

2. коммутативность конъюнкции

 коммутативность дизъюнкции

3.  ассоциативность конъюнкции

 ассоциативность дизъюнкции

4.  дистрибутивность конъюнкции относительно дизъюнкции

 дистрибутивность дизъюнкции относительно конъюнкции

5. законы идемпотентности

6.  законы де Моргана

   

7.  закон противоречия

 закон исключенного третьего

8.

9.

10.  законы поглощения

Равносильности, выражающие импликацию и эквиваленцию через другие логические операции

11.

12. .

Докажем один из законов де Моргана с помощью таблицы истинности.

 

 

Из таблицы видно, что формулы  и  принимают одинаковые значения при всех значениях переменных высказываний, входящих в эти формулы. Это означает, что .

 

 

Докажем первый дистрибутивный закон с помощью таблицы истинности.

 

Из таблицы видно, что формулы  и   принимают одинаковые значения при всех значениях переменных высказываний, входящих в эти формулы. Это означает, что .

Равносильности  указывают, что операции  и  коммутативны и ассоциативны, как обычные умножение и сложение. Первая из равносильностей  указывает, что операция  дистрибутивна относительно операции , как обычное умножение дистрибутивно относительно сложения. В силу этой аналогии мы будем операцию  называть умножением, а операцию  - сложением. Выражение  будем называть логическим произведением. Знак  иногда опускают. Выражение  будем называть логической суммой.

 

 

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

Используя основные равносильности можно формулу заменить равносильной ей формулой. Такие преобразования формулы называются равносильными.

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

Упражнения.

2.1. Доказать равносильность .

Используя равносильности  и  получаем:

Используя равносильность  получаем

.

Используя равносильности  получаем:

Этот результат получили, используя равносильность

2.2. Упростить формулу

Опустив знак  и используя равносильность , получаем

Используем равносильности  

По закону де Моргана и равносильности  получаем

.

Закон двойственности

Будем рассматривать формулы, содержащие только операции  . Если формула содержит операции  и  то эти операции, как показано выше, можно выразить через  и .

Определение. Операция  называется двойственной операции , а операция  двойственной операции .

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

Например, формула  двойственна формуле  а формула  двойственна формуле  

Теорема (Закон двойственности). Если формулы  и  равносильны, то и двойственные им формулы  и  также равносильны.

В приведенном выше примере  (первый дистрибутивный закон), по закону двойственности (второй дистрибутивный закон).

Основные равносильности 2-10 представляют собой пары равносильных формул и равносильных двойственных им формул.