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

Равносильность формул будем обозначать знаком з, тогда запись означает, что формулы Аи В равносильны.

Пример. Равносильные формулы:

X V X ш X,

(х л х) v у s у.

Тавтологией, или тождественно истинной, называется формула, принимающая значение 1 при всех значениях входящих в нее переменных.

Пример. Тождественно истинные формулы:

ivi, хЭ(хЭу).

Тождественно ложной называется формула, принимающая значение 0 при всех значениях входящих в нее переменных.

Пример. Тождественно ложная формула: х лх.

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы Аи В равносильны, то формула А «■» В — тавтология, и об­ратно, если формула Л «■» В — тавтология, то формулы Аи В равносильны.

Глава 4. Логические основы информатики

Важнейшие равносильности алгебры логики можно разбить на три группы:

□ основные равносильности;

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

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

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

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

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

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

1. ХАХ = Х.

2. ivihi

3. X Л 1 ■ X.

Xv 1-1.

IaOeO.

6. ivOsj.

7. х ах = 0 — закон противоречия.

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

9. is х— закон снятия двойного отрицания.

 

10. 1Л (у V X) si

11. X V (у АХ)=Х.

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

 

2.	xDy	mxvy.
3.	X Ay	= хму
4.	хм у	= XAy
5.	X Ay	= хм у.

6. X V у s X Л у.

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

Алгебра логики

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

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

 

X	У	х\у

Очевидно, имеют место равносильности:

1. х = х\х.

2. хлу = (х\у)\(х\у).

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

Отметим также, что х \ у ■ х л у.