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

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

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

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

Логические равносильности алгебры логики:

a → b ≡ Ú b;

a Å b ≡ & b Ú a & ;

a ~ b ≡ a & b Ú & .

a | b ≡ Ø (a & b)

a ¯ b ≡ Ø (a Ú b)

Равносильное упрощение формул выполняется по шагам:

1. замена операций импликации, строгой дизъюнкции, эквиваленции, функции Шеффера и стрелки Пирса логическими равносильностями;

2. применение законов алгебры логики.
Таблица 3. Свойства и законы алгебры логики

Название	Содержание
Коммутативность (переместительный)	a Ú b ≡ b Ú a a & b ≡ b & a
a Å b ≡ b Å a
Ассоциативность (сочетательный)	a Ú (b Ú c) ≡ (a Ú b) Ú с
a & (b & c) ≡ (a & b)& c
a Å (b Å c) ≡ (a Å b) Å c
Дистрибутивность (распределительный)	a & (b Ú c) ≡ (a & b) Ú (а & c)
a Ú (b & c) ≡ (a Ú b) & (а Ú c)
Закон снятия двойного отрицания	≡ а
Законы де Моргана	≡
≡
следствие закона	a Ú b ≡ ; a & b ≡
Законы поглощения	a Ú a & b ≡ a a & (a Ú b) ≡ a
Свойства константы Л	a Ú Л ≡ a а & Л ≡ Л
Свойства константы И	а Ú И≡ И а & И ≡ a
Закон исключения третьего	Ú a ≡ И
Законы идемпотентности	a Ú a ≡ a a & a ≡ a
Закон противоречия	& a ≡ Л
Законы склеивания	(a & b) Ú ( & b) ≡ b (aÚ b) & ( Ú b) ≡ b

Дата добавления: 2014-11-20