Электроника:Цифровая электроника/Булева алгебра/Логические правила для упрощения

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Перевод: Макаров В. (valemak) Контакты:</br>* Habr: @vakemak</br>* Сайт: www.valemak.com</br>Перевёл статей: 648.
Проверка/Оформление/Редактирование: Мякишев Е.А.


Логические правила для упрощения[1]

Булева алгебра находит наибольшее практическое применение в упрощении логических схем.

Если мы переведём функцию логической схемы в символьную (булеву) форму и применим определённые алгебраические правила к полученному уравнению, чтобы уменьшить количество членов и/или арифметических операций, упрощённое уравнение можно преобразовать обратно в форму схемы для логической схемы, выполняющей та же функция с меньшим количеством компонентов.

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

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

Тождества и свойства, уже рассмотренные в этой главе, очень полезны для булевого упрощения и по большей части имеют сходство со многими тождествами и свойствами «нормальной» алгебры.

Однако все правила, показанные в этом разделе, уникальны для булевой математики.

A + AB = A

Рис. 1. Сумму логической переменной и произведения этой переменной на другую логическую переменную можно упростить просто до этой логической переменной.
Рис. 1. Сумму логической переменной и произведения этой переменной на другую логическую переменную можно упростить просто до этой логической переменной.

Это правило может подтвердить символически, если вычленить «А» из обоих слагаемых, а затем применить правила А + 1 = 1 и 1А = А для достижения окончательного результата:

Рис. 2. Пример упрощения посредством применения алгебраических тождеств.
Рис. 2. Пример упрощения посредством применения алгебраических тождеств.

Обратите внимание, как правило «A + 1 = 1» использовалось для уменьшения члена «(B + 1)» до 1.

Когда правило, наподобие «A + 1 = 1» выражается через букву «A», это вовсе не означает, что оно применяется исключительно к выражениям, содержащим именно этот символ – «A». В подобном правиле («A + 1 = 1»), буква «A» означает вообще любую логическую переменную или даже набор (сумму или произведение) логических переменных.

Это, пожалуй, самая трудноусваиваемая концепция для новичков в области логического упрощения: применение стандартизированных идентификаторов, свойств и правил к выражениям, не имеющим стандартной формы.

Например, логическое выражение «ABC + 1» также сокращается до 1 с помощью тождества «A + 1 = 1».

В этом случае мы понимаем, что произвольная величина «A» в стандартной форме идентификатора может представлять всё произведение трёх величин «ABC» в исходном выражении.

A + A'B = A + B

Следующее правило напоминает предыдущее, однако на самом деле оно существенно отличается и требует более изощрённого доказательства:

Рис. 3.1. Схема, нуждающееся в упрощении.
Рис. 3.1. Схема, нуждающееся в упрощении.
Рис. 3.2. И соответствующее формальное доказательство.
Рис. 3.2. И соответствующее формальное доказательство.

Обратите внимание, как последнее правило («A + AB = A») используется для «антиупрощения» первого члена «A» в выражении, когда одинокую переменную «A» заменили на «A + AB». Хотя это может показаться шагом назад, усложнением, тем не менее это определённо помогло свести выражение к чему-то более простому!

Иногда в математике мы должны делать «откат», чтобы найти наиболее элегантное решение.

Понимание, когда необходимо сделать подобный «усложняющий» шаг, чтобы в итоге упростить, является частью искусства алгебры, точно так же, как выигрыш в шахматной партии зачастую достигается посредством просчитанных жертв.

(A + B)(A + C) = A + BC

Другое правило включает упрощение выражения произведения сумм:

Рис. 4.1. Схема, нуждающаяся в упрощении.
Рис. 4.1. Схема, нуждающаяся в упрощении.
Рис. 4.2. И соответствующее формальное доказательство.
Рис. 4.2. И соответствующее формальное доказательство.

Итог

Подводя итог, вот три новых правила логического упрощения, изложенные в этом разделе:

Рис. 5. Три полезных правила упрощения, выведенные в этом разделе.
Рис. 5. Три полезных правила упрощения, выведенные в этом разделе.

См.также

Внешние ссылки