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

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

Ассоциативность:

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

Эквивалентные преобразования формул

Соглашения об упрощенной записи формул.

Законы ассоциативности показывают, что значения формул, составленных из переменных и одних операций конъюнкции, не зависят от расстановки скобок. Поэтому вместо формул и мы будем для упрощения писать выражение , которое не является формулой, но может быть превращено в нее с помощью расстановки скобок. Аналогично, будем использовать выражения и (X1 + X2 + X3) для сокращения формул, состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно.

Если внешней функцией в формуле является одна из функций , то внешние скобки в записи формулы можно опустить.

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

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

Из определения эквивалентности формул непосредственно следует Принцип замены эквивалентных подформул:

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

Применяя этот принцип и используя основные тождества, можно находить для заданной формулы другие эквивалентные ей формулы. Часто это может приводить к существенному упрощению исходной формулы. Например, если в формуле заменим на основании тождеств (6) подформулу на 0, то получим эквивалентную формулу . По закону коммутативности (2) эта формула эквивалентна формуле , которая, в свою очередь, по одному из тождеств группы (6) эквивалентна формуле Y. Эту цепочку эквивалентных преобразований можно записать также следующим образом:

Date: 2015-12-13; view: 602; Нарушение авторских прав