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

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

Закон свертки логического выражения (СЛВ).

Закон Блейка- Порецкого.

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

Закон склеивания (расщепления).

Дополнительные законы.

Равносильности, выражающие основные законы алгебры логики.

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

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

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

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

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

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

, ;

, .

; .

.

.

Определение.

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

Имеет место следующий закон двойственности: если формулы А и В равносильны, то равносильны и им двойственные формулы, т.е. А^* º В^*.

Используя равносильности, приведенные в §4, можно часть формулы или всю формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными. (Аналог тождественным преобразованиям в арифметике, алгебре и тригонометрии).

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

Формула А считается проще равносильной ей формулы В, если она содержит меньше букв, меньше логических операций. При этом обычно операции эквивалентность и импликация заменяются операциями дизъюнкция и конъюнкция, а отрицание относят к элементарным высказываниям.

Для удобства использования и ссылок при проведении равносильных преобразований перечень наиболее часто употребляемых равносильностей (законов логических операций над высказываниями) можно свести в единую таблицу (см. следующий лист), в которой рассмотренные выше равносильности даны в сквозной нумерации.

При проведении равносильных преобразований каждый шаг основывается на использовании того или иного закона. Номер соответствующей формулы (из общей таблицы) мы будем указывать над знаком равносильности, предшествующим очередному шагу.

Рассмотрим ряд примеров равносильных преобразований.

Пример 1. Доказать равносильность .

Пример 2. Упростить формулу .

.

Пример 3. Доказать ТИ формулы .

Пример 4. Доказать законы склеивания.

Пример 5. Доказать закон Блейка - Порецкого.

Пример 6. Доказать закон свертки логического выражения.