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

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

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

,

xÚxºx,

(xÙ) Úyºy.

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

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

xÚ,

xÉ(xÉy).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x	y	x|y

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

Дата добавления: 2014-01-03