, 
, 
Схемы, соответствующие F(4) и F(4,5) показаны на рис. 204. Как видно, вторая схема (рис. 204 б) содержит на один контакт меньше, чем первая (рис. 204 а).
|
а |
б |
рис. 204. Схемы, реализующие функции f12 = x1x2 ∨ x̅1x̅3 и f13 = x1x̅3 ∨ x̅1x2.
а - с четырьмя узлами; б - с пятью узлами.
4. Логические схемы
1. Логические элементы. Контактные схемы исторически были первыми техническими средствами реализации булевых функций и первыми объектами применения алгебры логики для решения технических задач. Впоследствии появилось много различных устройств, реализующих элементарные булевы функции одной или нескольких переменных. Они основаны на использовании электронных и магнитных цепей, параметронов, стройной техники (пневмоники) и т.д.
Устройства, реализующие элементарные булевы функции, называют логическими элементами. Их входы соответствуют булевым переменным, а выход — реализуемой функции.
В технике для обозначения логических элементов используют различные графические символы и названия, которые учитывают свойства и специфические особенности конкретных элементов. В теории принимаются упрощенные изображении в виде прямоугольников или других фигур, внутри которых помещаются условные названия или символы соответствующей функции (табл. 7). Обычно рассматривают элементы с одним (для отрицания) и двумя входами (для функций двух переменных).
.................
4. Упрощение формул. Между формулой, выражающей булеву функцию, и функциональной схемой, реализующей эту функцию, имеется функциональное соответствие. Однако, поскольку одна и та же функция может быть выражена различными формулами, ее реализация неоднозначна. Всегда можно построить много различных логических схем, соответствующих данной логической функции. Такие схемы называют эквивалентными.
Из множества эквивалентных схем можно выделить наиболее экономичную или хотя бы достаточно простую схему путем упрощения формулы, соответствующей данной функции. Обычно принято считать более простыми те формулы, которые содержат меньшее количество вхождений переменных и символов логических операций.
Задача упрощения аналитических выражений решается в конкретном базисе с помощью тождественных преобразований. Чаще всего эту задачу связывают с базисом, состоящим из отрицания, дизъюнкции и конъюнкции, который будем называть булевым базисом. После того как формула выражена через основные операции, она упрощается на основании тождеств булевой алгебры, приведенных в (2. 1).
Например, функция из (3) упрощается следующим образом:
y = (x1 / x2) + (x̅3 → x1) =
= ¬(x1x2) + (x3 ∨ x1) =
= x1x2(x3 ∨ x1) ∨ ¬(x1x2)x3 ∨ x̅1 =
= x1x2 ∨ ¬(x1x2)(x3 ∨ x1) =
= x1x2 ∨ ¬(x1 ∨ x3).
5. Минимальные формы. Как было показано в (2. 3), любая булева функция представима в совершенной нормальной форме (дизъюнктивной или конъюнктивной). Более того, такое представление является первым шагом перехода от табличного задания функции к ее аналитическому выражению. В дальнейшем будем исходить из дизъюнктивной формы, а соответствующие результаты для конъюнктивной формы получаются на основе принципа двойственности (2. 1).
Каноническая задача синтеза логических схем в булевом базисе сводится к минимизации булевых функций, т.е. к представлению их в дизъюнктивной нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. При каноническом синтезе предполагается, что на входы схемы подаются как сигналы хi, так и их инверсии x̅i. Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением операции склеивания ab ∨ ab̅ = a и операций поглощения a ∨ ab = a; и a ∨ ab̅ = a ∨ b (дуальные тождества для конъюнктивной нормальной формы имеют
- 539 -
вид: (a ∨ b)(a ∨ b̅) = a; a(a ∨ b)= a; a(a̅ ∨ b) = ab ). Здесь под a и b можно понимать любую формулу булевой алгебры. В результате приходим к такому аналитическому выражению, когда дальнейшие преобразования оказываются уже невозможными, т. е. получаем тупиковую форму.