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

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

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

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

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

равны.

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

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

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

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

логическими тождествами.

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

Пусть

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

- это одна из функций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- это закон противоречия,

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

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

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

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

(7)

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

(8)

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

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

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

мы будем для упрощения писать

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

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

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

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

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

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

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

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

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

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

Главная сайта