1. Основные равносильности.

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

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

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

- закон снятия двойного отрицания

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

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

1. 4..

2. . 5..

3. . 6..

Здесь 3, 4, 5, 6 – законы Моргана.

Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4, соответственно, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания.

Таким образом, в доказательстве нуждаются первые четыре равносильности. Докажем одну из них : первую .

Так как при одинаковых логических значениях x и y истинными являются формулы , то истинной будет и конъюнкция. Следовательно, в этом случае обе части равносильности имеют одинаковые истинные значения.

Пусть теперь x и y имеют различные логические значения. Тогда будут ложными эквивалентность и одна из двух импликацийили. Но при этом будет ложной и конъюнкция.

Таким образом, и в этом случае обе части равносильности имеют одинаковые логические значения.

Аналогично доказываются равносильности 2 и 4.

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

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

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция “Штрих Шеффера”. Эта операция обозначается символом  и определяется следующей таблицей истинности:

x	y	xy
1	1	0
1	0	1
0	1	1
0	0	1

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

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

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

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

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

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

дизъюнкции.

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

конъюнкции.

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

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

, ;

, .

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

; .

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

.

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

.

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

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

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

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

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

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

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

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

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

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

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

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

6-10.

Нормальные формы функций.

При решении ряда задач, связанных с использованием формул алгебры высказываний, важную роль играют формулы, построенные особым образом из высказывательных переменных с помощью только операций дизъюнкции, конъюнкции и отрицания и называемые ДИЗЪЮНКТИВНЫМИ и КОНЪЮНКТИВНЫМИ НОРМАЛЬНЫМИ ФОРМАМИ (ДНФ и КНФ).

8.1 Элементарные дизъюнкции и конъюнкции.

Пусть задана система высказывательных переменных

(x₁,x₂,…,x_n). (1)

Элементарной дизъюнкцией высказывательных переменных из системы (1) называется дизъюнкция некоторых высказывательных переменных этой системы или их отрицаний.

ЭЛЕМЕНТАРНОЙ КОНЪЮНКЦИЕЙ называется конъюнкция некоторых высказывательных переменных этой системы или их отрицаний.

Если в элементарную дизъюнкцию (конъюнкцию) входит каждое высказывательное переменное из системы (1) (с отрицанием или без него) и притом только один раз, то она называется ПОЛНОЙ ЭЛЕМЕНТАРНОЙ ДИЗЪЮНКЦИЕЙ (КОНЪЮНКЦИЕЙ).

Из “n” высказывательных переменных можно образовать 2ⁿ всевозможных неэквивалентных полных элементарных дизъюнкций и столько же полных элементарных конъюнкций. Каждая полная элементарная дизъюнкция  только для одного варианта значений высказывательных переменных системы (1) принимает значение, равное нулю, а именно – когда каждое высказывательное переменное x_i, не находящееся в  под знаком отрицания, равно нулю, а каждое отрицательное – единице.

Систему значений высказывательных переменных, для которой данная полная элементарная дизъюнкция принимает значение, равное нулю, назовем нулем этой полной элементарной дизъюнкции.

Так, нулями элементарных дизъюнкций (2) являются: (0,0,0), (0,0,1), (0,1,0), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1).

Если обратиться к полным элементарным конъюнкциям, то можно обнаружить, что каждая из них только один раз принимает значение, равное единице – когда неотрицаемое переменное равно единице, а отрицаемое – нулю. Такую систему значений высказывательных переменных назовем ЕДИНИЦЕЙ соответствующей ПОЛНОЙ ЭЛЕМЕНТАРНОЙ КОНЪЮНКЦИИ.