3. Синтез схем

3.1. Определения

Пусть задано множество  элементов, каждый из которых имеет единственный выходной полюс и характеризуется числом входных полюсов и реализуемой этим элементом функцией от значений на входных полюсах. Значения переменных на входных и выходных полюсах элементов принимаются из множества {0,1}. Будем считать, что каждый элемент из  определяет тип элемента и что в наличии есть неограниченное множество элементов данного типа.

Схемой назовём композицию элементов из , полученную отожде-ствлением (связыванием) выходов некоторых элементов с входами других элементов, при которой выполняются следующие свойства:

1. С каждым входом связано не более одного выхода.

2. В схеме не образуются контуры.

3. С каждым выходом может быть связано более одного входа.

Назовём эти свойства свойством корректности связей схемы.

Все несвязанные входы элементов схемы назовём её входами, несвязанные выходы элементов и некоторые выделенные связанные выходы элементов схемы назовём выходами схемы.

Пример схемы приведён на рис. 3.1.

З десь x, y и z – входы схемы, g и f – её выходы, элементы 1 и 2 реализуют функцию конъюнкции, элемент 3 – функцию инверсии.

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

Для схемы 1: f=(xy)Z, g=xy .

Множество  назовём базисом схемы.

Задачей синтеза схем назовём задачу построения в заданном базисе  для заданных функций F={f1, f2,…,fm} схемы, реализующей эти функции.

Будем оценивать решение числом элементов в схеме.

Одно из важных требований к результирующей схеме состоит в том, что она должна иметь минимальное число элементов. Прежде чем рассматривать решение задачи синтеза, ответим на вопрос: каким требованиям должен отвечать базис, чтобы в нём можно было построить схему для любых заданных функций?

3.2. Функциональная полнота базиса

3.2.1. Классы функций

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

Рассмотрим некоторые классы функций.

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

3.2.2. Монотонные функции

Определение. Два набора значений двоичных переменных =<1,2,…,n> и =<1,2,…,n> назовём сравнимыми и будем писать  , если i i=1,…,n I  i. Здесь  понимается в обычном виде: 1>0.

Е сли   и  , наборы считаются несравнимыми.

Пример. Наборы =<010111> и =<010101> сравнимы и . Набор  и =<100111> несравнимы.

Определение. Функция f называется монотонной, если для любых двух наборов значений входных переменных  и  из того, что , следует, что f()f().

Свойства монотонных функций.

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

2. Пусть функция на наборе , отличном от единичного, равна 1, и пусть значение I-й компоненты в нём равно 0. Это значит, что на наборе, который отличается только тем, что i-я пере-менная в нём равна 1, функция тоже примет единичное зна-чение. Это означает, что конъюнкции в ДНФ, соответствую-щие этим наборам, можно склеить по переменной xi. Точно так же, для набора со значением переменной 0 (т.е. с возмож-ным значением в конъюнкции переменной с инверсией) найдётся набор со значением переменной 1, что приведёт к склеиванию по этой переменной. Значит, в минимальной ДНФ монотонной функции нет переменных в инверсной форме.

Из этих свойств можно вывести, что:

1. суперпозиция монотонных функций будет функцией монотонной, т.е. множество монотонных функций образует класс монотонных функций, обозначаемый как M;

2. базисом класса М будут обе константы и пара функций – конъюнкция и дизъюнкция, т.е. множество {xy, xy, 0,1}.

Задача. Докажите, что константы должны присутствовать в базисе.