logo search
флеров

Алгебраические свойства элементарных операций

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

1. Коммутативность (или перестановочность) операции  означает, что . Логическая операция  коммутативна, если связка  принадлежит следующему множеству связок (существенно только, чтобы символ  в равенстве всюду имел один и тот же смысл):

.

2. Ассоциативность операции  означает, что . Свойство ассоциативности позволяет записывать формулы, содержащие одинаковые ассоциативные связки, без скобок, например, .

Логическая операция  ассоциативна, если связка  принадлежит следующему множеству связок (существенно только, чтобы символ  в равенстве всюду имел один и тот же смысл):

.

3. Дистрибутивность (распределительный закон) операции  относительно операции  означает, что .

Дистрибутивность конъюнкции:

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

- дистрибутивность конъюнкции относительно логической суммы.

Дистрибутивность дизъюнкции:

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

- дистрибутивность дизъюнкции относительно импликации;

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

Дистрибутивность импликации:

- дистрибутивность импликации относительно конъюнкции;

- дистрибутивность импликации относительно дизъюнкции;

- дистрибутивность импликации относительно импликации.

4. Имеет место следующее соотношение для двойного отрицания: .

5. Имеют место следующие соотношения между отрицанием, конъюнкцией и дизъюнкцией:

суть правила де Моргана.

Указанные соотношения отражают отношение двойственности между дизъюнкцией и конъюнкцией.

6. Имеют место следующие соотношения, связанные с “навешиванием отрицания” на элементарные логические функции:

;

;

.

7.

8. Правила поглощения:

9. Выполняются следующие свойства конъюнкции и дизъюнкции:

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

Введенные нами элементарные функции не являются независимыми, так, например:

;

.

Имеется гораздо более радикальная возможность сведения: все элементарные функции могут быть выражены через одну-единственную: штрих Шеффера или стрелку Пирса.

Задача. Выразить все элементарные функции через | и .