.gif) |
1.5. Функционально-полные базисы (ФПБ)
Понятие ФПБ может быть задано следующим образом.
Определение.
Система булевых функций W называется функционально-полной, если
произвольная булева функция вида f (x1,
x2, ..., xn) может быть представлена
суперпозицией функций x1, x2, ...
,xn и суперпозицией конечного числа функций системы W.
В качестве простейших принято рассматривать следующие пять базисов:
- Дизъюнкция (xivxj),
конъюнкция (xi&xj),
инверсия (xi);
- Дизъюнкция (xivxj),
инверсия (xi);
- Конъюнкция (xi&xj),
инверсия (xi);
- Стрелка Пирса (xi
 xj
= Xi V Xj);
- Штрих Шеффера (xi | xj
= Xi & Xj).
Доказательство функциональной полноты базисов (1-5) мы не
рассматриваем, отсылая читателя к [7]. С точки зрения практической
реализации булевых функций функциональная полнота базисов (1-5)
показывает, что произвольная логическая сеть может быть построена
из простых функциональных элементов, вплоть до случая элементов
одного типа (например, Пирса или Шеффера).
В действительности электронной промышленностью выпускается
ограниченный, но заведомо избыточный набор логических элементов,
что позволяет сократить общее число микросхем в конкретном
логическом блоке за счет расширения номенклатуры.
|
