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


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


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

\Phi
и
\Psi
называются эквивалентными, если соответствующие им функции
f_{\Phi}
и
f_{\Psi}

равны.

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

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

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

Пусть

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

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

((X_1 \circ X_2) \circ X_3) \equiv (X_1 \circ(X_2 \circ X_3))

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

(X_1 \circ X_2) \equiv (X_2 \circ X_1 ))

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

((X_1 \vee X_2) \wedge X_3) \equiv ((X_1 \wedge X_3)\vee (X_2 \wedge X_3))
((X_1 \wedge X_2) \vee X_3) \equiv ((X_1 \vee X_3)\wedge (X_2 \vee X_3))
((X_1 + X_2) \wedge X_3) \equiv ((X_1 \wedge X_3)+ (X_2 \wedge X_3))

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

\neg (\neg X) \equiv X

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

\neg (X_1 \vee X_2) \equiv (\neg X_1 \wedge \neg X_2)
\neg (X_1 \wedge X_2) \equiv (\neg X_1 \vee \neg X_2)

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

(X \wedge X) \equiv X \hspace{20mm} (X \vee X) \equiv X
(X \wedge \neg X) \equiv 0 \hspace{20mm} (X \vee \neg X) \equiv 1
(X \wedge 0) \equiv 0 \hspace{20mm} (X \vee 0) \equiv X
(X \wedge 1) \equiv X \hspace{20mm} (X \vee 1) \equiv 1

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

(X \wedge \neg X) \equiv 0
- это закон противоречия,
(X \vee \neg X) \equiv 1
- это закон исключенного третьего.

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

(X_1 \rightarrow X_2) \equiv (\neg X_1 \vee X_2)

(7)

(X_1 + X_2) \equiv (( X_1 \wedge \neg X_2)\vee (\neg X_1\wedge X_2))

(8)

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

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

(X_1 \wedge X_2) \wedge X_3)

и

(X_1 \wedge (X_2 \wedge X_3))
мы будем для упрощения писать
(X_1 \wedge X_2 \wedge X_3).
Аналогично, будем использовать выражения
(X_1 \vee X_2 \vee X_3)
и
(X_1 + X_2 + X_3)\

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

\wedge, \vee, +, \rightarrow
.

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

(((X \vee Y)\vee(Z \wedge \neg X))\rightarrow ((Y + Z)+\neg X))

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

(X \vee Y \vee (Z \wedge \neg X))\rightarrow (Y + Z+\neg X).




Начало  Назад  Вперед



Книжный магазин