Тавтологии

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

Сейчас я выпишу ряд тавтологий булевой алгебры. В них все свободные переменные имеют одну и ту же область значений, состоящую из двух объектов: true и false.

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

Способ доказательства, пожалуй, самый простое и примитивный, какой только может быть: полный перебор. То есть, мы утверждаем, что некая формула истинна всегда (является тавтологией). Для доказательства мы просто перебираем все возможные варианты и убеждаемся, что действительно "всегда".

Запоминать все приведенные формулы нет нужды. Возможно, вам стоит сделать закладку.

Теперь перейдем к свойствам известных нам операций.

Перестановка операндов

Некоторые операции допускают перестановку операндов без изменения истинности:

(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)
(X (Y Z)) ((X Y) Z)
(X (Y Z)) ((X Y) Z)
(X (Y Z)) ((X Y) Z)

Это свойство обычно называют "ассоциативностью". Операция "" не обладает свойством ассоциативности. Четыре арифметические операции: сложения, вычитания, деления и умножения - тоже ассоциативны. Например: X + (Y + Z) = (X + Y) + Z

Ассоциативность означает, что не обязательно писать скобки, когда подряд идут одинаковые операции, раз все равно порядок вычисления не повлияет на результат. Например, можно написать просто X & Y & Z вместо X & (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 & Y) Z
(X & Y) (X & Z) X & (Y Z)
(X & Z) (Y & Z) (X Y) & Z

Сравните правило (X Y) & Z (X & Z) (Y & Z) и школьное правило (X + Y) * Z = (X * Z) + (Y * Z), которое называется звучно и длинно: "закон дитрибутивности умножения относительно сложения"... или сложения относительно умножения, уже не помню J. Тот закон выражается формулой: (X Y) + (X Z) = X (Y + Z).

Убирание отрицаний

Несколько правил позволяют избавляться от лишних знаков отрицания, а также заменять одни операции другими, добавляя лишние знаки отрицания:

~(~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)

Первое правило еще называют законом двойного отрицания (не имеет отношения к закону "отрицания отрицания" в диалектике), а два последних - законами Де Моргана (хотя точно неизвестно, кто их автор - возможно, Оккам).

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

Законы поглощения позволяют упрощать логические выражения, в которых встречаются операнды true, false, повтор операнда или его отрицание. Выпишем формулы для каждого из этих четырех случаев:

Комбинации с true

Комбинирование true с операцией действует как отрицание (X превращается в ~X и обратно):
(X true) ~X,     (true X) ~X,     (~X true) X,     (true ~X) X

Комбинирование true с операциями & и действует как отбрасывание true:
(X & true) X,     (true & X) X,     (~X & true) ~X,     (true & ~X) ~X
(X true) X,     (true X) X,     (~X true) ~X,     (true ~X) ~X

Комбинирование true с операцией действует как true:
(X true) true,     (true X) true,     (~X true) true,     (true ~X) true

Комбинирование true с операцией действует как отбрасывание левого операнда:
(X true) true,     (true X) X,     (~X true) true,     (true ~X) ~X

Комбинации с false

Комбинирование false с операциями и действуют как отбрасывание false:
(X false) X,     (false X) X,     (~X false) ~X,     (false ~X) ~X
(X false) X,     (false X) X,     (~X false) ~X,     (false ~X) ~X

Комбинирование false с операцией & действует как false:
(X & false) false,     (false & X) false,     (~X & false) false,     (false & ~X) false

Комбинирование false с операцией действует как отрицание (X превращается в ~X и обратно):
(X false) ~X,     (false X) ~X,     (~X false) X,     (false ~X) X

Комбинирование false с операцией действует как отрицание левого операнда:
(X false) ~X,     (false X) true,     (~X false) X,     (false ~X) true

Комбинации с отрицанием

Комбинирование с отрицанием в операциях и действует как true:
(X ~X) true,     (~X X) true
(X ~X) true,     (~X X) true

Комбинирование с отрицанием в операциях & и действует как false:
(X & ~X) false,     (~X & X) false
(X ~X) false,     (~X X) false

Комбинирование с отрицанием в операции и действует как отбрасывание левого операнда:
(X ~X) ~X,     (~X X) X

Повторы

Повторение в операциях и & действует как отбрасывание повторов:
(X X) X
(X & X) X

Повторение в операции действует как false:
(X X) false

Повторение в операциях и действует как true:
(X X) true
(X X) true

То же самое будет тавтологией и без true:
X X
X X

Похожие "законы поглощения" в школьной алгебре: X + 0 = X, или X 1 = X.

Приведение подобных членов

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

Если к формуле вида X & Y добавить еще раз один из ее операндов через , то можно совсем отбросить другой операнд:
(X & Y) X X
X (X & Y) X

(X & Y) Y Y
Y (X & Y) Y

Если к формуле вида X & Y добавить отрицание одного из ее операндов через , то можно убрать этот операнд без отрицания:

(X & Y) ~X ~X Y
~X (X & Y) ~X Y

(X & Y) ~Y X ~Y
~Y (X & Y) X ~Y

Если к формуле вида X & Y один из операндов содержит отрицание и мы добавим его без отрицания через , то можно убрать отрицание:

(~X & Y) X X Y
X (~X & Y) X Y

(X & ~Y) Y X Y
Y (X & ~Y) X Y

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

Тавтологии для импликации

(X Y) (~X Y)
(X Y) & (Y X) (X Y)
(X Y) (~Y ~X)

Кое-какие дополнительные полезные формулы-тавтологии можно найти в справочнике.

Вопросы и задания для самостоятельной работы

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