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

Определение. Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулы элементарных высказываний (переменных).

Обозначение. A≡B.

Пример.

.

Определение. Формула A называется тождественно истинной (тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных (напр., ).

Определение. Формула A называется тождественно ложной (противоречием), если она принимает значение 0 при всех значениях входящих в нее переменных (напр., ).

Утверждение. Отношение равносильности рефлексивно, симметрично, транзитивно.

Связь между понятиями равносильности и эквивалентности: если формулы A и B равносильны, то формула A↔B тавтология, и обратно, если формула A↔B тавтология, то формулы A и B равносильны.

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

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

· – законы идемпотентности;

· ;

· ;

· ;

· ;

· – закон противоречия;

· – закон исключенного третьего;

· – закон снятия двойного отрицания;

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

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

· ;

· ;

· ;

· ;

· ;

· .

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

Существуют операции, с помощью которых может быть выражена любая из 5 логических операций:

1) Связка Шеффера – дизъюнкция отрицаний.

Обозначение. x|y≡ («x не совместно с y»).

Логические значения связки Шеффера описываются следующей таблицей истинности:

x	y	x|y
1	1	0
1	0	1
0	1	1
0	0	1

Имеют место следующие равносильности: а) ; б) .

2) Связка Лукасевича – конъюнкция отрицаний.

Обозначение. x↓y≡ («ни x, ни y»).

Логические значения связки Лукасевича описываются следующей таблицей истинности:

x	y	x↓y
1	1	0
1	0	0
0	1	0
0	0	1

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

· – коммутативность конъюнкции;

· – коммутативность дизъюнкции;

· – ассоциативность конъюнкции;

· – ассоциативность дизъюнкции;

· – дистрибутивность конъюнкции относительно дизъюнкции;

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

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

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

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

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