Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





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

 

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

 

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

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

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

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

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

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

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

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

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

 

Date: 2015-12-13; view: 548; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию