Свойства логических
операций

[предыдущая глава]  [оглавление]  [следующая глава]

Закон двойного отрицания.

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

~(~x) = x

Обратные операции.

Формулы обратных операций позволяют убирать знак отрицания в формулах вида ~(x # y) путем замены некоторой операции # на другую операцию:

~(x & y) = x | y
~(x | y) = x & y
~(x > y) = x y
~(x y) = x > y
~(x < y) = x y
~(x y) = x < y
~(x y) = x y
~(x y) = x y
~(x y) = x y
~(x y) = x y
(Напоминание программистам: | - это штрих Шеффера, а не побитовое "или")

Коммутативные операции.

Коммутативными называют операции, которые позволяют переставлять местами свои операнды, не меняя операцию. По схеме: x + y = y + x, где + - некоторая операция.

x & y = y & x
x y = y x
x y = y x
x y = y x
x y = y x
x | y = y | x

Остальные операции также позволяют переставлять операнды, но с заменой на другую операцию:

x > y = y < x
x y = y x

Как видите, и в булевой алгебре операции сложения () и умножения (&) позволяют переставлять свои слагаемые.

Можно использовать простое мнемоническое правило: при перестановке операндов логической операции местами надо повернуть знак операции вокруг веритикальной оси. Если получится другой знак логической операции, взять его. Если получится тот же знак, взять его. Если получится несуществующий знак (для операции &), то оставить прежний знак.

Ассоциативные операции.

Ассоциативными называют операции, которые можно выполнять в произвольном порядке. По схеме: (x + y) + z = x + (y + z), где + - некоторая операция. Здесь приведена программа на языке C, позволяющая увидеть таблицу истинности всех 16 бинарных логических операций и проверить их ассоциативность путем перебора вариантов.

Проверка показывает ассоциативность всего лишь для 4 операций "&", "", "", "" из 10 нетривиальных.

(x & y) & z = x & (y & z)
(x y) z = x (y z)
(x y) z = x (y z)
(x y) z = x (y z)

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

(a & b) & (c & d) = a & d & c & b.

Дистрибутивные операции.

Дистрибутивной называют пару операций, для которых работает схема раскрытия скобок, характерная для сложения и умножения в арифметике:

x * (y + z) = (x * y) + (x * z) и
(x + y) * z = (x * z) + (y * z),
где * и + - некоторые логические операции.

Первую схему будем называть левой дистрибутивностью, вторую схему - правой дистрибутивностью, а если срабатывают обе схемы, то будем говорить о полной дистрибутивности или просто дистрибутивности.

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

Результаты программы выглядят так.

Из полученных правил наибольший практический интерес представляют:
x & (y z) = (x & y) (x & z)
(x y) & z = (x & z) (y & z)
x (y & z) = (x y) & (x z)
(x & y) z = (x z) & (y z)
x & (y z) = (x & y) (x & z)
(x y) & z = (x & z) (y & z)

Как видите, дистрибутивность между логическим умножением и сложением в алгебре логики такая же как в обычной алгебре (где она называется "распределительным законом"). Обратите внимание, что и для операций "" и "&" можно раскрывать скобки таким же способом. Причем обе операции оказываются равноправны: можно раскрывать скобки когда в них стоит "&", а вне скобок - "", а можно и в обратной ситуации - когда внутри скобок стоит "".

Законы поглощения.

Формула вида x # 0 (где # - некоторая бинарная операция) представляет собой функцию от одной переменной. Мы знаем все 4 функции от одной переменной, поэтому всякую такую формулу можно упростить до одной из этих 4 функций: 0, 1, x или ~x.

То же самое рассуждение применимо и к формулам вида: x # 1, x # x, x # ~x, 1 # x, 0 # x, ~x # x. В результате для каждой такой формулы получается закон поглощения, который позволяет избавиться от лишних знаков операций и переменных.

Как обычно, поручим нудную работу по перебору вариантов компьютеру. Здесь приведена программа на языке C, позволяющая получить список всех правил поглощения сразу в виде web-странички.

Цветом выделены законы поглощения, используемые чаще всего.

Закон исключенного третьего.

Это - один из законов поглощения:

x ~x = 1

В булевой алгебре этот закон оспорить невозможно, так как достаточно подставить значения x = 0, 1 и убедиться в наличии равенства в обоих случаях. Применение этого закона на практике, например в психологике, накладывает дополнительные ограничения, описанные в первой главе. Что, впрочем, справедливо и для осталных законов булевой алгебры.

Я специально останавливаюсь на этом законе потому, что в некоторых логических системах (интуиционистская логика, конструктивная логика), которые построены на иных принципах, чем булева алгебра, в этих системах закон исключенного третьего не действует. Что неудивительно, ведь в тех системах совсем другие границы применимости.

Законы Де Моргана.

~(x & y) = ~x ~y
~(x y) = ~x & ~y

Эти равенства удобны для избавления от лишних скобок.

Формулы для импликации.

x y = (x y) & (x y)
x y = y x
x y = ~x y
x y = ~y ~x