Введение в схемы, автоматы и алгоритмы

Эквивалентность булевых формул


Определение 1.3.Булевы формулы

и
называются эквивалентными, если соответствующие им функции
и

равны.

Обозначение:

. Эквивалентные формулы называют также тождественно равными, а выражения вида
логическими тождествами.

Таким образом, эквивалентные формулы являются различными заданиями одной и той же булевой функции. Ниже мы приводим ряд пар эквивалентных формул (тождеств), отражающих существенные свойства логических операций и важные соотношения между различными операциями. Они часто позволяют находить для булевых функций по одним задающим их формулам более простые формулы. Большинство из приводимых тождеств имеют собственные имена. Часто их называют законами логики.

Пусть

- это одна из функций
. Для этих трех функций выполнены следующие две эквивалентности (законы ассоциативности и коммутативности).

(1) Ассоциативность:

(2) Коммутативность:

(3) Дистрибутивные законы:

(4) Двойное отрицание:

(5) Законы де Моргана (внесение отрицания внутрь скобок):

(6) Законы упрощения:

Некоторые законы упрощения имеют собственные названия: эквивалентности в первой строке называются законами идемпотентности,

- это закон противоречия,
- это закон исключенного третьего.

Следующие две эквивалентности позволяют выразить импликацию и сложение по модулю 2 через дизъюнкцию, конъюкцию и отрицание.

(7)

(8)

Правильность этих эквивалентностей легко устанавливается прямым вычислением функций для их левых и правых частей.

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

и

мы будем для упрощения писать
Аналогично, будем использовать выражения
и

для сокращения формул, состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно. Будем также опускать внешние скобки в записи формулы, если ее внешней функцией является одна из функций

.

Таким образом, с использованием этих соглашений формула

может быть записана как



Содержание раздела