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

Правила преобразований мы будем записывать в виде равенств:

F = G,

где F и G - булевы функции, заданные в виде формул с унарными и бинарными операциями.

Такая запись означает: если в обоих частях равенства вместо переменных подставить любые константы и проделать вычисления, то в результате получатся одинаковые результаты: 0 = 0 или 1 = 1. Следует помнить, что это равенство не арифметическое. Например, нельзя переносить переменные из одной части равенства в другую с обратным знаком.

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

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

1. Если в обоих частях равенства заменить переменную на любую формулу (одну и ту же во всех местах, где встречается эта переменная), то получится равенство.

Например, из равенства

~(x & y) = x | y

путем замены x на x & ~y получим:

~((x & ~y) & y) = (x & ~y) | y.

Обратите внимание, что для сохранения порядка действий добавлены скобки.

2. Если F = G, то в любом равенстве можно заменять F на G или G на F и в результате получится равенство. В отличие от предыдущего случая делать замену во всех местах необязательно.

Например, пусть у нас есть два равенства:

~(x & y) = x | y    (1)
~(~x) = x    (2)

Мы можем взять равенство (1) и в нем вместо x подставить ~(~x), поскольку эти две формулы объединены равенством (2):

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