4.8. Схемы из функциональных элементов

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

Каждый такой узел способен вычислять или реализовывать некоторую булеву функцию. Логическая модель узла называется функциональным элементом (ф.э.). Выберем в качестве набора функциональных элементов элементы, реализующие функции &, .

Будем изображать такие элементы в виде:

&

Здесь стрелки, ведущие в ф.э. (входы элементов), представляют каналы, по которым в такие ф.э. поступают значения переменных.

По стрелкам, выходящим из ф.э. (выходам элемента), выдаются значения функций, вычисляемых элементами.

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

Из отдельных элементов строятся схемы из функциональных элементов (с.ф.э.), которые удовлетворяют следующим требованиям:

1) схема имеет конечное число входов, помеченных символами переменных;

2) выходы всякого входа схемы или элемента схемы могут разветвляться;

3) на всякий вход каждого функционального элемента в схеме подается ровно один выход входа схемы или выход другого функционального элемента;

4) ориентированные дуги, соединяющие функциональные элементы, не могут образовывать циклы.

Примером с.ф.э. может служить схема, приведенная на рис. 4.1.

x₁ x₂ x₃

&

&

Рис. 4.1

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

Например, нетрудно проверить, что приведенная ранее с.ф.э. вычисляет функцию, представляемую формулой:

В дальнейшем будем рассматривать только такие с.ф.э., которые имеют ровно один выход.

Поскольку всякая б.ф. может быть представлена с помощью формулы над множеством функций { }, то с помощью схем, составленных из функциональных элементов, можно вычислять любую б.ф.

Основная задача, относящаяся к с.ф.э., связана с отысканием для произвольной б.ф. f такой схемы , которая вычисляет f и составлена с помощью минимального количества функциональных элементов.

Сложностью произвольной с.ф.э.  называется число входящих в нее элементов & и . Сложность схемы  обозначается как L().

Пусть f(x₁, . . . , x_n)  некоторая б.ф. Предположим, что f отлична от тождественного нуля. Возьмем СДНФ для f, по которой построим с.ф.э., вычисляющую f, и определим сложность такой схемы.

f(x₁, . . . , x_n) = .

Представим СДНФ для f в виде K₁ . . . K_r, где r  число наборов, на которых f принимает значение 1, а K₁, . . . , K_r  все различные конъюнкции ранга n, принимающие значение 1 на таких наборах.

Для каждой конъюнкции K_i = построим с.ф.э. _k, вычисляющую эту конъюнкцию (рис. 4.2):

x₁ x₂ . . . x_n

_{1 2 n}

&

. . .

&

Рис.4.2